java - 在大型未排序列表中查找 n 个最大值，一次只处理一页值

Question

我在概念上很挣扎。

如何编写程序从大约 20 亿大小的列表中找出最大的 10,000 个数字？假设计算机一次只能处理大约 10,000 个数字(总共 20 亿)。排除程序本身的任何开销，假设我在主内存中有足够的空间来一次处理 10,000 个数字。

有人建议我使用堆来处理信息，但当我无法一次对所有数字进行排序时，我不知道如何执行此操作。

Answer 1

1. 将前 10,00 个数字添加到结果列表中。 (保持此列表排序以进行进一步的步骤)
2. 遍历其余 20 亿个数字；对于每一个检查它是否大于结果列表中的最小数字，如果是，用这个替换最小数字。

这样你只需要同时在内存中保留10,000个数字。

编辑 25/2/15:

假设 n = 结果大小，m = 输入大小，结果列表中必须替换数字的次数，此处计算 Number of assignments necessary to find the minimum value in an array?对于 n = 1 的情况，可以扩展到这种情况:

double averageReplacementCount = 0;
for (int i = n; i < m; i++) {
    averageReplacementCount += 1.0 / (i + 1);
}

对于 n = 10,000 和 m = 2,000,000,000，这仅为 ~12.206(< 13 !)。

这仅适用于数字均匀分布的情况。如果它们下降，则不需要替换，但如果它们上升(最坏情况!)，则需要 (m-n) 次替换。

这使得结果列表的数据结构选择可能不重要，只要最小值被缓存并且可以在恒定时间内进行比较即可。