エンジニア実践的基礎: 固定長配列

背景

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

固定長配列とは

固定長配列とは配列の長さが固定された配列のことです。配列は複数の値を格納でき、実務でも最も使用頻度が高いデータ構造の一つです。

参照・追加・削除別に計算量を確認します。

参照

固定長配列の参照の計算量 O(1) です。O(1) とは入力のサイズに関わらず、操作回数が常に一定という意味です。一方で、計算量が O(n) の場合は、入力に応じて線形的に操作回数が増えます。計算量では極端に大きな入力を仮定します。そのため、どんな入力に対しても計算量が定数な配列の参照は効率が良いです。

配列の要素はインデックスで参照します。インデックスは0から始まる数字で、RAM 上のアドレスに紐づいています。アドレスは値に紐づいているため、インデックスがわかれば、すぐに値を参照できます。これが配列の参照が O(1) である理由です。

# Python サンプル

# 1,3,5 の３つの要素を持つ配列を初期化
nums = [1,3,5]

# 1番目の要素をインデックス0で参照
nums[0]

削除

削除対象の要素の位置によって削除の計算量が異なります。最後の要素を削除する場合、計算量は O(1) になります。一方で、それ以外の要素を削除する場合は、計算量は O(n) になります。n は配列の長さです。

計算量は最悪のケースで定義されます。固定長配列の削除の最悪ケースは最初の要素を削除する場合です。なぜなら、2番目の要素から最後の要素までを順に左にシフトする必要があるからです。つまり、最悪で n - 1 回の操作が必要です。計算量では最も影響のある変数以外は無視するので、O(n-1) ではなく、O(n) になります。

def remove(arr, i, length):
    # i + 1 以降を左にシフトして値を上書きする
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]

挿入

削除同様に最後の位置にへの挿入は O(1) です。最後の要素以外は挿入位置以降の要素を右にシフトします。計算量は O(n) です。

削除と異なるのは、固定長配列の長さ以上に値を挿入できないことです。長さに関係なく値を追加できる動的配列もあります。それは別の記事で解説します。ちなみに Python の配列はデフォルトで動的配列です。

def insert(arr, i, n, length):
    # 右にシフト
    for index in range(length - 1, i - 1, -1):
        arr[index + 1] = arr[index]
    
    # i 番目に挿入
    arr[i] = n

まとめ