エンジニア実践的基礎: 動的配列

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

動的配列とは

動的配列は長さが可変の配列です。固定長配列と異なり、初期化時に長さを指定する必要がありません。要素数が予測できない場合に重宝します。デフォルトの配列が動的配列のプログラミング言語もあります。代表的なのは JavaScript や Python です。

メカニズム

動的配列も実は固定長配列から構成されます。固定長配列は初期化時に長さが決まっているので、挿入できる要素数に上限があります。長さを動的にするために、要素が満杯になったら長さを2倍にした新しい固定長配列を作成し、古い配列から要素をコピーします。数学的に動的配列の挿入は O(1) とされています。

なぜ O(1) なのでしょうか？確かに、配列が一杯になったときに要素数分のコピーが発生します。n 個の要素があれば n 回のコピーが必要になります。しかし、要素数を2倍にすることで、コピーの操作は滅多に起きなくなります。

具体的には、n個の要素を挿入する場合、リサイズ操作の回数は log n 回程度です。例えば、次のような計算をします：

1. 配列サイズが1から2に倍増するまでに1回のコピー。

2. 配列サイズが2から4に倍増するまでに2回のコピー。

3. 配列サイズが4から8に倍増するまでに4回のコピー。

このように、最後のリサイズまでに行ったコピー操作の回数は 1+2+4+...+n/21 + 2 + 4 + ... + n/21+2+4+...+n/2 であり、この和は 2n - 1 になります。

稀に起きる操作は平均で計算量を算出します。(2n - 1) / n  = 1 - 1/n で、計算量はO(1) となります。

基本の固定長配列にサイズ変更のアルゴリズムを加えることで動的配列を実現します。このようなデータ構造は今後も出てくるので、データ構造とアルゴリズムは密接な関係であることを覚えてください。

Python はデフォルトで動的配列ですが、あえて実装すると次のようになります。※クラスから重要な関数だけ抜粋しています。

def insert(self, n):
    # 一杯になったのでリサイズ
    if self.length == self.capacity:
        self.resize()
    
    # 要素を挿入
    self.arr[self.length] = n
    self.length += 1

def resize(self):
   
   self.capacity = 2 * self.capacity
   newArr = [0] * self.capacity 

   # 古い配列から新しい配列へコピー
   for i in range(self.length):
       newArr[i] = self.arr[i]
   self.arr = newArr

まとめ

削除、参照の計算量は固定長配列と同じく O(1) です。