15. リスト、タプル、配列

#15. リスト、タプル、配列

リスト、タプル、および配列のようなオブジェクトは、順序付けられたコレクションを表します。これらはすべてインデックス付きアクセスをサポートしていますが、ストレージ モデル、可変性ルール、パフォーマンスのトレードオフが異なります。

リストは、オブジェクト参照の変更可能なシーケンスです。

タプルは、オブジェクト参照の不変のシーケンスです。

配列のようなオブジェクトは、コンパクトな型付きデータを格納するか、連続したバッファを公開します。

CPython コンテナーは、その型が RAW ストレージ用に特別に設計されていない限り、参照を格納するため、これらの区別は重要です。

15.1 順序付けられたコレクション

Python にはいくつかの順序付きコレクション型があります。

リストとタプルには、あらゆるタイプのオブジェクトを格納できます。python xs = [1, "two", object()] t = (1, "two", object()) 配列には、1 つのマシンレベルの型の値が格納されます。```python from array import array

nums = array("i", [1, 2, 3])

CPython リストには、Python オブジェクトへのポインターが格納されます。

概念的には:```text
PyListObject
    PyVarObject header
        ob_size = logical length
    ob_item ----> array of PyObject *
    allocated = capacity
```のために：```python
xs = [10, 20, 30]
```レイアウトは次のとおりです。```text
list object
    ob_size = 3
    allocated >= 3
    ob_item ----+
                |
                v
              [ptr][ptr][ptr]
                |    |    |
                v    v    v
               10   20   30
```このリストは整数ペイロードをインライン化しません。整数オブジェクトへの参照を保存します。

これが、リストが混合型を保持できる理由です。```python
xs = [1, "hello", None, []]
```すべての要素スロットは同じ表現を持ちます。`PyObject *`。

## 15.3 リストの長さと容量

リストには論理長と割り当てられた容量があります。```text
length
    number of active elements

capacity
    number of slots currently allocated in the internal array
```例：```python
xs = []
xs.append("a")
xs.append("b")
xs.append("c")
```論理長は 3 です。割り当てられる容量は 3 より大きい場合があります。

この予備容量により、効率的な追加が可能になります。 CPython は通常、追加のたびに内部配列のサイズを変更しません。配列はより大きなステップで拡張されます。

概念的には:```text
append item
    if length < allocated:
        store item in spare slot
        length += 1
    else:
        allocate larger array
        copy references
        store item
        length += 1
```リストのオブジェクト ID は安定したままです。内部の要素配列が移動する可能性があります。```python
xs = []
before = id(xs)

for i in range(1000):
    xs.append(i)

after = id(xs)
print(before == after)   # True
```## 15.4 リストの追加`list.append`オブジェクト参照を 1 つ最後に追加します。```python
xs = []
xs.append(1)
xs.append(2)
```C レベルでは、追加は次のことを行う必要があります。```text
ensure there is enough capacity
increment the appended object's reference count
store the object pointer
increase the logical size
```オブジェクトを追加してもコピーされません。```python
item = []
xs = []
xs.append(item)

item.append(1)
print(xs)        # [[1]]
```リストには、への参照が保存されます。`item`。

## 15.5 リストの過剰割り当て

リストの過剰割り当てが、追加の繰り返しが効率的である理由です。

過剰割り当てがなければ、このループは何度も繰り返して配列全体をコピーします。```python
xs = []
for i in range(1_000_000):
    xs.append(i)
```過剰割り当てにより、CPython は一度に複数のスロットの容量を増加します。正確な式は実装の詳細ですが、動作は償却された定数時間の追加を示します。

重要な結果:

|操作 |     平均コスト |
| ------------------ | ---------------: |
|`append`           | `O(1)`償却済み |
|`pop()`端から |`O(1)`|
|ランダムなインデックス作成 |`O(1)`|
|前に挿入 |`O(n)`|
|途中から削除 |`O(n)`|

追記は最後まで触れているので安いです。先頭に挿入すると、多くの参照を移動する必要があるため、コストがかかります。

## 15.6 リストのインデックス付け

リストのインデックス付けは配列への直接アクセスです。```python
x = xs[i]
```概念的には:```text
check bounds
read ob_item[i]
return referenced object
```これにより、`O(1)`アクセス。

負のインデックスは次のように変換されます。```python
xs[-1]
```手段：```text
xs[len(xs) - 1]
```境界後の処理。

インデックスを作成すると、含まれるオブジェクトへの参照が返されます。そのオブジェクトはコピーされません。```python
xs = [[1], [2]]
a = xs[0]
a.append(99)

