動的に変化する単語の大きなファイルがあります。いくつかの単語を継続的に追加しています。それぞれの瞬間に流行語のトップ 10 を追跡するにはどうすればよいでしょうか?
ブログでこの質問を見つけましたが、答えがわかりませんでした。答えは: ハッシュ テーブル + 最小ヒープ
最小ヒープ部分ではなくハッシュテーブルの理由を理解しています。誰かが私を助けることができますか?
5540 次
2 に答える
8
その場合は、 aとともに atop 10 trending wordsを使用する必要があります。max-heaphash-table
新しい単語がファイルに追加されると、次のようになります。
Createとxを持つ新しい要素。x.key=wordx.count=1Addxにhash-table。O(1).Addxにmax-heap。O(lgn).
既存の単語がファイルに追加されると、次のようになります。
Findxでhash-table。O(1).Updatex.countにx.count++。
次に取得する必要がある場合top 10 trending words:
Extractから10回max-heap。10*O(lgn)=O(10*lgn)=O(lgn).
ご覧のとおり、必要なすべての操作はせいぜい で行われO(lgn)ます。
于 2012-08-27T05:38:02.393 に答える
1
トップ10だけを維持したい場合は、最大ヒープを使用するのはやり過ぎです。ソートされた配列に10個のエントリを保持することは、より簡単で高速になります。
並べ替えには、配列の下から挿入ソートを使用します。候補者がすでにトップ10に入っているかどうかを確認し、必要に応じてその位置を更新する必要があります。
于 2012-08-28T07:05:20.473 に答える