動的配列 (Dynamic Arrays)

2025-08-17

動的配列の学習ノート

PythonとJavaScriptのリストって実は「動的配列」だったんだ！サイズが自動で増えるのを「当たり前」と思ってたけど、裏側の仕組みを知って感動した。

動的配列とは

静的配列と違って、要素を追加していくと自動でサイズが増える配列。JavaScriptとPythonではこれがデフォルト。

# Pythonのリストは動的配列
arr = []  # サイズ指定不要！
arr.append(1)
arr.append(2)
arr.append(3)  # 勝手に増える

でも魔法じゃない。実は裏でリサイズという処理が動いてる。

動的配列の実装

class DynamicArray:
    def __init__(self):
        self.capacity = 1  # 初期容量
        self.length = 0    # 実際の要素数
        self.data = [None] * self.capacity
    
    def __len__(self):
        return self.length
    
    def __getitem__(self, index):
        if 0 <= index < self.length:
            return self.data[index]
        raise IndexError("Index out of range")

末尾への挿入（pushback） - O(1) amortized

def append(self, value):
    # 容量が足りない場合はリサイズ
    if self.length == self.capacity:
        self._resize()
    
    # 末尾に挿入
    self.data[self.length] = value
    self.length += 1

def _resize(self):
    # 容量を2倍にする（これが重要！）
    self.capacity = 2 * self.capacity
    new_data = [None] * self.capacity
    
    # 既存のデータをコピー
    for i in range(self.length):
        new_data[i] = self.data[i]
    
    self.data = new_data

なぜ容量を2倍にするのか？

最初これがわからなかった。1.5倍とか、+10とかじゃダメなの？

# 容量の増え方：1 → 2 → 4 → 8 → 16 → 32...

# n個の要素を追加するまでのコピー回数を計算
def calculate_operations(n):
    operations = 0
    capacity = 1
    
    while capacity < n:
        operations += capacity  # リサイズ時のコピー回数
        capacity *= 2
    
    operations += n  # 各要素の挿入
    return operations

# 例：8個の要素を追加
# リサイズ: 1 + 2 + 4 = 7回のコピー
# 挿入: 8回
# 合計: 15回の操作

重要な発見：

最後の項（8）が、それまでの全ての項の和（1+2+4=7）より大きい
だから合計操作数は最大でも 2n
つまり、n個追加するのに O(n) → 1個あたり O(1) amortized！

償却時間計算量（Amortized Time）って何？

最初「amortized」って何？って思った。

# 通常の追加：O(1)
arr.append(5)  # 空きがあれば一瞬

# リサイズが発生する追加：O(n)
arr.append(9)  # 満杯だったら全要素コピー

# でも平均すると：O(1) amortized
# なぜなら、リサイズは時々しか起きないから

視覚的に理解する

容量1: [1]           → 満杯
容量2: [1,2]         → 満杯（1回コピー）
容量4: [1,2,3,4]     → 満杯（2回コピー）
容量8: [1,2,3,4,5,6,7,8] → 満杯（4回コピー）

8個追加するのに: 1+2+4 = 7回のコピー + 8回の挿入 = 15回
15回 ÷ 8個 = 約1.9回/個 → O(1)!

完全な動的配列の実装

