algorithm - 在内存中布局有向无环图以最大化数据局部性的算法

Question

说我有边缘

A -> C
A -> D
A -> E
B -> D
B -> E

为了最大化数据局部性，我会安排 DAG 按此顺序存储在内存中（作为数组），以最小化节点与其依赖项之间的距离。

C, A, D, E, B

使得 A 到 C 的距离为 1，到 D 的距离为 1，到 E 的距离为 2。

B 到 E 的距离是 1，到 D 的距离是 2。

有这样做的算法的名称吗？如果没有，人们将如何实现这一点？

score 2 · Accepted Answer

看起来你想要线性化 DAG。我不知道您是否将其用于依赖关系解析。Topological_sorting你的问题看起来很熟悉。该程序tsort也做了非常相似的事情。

然而，它是依赖线性化。

neel@gentoo:~$ tsort
C A
D A
E A
D B
E B

C
D
E
B
A

打印必须执行该任务的顺序。如果有循环，它可能不起作用。正如你提到的它的非循环的，它是相关的。

我不知道是否有任何这样的算法data locality ordering string或类似的算法，但是看起来您的数据位置字符串有一些问题。

如果C接近（1）A并且也接近（1）B并且B太远（4），A您将如何用您的数据位置字符串表示它？

我现在不知道你到底想做什么。如果您想线性化依赖关系以按正确顺序执行任务，请进行拓扑排序。

score 1 · Accepted Answer

这是改善局部性的略有不同的方法：

所描述的算法似乎更接近于力导向的图形绘制算法而不是拓扑排序。

您还应该阅读有关内存图形数据库的论文，例如imGraph

2 回答 2