我正在实现一个基于图约简规则的算法。这段视频比文字更好地解释了算法,但是,为了完成任务,下面是一个简短的总结:
该算法工作在一个图中,每个节点都有三个边,其中一个是“主”边。当主边缘相交时,节点被认为是活动的,并且应用了约简规则。还值得注意的是,当两个节点交互时,非常接近它们的另一个节点很可能会成为活动节点。
我目前正在存储这个图,完全没有局部性:我只是在缓冲区中添加新的节点。这是我使用的朴素分配策略的代码,在JavaScript中是原型的:
function Node(type,tag){
var idx = garbage.pop() || memory.length;
memory[idx+0] = type; // Node type (used on readback)
memory[idx+1] = 0; // Port 0 target port
memory[idx+2] = 0; // Port 1 target port
memory[idx+3] = 0; // Port 2 target port
memory[idx+4] = 0; // Port 0 target node
memory[idx+5] = 0; // Port 1 target node
memory[idx+6] = 0; // Port 2 target node
memory[idx+7] = ++next_id; // Unique id
memory[idx+8] = tag; // Tag (used to decide which reduction rule apply)
return idx;
};为了最大限度地提高这种图形算法的局部性和缓存效率,在内存中组织这个图的最佳方法是什么?
发布于 2015-08-12 12:27:25
我只知道两种“存储”图形的方法。所谓“存储”,我指的是实现。
任何一个边都存储在每个节点的链接列表中,其中的所有优点是:添加和删除边是快速的,但是找到一个边是很长的。
或者边存储在节点矩阵中,而Arraynode1的值是边的权重。添加和删除一个节点是很长的,但是找到一个节点或边缘是快速的。
使用链接列表方法,您只存储存在的内容,使用矩阵方法,您存储每个边,即使它不存在,您必须为它提供一个值。
https://stackoverflow.com/questions/31955567
复制相似问题