1

我一直在研究一个我认为人们可能会感兴趣的问题（也许有人知道预先存在的解决方案）。

我有一个大型数据集，由一长串指向对象的指针组成，如下所示：

[
  (a8576, b3295), 
  (a7856, b2365), 
  (a3566, b5464),
  ...
]

任何时候都有太多的对象需要保存在内存中（可能有数百 GB），因此它们需要存储在磁盘上，但可以缓存在内存中（可能使用 LRU 缓存）。

我需要遍历这个列表来处理每一对，这需要将这对中的两个对象都加载到内存中（如果它们还没有缓存在那里）。

所以，问题是：有没有办法重新排序列表中的对以最大化内存缓存的有效性（换句话说：最小化缓存未命中的数量）？

笔记

  1. 显然，重新排序算法应该尽可能快，并且不应该依赖于能够一次将整个列表保存在内存中（因为我们没有足够的 RAM）——但它可以迭代必要时列出数次。

  2. 如果我们处理的是单个对象，而不是对，那么简单的答案就是对它们进行排序。这显然在这种情况下不起作用，因为您需要考虑这对中的两个元素。

  3. 问题可能与找到最小图割有关，但即使问题是等价的，我认为最小割的解决方案也不满足

  4. 我的假设是启发式方法会将数据从磁盘中流出，并以更好的顺序将其分块写回。它可能需要多次迭代。

  5. 实际上，它可能不仅仅是成对的，它可能是三胞胎、四胞胎或更多。我希望对对执行此操作的算法可以很容易地推广。

4

4 回答 4

1

首先，您可以映射列表。如果有足够的地址空间，而不是内存，例如在 64 位 CPU 上，这将有效。这使得按顺序访问元素变得更加容易。

您可以根据缓存中考虑这两个元素的最小距离对该列表进行排序，如果对象位于连续空间中，则效果很好。排序函数可能类似于：将 (a, b) 与 (c, d) = (a - c) + (b - d) 进行比较（看起来像汉明距离）。然后根据列表提取对象存储的切片并进行处理。

编辑：修复了远处的一个错误。

于 2009-01-31T21:35:55.737 回答
1

即使您不只是对该列表进行排序，多路合并排序的一般模式也可能适用 - 也就是说，考虑将集合的某种（可能是递归的）分解为可以在内存中单独处理的较小集合，然后是第二个阶段，之前处理过的集合的小块可以全部组合在一起。即使不知道您对这些对所做的具体性质，可以肯定地说，当您处理已排序的数据时，许多算法问题会变得更加简单（包括图形问题，这可能是您的手在这里）。

于 2009-01-31T21:48:12.000 回答
1

您的问题与计算机图形硬件的类似问题有关：

在三角形网格中渲染索引顶点时，通常硬件会缓存最近转换的顶点（上次我不得不担心它时大约有 128 个，但怀疑这些天这个数字更大）。未缓存的顶点需要相对昂贵的变换操作来计算。用于重构三角形网格以优化缓存使用的“网格优化”曾经是一个非常热门的研究课题。谷歌搜索顶点缓存优化（或优化：^）可能会找到一些与您的问题相关的有趣材料。正如其他海报所暗示的那样，我怀疑有效地做到这一点将取决于利用数据中任何固有的连贯性。

另一件要记住的事情：当 LRU 缓存变得过载时，非常值得更改为 MRU 替换策略，以至少在内存中保留一些项目（而不是每次传递都翻转整个缓存）。我似乎记得 John Carmack 就这个主题写了一些与 Direct3D 纹理缓存策略相关的好材料。

于 2009-02-01T10:30:33.117 回答
0

我认为这个问题的答案将在很大程度上取决于这对对象的访问模式。正如您所说，在简单的非配对情况下，最好只对指针进行排序。在更复杂的情况下，如果模式使得这些值的局部性更重要（例如，这些是键/值对并且您正在做一个很多搜索，键的位置比值的位置更重要）。

所以，真的，我的回答是这个问题不能在一般情况下回答。

为了存储您的结构，您真正想要的可能是B-tree。这些是为您正在谈论的内容而设计的——跟踪您不想（或不能）将整个内容保存在内存中的大型集合。

于 2009-01-31T21:29:24.393 回答