天道酬勤,学无止境

Cache-aware tree impementation

I have a tree where every node may have 0 to N children.

Use-case is the following query: Given pointers to two nodes: Are these nodes within the same branch of the tree?

Examples

q(2,7) => true
q(5,4) => false

By the book (slow)

The straight forward implementation would be to store a pointer to the parent and a pointer to a list of children at each node. But this would lead to bad performance because the tree would be fragmented in memory and therefor not cache-aware.

Question

What would be a good way to represent the tree in compact form? The whole tree has about 100,000 nodes. So it should be possible to find a way to make it fit completely in the CPU-cache.

Binary trees for example are often represented implicitly as an array and are therefor perfect to be completely stored in the CPU-cache (if small enough).

评论

You can pre-allocate a contiguous block of memory where you concatenate the information for all nodes.

Afterwards, each node would only need a way to retrieve the beginning of its information, and the length of that information.

In this case, the information for each node could be represented by the parent, followed by the list of children (let's assume that we use -1 when there is no parent, i.e. for the root).

For example, for the tree posted in the question, the information for node 1 would be: -1 2 3 4, the information for node 2 is: 1 5, and so on.

The contiguous array would be obtained by concatenating these arrays, resulting in something like:

-1 2 3 4 1 5 1 9 10 1 11 12 13 14 2 3 5 5 5 3 3 4 4 4 15 4

Each node would use some metadata to allow retrieving its associated information. As mentioned, this metadata would need to consist of a startIndex and length. E.g. for node 3, we would have startIndex = 6, length = 3, which allows to retrieve the 1 9 10 subarray, indicating that the parent is node 1, and its children are nodes 9 and 10.

In addition, the metadata information can also be stored in the contiguous memory block, at the beginning. The metadata has fixed length for each node (two values), thus we can easily obtain the position of the metadata for a certain node, given its index.

In this way, all the information about the graph will be stored in a contiguous, cache-friendly, memory block.

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • How do I call a base class implementation of an explicitly impemented interface method?
    I'm trying to call an explicitly implemented interface method implemented on the base class but just can't seem to get it to work. I agree the idea is ugly as hell, but I've tried every combination I can think of, to no avail. In this case, I can change the base class, but thought I'd ask the question to satisfy my general curiosity. Any ideas? // example interface interface MyInterface { bool DoSomething(); } // BaseClass explicitly implements the interface public class BaseClass : MyInterface { bool MyInterface.DoSomething() { } } // Derived class public class DerivedClass : BaseClass { //
  • 利用XGBoost特征选择和堆叠集成分类器提高蛋白质-蛋白质相互作用预测精度
    文章目录 论文基本情况一、论文创新点:二、方法(一)、特征提取方法(二)、XGBoost特征选择(三)、叠迭分类器:三、数据四、实验结果(一)参数的确定(m=9)(二)、基分类器确定,元分类器比较 论文基本情况 期刊:《Computers in Biology and Medicine》影响因子及中科院分区:IF: 3.434,中科院三区发表日期:2020年7月作者单位:青岛科技大学代码地址: https://github.com/QUST-AIBBDRC/StackPPI/原文链接:https://www.sciencedirect.com/science/article/abs/pii/S0010482520302481 一、论文创新点: 提出了一种新的预测蛋白质-蛋白质相互作用的方法——StackPPI融合PAAC、AD、AAC-PSSM、Bi-PSSM和CTD提取物理化学、进化和序列信息采用XGBoost特征选择方法消除冗余,保留最优特征子集首次利用RF、ET和LR构建了堆叠集成分类器。 二、方法 (一)、特征提取方法 伪氨基酸组成(PAAC)自相关拓扑指数(AD:MoreanBroto, Moran, and Geary autocorrelation)ACC-PSSM和Bi-PSSMCTD(CTDC,CTDD,CTDT) 详情见代码 (二)、XGBoost特征选择
  • Effective optimization strategies on modern C++ compilers
    I'm working on scientific code that is very performance-critical. An initial version of the code has been written and tested, and now, with profiler in hand, it's time to start shaving cycles from the hot spots. It's well-known that some optimizations, e.g. loop unrolling, are handled these days much more effectively by the compiler than by a programmer meddling by hand. Which techniques are still worthwhile? Obviously, I'll run everything I try through a profiler, but if there's conventional wisdom as to what tends to work and what doesn't, it would save me significant time. I know that
  • Generic Entity Base Class
    I've just read a post about Generic Entity Base Classes. Simply and if I'm not wrong, the main idea in behind is collecting all generic, non-entity-spesific fields in one interface, than implement it in main entities. It's going to be a TL:DR; Let's see some code. This is the base entity interface and it's generic impementation to another interface public interface IEntity : IModifiableEntity { object Id { get; set; } DateTime CreatedDate { get; set; } DateTime? ModifiedDate { get; set; } string CreatedBy { get; set; } string ModifiedBy { get; set; } byte[] Version { get; set; } } public
  • Initializing a property, dot notation
    Is it a bad idea to use the dot notation to initialize retain properties to nil in my init methods? With any ordinary property like this: @property (nonatomic, retain) id foo; Say in my init method I set self.foo = nil. The synthesized method first releases or autoreleases foo (not exactly sure of the underlying impementation). Is foo guaranted to be nil before the first setter or getter call? Or would it point to random garbage unless I explicitly set foo = nil without the dot notation?
  • Using java class HttpsURLConnection
    I have a small piece of code which basically impements a HTTP-Client, i.e. it POSTS request and works with re RESPONSE. As long as HTTP is concenerned everthing work well. For some reason I now have to support HTTPS too. So here is briefly what I do in order to get a connection opened: URL url = new URL(serverAddress); HttpsURLConnection httpsConn = (HttpsURLConnection) url.openConnection(); This fails, stating: sun.net.www.protocol.https.HttpsURLConnectionImpl cannot be cast to com.sun.net.ssl.HttpsURLConnection I guess this is kinda trivial, but I just don't get what I'm doing wrong in this
  • Securing your Data Layer in a C# Application
    I was thinking about how to secure the Data Layer in a C# Application, the layer could in this case be either a LINQ to SQL Model Diagram stored with the Application itself containg the connection string to the SQL Server Database. Or it could be connectivity between the application and webservices. Either you need to impement some sort of security, for instance, the Connection String in a Application can easily be reverse engineered and Webservices can easily be tracked and used for other reasons than the applications original purpose. So my question is in a shorter way: How do you solve the
  • jmeter connection reset解决方法
    方法仅作参考:1.修改HTTP请求下面的Impementation选项,改成HttpClient42.在user.properties文件内修改:hc.parameters.file=hc.parameters#Jmeter 2.10以后禁用了失败请求重试3.在hc.parameters文件内修改:http.connection.stalecheck$Boolean=true#Jmeter 2.10以后禁用了失效检查重启Jmeter再尝试一下 新建注册表脚本reg文件,编辑值如下,保存后双击执行;重启电脑,再次压测即不会出现报错相关值解析MaxUserPort:最大动态端口数(Default = 5000, Max = 65534)TcpTimedWaitDelay:TCP等待延迟时间(30)TcpNumConnections:TCP最大连接数(Default = 16,777,214)MaxFreeTcbs:最大TCP控制块(1000-2000)MaxHashTableSize:最大TCB Hash table数量(64-65536)解析中值为10进制,下方脚本已全转换为16进制Windows Registry Editor Version 5.00[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip
  • jQuery Login modal popup for ASP.NET 2.o Page
    I have an ASP.NET web page(Not MVC ) (HomePage.aspx) and another page (PRiceList.aspx).I have a login feature in my Home page.So when a user logged in the site, They can go to the pricelist.aspx page easily using a link in homepage.If some one is entering the page with out logging in , I want to show a modal login box (background disabled) to login . I saw this in jqueryui site.Can any one tell me how to impement this in my site ? Is there any security problem in this since i am using the javascript to send the user credentials to the site when using this method (I am not sure) . Please advice
  • Chef:如何检查是否已安装服务?(Chef: How do I check to see if a service is installed?)
    问题 在食谱中,我想检查是否已安装服务,以及是否未通知安装该服务所需的3种资源。 我尝试了服务资源,该资源可以在安装时正确识别服务,但是如果未安装该服务,则会引发异常。 我不确定在这里使用什么动作。 :什么都不会跳过资源,因此它永远不会被执行,但是当其他任何操作试图对不存在的服务进行操作时,它们都会出错。 如何检测是否已安装服务并根据该信息采取行动? 如果相关的话,我正在Windows上运行。 回答1 看看如何定义Windows服务 https://github.com/opscode/chef/blob/master/lib/chef/provider/service/windows.rb AFAIU非常简单地将导入添加到您的食谱中: require 'win32/service' 然后您可以检查服务是否存在 Win32::Service.exists?(@new_resource.service_name) 瞧-您可以对库(http://docs.opscode.com/essentials_cookbook_libraries.html)进行插入,而不是污染配方代码并使用简单的方法service_exists?。
  • Why are many Python built-in/standard library functions actually classes
    Many Python builtin "functions" are actually classes, although they also have a straightforward function implementation. Even very simple ones, such as itertools.repeat. What is the motivation for this? It seems like over-engineering to me. Edit: I am not asking about the purpose of itertools.repeat or any other particular function. It was just an example of a very simple function with a very simple possible impementation: def repeat(x): while True: yield x But itertools.repeat is not actually a function, it's implemented as a class. My question is: Why? It seems like unnecessary overhead
  • MATLAB中的矩阵乘法时间复杂度(Matrix multiplication time complexity in MATLAB)
    问题 有谁知道MATLAB用于矩阵乘法的算法及其时间复杂度是多少? 回答1 为了完整性-如该线程中所述,Matlab使用BLAS(基本线性代数子程序)中的DGEMM(双通用神经矩阵乘法)例程。 请注意,没有BLAS的单一实现-它针对特定的处理器体系结构进行了调整。 因此,如果不找出正在使用哪个版本的BLAS,就不能完全确定计算机上正在使用哪种算法。 BLAS规范指定了每个子例程的输入和输出,并为每个子例程的输出提供了可接受的误差范围。 只要遵循规范,实现即可自由使用其喜欢的任何算法。 BLAS的参考实现在DGEMM中使用块矩阵乘法算法,该算法具有时间复杂度O( n ^ 3)来将两个n x n矩阵相乘。 我认为可以合理地假设,大多数BLAS实现将或多或少地遵循参考实现。 请注意,它不使用朴素矩阵乘法算法 for i = 1:N for j = 1:N for k = 1:N c(i,j) = c(i,j) + a(i,k) * b(k,j); end end end 这是因为,通常,整个矩阵都无法放入本地内存中。 如果不断将数据移入和移出本地内存,该算法将变慢。 块矩阵算法将运算分为几个小块,这样每个块都足够小以适合本地内存,从而减少了移入和移出内存的次数。 存在渐近更快的矩阵乘法算法,例如Strassen算法或Coppersmith-Winograd算法,其速率比O( n ^ 3
  • Waiting for multipart image sending get completed
    I'm impementing an application in iOS7, it's kind of a social network app with posts with images and a backend that saves all of the data sent form the client. The iOS client is sending the information of the post via json and after the info is sent, it starts to send the image via multipart form using AFNetworking. I need to be notified when the image is sent, so that I can refresh the main view of the app with the new posts, including the recently posted by the client. In the practice if I request the backend for the last posts and the multipart hasn't finished, the sending of the image gets
  • How to hook Jackson ObjectMapper with Guice / Jersey
    I can't seem to get my Jackson ObjectMapper Module registered correctly. I'm using a Guice + Jersey + Jackson (FasterXML) stack. I've followed how to customise the ObjectMapper based on various question here. In particular, I have a ContextResolver declared, marked as an @javax.ws.rs.ext.Provider and a @javax.inject.Singleton. I have a GuiceServletContextListener along the lines of: @Override protected Injector getInjector() { Injector injector = Guice.createInjector(new DBModule(dataSource), new ServletModule() { @Override protected void configureServlets() { // Mapper bind(JacksonOMP.class)
  • 以编程方式启用和禁用自动旋转?(Enable and disable auto rotate programmatically?)
    问题 有很多很酷的小部件,它们可以在您的手机上启用和禁用自动旋转。 禁用它会在手机上的所有应用程序中将其关闭。 任何想法,他们如何做到这一点? 回答1 这应该为您解决问题: import android.provider.Settings; public static void setAutoOrientationEnabled(Context context, boolean enabled) { Settings.System.putInt( context.getContentResolver(), Settings.System.ACCELEROMETER_ROTATION, enabled ? 1 : 0); } 向AndroidManifest.xml添加权限 <uses-permission android:name="android.permission.WRITE_SETTINGS" /> 您可以在这里找到文档 回答2 始终使用用户指定的屏幕方向,这将应用用户选择的任何方向,并且在禁用屏幕时不会旋转屏幕。 activity.setRequestedOrientation(ActivityInfo.SCREEN_ORIENTATION_USER); 回答3 这是我对这个问题的重视。 我必须实现一个按钮,该按钮具有与设置菜单中的lockbutton相同的功能。
  • 读取CPU缓存内容(read CPU cache contents)
    问题 有什么方法可以读取CPU缓存内容? 体系结构是针对ARM的。 我要使一个地址范围无效,然后要确保它是否无效。 尽管我可以在使无效和检查无效的情况下进行读写地址范围,但是我想知道是否可以读取缓存内容 谢谢!! 回答1 ARM9提供了高速缓存操作和测试寄存器,使您可以检查高速缓存的状态。 这是一个合理的起点: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0151c/Chdcfejb.html ICache和DCache使用对CP15寄存器7和9的MCR和MRC指令进行维护,该指令由ARM v4T程序员的模型定义。 使用MCR和MRC到CP15寄存器15可以进行其他操作。这些操作与使用寄存器7和9的操作结合使用,可以完全在软件中测试缓存。 这些是特权说明,因此您的目标平台上可能无法访问它们。 我将从一个简单的程序开始,该程序转储所有缓存行的状态。 这将为您提供足够的信息,只需读取高速缓存标签提供的内存位置即可读取高速缓存中的数据。 回答2 我很犹豫地写这是不可能的,所以我在写它非常困难。 可能没有通用答案。 鉴于CPU缓存透明地工作,因此无法在不更改缓存内容的情况下从连接的CPU读取其内容。 如果CPU试图访问数据,则通常将CPU高速缓存实现为CAM(内容可寻址内存,关联内存),查找高速缓存
  • HashMap get performance with simple and complex key
    I want a map whose get operation is as fast as possible. The key is set of string (2 table names in database which are related) and value is a integer (the number is id of row in database which has actual relationship between tables), example : table 1 - employee table 2 - company relationship - employee.comp_id = company.id I have no intentions to read keys in the map. I just want the relationship id for the given 2 table names. so I wrote a small program to test get operation in HashMap. public static void main(String args[]) throws NoSuchMethodException, SecurityException { int limit = 1000
  • 毕加索图片加载回调(Picasso image load callback)
    问题 我想使用毕加索在列表视图中一个接一个地加载三个连续的图像。 使用毕加索提供的方法可以轻松做到这一点。 但是,由于这些图像在不同的时间加载,因此在图像进入时会引起闪烁效果。例如,有时图像2出现在图像1之前,而当图像1加载时会导致不自然的结结。 如果可以将Listview的可见性设置为不可见,直到可以显示所有图像,那将更好。 但是,我找不到用于毕加索的回调方法,该方法会在加载图像时发出信号。 有人知道使用毕加索解决这种情况的解决方案吗? 谢谢 回答1 .into方法提供了第二个参数,该参数是对成功和失败的回调。 您可以使用它来跟踪何时调用了这三个函数,并立即对它们的可见性进行操作。 Javadoc:https://square.github.io/picasso/2.x/picasso/com/squareup/picasso/RequestCreator.html#into-android.widget.ImageView-com.squareup.picasso.Callback- 回答2 这是一个简单的示例,如何实现毕加索图片加载的回调: Picasso.with(MainActivity.this) .load(imageUrl) .into(imageView, new com.squareup.picasso.Callback() { @Override public
  • 使用Java类HttpsURLConnection(Using java class HttpsURLConnection)
    问题 我有一小段代码,基本上可以实现HTTP客户端,即它POSTS请求并与re RESPONSE一起工作。 只要保持一致,HTTP便可以正常工作。 由于某种原因,我现在也必须支持HTTPS。 因此,这是我为打开连接所做的简要操作: URL url = new URL(serverAddress); HttpsURLConnection httpsConn = (HttpsURLConnection) url.openConnection(); 这失败,说明: sun.net.www.protocol.https.HttpsURLConnectionImpl cannot be cast to com.sun.net.ssl.HttpsURLConnection 我想这有点琐碎,但是我没弄明白我在这做错了什么...谷歌搜索,代码看起来很正确-不是吗? 任何想法表示赞赏! 回答1 只需将其保留为java.net.URLConnection或将其强制转换为java.net.HttpURLConnection。 两者都提供了可以很好地完成所需任务的方法。 与技术问题无关的旁注:您永远不要在代码中显式导入/使用Sun Java SE实现特定的类。 这些是未记录的类,可能会发生更改,这些更改可能会在升级JVM时导致代码中断。 另一方面,当您在其他品牌的JVM上运行代码时,代码也可能会中断。
  • XGBoost算法原理小结
    我只是一名搬运工,以下内容来自:刘建平Pinard https://www.cnblogs.com/pinard/p/10979808.html 前言   在之前作过梯度提升树(GBDT)原理小结,但是对GBDT的算法库XGBoost没有单独拿出来分析。虽然XGBoost是GBDT的一种高效实现,但是里面也加入了很多独有的思路和方法,值得单独讲一讲。因此讨论的时候,我会重点分析和GBDT不同的地方。   本文主要参考了XGBoost的论文和陈天奇的PPT。 1. 从GBDT到XGBoost   作为GBDT的高效实现,XGBoost是一个上限特别高的算法,因此在算法竞赛中比较受欢迎。简单来说,对比原算法GBDT,XGBoost主要从下面三个方面做了优化:   一是算法本身的优化:在算法的弱学习器模型选择上,对比GBDT只支持决策树,还可以直接很多其他的弱学习器。在算法的损失函数上,除了本身的损失,还加上了正则化部分。在算法的优化方式上,GBDT的损失函数只对误差部分做负梯度(一阶泰勒)展开,而XGBoost损失函数对误差部分做二阶泰勒展开,更加准确。算法本身的优化是我们后面讨论的重点。   二是算法运行效率的优化:对每个弱学习器,比如决策树建立的过程做并行选择,找到合适的子树分裂特征和特征值。在并行选择之前,先对所有的特征的值进行排序分组,方便前面说的并行选择。对分组的特征