c - 如何避免动态图中出现 "heap pointer spaghetti"？

Question

一般性问题

假设您正在编写一个系统，该系统由一个图以及可以根据相邻节点的配置激活的图重写规则组成。也就是说，您有一个在运行时不可预测地增长/收缩的动态图。如果您天真地使用 malloc，新节点将被分配到内存中的随机位置；足够长的时间后，您的堆将成为指针意大利面条，给您带来糟糕的缓存效率。是否有任何轻量级增量技术可以使连接在一起的节点在内存中保持紧密？

我尝试过的

我唯一能想到的是将节点嵌入到笛卡尔空间中，并使用一些排斥/吸引节点的物理弹性模拟。这会将有线节点保持在一起，但看起来很愚蠢，我猜模拟的开销会比缓存效率加速更大。

实例

This是我要实现的系统。 This是我试图在 C 中优化的代码的简短片段。This repo 是 JS 中的原型(prototype)，工作实现，具有糟糕的缓存效率(以及语言本身)。 This video以图形方式显示运行中的系统。

Answer 1

您要解决的是线性排列问题。完美的解决方案被认为是 NP 难的，但存在一些很好的近似值。这是一个 paper这应该是一个很好的起点。