たとえば、1GB という巨大なファイルが与えられたとします。ファイルには各行に 1 つの単語 (合計 n 単語) が含まれており、ファイル内で最も頻繁に使用される k 個の用語を見つけたいとします。
さて、これらの単語を格納するのに十分なメモリがあると仮定すると、Big-O の複雑さにおけるメモリ使用量と一定のオーバーヘッドを削減するという観点から、この問題に取り組むより良い方法は何でしょうか? 使用できる基本的なアルゴリズムは 2 つあります。
どちらがより良いアプローチですか?
また、ハッシュ テーブル/トライに十分なメモリがない場合 (つまり、メモリが 10MB 程度に制限されている場合)、最善の方法は何ですか?
定数に関してどちらがより効率的であるかは非常に依存しています。一方では、トライはO(N)すべての要素を挿入するための厳密な時間の複雑さを提供しますが、最悪の場合
、ハッシュ テーブルは 2 次時間に減衰する可能性があります。
一方、キャッシュに関しては、試行はあまり効率的ではありません。シークごとにO(|S|) ランダム アクセスメモリ要求が必要になるため、パフォーマンスが大幅に低下する可能性があります。
どちらのアプローチも有効であり、最大レイテンシ(リアルタイム システムの場合)、スループット、開発時間など、いずれかを選択する際に考慮する必要がある複数の考慮事項があると思います。
平均的なケースのパフォーマンスがすべて重要である場合は、一連のファイルを生成し、統計分析を実行することをお勧めします。ウィルコクソンの符号付き検定は、事実上使用されている最先端の仮説検定です。
組み込みシステムに関して: 両方のアプローチはまだ有効ですが、ここでは: トライ内の各「ノード」(またはノードの束) は、RAM ではなくディスク上にあります。トライ O(|S|)ランダム アクセスディスクはエントリごとにシークすることを意味することに注意してください。これは遅くなる可能性があります。
ハッシュ ソリューションの場合、10MB あります。たとえば、ディスクへのポインタのハッシュ テーブルにこれらのうち 5MB を使用できるとします。また、これらの 5MB に 500 の異なるディスク アドレスを格納できると仮定します (ここでは悲観的な分析)。つまり、各ハッシュ シーク後にバケットをロードするために 5MB が残っていることを意味します。 500 * 5MB * 0.5 ~= 1.25GB > 1GB のデータを格納できるため、ハッシュ テーブル ソリューションを使用するため、ハッシュを使用すると、関連する文字列を含むバケットを見つけるために、各シークでO(1) ランダムディスク シークのみが必要になります。
それでも十分でない場合は、仮想メモリ メカニズムのページング テーブルで行われていることと非常によく似た、ポインター テーブルを再ハッシュできることに注意してください。
このことから、組み込みシステムの場合、ほとんどの場合、ハッシュ ソリューションの方が優れていると結論付けることができます(最悪の場合でも、遅延が大きくなる可能性があることに注意してください。ここでは特効薬はありません)。
PS、基数ツリーは通常、トライよりも高速でコンパクトですが、ハッシュテーブルと比較してトライと同じ副作用があります（もちろん、それほど重要ではありません）。
限られたメモリオプションの場合、最初にリストをクイックソートしてから、ハッシュテーブルにk個のアイテムを入力するだけです。次に、現在の単語のどこでチェックしていたアイテムの数を知るために、もう1つのカウンターが必要になります。それより高い場合は、ハッシュテーブルの一番下のアイテムを現在のアイテムに置き換えます。
これはおそらく最初のリストでは問題なく機能しますが、リスト全体をスキャンしてハッシュテーブルにカウントを入力するよりも遅くなります。
中間結果を保存するためにドライブしますか? 真であれば：
何らかのメタ構造を持っている可能性があります。ハッシュテーブルのセット。データの一部を読み取り (ハッシュのサイズが 3 MB 未満)、ハッシュテーブルに入力します。サイズが 3 MB を超えると、ディスクに保存されます。制限が10 mbの場合、ハッシュテーブルのサイズは3 mbです(たとえば)。
メタはハッシュテーブルを記述します。メタでは、このハッシュ内の一意の単語の数とすべての単語の数、および 1 つの世界の最大数を格納できます!!! 私
この後。ディスクからハッシュテーブルをロードしてマージすることができます。
たとえば、一意の単語の昇順でハッシュテーブルをロードしたり、ハッシュ内の 1 つの世界の最大数をロードしたりできます。このステップでは、ヒューリスティックを使用できます。