算法:计算单词列表频率的更好方法

Question

这个问题实际上非常简单但我希望在进入编码之前听到一些想法.给定每行中包含单词的文件,计算最多n个频繁的数字.

第一个也是唯一一个在我脑海中突然出现的东西用来使用a std::map.我知道C++的同事们会说这unordered_map将是非常合理的.

我想知道是否有任何东西可以添加到算法方面,或者这基本上是"谁选择了最好的数据结构获胜"类型的问题.我通过互联网搜索了它并读取了哈希表和优先级队列可能会提供一个运行时间为O(n)的算法,但我认为这将是复杂的实现

有任何想法吗？

Answer 1

用于此任务的最佳数据结构是Trie:

http://en.wikipedia.org/wiki/Trie

它将胜过用于计算字符串的哈希表.

Answer 2

对于这个问题有很多不同的方法。它最终取决于场景和其他因素，例如文件的大小（如果文件有十亿行），那么 aHashMap将不是一种有效的方法。您可以根据您的问题执行以下操作：

1. 如果您知道唯一单词的数量非常有限，则可以TreeMap在您的情况下使用 or std::map。
2. 如果单词数量非常大，那么您可以构建一个trie数据结构并在另一个数据结构中记录各个单词的数量。这可能是一个大小为 的堆（最小/最大取决于您想要做什么）n。因此，您不需要存储所有单词，只需存储必要的单词即可。