我一直在研究一个我认为人们可能会感兴趣的问题(也许有人知道一个预先存在的解决方案)。
我有一个大型数据集，其中包含一长串指向对象的指针对，如下所示:
[
(a8576, b3295),
(a7856, b2365),
(a3566, b5464),
...
]
在任何时候都有太多的对象无法保存在内存中(可能有数百 GB)，因此它们需要存储在磁盘上，但可以缓存在内存中(可能使用 LRU 缓存)。
我需要遍历这个列表来处理每一对，这需要将这对中的两个对象都加载到内存中(如果它们还没有缓存在那里)。
因此，问题是:是否有一种方法可以重新排列列表中的对，以最大限度地提高内存缓存的有效性(换句话说:最大限度地减少缓存未命中的次数)？
注意事项
显然，重新排序算法应该尽可能快，并且不应该依赖于能够一次将整个列表存储在内存中(因为我们没有足够的 RAM)-但如有必要，它可以多次遍历列表。
如果我们处理的是单个对象，而不是成对对象，那么简单的答案就是对它们进行排序。这在这种情况下显然行不通，因为您需要考虑这对中的两个元素。
问题可能与寻找minimum graph cut 的问题有关。 , 但即使问题是等价的，我也不认为 min-cut 的解决方案满足
我的假设是，启发式算法会将数据流出磁盘，然后以更好的顺序将其写回 block 中。它可能需要对此进行多次迭代。
实际上它可能不仅仅是一对，它可能是三胞胎、四胞胎或更多。我希望为对执行此操作的算法可以很容易地推广。
最佳答案
您的问题与计算机图形硬件的类似问题有关:
在三角形网格中渲染索引顶点时，通常硬件有一个最近变换顶点的缓存(上次我不得不担心它时大约有 128 个，但怀疑这些天这个数字更大)。未缓存的顶点需要相对昂贵的变换操作来计算。重构三角形网格以优化缓存使用的“网格优化”曾经是一个非常热门的研究课题。谷歌搜索 顶点缓存优化 (或优化 :^)可能会为您找到一些与您的问题相关的有趣 Material 。正如其他张贴者所建议的那样，我怀疑有效地做到这一点将取决于利用数据中的任何内在连贯性。
另一件要记住的事情:当 LRU 缓存变得过载时，很值得更改为 MRU 替换策略以至少将一些项目保留在内存中(而不是每次通过都翻转整个缓存)。我似乎记得 John Carmack 在与 Direct3D 纹理缓存策略相关的这个主题上写了一些很好的 Material 。
关于algorithm - 大型数据集的高效重新排序以最大化内存缓存效率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/499562/