Introduction

Python有两个相似的序列类型，元组 tuples 和列表 lists。它们之间最显著的区别是 tuples 是不可变的（immutable），也就是说，你不能改变它们的大小以及它们的不变对象（immutable objects）。

不能更改 tuple 中的元素：

1
2
3
4
5
>>> a = (1,2,3)
>>> a[0] = 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

但是可以改变其中的可变对象：

1
2
3
4
5
6
>>> b = (1,[1,2,3],3)
>>> b[1]
[1, 2, 3]
>>> b[1].append(4)
>>> b
(1, [1, 2, 3, 4], 3)

在python中，lists 和 tuples 都是作为Python Objects（items）的指针列表实现的。从列表中删除元素时，对元素的引用将被销毁。但如果程序中有其他对此元素的引用时，则删除的元素保持活动状态。

Tuples

尽管一般情况下 tuples 的使用没有 lists多，但它是一种基本数据类型，在 Python 内部和实际使用中也是应用很多的。

你可能没注意到，但是会在以下情况下使用元组：

  • 使用 arguments 和 parameters
  • 从函数返回2个或更多元素
  • 迭代一个字典的键值对
  • 使用字符串格式
  • …

通常，正在运行的程序具有数千个分配的 tuples。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>>> import gc
>>> def type_stats(type_obj):
...     count = 0
...     for obj in gc.get_objects():
...         if type(obj) == type_obj:
...             count += 1
...     return count
...
>>> type_stats(tuple)
3136
>>> type_stats(list)
659
>>> import pandas
>>> type_stats(tuple)
6953
>>> type_stats(list)
2455

Empty lists vs empty tuples

一个空的元组（Empty tuple）饰演着一个单例（singleton），也就是说，始终只有一个长度为零的 tuple 。 当创建一个空元组时，Python 指向一个已预先分配的空元组，这样任何空元组在内存中都具有相同的地址。因为tuples 是不可变的，有时可以节省大量内存。

1
2
3
4
5
6
7
8
>>> a = ()
>>> b = ()
>>> a is b
True
>>> id(a)
4409020488
>>> id(b)
4409020488

这不适用于 lists，因为它们可以被修改。

1
2
3
4
5
6
7
8
>>> a = []
>>> b = []
>>> a is b
False
>>> id(a)
4465566920
>>> id(b)
4465370632

Allocation optimization

Allocation optimization for small tuples

为了减少内存碎片并加速分配，Python重用（reuse）了旧元组。 如果一个元组不再需要并且少于20个项，则Python会将其移动到 free list 中，而不是永久删除它。

一个 free list 分为20组，其中每组代表长度 n 为 0 到 20 之间的 tuples。每个组最多可存储2000个 tuple，第一个（零）组只包含1个元素并表示一个空元组。

1
2
3
4
5
6
7
>>> a = (1,2,3)
>>> id(a)
4427578104
>>> del a
>>> b = (1,2,4)
>>> id(b)
4427578104

在上面的例子中，我们可以看到 a 和 b 具有相同的 id。这是因为我们立即占用了一个被销毁的位于 free list中的 tuple。

Allocation optimization for lists

由于 lists 可以修改，因此 Python 不使用与 tuples 中相同的优化。Python的 lists 也有一个 free list，但它仅用于空对象。 如果一个empty list被GC删除或收集，则可以在之后重用。

1
2
3
4
5
6
7
>>> a = []
>>> id(a)
4465566792
>>> del a
>>> b = []
>>> id(b)
4465566792

List resizing

为避免调整 lists 大小的成本，Python不会在每次需要向 lists 中添加或删除元素时，调整 lists 大小。相反，每个 lists 都有许多空的位置。这些空位置对用户是隐藏的，但可用于新的元素。如果位置都被占用，Python会为 lists 分配额外的空间。新加位置的数量根据 lists 当前大小进行选择。即 over-allocate

开发者文档描述如下：

This over-allocates proportional to the list size, making room for additional growth. The over-allocation is mild but is enough to give linear-time amortized behavior over a long sequence of appends() in the presence of a poorly-performing system realloc().

The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …

Note: new_allocated won’t overflow because the largest possible value is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.

例如，如果想将一个元素追加到长度为8的 lists 中，Python会将其大小调整为16，并添加新元素为第9个元素。其余的位置将隐藏并保留为新的元素。

增长方式如下所示：

