最小化大负载数量的算法

Question

我有一个算法，我需要计算大对象之间的所有成对距离(其中距离是一个真实的度量，所以 dist(a,b) == dist(b,a)，以及所有其他指标要求)。我有大约一千个物体，所以我需要计算大约 500,000 个距离。有几个问题:

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

鉴于从磁盘读取是瓶颈，而且我不能一次读取超过一半，有谁能想出一种读取和释放这些对象的算法，从而最大限度地减少读取总数？

我考虑过在上半部分阅读，完成所有这些成对距离，释放所有内存并阅读下半部分，然后完成所有这些成对距离。此时，我仍然需要前半部分的对象和后半部分的对象之间的距离，但我不确定该怎么做。我还考虑过有一个缓存，当它已满时，随机选择一个当前对象来逐出并读取下一个，但我觉得必须有更好的选择。我考虑过类似 LRU 的方法，但它可能导致所需对象在上次计算时被逐出的行为。

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

Answer 1

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

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

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