· 開発

配列の末尾への追加はなぜ O(1) なのか：動的配列と償却計算量

満杯になると全要素をコピーすることがあるのに append が O(1) とされる理由を、容量と償却解析で説明し、Java・C++・Rust・Go のドキュメントが保証する範囲と実装が決める増加率、容量を先に確保する方法をまとめました。

開発アルゴリズムデータ構造

Python の list.append、Java の ArrayList.add、C++ の vector::push_back、Rust の Vec::push は、どれも「末尾に1つ追加するのは O(1)」と説明されます。しかしこれらは要素を連続した配列1つに格納していて、配列が満杯になると、より大きな格納領域を確保します。その際、新しい配列を用意して格納済みの値をすべて移すことがあります。Python と Java の配列に入っているのはオブジェクトそのものではなく参照なので、移るのは参照です。ときどき n 個を移すのに O(1) と呼べるのは、この O(1) が償却（amortized）O(1) だからです。

サイズと容量

動的配列は2つの数を別々に管理しています。いま入っている要素数（サイズ）と、再確保せずに格納できる数（容量）です。Java の ArrayList のドキュメントは、容量を要素を格納する配列のサイズと説明し、容量は常にリストのサイズ以上だと書いています。

サイズが容量より小さければ、追加は空いている位置に値を書くだけで終わります。サイズが容量と等しいときは格納領域を広げる必要があり、新しい配列を確保して値を移すことがあります。Rust の Vec::push のドキュメントは、再確保が必要な場合に容量に比例する O(capacity) の時間がかかると書いています。

償却 O(1) の計算

空の配列から始めて、満杯になるたびに容量を2倍にするとします。1、2、4、8…個で満杯になるたびにコピーが起きるので、n 回追加する間に移す要素数は 1 + 2 + 4 + … で、この合計は 2n より小さくなります。総コストが n に比例するので、1回あたりの平均コストは定数です。この平均は入力がランダムだという仮定から出たものではありません。空の配列から n 回追加すれば、何を追加しても総コストが n に比例する、という意味です。すでに満杯の大きな配列から数え始めると最初の1回だけで大きなコストがかかりうるので、この計算は空の配列から始める場合を前提にしています。

重要なのは増やし方です。新しい容量を max(1, ceil(r × 元の容量)) のように定めて必ず増やす規則で、r が1より大きい固定値なら、コピー量は等比数列の和なので n に比例します。たとえば r を1.5にできます。一方、毎回10個ずつ足す方式ではコピー量が n² に比例します。次のコードで空の配列に100万個を追加する場合を数えると、2倍ではコピー 1,048,575 回（最初の確保を含む確保・拡張21回）、10個ずつでは 49,999,500,000 回（確保・拡張10万回）になります。

def count_copies(n, grow):
    cap = size = copies = 0
    for _ in range(n):
        if size == cap:
            copies += size
            cap = grow(cap)
        size += 1
    return copies

count_copies(10**6, lambda c: max(1, c * 2))  # 1048575
count_copies(10**6, lambda c: c + 10)         # 49999500000

ドキュメントが保証することと実装が決めること

公式ドキュメントや仕様の多くは結果だけを約束し、増加率は決めていません。

  • Java ArrayList：要素の追加が償却定数時間のコストを持つこと以外、増加ポリシーは規定しないと書いています。
  • C++ 規格の公開ワーキングドラフト：vector の push_back などの操作は償却定数時間で実装するよう求めています。倍率は定めていません。
  • Rust Vec：特定の増加戦略は保証しないが、どの戦略でも push の償却 O(1) は保証すると書いています。
  • Go の仕様：容量が足りなければ append は十分な大きさの新しい配列を確保する、とだけ述べています。

実際の倍率は実装が決めます。CPython 3.13 の list_resize は、1つずつ追加する場合、新しいサイズにその 1/8 と 6 を足して4の倍数にそろえます。ソースのコメントには 0, 4, 8, 16, 24, 32, 40, 52, 64, 76… という増え方が書かれています。ただし extend のように一度に大きく増やし、新しいサイズと以前のサイズの差が、計算上の確保容量と新しいサイズの差より大きいときは、余分を取らず新しいサイズを4の倍数に切り上げた分だけ確保します。通常の GIL 有効ビルドでは realloc でサイズを変えるため、アロケータがその場で領域を広げられればコピーは起きません。free-threaded ビルドは新しい配列を確保してコピーします。OpenJDK 21 の ArrayList は元の容量の半分を希望する増加量として渡すため、1つずつ追加する場合、通常のサイズでは容量が約1.5倍になります。どちらもバージョンによって変わりうる内部実装なので、コードがこの数値に依存してはいけません。

償却 O(1) の限界

償却 O(1) は、1回ごとの呼び出しが速いという保証ではありません。格納領域を広げる際に新しい配列を確保して値をコピーまたは移動すると、最悪の場合は要素数に比例する時間がかかります。そのため、応答時間の最大値が重要なコードでは、ときどき突出した遅延が出ることがあります。

新しい格納領域を確保する拡張は、要素の位置も変えます。C++ 規格のドラフトは、再確保によって要素を指す参照・ポインタ・イテレータがすべて無効になると定めています。Go では、容量が足りれば append は既存の配列を再利用し、足りなければ新しい配列を確保するので、返されたスライスを受け取って使う必要があります。

要素数が前もって分かるとき

追加する要素数がおおよそ分かっていれば、先に容量を確保して再確保の回数を減らせます。C++ の reserve、Java の ensureCapacity、Rust の with_capacity と reserve がその役割です。保証の強さは異なります。C++ 規格のドラフトは reserve の後、サイズが容量を超えるまで挿入中に再確保が起きないとしていますが、Java のドキュメントは ensureCapacity で再確保を減らせる可能性がある、と述べるだけです。

ソートについては安定ソートの記事もどうぞ。

参照した仕様とドキュメント

ブログへ