class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.length = 0
        self.data = [None] * self.capacity
    
    def append(self, value):
        """末尾に要素を追加 O(1) amortized"""
        if self.length == self.capacity:
            self._resize()
        
        self.data[self.length] = value
        self.length += 1
    
    def pop(self):
        """末尾から要素を削除 O(1)"""
        if self.length == 0:
            raise IndexError("Pop from empty array")
        
        self.length -= 1
        value = self.data[self.length]
        self.data[self.length] = None  # メモリクリア
        
        # オプション：配列が1/4になったら縮小
        if self.length > 0 and self.length == self.capacity // 4:
            self._shrink()
        
        return value
    
    def insert(self, index, value):
        """任意の位置に挿入 O(n)"""
        if index < 0 or index > self.length:
            raise IndexError("Index out of range")
        
        if self.length == self.capacity:
            self._resize()
        
        # 要素を右にシフト
        for i in range(self.length, index, -1):
            self.data[i] = self.data[i - 1]
        
        self.data[index] = value
        self.length += 1
    
    def remove(self, index):
        """任意の位置から削除 O(n)"""
        if index < 0 or index >= self.length:
            raise IndexError("Index out of range")
        
        value = self.data[index]
        
        # 要素を左にシフト
        for i in range(index, self.length - 1):
            self.data[i] = self.data[i + 1]
        
        self.length -= 1
        self.data[self.length] = None
        
        return value
    
    def _resize(self):
        """容量を2倍に拡張"""
        self.capacity *= 2
        new_data = [None] * self.capacity
        
        for i in range(self.length):
            new_data[i] = self.data[i]
        
        self.data = new_data
    
    def _shrink(self):
        """容量を半分に縮小"""
        self.capacity //= 2
        new_data = [None] * self.capacity
        
        for i in range(self.length):
            new_data[i] = self.data[i]
        
        self.data = new_data
    
    def __str__(self):
        return str([self.data[i] for i in range(self.length)])

Pythonのlistの裏側

import sys

# Pythonのリストがどう成長するか観察
arr = []
old_capacity = 0

for i in range(20):
    arr.append(i)
    # sys.getsizeofでバイト数を取得
    current_size = sys.getsizeof(arr)
    
    if current_size != old_capacity:
        print(f"要素数: {len(arr)}, サイズ: {current_size}バイト")
        old_capacity = current_size

# 出力例：
# 要素数: 1, サイズ: 88バイト
# 要素数: 5, サイズ: 120バイト  ← 容量増加
# 要素数: 9, サイズ: 184バイト  ← 容量増加
# ...

時間計算量まとめ

操作	時間計算量	備考
アクセス	O(1)	インデックスアクセス
末尾に追加	O(1)*	amortized（償却）
末尾から削除	O(1)	簡単
中間に挿入	O(n)	シフトが必要
中間から削除	O(n)	シフトが必要

*リサイズ時は O(n) だが、平均すると O(1)

よくある間違い・気づき

1. リサイズを1ずつ増やしたら？

# ダメな例：容量を1ずつ増やす
def bad_resize(self):
    self.capacity += 1  # これだとO(n²)になる！
    # n個追加するのに: 1+2+3+...+n = n(n+1)/2 = O(n²)

2. なぜ1.5倍じゃなくて2倍？

# 1.5倍でも動くけど...
self.capacity = int(self.capacity * 1.5)

# 2倍の利点：
# - 計算が簡単（ビットシフトで済む）
# - メモリアロケータと相性が良い
# - 数学的に美しい（等比数列）

3. 縮小も必要？

# 要素を削除し続けると無駄なメモリが...
arr = [1,2,3,...,1000000]  # 100万要素
for _ in range(999999):
    arr.pop()  # 1個だけ残る
# メモリは100万要素分確保されたまま！

# 解決策：1/4になったら半分に縮小
if self.length <= self.capacity // 4:
    self._shrink()

実践での使い方

# スタックとして使う
stack = []
stack.append(1)  # push
stack.append(2)
value = stack.pop()  # pop

# キューとして使う（効率は悪い）
queue = []
queue.append(1)  # enqueue
queue.append(2)
value = queue.pop(0)  # dequeue (O(n)なので非効率)

# より良い方法：collections.deque
from collections import deque
queue = deque()
queue.append(1)  # O(1)
queue.popleft()  # O(1)

まとめ

動的配列は自動でサイズが増える便利な配列
裏では2倍リサイズが起きてる
追加はO(1) amortized（平均的に高速）
メモリと速度のトレードオフ（未使用領域を持つ代わりに高速）
PythonやJavaScriptの配列はこの仕組み

次はスタックについて学んだことをまとめる

Tags: 配列動的配列リサイズ