KATOエンジニヤリング開発日誌

「アウトプット無きエンジニアにインプットもチャンスも無い」の精神で書いています

「なっとくアルゴリズム」を読んだ - データ構造 -

表紙買いした「なっとくアルゴリズム」を読み終わったので理解したことを何回かに分けて書きます。

なっとく! アルゴリズム

なっとく! アルゴリズム

  • 作者: アディティア・Y・バーガバ,株式会社クイープ
  • 出版社/メーカー: 翔泳社
  • 発売日: 2017/02/01
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログを見る

アルゴリズムの速度を表す指標

ビッグオー記法

アルゴリズムがどれくらい高速かを表す表記法のことをビッグオー記法(Big O notation)という。ビッグオー記法を使うとさまざまなアルゴリズムの最も一般的な計算時間を示すことができる。

ビッグオー記法の一般的な時間計算量は下記の通り。

  • O(1) 定数時間
    • ハッシュテーブルを利用したインデックスアクセスが該当する
    • 入力がどんなに膨大でも費やす時間は固定
    • この中では最も高速
  • O(log n ) 対数時間
    • 二分探索などのアルゴリズムが該当する
    • nの対数に比例した時間を必要とする
    • この中では2番目に高速
  • O(n) 線形時間
    • 配列を順に走査するような単純探索などのアルゴリズム
    • nに直接比例した時間を費やす
    • 対数時間に次いで高速
  • O(n × log n) 線形時間と対数時間を掛け合わせたもの
    • クイックソートのような高速なソートアルゴリズムがある
    • データ量が増えると徐々に計算時間が増えていく
    • 線形時間に次いで高速
  • O(n2) 多項式時間
    • 選択ソートといった低速なアルゴリズムがある
    • O(n × log n)以上にデータ量が増えると計算時間の増加が大きい
    • この中では階乗時間に次いで低速
  • O(n!) 指数関数時間
    • 巡回セールスマン問題のような総当りによる非常に低速なアルゴリズム
    • 階乗時間の問題は厳密解を出すのが難しいので、後述する貪欲法のような近似アルゴリズムで大域的最適解を出すことが現実的
    • この中では最も低速なアルゴリズムとなる

配列とリンクリストとハッシュテーブル

配列

配列を使うとすべての要素がメモリ上に連続的に格納されることになる。配列は宣言時に必要な要素分のメモリを事前に確保しておく。そのため宣言した要素数以上のアイテムを格納するときに連続的にメモリを用意できず、すべてのアイテムを別メモリにあらためて格納し直す可能性もある。その場合には配列の格納し直しの分、処理に時間が掛かる。また、必要以上にメモリを用意しておくと、使用しない部分のメモリが無駄になってしまうことになる。

配列はリンクリストと異なり要素の挿入は苦手だが、メモリ上に連続的にアイテムが用意されているのがわかっているので、配列から要素をランダムに読み取りたい場合には高速に処理できる。

リンクリスト

リンクリストはアイテムをメモリ内のどこにでも配置することができる。リンクリストの要素はそれぞれ次の要素のアドレスを格納している。そのためリンクリストは配列のようにメモリ上に連続的に要素を確保しておく必要は無いし宣言時に要素数を決める必要は無い。

リンクリストは配列と異なり要素が隣接していないため、メモリ内のN番目の要素に瞬時にアクセスするということはできないが、リスト内に要素を追加することは配列と比べると高速に処理できる。

ハッシュテーブル

ハッシュテーブルはハッシュ関数を用いて予め用意してあるマッピングテーブルに値を格納する手法である。

ハッシュ関数は文字列(バイトシーケンス)を渡すと数字を返す関数のこと。同じ文字列を渡すとハッシュ関数は毎回同じ値を返し、渡す値を少し変えただけでハッシュ関数の戻り値は大きく変わる。

ハッシュテーブルには衝突という概念がある。ハッシュ関数で得られた値のインデックスに既に他の文字列がある場合、マッピングテーブルに格納してあった文字列が上書きされてしまうことになる。

ハッシュ関数に与えた先頭文字列によって格納するマッピングテーブルを例にすると下記のようになる。

ハッシュテーブルのインデックス 格納されている値
A Apple
B Banana
C
D Durian

このマッピングテーブルに文字列「Coconut」をハッシュ関数を使って格納すると次のようになる。

ハッシュテーブルのインデックス 格納されている値
A Apple
B Banana
C Coconut
D Durian

さらにこのマッピングテーブルに文字列「Apricot」をハッシュ関数を使って格納すると次のようになる。

ハッシュテーブルのインデックス 格納されている値
A Apricot
B Banana
C Coconut
D Durian

ハッシュテーブルのインデックス「A」にあった「Apple」が「Apricot」に上書きされてしまう。

しかし、十分なハッシュテーブルのインデックスを用意することは難しいので、実際にはハッシュテーブルの各インデックスにリンクリストを用いるような手法が使われる。

ハッシュテーブルのインデックス 格納されている値
A (Apple, Apricot)
B (Banana)
C (Coconut)
D (Durian)

その場合には、インデックス「A」には「Apple」と「Apricot」のリンクリストが格納されることになる。

良いハッシュ関数の条件は下記の通り。

  • ハッシュ関数は配列の大きさを把握しており、有効なインデックスを返す
    • マッピングテーブルの要素数が10しかないのにハッシュ関数が1000 を返しても格納する場所が無い
  • 各インデックスにリンクリストを格納する場合、ハッシュ関数の戻り値が各インデックスに均等に分散されること

ハッシュテーブルは平均的なケースでは検索・挿入・削除すべてが定数時間となり、配列とリンクリストのいいとこ取りであるが、最悪のケースでは検索・挿入・削除すべてが線形時間となる。ハッシュテーブルを使うときは最悪のパフォーマンスとならないように「衝突」を回避する必要がある。

とはいえ、大抵のプログラミング言語に実装されているハッシュ関数は、平均的な時間(定数時間)で処理を行えることが多い。

処理 ハッシュテーブル
(平均)
ハッシュテーブル
(最悪)
配列 リンクリスト
検索 O(1) O(n) O(1) O(n)
挿入 O(1) O(n) O(n) O(1)
削除 O(1) O(n) O(n) O(1)