为什么元组在Python中比列表快？

Question

我刚在“深入Python”上看到说“元组比列表快”。

元组是不可变的，而列表是可变的，但我不太明白为什么元组会更快。

有人做过性能测试吗？

Answer 1

Alex的回答很不错，但我想补充一些我认为值得提及的内容。一般来说，性能差异很小，而且跟具体的实现有关，所以不要太过于依赖这些差异。

在CPython中，元组是存储在一块连续的内存区域里的，所以创建一个新的元组最多只需要一次内存分配的调用。列表则分成两个部分来分配内存：一个是固定的部分，里面存储了所有Python对象的信息，另一个是可变大小的部分，用来存储数据。这也是为什么创建元组会更快的原因之一，同时也能解释为什么索引速度会有一点差别，因为元组需要跟踪的指针少了一些。

CPython中还有一些优化措施来减少内存分配：被释放的列表对象会被保存在一个空闲列表中，以便可以重复使用，但分配一个非空的列表仍然需要为数据分配内存。元组则被保存在20个不同大小的空闲列表中，所以分配一个小的元组通常根本不需要进行内存分配的调用。

这些优化在实际使用中是很有帮助的，但也可能让人冒险过于依赖'timeit'的结果。当然，如果你换到像IronPython这样的环境，内存分配的方式会完全不同。

Answer 2

总结

元组在几乎所有方面的表现都比列表好：

1) 元组可以被常量折叠。

2) 元组可以被重用，而不是复制。

3) 元组占用空间小，不会多分配。

4) 元组直接引用它们的元素。

元组可以进行常量折叠

Python 的小优化器或 AST 优化器可以提前计算常量元组。而列表则是从头开始构建的：

    >>> from dis import dis

    >>> dis(compile("(10, 'abc')", '', 'eval'))
      1           0 LOAD_CONST               2 ((10, 'abc'))
                  3 RETURN_VALUE   

    >>> dis(compile("[10, 'abc']", '', 'eval'))
      1           0 LOAD_CONST               0 (10)
                  3 LOAD_CONST               1 ('abc')
                  6 BUILD_LIST               2
                  9 RETURN_VALUE

元组不需要复制

运行 tuple(some_tuple) 会立即返回它自己。因为元组是不可变的，所以不需要复制：

>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True

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

>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False

元组不会多分配空间

由于元组的大小是固定的，它可以比列表更紧凑地存储，因为列表需要多分配空间以提高 append() 操作的效率。

这让元组在空间上有了很大的优势：

>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200

这里是来自 Objects/listobject.c 的注释，解释了列表是如何工作的：

/* 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.
 */

元组直接引用它们的元素

元组对象直接包含对对象的引用。而列表则需要额外的层级来指向一个外部的指针数组。

这让元组在索引查找和解包时有一点速度优势：

$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'a[1]'
10000000 loops, best of 3: 0.0304 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'a[1]'
10000000 loops, best of 3: 0.0309 usec per loop

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

这里是元组 (10, 20) 的存储方式：

    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;

这里是列表 [10, 20] 的存储方式：

    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;

注意，元组对象直接包含了两个数据指针，而列表对象则多了一层间接引用，指向一个外部数组来存储这两个数据指针。

Answer 3

这里提到的“构建速度”比率只适用于常量元组（也就是那些用字面量表示的元组）。仔细观察一下（你可以在自己的电脑上试试，只需要在命令行窗口输入这些命令就行！）…:

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.379 usec per loop
$ python3.1 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.413 usec per loop

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.174 usec per loop
$ python3.1 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0602 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.352 usec per loop
$ python2.6 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.358 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.157 usec per loop
$ python2.6 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0527 usec per loop

我没有在3.0上做测量，因为我根本不想再用它——它已经完全过时了，根本没有理由继续使用，因为3.1在各方面都比它好（如果你能升级到Python 2.7，它在每个任务上比2.6快将近20%——而2.6，如你所见，比3.1快——所以，如果你真的在意性能，Python 2.7才是你应该选择的版本！）。

无论如何，这里最关键的一点是，在每个Python版本中，用常量字面量构建列表的速度大致和用变量引用的值构建列表的速度差不多，或者稍微慢一点；但元组的表现就很不一样了——用常量字面量构建元组的速度通常是用变量引用的值构建元组的三倍！你可能会想，这怎么可能呢？-)

答案是：用常量字面量构建的元组，Python编译器可以很容易地识别为一个不可变的常量字面量：所以它基本上只在编译器把源代码转换成字节码时构建一次，然后存放在相关函数或模块的“常量表”中。当这些字节码执行时，它们只需要取出预先构建好的常量元组——太简单了！-)

这种简单的优化不能应用于列表，因为列表是可变对象，所以如果同样的表达式，比如[1, 2, 3]，在循环中执行两次（timeit模块会为你处理这个循环;-），每次都会构建一个全新的列表对象——而这种构建（就像当编译器无法简单地识别它为编译时常量和不可变对象时构建元组一样）确实需要一点时间。

话虽如此，元组的构建速度（当两种构建都必须发生时）仍然大约是列表构建速度的两倍——而这种差异可以用元组的简单性来解释，其他答案也多次提到过。但这种简单性并不能解释六倍或更多的速度提升，尤其是当你只比较用简单常量字面量作为元素的列表和元组的构建速度时！

为什么元组在Python中比列表快？

8 个回答

总结

元组可以进行常量折叠

元组不需要复制

元组不会多分配空间

元组直接引用它们的元素

撰写回答