0

この質問を解決する1つの方法は、単語とそれに対応する単語数をハッシュすることです。次に、ハッシュマップをトラバースして、上位3つを見つけます。

これを解決するためのより良い方法はありますか？HashMapの代わりにBSTを使用した方が良いでしょうか？

4

4 に答える 4

1

Trieは、このための優れたデータ構造です。ハッシュ計算の必要はなく、挿入と更新の時間計算量O(1)は辞書のサイズにあります。

于 2012-06-26T20:05:19.480 に答える
0

HashMapまたはBSTのいずれかが妥当な選択です。それぞれのパフォーマンスは、カウントする必要のある単語の数によって異なります。これらのインスタンスでは、プロファイラーが友だちです（VisualVMから始めるのが妥当です）。

于 2012-06-26T19:13:58.190 に答える
0

この場合、多くの異なる単語が存在する可能性があるため、ハッシュテーブルのパフォーマンスが向上することを賭けます。ルックアップがO(1)引き継ぎO(log N)ます。

于 2012-06-26T20:02:19.367 に答える
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 に答える