研究所のデータ グリッド ステーション用のアプリケーションを開発する必要がある場合。アプリケーションの目的は、1 週間に 1 回、午前 10 時から午前 10 時 30 分の間にデータ GRID ステーションからデータを受信し、それをデータ構造に格納することです。データは数字のみで構成されていますが、1 つのエントリに対して数字が非常に長くなる可能性があります。次に、配列、リスト、連結リスト、二重連結リスト、キュー、優先キュー、スタック、二分探索木、AVL 木、スレッド化二分木、ヒープ、ソートされた順次配列、およびスキップ リストから、どのデータ構造が特定のシナリオに最適であるか
ソートされた数字を保存したい。ソートされたデータは昇順または降順であり、主な関心事は「高速で効率的な検索」です。
あなたの説明から、数字や数字を含む他のデータを保存していないことがわかります。したがって、基本的には、数値がセットに含まれているかどうかを知りたいと考えています。
これを知る最も速い方法は、数値ごとにフラグの配列を用意することです。1 から 1000 までの数字を扱うとしましょう。数字 200 がセットに含まれているかどうかを知りたいとします。フラグが true か false かどうか、位置 200 を見てください。おわかりのように、これが最速の方法です。検索する場所は 1 か所だけだからです。
ここではブール値フラグについて話しているので、ストレージには少しで十分です。数値の数、使用可能なメモリ、およびマシンのアーキテクチャに応じて、ブール値をビット、バイト、ワードなどで格納するかどうかを決定します。
そうは言っても、非常に多くの数を処理する必要があるため、上記のアプローチはこれ以上実行できません。理論的には最速ですが、メモリが限られている場合、ハードディスクへのスワップ、そこからの読み取りが非常に多い場合、他のアルゴリズムがより優れていることが証明される場合があります。次のいずれかを選択できます。
これらのうちどれが最も効率的であるかは、データとマシンによって異なります。
実行する検索の種類によって異なります。数値がデータセット内にあるかどうかを知りたいだけの場合、ハッシュは非常に高速で、データセットのサイズに依存しません。また、並べ替える必要はなく、順序の概念さえありません。
Perl の作者である Larry Wall を引用するとしたら、次のようになります。
連想配列に対して線形スキャンを実行することは、ロードされた Uzi で誰かを棍棒で殺そうとするようなものです。
(連想配列はハッシュと同義です。)