我知道这个问题已经在论坛上被问过两次，我没有找到任何可以认为是最合适的解决方案的“ TAGGED”答案-因此请再次提出：
书中给我们提供了非常大的文字，所有这些文字都无法放入记忆中。我们需要找到文本中最常见的10个单词。这样做的最佳方式（时间和空间）是什么？
我的想法：
将文件分为k个可调整大小的块（这样每个块都可以存储在内存中）。现在，对每个块执行外部排序。一旦我们将（N / k）-排序的文件放在磁盘上（假设N是书中文本的总大小）-我不确定该如何继续才能从中获得前10个元素k个排序的数组。
另外，如果有不同的想法，请提出建议。
编辑 ：此算法存在问题，特别是递归合并列表使其成为多项式运行时算法。但我将其作为有缺陷的算法的示例留在这里。
您不能丢弃数据块中的任何单词，因为一个单词可能仅在一个数据块中存在100次，而另一个单词在100个不同的数据块中每个存在一次。
但是您仍然可以以类似于MapReduce算法的方式使用块。您将每个块映射到一个单词列表（包括计数），然后通过将单词列表递归合并为一个单词来减少。
在映射步骤中，将每个单词映射到每个块的计数。按 字母顺序排序 ，而不是按计数排序，然后将列表存储到磁盘。现在，您可以线性地成对合并列表，而不必在内存中保留两个以上的单词：
a
b
继续执行此成对合并，直到所有文件合并到一个列表中。然后，您可以扫描一次结果列表，并保留十个最常用的单词。