1
2
3
4
5
6
7
8
9
10
11
>>> def get_new_size(n_items):
...     new_size = n_items + (n_items // 2 ** 3)
...     if n_items < 9:
...             new_size += 3
...     else:
...             new_size += 6
...
...     return new_size
...
>>> get_new_size(9)
16

Performance Summary

tuples 几乎在每个类别中，都比 lists 表现更好：

  • tuples 可以常数折叠（constant folded）。

  • tuples 可以重用，而不是复制一个新的。

  • tuples 是紧凑的，不会像 lists 那样 over-allocate。

  • tuples 直接引用它们的元素。

tuples可以常数折叠

常量元组（Tuples of constants）可以通过Python的窥孔优化器（peephole optimizer）或AST优化器（AST-optimizer ）进行预先计算。 而另一方面，lists 从头开始构建：

dis模块反汇编函数的字节代码，有助于查看 tuples 和 lists 之间的区别。在这种情况下，可以看到访问元素会生成相同的代码，但分配 tuples 要比分配 lists 快得多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
>>> def a():
...     x=[1,2,3,4,5]
...     y=x[2]
...
>>> def b():
...     x=(1,2,3,4,5)
...     y=x[2]
...
>>> import dis
>>> dis.dis(a)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 LOAD_CONST               4 (4)
             12 LOAD_CONST               5 (5)
             15 BUILD_LIST               5
             18 STORE_FAST               0 (x)

  3          21 LOAD_FAST                0 (x)
             24 LOAD_CONST               2 (2)
             27 BINARY_SUBSCR
             28 STORE_FAST               1 (y)
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE
>>> dis.dis(b)
  2           0 LOAD_CONST               6 ((1, 2, 3, 4, 5))
              3 STORE_FAST               0 (x)

  3           6 LOAD_FAST                0 (x)
              9 LOAD_CONST               2 (2)
             12 BINARY_SUBSCR
             13 STORE_FAST               1 (y)
             16 LOAD_CONST               0 (None)
             19 RETURN_VALUE

tuples可以重用

运行tuple(some_tuple)会立即返回some_tuple自身。由于 tuples 是不可变的，因此不必复制它们：

1
2
3
4
>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True

相比之下，list(some_list)将所有数据复制到一个新的 lists 中：

1
2
3
4
>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False

tuples不会over-allocate

由于 tuples 的大小是固定的，因此它可以比需要over-allocate以使append()操作有效 的lists 更紧凑地存储元素。

这为 tuples 提供了一个很好的空间优势：

1
2
3
4
5
>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200

tuples 直接引用它们的元素

对象的引用直接包含在 tuples 对象中。相比之下，lists 有一个额外的间接层指向外部指针数组。

这为 tuples 提供了实例化、索引查找和解包的一些速度优势：

使用 Python timeit来帮助我们量化 tuples 的速度优势：

tuples 实例化的速度优势，几乎快了一个数量级：

1
2
3
4
5
$ python -m timeit "x=(1,2,3,4,5,6,7,8)"
10000000 loops, best of 3: 0.0388 usec per loop

$ python -m timeit "x=[1,2,3,4,5,6,7,8]"
1000000 loops, best of 3: 0.363 usec per loop

tuples 索引查找和解包的速度优势：

1
2
3
4
5
6
7
8
9
$ python -m timeit -s 'a = (10, 20, 30)' 'a[1]'
10000000 loops, best of 3: 0.0304 usec per loop
$ python -m timeit -s 'a = [10, 20, 30]' 'a[1]'
10000000 loops, best of 3: 0.0309 usec per loop

$ python -m timeit -s 'a = (10, 20, 30)' 'x, y, z = a'
10000000 loops, best of 3: 0.0249 usec per loop
$ python -m timeit -s 'a = [10, 20, 30]' 'x, y, z = a'
10000000 loops, best of 3: 0.0251 usec per loop

从这里我们可以看到 tuple (10, 20)如何存储：

1
2
3
4
5
6
typedef struct {
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
    Py_ssize_t ob_size;
    PyObject *ob_item[2];     /* store a pointer to 10 and a pointer to 20 */
} PyTupleObject;

从这里我们可以看到 list [10, 20]如何存储：

1
2
3
4
5
6
7
8
9
PyObject arr[2];              /* store a pointer to 10 and a pointer to 20 */

typedef struct {
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
    Py_ssize_t ob_size;
    PyObject **ob_item = arr; /* store a pointer to the two-pointer array */
    Py_ssize_t allocated;
} PyListObject;

注意到 tuples 对象直接包含两个数据指针，而 lists 对象具有一个间接的附加层来指向包含两个数据指针的外部数组。

Reference

  1. Optimization tricks in Python: lists and tuples
  2. Are tuples more efficient than lists in Python?