最近在一次技术面试中,我被要求编写一个程序来查找教科书中的高频词(出现次数最多的词)。该程序的设计方式应该是,它以最少的内存处理整个教科书。性能不是问题。我能够通过编程来找到单词的频率,但它消耗了大量内存。
你如何使这个操作减少内存密集度?任何策略/解决方案?
-斯内哈尔
最佳答案
您可能使用了内存密集型但具有恒定查找时间的哈希表——因此性能/内存权衡是显而易见的。当你读到本书的结尾时,你就会知道你的答案。此外,每个单词的计数器递增速度很快(因为可以快速查找哈希表)。
光谱的另一端是查看第一个单词,然后浏览整本书以查看该单词出现的次数。这需要最少的内存。然后你对下一个单词做同样的事情并通读整本书。如果该词出现更多次,则将其添加为最上面的词(或前 N 个词)。当然,这是非常低效的——如果第一个和第三个单词相同,即使你只是对第一个单词做了同样的事情,你最终也会再次阅读整本书。
关于text - 如何在内存不足的环境中找到书中的高频词?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/742125/