私は大規模なプロジェクトに取り組んでいます。わざわざここで要約するつもりはありませんが、プロジェクトのこのセクションでは、非常に大きなテキスト ドキュメント (最小で約 50,000 語 (一意ではない)) を取得し、それぞれの一意のテキストを出力します。最も使用されている単語から最も使用されていない単語の順に並べます (おそらく、上位 3 つは「a」、「an」、および「the」になります)。
もちろん、私の質問は、使用するのに最適な並べ替えアルゴリズムは何ですか? 私はソートのカウントを読んでいましたが、それは気に入っていますが、一意の単語の数に比べて値の範囲が大きすぎることが懸念されます。
助言がありますか？
まず、ワード -> カウントのマップが必要です。50,000 語はそれほど多くはありません。簡単に記憶に収まるので、心配する必要はありません。C++ では、標準の STL std::map を使用できます。
次に、マップを取得したら、すべてのマップ キーをベクターにコピーできます。
次に、カスタム比較演算子を使用してこのベクトルを並べ替えます。単語を比較する代わりに、マップのカウントを比較します。(特定の並べ替えアルゴリズムについて心配する必要はありません。配列はそれほど大きくないため、標準ライブラリの並べ替えはどれでも機能します。)
クイックソートから始めて、そこから進みます。
ただし、違いについては、並べ替えアルゴリズムに関する wiki ページを参照してください。
MSD 基数ソートを試してください。エントリを辞書順に並べ替えます。これは、あなたが興味を持っているかもしれないGoogleコードプロジェクトです.
2つの単語が同じ回数出現する場合、それらを出力する順序は重要ではないと仮定すると、この特定の問題でクイックソートよりも優れたパフォーマンスを得ることができます。
最初のステップ：単語をキー値、頻度を関連値としてハッシュマップを作成します。ファイルを解析するときに、このハッシュマップを入力します。これを行っている間、遭遇した最高周波数を追跡するようにしてください。このステップはO（n）の複雑さです。
2番目のステップ：最初のステップからの最高頻度に等しいエントリの数でリストを作成します。このリストの各スロットのインデックスは、頻度カウントがインデックスに等しい単語のリストを保持します。したがって、ドキュメント内で3回出現する単語は、たとえばlist[3]に含まれます。ハッシュマップを繰り返し処理し、リスト内の適切な場所に単語を挿入します。このステップはO（n）の複雑さです。
3番目のステップ：リストを逆に繰り返し、すべての単語を出力します。このステップはO（n）の複雑さです。
全体として、このアルゴリズムは、クイックソートで必要なO（nlogn）ではなく、O（n）時間でタスクを実行します。
これまでにテストしたほとんどすべてのケースで、Quicksort が最適でした。ただし、Combsort が最適なケースが 2 つあります。コードが非常に小さいため、またはデータの順序付けの癖が原因で、これらのケースではcombsortの方が優れていた可能性があります。
並べ替えが私のプロフィールに表示されるときはいつでも、主要な並べ替えを試します。クイックソートとコムソートの両方を上回ったことはありません。
リンクを見てください。さまざまなアルゴリズムがどのように機能するかを絵で表したもの。これがヒントになります！
大規模なセットの場合は、情報検索で「ソート ベースのインデックス作成」と呼ばれるものを使用できますが、50,000 語の場合は次の方法を使用できます。
以下の投稿で説明されているように、何かをしたいと思います。
http://karephul.blogspot.com/2008/12/groovy-closures.html
エリックが言及したLINQのように、クロージャーをサポートする言語はソリューションを非常に簡単にします。
Trie とも呼ばれるデジタル ツリーの実装を試すこともできます。ここにリンクがあります