print(xs)        # [[1, 99], [2]]
```## 15.7 リストの代入

リスト項目の割り当ては、保存されている 1 つの参照を置き換えます。```python
xs = [1, 2, 3]
xs[1] = "two"
```C レベルでは、置換は参照カウントを安全に処理する必要があります。```text
increment new item
store new item pointer
decrement old item
```新しいオブジェクトと古いオブジェクトが同じオブジェクトである可能性がある場合、安全な順序が重要になります。

概念的には:```c
Py_INCREF(new_item);
old_item = items[index];
items[index] = new_item;
Py_DECREF(old_item);
```これにより、ファイナライザーが実行中に実行された場合でも、所有権の不変条件が保持されます。`Py_DECREF`。

## 15.8 リストのスライス

スライスすると新しいリストが作成されます。```python
xs = [[1], [2], [3]]
ys = xs[0:2]
```新しいリストには、同じ要素オブジェクトへの参照が含まれます。```python
ys[0].append(99)

print(xs)    # [[1, 99], [2], [3]]
print(ys)    # [[1, 99], [2]]
```これは浅いコピーです。

外側のリストは新しいものです。含まれるオブジェクトは共有されます。```text
xs ----> [ptr A][ptr B][ptr C]
ys ----> [ptr A][ptr B]
```ディープ コピーには再帰的なコピーが必要です。```python
import copy

ys = copy.deepcopy(xs)
```## 15.9 リストの挿入と削除

途中に挿入すると、後の参照が移動します。```python
xs = [1, 2, 3, 4]
xs.insert(1, "x")
```概念的には:```text
[1][2][3][4]
insert at index 1
[1]["x"][2][3][4]
```インデックス 1 以降の要素は右にシフトします。

中央から削除すると左に移動します。```python
del xs[1]
```これらの操作は、`O(n)`多くのポインタを移動する可能性があるためです。

オブジェクト自体はコピーされません。 CPython は内部配列内の参照を移動します。

## 15.10 リストのソート`list.sort`リストをその場で並べ替えます。```python
xs = [3, 1, 2]
xs.sort()

sorted(xs)新しいリストを作成します。python ys = sorted(xs) CPython はリストの並べ替えに Timsort を使用します。これは安定しています。つまり、等しいキーは相対的な順序を保持します。```python items = [ ("a", 2), ("b", 1), ("c", 2), ]

items.sort(key=lambda x: x[1]) print(items) # [('b', 1), ('a', 2), ('c', 2)]

## 15.11 タプルは参照をインラインで保存します

タプルは不変のシーケンスです。

概念的には:```text
PyTupleObject
    PyVarObject header
        ob_size = length
    ob_item[0]
    ob_item[1]
    ...
```のために：```python
t = (10, 20, 30)
```レイアウトは次のとおりです。```text
tuple object
    ob_size = 3
    ob_item[0] ---> 10
    ob_item[1] ---> 20
    ob_item[2] ---> 30
```リストとは異なり、タプル項目はタプル割り当ての一部としてインラインで保存されます。サイズ変更可能な個別の配列はありません。

タプルの長さは作成後に変更できないため、これが可能になります。

## 15.12 タプルの不変性

タプルの不変性は、タプルの項目参照を変更できないことを意味します。```python
t = (1, 2, 3)
t[0] = 99        # TypeError
```タプル オブジェクトには参照が引き続き保存されます。 1 つの参照オブジェクトが変更可能である場合、そのオブジェクトは変更される可能性があります。```python
t = ([],)
t[0].append("x")

print(t)         # (['x'],)
```タプルは依然として同じリストを指します。リストが変わりました。

この区別はハッシュ化にとって重要です。```python
hash((1, 2, 3))      # works
hash(([],))          # TypeError
```タプルは、すべての要素がハッシュ可能である場合にのみハッシュ可能です。

## 15.13 タプルの作成

タプル リテラルは一般的です。```python
t = (1, 2, 3)
```括弧だけではタプルは作成されません。コンマはそうです。```python
a = (1)
b = (1,)

