『なっとく! アルゴリズム』メモその２ リスト・ハッシュテーブル
『なっとく! アルゴリズム』を読んで並行して勉強したことをメモしておく。
- 作者: アディティア・Y・バーガバ,株式会社クイープ
- 出版社/メーカー: 翔泳社
- 発売日: 2017/02/01
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
配列
配列を定義するときはその配列の要素分メモリを確保することになる。
初心者に説明するときには大体箱で説明すると思う。
大きな箱１つの中に小さい箱5個あって、そこに必要なアイテムものを入れていくと思うんだけど最初に5個定義したときに、以下の問題が発生する。
- 箱が5個あるが入れるアイテムが1つしかない
- 箱が5個あるが入れるアイテムが6つある
- 箱が5個あってアイテムが3つある場合、１つめと2つ目の間にアイテムを挿入したい
- 箱が5個あってアイテムが3つある場合、2つ目の間を削除したい
メモリに確保する要素の数の問題
要素数に対して格納される値が少ない場合は、メモリに確保している数がもったいない。
要素数に対して格納される値が少ない場合は、要素数を増やす必要がある。
しかし、その増やすべき要素数が分からない場合その対応を何回すればいいのだという問題がある。
これの対応としては配列の動的確保である。
前述の例では、プログラム中で宣言時に指定した固定のサイズ（整数定数）による配列確保（静的確保）であった。実用的には、配列の要素数が宣言時（あるいはコンパイル時）に静的に決まってしまうよりも、実行時に要素数を動的に指定して配列を確保できたほうが便利なことがある。例えば、縦横任意サイズの画像ファイルから全画素情報を読み出す場合や、コンピュータで利用可能な空きメモリ量に合わせて扱うデータ個数上限を変化させたい場合などである。
配列 - Wikipedia
要素間のデータの検索
ビッグオー記法ではにあたる。
配列の特徴としてランダムアクセスが可能、つまりアイテム2を取ってくるにあたって直接アイテム1は確認しなくてよいということ。
要素間のデータの挿入・削除
ビッグオー記法ではにあたる。これはデータの挿入も削除も同じ。
箱にあるアイテムを追加したり削除したりするのはいつも一番最後とは限らない。アイテム間のアイテムを削除したいときもある。
その場合、間に入れたらその次の要素を隣にずらしていかなければらないが、それって単純にはできない。
アイテム2とアイテム3の間を挿入したいとして、単純検索としてアイテム1～アイテム5まで順番に確認していって、アイテム2とアイテム3の間にアイテム2´をセットしなければならんから。
リンクリスト
リンクリスト要素と要素でつながりがあるリストになる。
例えるのであれば食堂で、「食券を買う」→「食券を渡す」→「注文したものを受け取る」→「皿を返却する」のこの流れ。
リンクリストの特徴として、事前にメモリを確保しなくてもよい点、要素の追加削除が用意、シーケンシャルアクセスである。
データ同士が参照する関係
データ同士は独立している。配列でいう大きな箱に入っていない状態となる。
要素の順番ではなくて、データが次のデータ（ノード）へのリンクを含んでいるので、メモリを事前に確保する必要がない。
処理の終わりはNULLで定義される。
「食券を買う」(次は食券を渡す)→「食券を渡す」(次は注文したものを受け取る)→「注文したものを受け取る」(次は皿を返却する)→「皿を返却する」(NULL)
要素間のデータの検索
ビッグオー記法ではにあたる。
シーケンシャルアクセルが特徴と上で記載した通り、値を取ってきたい場合は先頭から順番に見ていかなければならない。
「食券を渡す」を取ってきたい場合、まずは食券を買わなければならない。
要素間のデータの挿入・削除
ビッグオー記法ではにあたる。これはデータの挿入も削除も同じ。
配列と違うのは単純検索としてアイテム1～アイテム5まで順番に確認する必要がないという点。
食券を渡した後「水を汲む」という動作を入れる場合、
「食券を買う」(次は食券を渡す)→「食券を渡す」(次は注文したものを受け取る)→「注文したものを受け取る」(次は皿を返却する)→「皿を返却する」(NULL)
↓「食券を買う」(次は食券を渡す)→「食券を渡す」(次は水をくむ)→「水を汲む」(次は注文したものを受け取る)→「注文したものを受け取る」(次は皿を返却する)→「皿を返却する」(NULL)
となる。
ハッシュテーブル
key:value型のテーブル構成のこと。ハッシュ関数を使用する。
ハッシュ関数は文字列を渡すと数値を返却する関数のこと。以下みたいな感じ
| ハッシュ(インデックス) | key | value |
|---|---|---|
| 1 | apple | red |
| 2 | banana | yellow |
| 5 | egg | white |
key:value型であればkey=ハッシュなんじゃないのかって思ったけど、上の数値、つまりハッシュ関数はインデックスのことを指す。
appleであれば、1,apple:red
bananaであれば、2,banana:yellow
こんな感じでインデックスを持っていてインデックス順に並んでいる。
ハッシュ関数の特徴として
上のapple、banana、eggのケースで考えると、この3つの要素は必ず同じインデックスである。2回目と3回目でインデックス番号は変化しない。
この場合3つしか要素がないので、ハッシュ関数で100は返さない。有効なものだけ返す。
インデックス採番の落とし穴
これだけだとあたかも簡単そうな感じだが、インデックス番号の振り方に１つ問題がある。
apple、banana、eggのインデックス番号の振り方を先頭1文字の英字からとってこようとした場合、avocadosがappleと同じインデックスになってしまう問題。
| ハッシュ(インデックス) | key | value |
|---|---|---|
| 1 | apple | red |
| 1 | avocados | green |
| 2 | banana | yellow |
| 5 | egg | white |
そうしたときに、appleは赤だが、avocadosは緑として更新すると、appleをkeyとして取得したときにgreenという全然違う値が取得されてしまう問題が発生する。
それを衝突という。
要素間のデータの検索・挿入・削除
ビッグオー記法では平均時間計算量としてはにあたる。
最悪時間計算量としてはとなる。
これはデータの挿入も削除も同じ。
ハッシュテーブルの特徴として1つのハッシュ関数を使用して値を取得する場合は処理がものすごく速い。
keyを指定指定してあげることでハッシュを通してvalueが出力できるから。
ただし、最悪時間計算量にも記載の通り、ハッシュテーブルは必ずしも早いわけではない。
ハッシュテーブルは順序保証がないという弱点を持っているから。
順序保障がないというのはどういうことかというと、プログラム上でハッシュテーブルに追加した順番と、メモリ上で持っている順番が必ずしもイコールであるとは限らないということ。
プログラム上、apple→avocados→banana→eggの順番で実装したとしてなんとなく上記順番でメモリに格納されているのではないかと思っている。
ただ実際のハッシュは以下になっている。
| ハッシュ(インデックス) | key | value |
|---|---|---|
| 1 | apple | red |
| 2 | banana | yellow |
| 5 | egg | white |
| 6 | avocados | green |
だからavocadosの値を取ってくるときにkeyで指定せずに単純検索、つまりforループで順番に取ってきた場合に要素2にあると思い込んでいると、実は要素4にあったので処理に時間がかかったという状況になる。
Pythonでのリスト・ハッシュリストのビッグオー記法
Pythonで実装する上でのパフォーマンスを知るためにも各型別の時間計算量をメモした。
順序保障はハッシュテーブルに記載している通り、要素を追加したときの順番をちゃんと守っているのか。
要素指定はひとつの値を取ってくるのに明示的に指定することができるか（リスト型なら要素番号、ハッシュテーブルならkey）。
要素変更は要素の追加・削除ができるか。
なお、辞書型で順序保障がされていない問題についてはPython3.7で解消された模様。
dict オブジェクトの挿入順序を保存するという性質が、公式に Python 言語仕様の一部であると 宣言されました 。
What's New In Python 3.7 — Python 3.7.2 ドキュメント
