なにこれ
最近、OpenDataStructuresを読んで、データ構造を勉強しています。
「みんなのデータ構造」という和訳された書籍もありますが、日本語のPDFが無料で読めるので、そちらを利用しています。
今回は、第2章のListインターフェースを実装した5つのデータ構造についてまとめます。
- ArrayStack
- ArrayQueue
- ArrayDeque
- DualArrayDeque
- RootishArrayStack
またコードはpythonで実装しており、こちらを参考にしています。 github.com
インターフェースと実装
データ構造を理解するうえで、インターフェースと実装の違いをはっきりさせる必要があります。
- インターフェースとは、データに対する操作一式をその操作に対する引数・返り値を定義したもの
- 実装とは、そのインターフェースを実現させるための内部表現のこと
Queue, Stack, Deque, Listインターフェース
いずれもデータを連鎖的に保持するためのデータ構造ですが、データ取り出し規則が異なります。
Queueのデータ取り出し規則はFIFO(first-in first-out)です。
Stackのデータ取り出し規則はLIFO(last-in first-out)です。
Dequeはデータの取り出し規則を一般化し、先頭・末尾両方に対して追加・削除ができるものです。
これら3つをまとめたものがListインターフェースです。
例えばArrayStackはListインターフェースと同時に、Stackインターフェースを実装しているわけです。
5つのデータ構造
第2章のタイトルが、「配列を使ったリスト」となっているように、5つのデータ構造は、backing arrayを基本としています。 backing arrayは、自動では伸び縮みしない単なる配列として解釈すればいいと思います。
ArrayStack
- getやsetなどは、そのままindexの値を取ってくればよい。
- すなわちO(1)
- addやremoveなどでbacking arrayサイズに過不足がある場合は、backing arrayをresizeする（サイズを変えたbacking arrayを用意して、既存のbacking arrayの値を全て移す）
- addやremoveはindex以降の値を全て移して、値を追加したり削除したりする
- すなわちO(n-i)
ArrayQueue
Queueを実装するにはArrayStackは好ましくないです。 FIFOに従って先頭を取り出すと、常にO(n-i)がかかるからです。 そこでbacking arrayに入っている先頭のインデックスを常に保持し、たとえ値を削除したとしても、全ての値を移さないことを考えます。
- removeで先頭を取り出すときは、保持している先頭のインデックスを取り出せばよい
- addで末尾に追加するときは、「保持しているインデックス + backing arrayに入っている要素の数」をbacking arrayの長さで剰余演算したインデックスに追加する
ArrayDeque
ArrayQueueを一般化し、どこにでもadd・どこからでもremoveできるようにします。
- ArrayStackではaddやremoveをした時に常に先頭に詰めていましたが、先頭のインデックスを保持することで、先頭に近い値をどうにかするなら末尾に詰めるし、末尾に近い値をどうにかするなら先頭に詰めるようにする
- すなわちO(n-i)ではなく、O(min{i, n-i})で処理できるようになる
DualArrayDeque
ArrayStackは末尾の方を変更するときにO(n)に近い性能しか出ません。 そこでArrayStackを鏡合わせで2つ作り、その2つにバランスよく値を詰めることで、O(min{i, n-i})で変更できるようにします。
RootishArrayStack
今までの4つのデータ構造の共通の欠点として、backing arrayに空きが多いことが挙げられます。 上記ではまとめていないのだが、addやremoveのたびにbacking arrayのサイズを確認し、サイズに過不足がbacking arrayのresizeを行なっています。 不足があった場合に行うresizeでは、サイズnをサイズ2nに増やすので、半分が空っぽの状態です。
そこで、保持する値の数を1つずつ増やしたようなArrayStackを複数保持するような実装を考えます。
重要なのは、アクセスしようとした値が何番目のArrayStackに保持されているかですが、これは一意に求めることができます。(ここでは省略します...）