print(type(a))   # int
print(type(b))   # tuple
```タプルは以下の目的で内部的に頻繁に使用されます。```text
function arguments
multiple return values
constant groups
dictionary keys
bytecode constants
C API argument packing
```タプルは不変でコンパクトであるため、固定グループの自然なコンテナーとなります。

## 15.14 タプルのパッキングとアンパッキング

Python では、複数の値をパックするためにタプルを使用します。```python
point = 10, 20
```これによりタプルが作成されます。

解凍すると要素が抽出されます。```python
x, y = point
```バイトコード レベルでは、パッキングとアンパッキングは共通であるため、専用の命令があります。

拡張開梱:```python
first, *middle, last = [1, 2, 3, 4, 5]
```スター付きターゲットのリストを作成します。```python
print(middle)    # [2, 3, 4]
```## 15.15 リストとタプル

リストとタプルのインデックス作成動作は似ていますが、設計目標は異なります。

|特集 |リスト |タプル |
| ---------- | ------------------------ | ------------------------ |
|可変性 |可変 |不変 |
|長さ |変更可能 |修正済み |
|ストレージ |サイズ変更可能な個別の配列 |インライン項目参照 |
|追加 |はい |いいえ |
|ハッシュ可能 |いいえ |要素がハッシュ可能である場合 |
|主な用途 |可変シーケンス |固定グループまたはレコード |
|構文 |`[1, 2]`                 | `(1, 2)`|

コレクションが変更された場合はリストを使用します。

コレクションが固定グループを表す場合は、タプルを使用します。

## 15.16 配列は生の値を保存します`array.array`Python オブジェクト参照ではなく、コンパクトな型付き値を格納します。```python
from array import array

xs = array("i", [1, 2, 3])
```型コードは C レベルの表現を制御します。

例:

|タイプコード |意味 |
| --------- | -------------- |
|`"b"`|符号付き文字 |
|`"B"`|符号なし文字 |
|`"h"`|署名付きショート |
|`"H"`|符号なしショート |
|`"i"`|符号付き整数 |
|`"I"`|符号なし整数 |
|`"l"`|長い署名付き |
|`"L"`|符号なしロング |
|`"f"`|フロート |
|`"d"`|ダブル |

整数の配列は、Python 整数オブジェクトのリストよりもはるかにコンパクトです。

概念的には:```text
list of ints
    [ptr][ptr][ptr]
      |    |    |
      v    v    v
     int  int  int

array("i")
    [raw int][raw int][raw int]
```## 15.17 配列のトレードオフ

配列はコンパクトですが、リストほど一般的ではありません。

|特集 |リスト |`array.array`|
| --------------------- | ------------------------------------------ | ---------------------------- |
|要素の種類 |任意の Python オブジェクト | 1 つのプリミティブ型 |
|メモリ使用量 |より高い |下 |
|数値のコンパクトさ |悪い |良い |
| Python オブジェクトのメソッド |完全なオブジェクト参照 |境界で変換された値 |
|異種データ |はい |いいえ |
|バッファプロトコル |配列 | のような生の数値バッファを直接使用することはできません。はい |

配列は、バイナリ I/O、コンパクトな数値ストレージ、およびバッファ互換データに役立ちます。

大量の数値計算の場合、通常、NumPy 配列などのサードパーティ配列の方が強力です。

## バイト配列としての 15.18 バイト`bytes`は不変のバイト シーケンスです。```python
b = b"abc"

print(b[0])     # 97
```シーケンスのように動作しますが、生のバイトを保存します。`bytearray`は可変バージョンです:```python
buf = bytearray(b"abc")
buf[0] = 65

print(buf)      # bytearray(b'Abc')
```バイナリデータの場合、`bytes`そして`bytearray`よりもコンパクトです`list[int]`。```python
data = [97, 98, 99]     # list of Python int objects
raw = b"abc"            # compact bytes
```## 15.19 メモリービューとゼロコピー・スライシング

あ`memoryview`ビューを既存のバッファーに公開できます。```python
buf = bytearray(b"abcdef")
view = memoryview(buf)[2:5]

