我知道这已经在论坛上被问过几次，我没有找到任何可以被认为是最合适的解决方案的“标记”答案 - 所以再次询问：
我们从书中得到了一个非常大的文本，所有这些都无法放入记忆中。我们需要找到文本中出现频率最高的 10 个单词。做到这一点的最佳（时间和空间）方式是什么？
我的想法：
将文件分成 k 个大小的块（这样每个块都可以存储在内存中）。现在，对每个块执行外部排序。一旦我们在磁盘上有 (N/k)- 排序的文件（假设 N 是书中文本的总大小） - 我不知道应该如何继续，以便我可以从k 排序数组。
另外，如果有不同的思路，请提出建议。
这是流算法领域的经典问题。在某些退化的情况下，显然没有办法做到这一点。您需要适应一堆大约（在明确定义的意义上）流中前 k 个单词的元素。我不知道任何经典的参考资料，但一个快速的谷歌把我带到了这个。它似乎对进行流式 top-K 的各种技术进行了很好的调查。您可以查看其中的参考资料以获取其他想法。
另一个想法（并且在流模型中不适用）只是随机采样尽可能多的单词以适合内存，对它们进行排序和唯一化，然后再次遍历文件，计算单词在你的样品。然后你可以很容易地找到前k个。
编辑：此算法存在问题，特别是递归合并列表使其成为多项式运行时算法。但我将把它留在这里作为一个有缺陷的算法的例子。
您不能从块中丢弃任何单词，因为可能有一个单词仅在一个块中存在 100 次，而另一个单词在 100 个不同块中的每一个中都存在一次。
但是您仍然可以使用类似于MapReduce算法的方式使用块。您将每个块映射到一个单词列表（包括计数），然后通过递归地将单词列表合并为一个来减少。
在映射步骤中，将每个单词映射到每个块的计数。按字母顺序排序，而不是按计数并将列表存储到磁盘。现在您可以成对线性合并列表，而无需在内存中保留两个以上的单词：
aba= b：
a> b：
b将其计数写入Rb从 B读取一个新行a< b:
a将其计数写入Ra从 A读取一个新行继续执行此成对合并，直到所有文件合并到一个列表中。然后您可以扫描一次结果列表并保留十个最常用的单词。