0

我知道解决这个问题的一种方法是散列单词及其相应的字数。然后遍历Hash map，找出top 3。

有没有更好的方法来解决这个问题？如果我使用 BST 而不是 HashMap 会更好吗？

4

4 回答 4

1

Trie是一个很好的数据结构。不需要哈希计算，插入和更新的时间复杂度O(1)与字典的大小一样。

于 2012-06-26T20:05:19.480 回答
0

我敢打赌，哈希表在这种情况下会有更好的性能，因为可能有很多不同的词。查找将O(1)接管O(log N)。

于 2012-06-26T20:02:19.367 回答
0

HashMap 或 BST 都是合理的选择。每个人的表现将根据您需要计算的字数而有所不同。在这些情况下，分析器是您的朋友（VisualVM是一个合理的开始选择）。

于 2012-06-26T19:13:58.190 回答
0

基本上，直方图是这样做的标准方式，您可以选择要用于直方图接口的实现，它们之间的区别实际上是特定于实例的 - 每个都有其优点和缺点。

您可能还需要考虑使用map-reduce设计来计算字数：

map(doc):
   for each word:
     emitIntermediate(word,"1")

reduce(word,list<string>):
   emit(word,size(list))

如果您有很多文档，这种方法可以提供很好的可扩展性 - 使用 map-reduce 接口，或者如果您喜欢函数式编程，则使用优雅的解决方案。

注意：这种方法与散列解决方案基本相同，因为映射器(key,values)使用散列传递元组。

于 2012-06-26T20:29:59.597 回答