print(view.tobytes())   # b'cde'
```ビューは基礎となるバイトをコピーしません。

書き込み可能なビューを介して変更すると、エクスポーターに影響します。```python
buf = bytearray(b"abcdef")
view = memoryview(buf)

view[0] = ord("X")

print(buf)              # bytearray(b'Xbcdef')
```これは、バイナリ パーサー、ネットワーク プロトコル、ファイル形式、および拡張モジュールに役立ちます。

## 15.20 シーケンスプロトコル

リスト、タプル、バイト、バイト配列、範囲、および配列は、シーケンスの動作に関与します。

一般的な操作:```python
len(xs)
xs[i]
xs[i:j]
x in xs
for x in xs:
    ...
```タイプによって、それらの操作を実装する方法が決まります。

C レベルでは、シーケンスの動作は次のようなシーケンス スロットを通じて公開されます。```text
sq_length
sq_item
sq_ass_item
sq_contains
sq_concat
sq_repeat
```不変シーケンスでは割り当てスロットが省略されます。

可変シーケンスは代入動作を提供します。

## 15.21 反復

リスト反復子は、リストへの参照と現在のインデックスを保存します。```python
xs = [1, 2, 3]
it = iter(xs)

print(next(it))    # 1
```概念的には:```text
list iterator
    sequence reference
    current index
```タプルの反復も同様です。

リストの反復では、スナップショットのコピーではなくリスト オブジェクトが参照されます。```python
xs = [1, 2, 3]

for x in xs:
    if x == 2:
        xs.append(4)
```反復中にリストを変更すると、混乱を招く動作が発生する可能性があります。意図的に行動を制御しない限り、これは避けてください。

## 15.22 メンバーシップのテスト

リストまたはタプルの場合:```python
x in xs
```リニアスキャンを実行します。

概念的には:```text
for each item:
    compare item == x
```これは`O(n)`。

メンバーシップが多いワークロードの場合は、セットまたは辞書を使用します。```python
seen = set(xs)

if x in seen:
    ...
```セットではハッシュが使用され、通常は平均値が得られます。`O(1)`メンバーシップ。

## 15.23 コピー

リストのコピー方法は浅いです:```python
a = [[1], [2]]

b = a.copy()
c = list(a)
d = a[:]
```3 つすべてが新しい外部リストを作成します。内部オブジェクトは共有されます。```python
b[0].append(99)

print(a)    # [[1, 99], [2]]
```実際のコピーが必要ない場合、タプルのコピーは通常、同じオブジェクトを返します。```python
t = (1, 2, 3)
u = tuple(t)

print(t is u)    # True
```タプルは不変であるため、この再利用は安全です。

## 15.24 繰り返し

シーケンスの繰り返しは参照を繰り返します。```python
xs = [[]] * 3
xs[0].append(1)

print(xs)        # [[1], [1], [1]]
```3 つのスロットはすべて同じ内部リストを指します。

正しいパターン:```python
xs = [[] for _ in range(3)]
```これで、各要素は異なるリストになります。

これは参照モデルの問題であり、リスト乗算のバグではありません。

## 15.25 オブジェクトのリストの並べ替え

並べ替えには比較またはキー関数が使用されます。```python
items = ["aaa", "b", "cc"]
items.sort(key=len)
```と`key`, CPython はキーを計算し、それらのキーを使用して並べ替えます。

これにより、高価な比較ロジックの繰り返しの再計算が回避されます。

安定したソートによりマルチパスソートが可能になります。```python
items.sort(key=lambda x: x.name)
items.sort(key=lambda x: x.group)
```2 回目の並べ替え後、グループが等しい項目は最初の並べ替え時の名前の順序を維持します。

## 15.26 リスト内包表記

リスト内包表記はリストを直接構築します。```python
squares = [x * x for x in range(10)]
```通常、単純な変換では手動の追加ループよりも高速かつ明確です。

同等の形状:```python
squares = []
for x in range(10):
    squares.append(x * x)
