15.列表、元组和数组

列表、元组和类似数组的对象表示有序集合。它们都支持索引访问，但具有不同的存储模型、可变性规则和性能权衡。

列表是对象引用的可变序列。

元组是对象引用的不可变序列。

类似数组的对象存储紧凑类型的数据或公开连续的缓冲区。

这些区别很重要，因为 CPython 容器存储引用，除非该类型是专门为原始存储设计的。

15.1 有序集合

Python 有多种有序集合类型。

|类型 | 可变 |商店 |主要用途| | ------------- | -------------：| ----------------- | ------------------------------------------- | |list| 是的 |对象参考|一般可变序列 | |tuple| 没有 |对象参考|固定记录、不可变组 | |array.array| 是的 |原始类型值 |紧凑的数字存储 | |bytes| 没有 |原始字节 |不可变的二进制数据 | |bytearray| 是的 |原始字节 |可变二进制数据 | |memoryview|视图相关 |原始缓冲区视图 |零拷贝缓冲区访问 |

列表和元组可以存储任何类型的对象：python xs = [1, "two", object()] t = (1, "two", object()) 数组存储一种机器级类型的值：```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, []]
```每个元素槽都有相同的表示：a`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
```列表的对象标识保持稳定。内部元素数组可能会移动。```python
xs = []
before = id(xs)

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

after = id(xs)
print(before == after)   # True
```## 15.4 列表追加`list.append`在末尾添加一个对象引用。```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 列表赋值

列表项分配取代了一个存储的引用。```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
```元组对象仍然存储引用。如果一个引用的对象是可变的，则该对象可以更改。```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对象|一种原始类型 |
|内存使用 |更高 |降低|
|数值紧凑性 |可怜|好 |
| 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 和零拷贝切片

一个`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[:]
```这三个都创建一个新的外部列表。内部对象是共享的。```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]]
```所有三个槽都指向同一个内部列表。

正确模式：```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)
```第二次排序后，具有相同组的项目保留第一次排序的名称顺序。

## 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))
```当您需要索引、重复遍历或具体化数据时，请使用列表。

当您需要一次传递并希望避免存储所有结果时，请使用生成器。

## 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_Appendincrements the item reference internally.本地拥有的引用仍必须被释放。

元组创建：```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 所有权陷阱之一。

## 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 对象的引用。它们更适合二进制数据和类型化数字存储。

了解这些布局可以解释大多数性能和正确性行为：追加效率、前端插入成本、浅拷贝、重复引用陷阱、元组不变性、缓冲区视图以及通用对象容器和紧凑原始存储之间的差异。