0

我有一个算法，我需要计算大型对象之间的所有成对距离（其中距离是一个真正的度量，因此dist(a,b) == dist(b,a)，在所有其他度量要求中）。我有大约一千个物体，所以我需要计算大约 500,000 个距离。有几个问题：

  1. 所有这 1000 个对象都被序列化，位于磁盘上的单个文件中。
  2. 与相对微不足道的距离计算相比，从磁盘读取它们是一项巨大的操作。
  3. 我不能在不交换的情况下同时将它们全部存储在内存中，然后再颠簸。我一次可以容纳大约 500 个内存。
  4. 这意味着在某个时间点我需要在之前某个时间点读取并释放内存之后将对象重新读入内存。

因此，鉴于从磁盘读取是瓶颈，并且我一次不能读取超过一半，任何人都可以想到一种算法来读取和释放这些对象，从而最大限度地减少读取总数？

我考虑在前半部分阅读，做所有这些成对的距离，释放所有的记忆并阅读下半部分，然后再做所有的成对距离。此时，我仍然需要前半部分的对象和后半部分的对象之间的距离，我不知道该怎么做。我还考虑过拥有一个缓存，当缓存已满时，它会随机选择一个当前对象来驱逐并读取下一个对象，但我觉得必须有更好的选择。我考虑过 LRU 之类的东西，但它可能导致所需对象在最后一次计算中被驱逐的行为。

总而言之，我有点卡住了。有什么建议吗？

4

3 回答 3

3

加载上半场的积分。计算成对距离。将前半部分保留在内存中，将后半部分中的点逐个加载，计算距离。加载整个后半部分并计算成对距离。这大约是每点 1.5 次读取，这在以下模型中是最佳的。

模型是这个任务的语法正确的程序是 LOAD( i , j ) 形式的指令序列，其含义是将点i加载到内存位置j中。如果对于每一对点，都存在一条指令，然后两个点都在内存中，则程序是正确的。

很明显，在正确的程序中，每个点都至少加载一次。假设正好有 1000 个点和 500 个位置，那么至少有 500 次驱逐有利于第一次加载点。假设不失一般性，在内存中没有任何点被重复。在第一次加载点p以支持点q后，需要重新加载p以便计算p和q之间的距离。因此，至少有 500 次重新加载，因此至少有 1500 次加载。

于 2013-08-26T15:19:12.593 回答
2

我的第一个想法（所以它可能不是最好的）：

对于每个 i：

  • 阅读第 i 组 250。计算它们之间的距离。

  • 对于每个剩余的 250 组 j：

    • 阅读第 j 组。

    • 计算第 i 组和第 j 组中的点之间的距离。

    • 丢弃组 j。

  • 丢弃组 i。

因此，您将阅读以下组：

i  j
1  2
   3
   4
2  3
   4
3  4
4

你会注意到单独阅读第 4 组是毫无意义的——你可以在阅读第 3 组（或其他）时计算距离。

因此，您以每点的平均(1+2+3+3)/4 = 2.25读取次数结束。

于 2013-08-26T15:02:46.123 回答
1

我会尝试稍微改进@Dukeling 的答案。如果我理解正确，这会更好

i j
1 2
  3
  4
2 
3
  2

现在您每点有 (1+3+2+1)/4=1.75 次读取。

于 2013-08-26T15:13:24.507 回答