配列（Array） は、同じ型の要素をメモリ上に連続して並べたデータ構造。
要素はメモリ上で連続して配置される
インデックスで任意の要素に でアクセスできる
固定長（静的配列）と可変長（動的配列）がある
計算量¶
| 操作 | 計算量 | 備考 |
|---|---|---|
アクセス a[i] | メモリアドレスの計算で直接参照 | |
| 末尾への追加（動的配列） | 平均 | 容量不足時は の再確保 |
| 先頭・途中への挿入 | シフトが必要 | |
| 先頭・途中からの削除 | シフトが必要 | |
| 線形探索 | ||
| 二分探索（ソート済み） |
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")Python の list¶
Python の list は動的配列（dynamic array） として実装されている。
要素はメモリ上に連続して配置される（各要素はPythonオブジェクトへのポインタ）
容量が不足すると、より大きいメモリ領域を確保して全要素をコピーする
appendは平均 （だがたまにしか発生しないので平均は低い）insert(0, x)は異なる型の要素を混在できる
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動的配列の成長戦略¶
CPythonの list は容量不足時に現在のサイズの約1.125倍（+ α）に拡張する。
拡張時に全要素をコピーするため かかるが、拡張の頻度が指数的に減るため、
append の 償却計算量 （amortized time complexity、平均でみたとき） は になる。
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 = sizelist vs array vs numpy.ndarray¶
| 特性 | list | array.array | numpy.ndarray |
|---|---|---|---|
| 要素の型 | 任意（混在可） | 同一の数値型 | 同一の数値型 |
| メモリ効率 | 低い | 高い | 高い |
| 数値演算速度 | 遅い | やや遅い | 速い（ベクトル化） |
| 多次元配列 | 不可（ネスト） | 不可 | 可 |
| 用途 | 汎用コレクション | 数値の省メモリ保存 | 数値計算・科学計算 |