```内包表記には専用のバイトコード パターンがあり、ループ本体をコンパクトに保ちます。

## 15.27 ジェネレーター式とリスト

リスト内包表記では、すべての要素が即座に作成されます。```python
xs = [x * x for x in range(1_000_000)]
```ジェネレーター式は値を遅延して生成します。```python
it = (x * x for x in range(1_000_000))
```インデックス作成、反復的な走査、または具体化されたデータが必要な場合は、リストを使用します。

1 つのパスが必要で、すべての結果を保存することを避けたい場合は、ジェネレーターを使用します。

## 15.28 一般的なパフォーマンスパターン

|タスク |より良い選択 |理由 |
| ------------------------ | ---------------------- | ------------------------ |
|多くの項目を追加する |`list.append`|償却済み`O(1)`|
|反復可能なものから構築する |`list(iterable)`|効率的なコンストラクター パス |
|修正されたレコード |`tuple`|不変でコンパクト |
|会員テスト |`set`|ハッシュベースの検索 |
|左からの列 |`collections.deque`|効率的な左ポップ |
|数値コンパクトストレージ |`array.array`または NumPy |生の型付きストレージ |
|バイナリデータ |`bytes`または`bytearray`|コンパクトなバイトストレージ |
|ゼロコピーバイナリスライス |`memoryview`|割り当てを回避 |
|多くの連結 |`join`|繰り返しのコピーを回避 |

リストは汎用です。これらは、注文されたすべてのワークロードに最適であるわけではありません。

## 15.29 よくある間違い

いくつかのよくある間違いは、CPython の参照ベースのコンテナ モデルから直接発生します。

共有内部リスト:```python
matrix = [[0] * 3] * 3
```より良い：```python
matrix = [[0] * 3 for _ in range(3)]
```大規模な検索セットにリスト メンバーシップを使用する:```python
if user_id in user_ids_list:
    ...
```より良い：```python
user_ids = set(user_ids_list)
if user_id in user_ids:
    ...
```前方削除の繰り返し:```python
while xs:
    xs.pop(0)
```より良い：```python
from collections import deque

q = deque(xs)
while q:
    q.popleft()
```繰り返される文字列またはバイトの連結:```python
s = ""
for part in parts:
    s += part
```より良い：```python
s = "".join(parts)
```## 15.30 C API スケッチ

リストの作成:```c
PyObject *list = PyList_New(0);
if (list == NULL) {
    return NULL;
}
```追加:```c
PyObject *item = PyLong_FromLong(42);
if (item == NULL) {
    Py_DECREF(list);
    return NULL;
}

if (PyList_Append(list, item) < 0) {
    Py_DECREF(item);
    Py_DECREF(list);
    return NULL;
}

Py_DECREF(item);

PyList_Append項目参照を内部的にインクリメントします。ローカル所有の参照は引き続き解放する必要があります。

タプルの作成:```c PyObject *tuple = PyTuple_New(1); if (tuple == NULL) { return NULL; }

PyObject *item = PyLong_FromLong(42); if (item == NULL) { Py_DECREF(tuple); return NULL; }

PyTuple_SET_ITEM(tuple, 0, item);

`PyTuple_SET_ITEM`参照を盗みます。しないでください`Py_DECREF(item)`使用に成功した後。

この違いは、C API の所有権に関する古典的な罠の 1 つです。

## 15.31 メンタルモデル

このモデルを使用します。```text
list
    mutable sequence
    separate resizable array of PyObject *
    over-allocates for efficient append

tuple
    immutable sequence
    inline fixed array of PyObject *
    compact for fixed groups

array
    mutable typed sequence
    raw value storage
    compact but homogeneous

bytes
    immutable raw byte sequence

bytearray
    mutable raw byte sequence

memoryview
    zero-copy view over buffer-exporting object
```リストとタプルの場合、要素は参照であることに注意してください。コンテナをコピーしても、コンテナ内のオブジェクトはコピーされません。

## 15.32 概要

リストとタプルは参照コンテナです。リストは変更可能で、個別に割り当てられたサイズ変更可能な配列を使用します。タプルは不変であり、項目参照を固定サイズの割り当てにインラインで格納します。

配列とバイトのようなオブジェクトは、任意の Python オブジェクトへの参照ではなく、コンパクトな生データを保存します。これらは、バイナリ データおよび型付き数値ストレージに適しています。

これらのレイアウトを理解すると、ほとんどのパフォーマンスと正確性の動作が説明されます。追加の効率、前挿入コスト、浅いコピー、反復参照の落とし穴、タプルの不変性、バッファー ビュー、一般的なオブジェクト コンテナーとコンパクトな RAW ストレージの違いなどです。