我有非常大的文本文件，有数千万字，每行一个字。我需要在该文件中找到最常见的 10 个单词。有一些限制：仅使用标准库和使用少于 1 KB 的 memory。
保证该文件中的任何 10 个单词都足够短以适应所述 memory 限制，并且对于某些其他变量（例如计数器等）将有足够的 memory 。
我提供的唯一解决方案是使用另一个文本文件作为附加的 memory 和缓冲区。但是，处理该问题似乎是一种糟糕而缓慢的方法。
有没有更好更有效的解决方案？
回答1
您可以首先对这个文件进行排序（使用有限的 memory 可以实现，但当然需要磁盘 IO - 请参阅 https://stackoverflow.com/questions/7918060/how-do-i-sort-very-large-files 作为入门）。
然后您将能够逐行读取排序的文件并逐个计算每个单词的频率 - store 它们，在 10 个单词之后 - 如果频率高于所有存储在您的数组中 - 将其添加到内部数组并删除最少发生了一个，因此在此阶段您将在 memory 中仅保留 10 个最常用的单词。
正如@John Bollinger 提到的 - 如果您的要求是打印所有前 10 个单词，例如 - 文件中的所有单词都具有相同的频率，即它们都是“top”，那么这种方法将不起作用，您需要计算频率对于文件中的每个单词，store，对其进行排序，然后打印前 10 个，包括与第 10 个频率相同的所有单词。
回答2
如果您可以创建一个新文件，无论文件多么大，您都可以创建一个简单的https://en.wikipedia.org/wiki/AVL_tree 数据库，其中包含到目前为止的每个单词及其频率。这将花费你每次 O(log n)，n 从 1 到 N 个单词，加上对整个 N 大小的树的最终扫描，加起来是 O(N log N)。
如果您无法创建新文件，则需要对整个文件执行就地排序，这将花费大约 O(N2)。我认为这更接近于 O((N/k)2)，其中 k 是您可以在 memory 中保留的平均单词数，用于最简单的冒泡排序 - 但这是 O(1 /k2)O(N2) = K O(N2) 仍然是 O(N2 ）。此时您可以最后一次重新扫描文件，并且在每次运行每个单词之后，您都会知道该单词是否可以进入您的前十名，以及在哪个位置。所以你只需要在 memory 中放入 12 个单词（前 10 个单词、当前单词和刚刚从文件中读取的单词）。 1K应该够了。
所以，辅助文件实际上是最快的选择。