データ構造の解説
どのプログラムもデータをどこかにしまっていて、そのしまい方が何が速く何が遅いかを決めます。100万人の名前の一覧は、1人ずつ順に探すこともできれば、どの名前も20回の比較で見つかるように並べておくこともできます。データ構造とはそうした並べ方のことです。ほとんどがパソコンよりも古い一握りのアイデアが、あらゆるデータベース、OS、ブラウザー、ゲームの中に入っています。
データ構造は何のためにあるのか
データ構造は、答えなければならない質問によって選びます。電話の通話履歴は最新の通話を最初に、プリンターのジョブは最も古いものを最初に、辞書は10万語の中の1語の意味を、経路探索は最も近い未訪問の交差点を必要とします。どの構造も、ある操作を速くする代わりに別の操作をあきらめており、オーダー記法はその取引を表します。O(1)は要素数nが増えても時間が増えないこと、O(log n)はnが2倍になると1ステップ増えること、O(n)は時間がnに比例して増えることを意味します。
スタック、キュー、デック
スタックは同じ端で追加と削除を行います。後入れ先出しです。元に戻す履歴、戻るボタン、実行中のプログラムの関数呼び出しはスタックです。キューは末尾に追加して先頭から取り出します。先入れ先出しで、キー入力や印刷キューがその例です。デックは両端でその両方ができます。3つとも1回の操作は一定時間です。キューはよくリングバッファに収められます。これは固定された配列で、先頭と末尾は最後の位置を越えると最初に戻ります。満杯になると、要素は2倍の大きさの配列にコピーされます。コピーにはO(n)かかりますが、めったに起きないので、1回の操作は平均するとやはりO(1)です。これをならし計算量の上界と呼びます。
連結リスト
連結リストは、各値を次のノードへのポインタを持つノードに収めます。挿入や削除ではポインタを1つか2つ付け替えるだけで、何も動かす必要はありませんが、10番目のノードへ一気に飛ぶことはできません。先頭からリンクをたどります。先頭だけを持つリストが末尾に届くにはO(n)ステップかかります。実際のリストは末尾ポインタも持つことが多く、双方向リストは前へのポインタも持ちます。ブラウザーの履歴やLRUキャッシュはこうして作られています。
二分探索木
二分探索木は各ノードで、小さい値を左部分木に、大きい値を右部分木に置きます。探索は比較して左か右へ進み、中間順巡回は値を小さい順に読み出します。葉の削除はそれを取り除くだけ、子が1つのノードはその子で置き換え、子が2つのノードは中間順の後続、つまり右部分木の最小値で置き換えます。これらはすべて木の高さに比例する時間がかかります。木が茂っていればおよそlog nですが、値が整列した順で届くと木はリストに退化し、nになります。
AVL木と赤黒木
自己平衡木は変更のたびに形を修復します。1962年にアデルソン=ヴェリスキーとランディスが考案したAVL木は、各ノードの2つの部分木の高さの差を1以内に保ちます。あるノードのバランス係数が±2になると、1回の回転(LLとRRの場合)か2回の回転(LRとRL)でバランスを取り戻します。赤黒木はノードを色分けし、根を黒にし、赤いノードが赤い子を持たず、下へ向かうどの経路も同じ数の黒いノードを通るようにします。これで最長の経路は最短の経路の2倍以内に収まります。塗り直しと多くても数回の回転で自分を修復し、JavaのTreeMap、C++のstd::map、Linuxのスケジューラーの中にあるのはこの木です。
ヒープと優先度付きキュー
二分ヒープは、ポインタを使わずに配列に収めた完全二分木です。位置iの子は2i + 1と2i + 2にあります。最小ヒープではどの親も子以下の大きさなので、最小の値は常に根にあります。新しい値は末尾に置かれ、大きな親を越えて浮かび上がります。根を取り出すと、最後の値が一番上に移って沈んでいきます。どちらもO(log n)で、配列全体をO(n)でヒープにできます。ヒープはダイクストラ法の最短経路、イベントシミュレーション、OSのスケジューラーの優先度付きキューを動かし、ヒープソートも生み出します。
ハッシュテーブル
ハッシュテーブルはハッシュ関数でキーを配列のインデックスに変え、そこへ直接向かいます。異なるキーが同じインデックスに当たることがあり、これが衝突です。チェイン法は各バケットに小さなリストを持ちます。線形探査のようなオープンアドレス法は空いたスロットが見つかるまで次のスロットを試し、キーを削除するときは後の探索が探査を続けられるように墓石を残さなければなりません。よいハッシュ関数を使い、テーブルを大きくして負荷率(バケットあたりのキー数)を低く保てば、挿入、探索、削除は平均O(1)です。単語の文字コードを合計するような質の悪い関数は、アナグラムを同じバケットに送ります。Pythonのdict、JavaScriptのオブジェクト、データベースのインデックスの裏にはハッシュテーブルがあります。
トライとUnion-Find
トライ(接頭辞木)は文字列を1階層に1文字ずつ記録するので、同じ始まりの単語は経路を共有し、ノードが単語の終わりを示します。長さLの単語を探すには、記録された単語の数に関係なくLステップで済み、ある接頭辞を持つ単語はすべて1つの部分木に入っています。入力補完やスペルチェックはこうして動きます。Union-Findは要素を素集合に分けて持ち、それぞれの集合は根がその集合を代表する木です。Findは親リンクを根までたどり、Unionは一方の根をもう一方の根の下につなぎます。ランクによる併合と経路圧縮を使うと、長い一連の操作で1回あたりのコストはほぼ一定、つまりアッカーマン関数の逆関数α(n)となり、現実的などんなnでも4以下です。最小全域木を求めるクラスカル法はこれに頼っています。
よくある質問
配列と連結リストの違いは何ですか?
配列は要素をメモリ上に隣り合わせて並べるので、どの位置にもすぐに届きますが、途中に挿入するとその後ろをすべてずらす必要があります。連結リストはポインタを変えるだけでどこにでも挿入できますが、ある位置に届くには先頭から歩いていかなければなりません。配列はプロセッサーのキャッシュもずっとうまく使えるので、実際にはたいてい速くなります。
ならし計算量とは何ですか?
1回の操作がときどき高くつくことがあっても、長い一連の操作で平均した1回あたりのコストのことです。満杯になると2倍になるリングバッファは、ときどきn個の要素をすべてコピーしますが、バッファが大きくなるほどコピーはまれになるので、n回の追加は合計O(n)、つまり平均して1回O(1)です。
ヒープは二分探索木と同じものですか?
いいえ。二分探索木はすべての左部分木をそのノードの前に、すべての右部分木を後ろに並べるので、すべての値を順に列挙でき、どの値もすばやく見つけられます。ヒープが約束するのは、どの親も子より前に来ることだけです。それは最小値や最大値をすぐ見つけるには十分ですが、任意の値を探すには足りません。
Union-Findは2つの要素がつながっているかをどうやって知るのですか?
それぞれの要素から親リンクをたどって木の根まで行きます。両方が同じ根に着けば、同じ集合です。その後、経路圧縮によって経路上のすべてのノードが根を直接指すようになるので、次に同じことを尋ねたときは1ステップで済みます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
データ構造ビジュアライザーを開く