配列

Contents

配列#

配列（Array） は、同じ型の要素をメモリ上に連続して並べたデータ構造。

要素はメモリ上で連続して配置される
インデックスで任意の要素に \(O(1)\) でアクセスできる
固定長（静的配列）と可変長（動的配列）がある

計算量#

操作	計算量	備考
アクセス `a[i]`	\(O(1)\)	メモリアドレスの計算で直接参照
末尾への追加（動的配列）	平均 \(O(1)\)	容量不足時は \(O(n)\) の再確保
先頭・途中への挿入	\(O(n)\)	シフトが必要
先頭・途中からの削除	\(O(n)\)	シフトが必要
線形探索	\(O(n)\)
二分探索（ソート済み）	\(O(\log n)\)

Python の `array` モジュール#

array.array は、C言語の配列に近い型付き配列を提供する。

全要素が同じ型（C言語の数値型）でなければならない
list よりメモリ効率が良い（Pythonオブジェクトのオーバーヘッドなし）
数値の大量処理に向いているが、numpy ほど高機能ではない

主な型コード：

型コード	C 型	Python 型	サイズ
`'b'`	signed char	int	1 byte
`'i'`	signed int	int	2〜4 bytes
`'f'`	float	float	4 bytes
`'d'`	double	float	8 bytes

import array
import sys

# array.array の使用例
arr = array.array('i', [1, 2, 3, 4, 5])  # 'i' は signed int
print(arr)       # array('i', [1, 2, 3, 4, 5])
print(arr[2])    # 3

arr.append(6)
print(arr)       # array('i', [1, 2, 3, 4, 5, 6])

# list とのメモリ使用量の比較
lst = list(range(1000))
arr2 = array.array('i', range(1000))
print(f"list:  {sys.getsizeof(lst)} bytes")
print(f"array: {sys.getsizeof(arr2)} bytes")

array('i', [1, 2, 3, 4, 5])
3
array('i', [1, 2, 3, 4, 5, 6])
list:  8056 bytes
array: 4200 bytes

Python の `list`#

Python の list は動的配列（dynamic array） として実装されている。

要素はメモリ上に連続して配置される（各要素はPythonオブジェクトへのポインタ）
容量が不足すると、より大きいメモリ領域を確保して全要素をコピーする
append は平均 \(O(1)\) （\(O(n)\)だがたまにしか発生しないので平均は低い）
insert(0, x) は \(O(n)\)
異なる型の要素を混在できる

lst = [1, 2, 3, 4, 5]

# インデックスアクセス O(1)
print(lst[2])       # 3
print(lst[-1])      # 5（末尾）

# スライス O(k)
print(lst[1:3])     # [2, 3]

# 末尾への追加 O(1) 平均
lst.append(6)
print(lst)          # [1, 2, 3, 4, 5, 6]

# 末尾からの削除 O(1)
lst.pop()
print(lst)          # [1, 2, 3, 4, 5]

# 途中への挿入 O(n)
lst.insert(2, 99)
print(lst)          # [1, 2, 99, 3, 4, 5]

# 途中からの削除 O(n)
lst.pop(2)
print(lst)          # [1, 2, 3, 4, 5]

# 線形探索 O(n)
print(3 in lst)     # True
print(lst.index(3)) # 2

3
5
[2, 3]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5]
[1, 2, 99, 3, 4, 5]
[1, 2, 3, 4, 5]
True
2

動的配列の成長戦略#

CPythonの list は容量不足時に現在のサイズの約1.125倍（+ α）に拡張する。拡張時に全要素をコピーするため \(O(n)\) かかるが、拡張の頻度が指数的に減るため、 append の 償却計算量 （amortized time complexity、平均でみたとき）は \(O(1)\) になる。

import sys

# list の内部的な容量確認（拡張のタイミングを観察する）
lst = []
prev_size = sys.getsizeof(lst)
print(f"要素数  0: {prev_size} bytes")

for i in range(20):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev_size:
        print(f"要素数 {i+1:2d}: {size} bytes（容量拡張）")
        prev_size = size

要素数  0: 56 bytes
要素数  1: 88 bytes（容量拡張）
要素数  5: 120 bytes（容量拡張）
要素数  9: 184 bytes（容量拡張）
要素数 17: 248 bytes（容量拡張）

`list` vs `array` vs `numpy.ndarray`#

特性	`list`	`array.array`	`numpy.ndarray`
要素の型	任意（混在可）	同一の数値型	同一の数値型
メモリ効率	低い	高い	高い
数値演算速度	遅い	やや遅い	速い（ベクトル化）
多次元配列	不可（ネスト）	不可	可
用途	汎用コレクション	数値の省メモリ保存	数値計算・科学計算