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

说我有优势

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

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

C, A, D, E, B

所以A的距离是1到C，1到D，2到E。
B的距离是1到E，2到D。
有没有一个算法能做到这一点？如果没有，该如何实现？

最佳答案

看起来你想把DAG线性化。我不知道你是不是用它来解决依赖问题。你的问题看起来很熟悉。而且程序Topological_sorting做了非常相似的事情。
但它是依赖线性化的。

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

C
D
E
B
A

它打印任务执行的顺序。如果有周期的话就可能不起作用正如你提到的，它是无环的。
我不知道是否有这样的tsort算法或者类似的算法，但是看起来您的数据局部性字符串有一些问题。
如果data locality ordering string与C接近（1）且也与A接近（1）且B与B距离太远（4），您将如何用数据局部字符串表示它？
我现在不知道你到底想干什么。如果您想将依赖项线性化，以便按正确的顺序执行任务，那么请执行拓扑排序。

关于algorithm - 用于在内存中布置有向无环图以最大化数据局部性的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10631380/