c++ - 効率的な周波数計算に関するデータ構造の決定

Question

質問：テキストファイルで最も頻繁に使用されるn個の単語を計算する場合、どのデータ構造がより効率的ですか。ハッシュテーブルまたは優先キュー？

以前にこのテーマに関連する質問をしましたが、創造的な応答の後で混乱し、実際に簡単に実装できる2つのデータ型を決定しました。ハッシュテーブルと優先キュー

優先キューの混乱：正直なところ、優先キューに関連するYouTubeの講義を聞いたことがありますが、それがすべてのコンポーネントであることを理解しましたが、その適用性に関しては混乱します。バイナリヒープを使用すると、優先キューを簡単に実装できますが、私の課題は、コンポーネントの使用法を頻度の問題に一致させることです。

私のハッシュテーブルのアイデア：ここでハッシュテーブルのサイズを決定するのは少し不確かだったので、私にとってもっと意味のあるものを選ぶことにしました：26。アルファベットの文字数が原因です。さらに、優れたハッシュ関数があれば効率的です。ただし、リンクリストに何度も連絡を取り（共謀に個別のチェーンを使用）、その整数値を1ずつ増やすことは、私の意見では効率的ではありません。

長い投稿で申し訳ありませんが、プログラマーの仲間として、どちらをお勧めしますか。優先キューが私の質問に関連付けるためのアイデアを私に与えることができれば、ハッシュテーブルをさらに効率的にするために何かできるでしょうか？

Answer 1

ハッシュテーブルは、より理にかなっていることに加えて、提供された2つの選択肢の中でより高速です。サイズ26を選択するのではなく、固有の単語の総数を見積もる場合（そして、専門用語以外のほとんどの人の語彙は10,000をはるかに超えない場合、20,000は実際に大きく、30,000は単語を集めるのが好きです）、サイズを十分に大きくして、それを埋めることが期待できないようにして、衝突の可能性が低くなるようにします（25％以下）。より保守的にしたい場合は、テーブルの内容を元のサイズの2倍のテーブルに再ハッシュする関数を実装します（サイズをプライムにするため、元のサイズの約2倍にします）。

これはC++のタグが付けられているので、標準のテンプレートライブラリから直接マルチセットを使用していない理由を自問するかもしれません。それはあなたがそれに入力した各単語の数のカウントを保持します。

どちらの場合も、頻度のランク順ではなく頻度しか持っていないため、どの単語が最も頻度が高いかを見つけるために別のパスを作成する必要があります。

Answer 2

汎用/ユニバーサル文字列ハッシュ関数を使ってみませんか？結局のところ、最初の文字を数えたくないので、考えられるすべての単語を数えたいのです。バケット数は動的に保ちます。そうでない場合は、非常に多くのリンクリストトラバーサルを実行する必要があります。