text - 如何在内存不足的环境中找到书中的高频词？

Question

最近在一次技术面试中，我被要求编写一个程序来查找教科书中的高频词(出现次数最多的词)。该程序的设计方式应该是，它以最少的内存处理整个教科书。性能不是问题。我能够通过编程来找到单词的频率，但它消耗了大量内存。

你如何使这个操作减少内存密集度？任何策略/解决方案？

-斯内哈尔

Answer 1

您可能使用了内存密集型但具有恒定查找时间的哈希表——因此性能/内存权衡是显而易见的。当你读到本书的结尾时，你就会知道你的答案。此外，每个单词的计数器递增速度很快(因为可以快速查找哈希表)。

光谱的另一端是查看第一个单词，然后浏览整本书以查看该单词出现的次数。这需要最少的内存。然后你对下一个单词做同样的事情并通读整本书。如果该词出现更多次，则将其添加为最上面的词(或前 N 个词)。当然，这是非常低效的——如果第一个和第三个单词相同，即使你只是对第一个单词做了同样的事情，你最终也会再次阅读整本书。