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

Question

我刚刚在“深入Python”中读到，“元组比列表更快”。

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

是否有人对此进行过性能测试？

- Quan Mai

---

请编辑您的问题并添加一个链接，以便我可以查看您引用的内容。为了方便起见，我甚至可以提供给您链接：http://diveintopython3.org/native-datatypes.html#tuples - gotgenes

我读的是PDF版本，所以没有链接。谢谢：），我会把它添加到问题中。 - Quan Mai

另外，你对这些说法提出质疑是正确的。Python解释器在每个版本中都会有变化；在追随它们之前，性能声明应始终在自己的平台上进行经验证实。 Alec Thomas的答案是如何快速为您自己做到这一点的亮点示例。另请参阅timeit文档：http://docs.python.org/library/timeit.html - gotgenes

@gotgenes：正在阅读，谢谢 :) - Quan Mai

Answer 1

所谓的“建造速度”比率仅适用于常量元组（其中每个项都由文字表示）。请仔细观察（并在您的计算机上重复 - 您只需在shell /命令窗口中键入命令）...：

$ 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，则在每个任务中，Python 2.7的速度几乎比2.6快20％ - 而2.6，如您所见，比3.1更快 - 所以，如果您真的关心性能，Python 2.7确实是您应该选择的唯一版本！）。

无论如何，这里的关键点是，在每个Python发布版本中，使用常量字面值构建列表的速度与使用变量引用的值构建列表的速度大致相同，或稍微慢一些;但元组的行为非常不同-使用常量字面值构建元组通常比使用变量引用的值构建元组快三倍！你可能会想知道这是如何实现的？

答案：由于Python编译器可以轻松地将由常量字面值组成的元组识别为一个不可变的常量字面值本身，因此它实际上只在编译器将源代码转换为字节码时构建一次，并存储在相关函数或模块的“常量表”中。当这些字节码执行时，它们只需要恢复预先构建的常量元组即可。

这种简单的优化不能应用于列表，因为列表是可变对象，所以如果同一表达式（如[1,2,3]）两次执行（在循环中-使用timeit模块代表您执行循环;-)，每次都需要构建一个新的列表对象 - 而且那个构造过程（就像编译器无法轻易地将其识别为编译时的常量和不可变对象的元组的构造）确实需要一点时间。

话虽如此，元组的构造（当两个构造实际上必须 发生）仍然比列表构造快大约两倍 - 但是，那个差异可以通过元组的简单性来解释，其他答案已经反复提到了。但是，这种简单性并不能解释仅比较使用简单常量字面值作为其项目的列表和元组的构造速度的加速六倍或更多！

- Alex Martelli

---

回答很好，但是 shell 代码片段阅读起来有些困难。请考虑重新编写或添加摘要表格。 - Dima Tisnek

Answer 2

执行摘要

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

1) 元组可以进行常量折叠。

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

3) 元组紧凑且不会过度分配。

4) 元组直接引用其元素。

元组可以进行常量折叠

Python的Peephole优化器或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;

请注意，元组对象直接包含两个数据指针，而列表对象则具有额外的间接层，指向包含两个数据指针的外部数组。

- Raymond Hettinger

Answer 3

Alex提供了很好的答案，但我想进一步扩展一些值得一提的事情。任何性能差异通常都很小，并且与具体的实现有关：因此不要过于依赖它们。

在CPython中，元组以单个内存块存储，因此创建新元组最坏情况下只需要调用一次分配内存的函数。列表使用两个块进行分配：一个固定大小的块包含所有Python对象信息，而另一个块是可变大小的数据块。这就是创建元组更快的部分原因，但这可能也解释了索引速度略有差异，因为少了一个指针需要跟踪。

在CPython中也有优化来减少内存分配：已释放的列表对象保存在空闲列表中，以便可以重复使用，但分配非空列表仍需要为数据分配内存。元组保存在20个用于不同大小元组的空闲列表中，因此分配小元组通常根本不需要调用任何内存分配函数。

像这样的优化在实践中很有帮助，但也可能使过于依赖“timeit”的结果变得有风险，当然如果转移到诸如IronPython之类的其他编程语言中时，则完全不同。

- Duncan

---

“一个指针少跟踪”并不是这样的；虽然内存分配存在差异，但获取特定项的函数（在剥离错误检查后）是相同的：PyObject * PyBLAH_GetItem(PyObject *op, Py_ssize_t i) {return ((PyBLAHObject *)op) -> ob_item[i];} - John Machin

是的。在元组的数据结构中，ob_item 是结构末尾的一个数组。而在列表中，ob_item 是指向数组的指针。访问这两个数组中的元素的 C 代码是相同的，但在列表的情况下，需要额外的内存读取来获取指针的值。 - Duncan

你是正确的。tupleobject.h 有 PyObject * ob_item[1];，而 listobject.h 则有 PyObject ** ob_item;。 - John Machin

Answer 4

借助于timeit模块的强大功能，您通常可以自行解决与性能有关的问题：

$ python2.6 -mtimeit -s 'a = tuple(range(10000))' 'for i in a: pass'
10000 loops, best of 3: 189 usec per loop
$ python2.6 -mtimeit -s 'a = list(range(10000))' 'for i in a: pass' 
10000 loops, best of 3: 191 usec per loop

这表明对于迭代，元组比列表稍微快一些。我得到了类似的结果用于索引，但是对于构建，元组优于列表：

$ python2.6 -mtimeit '(1, 2, 3, 4)'   
10000000 loops, best of 3: 0.0266 usec per loop
$ python2.6 -mtimeit '[1, 2, 3, 4]'
10000000 loops, best of 3: 0.163 usec per loop

因此，如果迭代速度或索引是唯一的因素，那么二者实际上没有区别，但在构造方面，元组胜出。

- Alec Thomas

---

在请求重新编写之前，你是否尝试过使用Python 3.0来运行那段代码了？ - gotgenes

几乎没有人使用Python 3。安装2.x版本，不要指望别人为你跳过障碍。 - Glenn Maynard

我认为元组明显更快的情况只有一个，那就是在构建它们时，这也是元组被广泛用于从函数返回多个值的情况下进行优化的主要点。一般来说，选择使用元组并不是基于性能考虑的。（在快速测试中，元组在索引方面实际上比列表慢约20％；我没有研究过原因。） - Glenn Maynard

在命令行（如果你使用的是Windows，则为DOS）上运行Alec给你的命令。 - mechanical_meat

阅读六年前的评论：“几乎没有人使用Python 3” 哈。 - David Andrei Ned

Answer 5

在Python中，我们有两种类型的对象。1. 可变的(Mutable) 2. 不可变的(Immutable)。在Python中，列表属于可变对象，元组属于不可变对象。

元组(Tuples)存储在单个内存块中。元组是不可变的，因此不需要额外的空间来存储新对象。

列表(Lists)分配在两个块中：一个固定的块包含所有Python对象信息和一个可变大小的块用于数据。

这就是创建元组比列表更快的原因。

它还解释了索引速度略微快于列表，因为在元组中进行索引时遵循较少的指针。

使用元组的优点： 1. 元组使用的内存较少，而列表使用的内存较多。 2. 我们可以将元组用作字典中的键，但不能使用列表。 3. 我们可以在元组和列表中使用索引访问元素。

使用元组的缺点：

• 我们无法向元组中添加元素，但是可以向列表中添加元素。

• 我们无法对元组进行排序，但是在列表中，我们可以通过调用list.sort()方法进行排序。

• 我们无法从元组中删除元素，但是在列表中，我们可以删除一个元素。

• 我们无法替换元组中的元素，但是在列表中，可以进行替换。

---

来源

- M. Rostami

---

如果一个元组包含一个列表，例如 s = ('a', [1,2,3], 'b')，那么如果我们向列表中添加元素，空间会如何分配？@M.Rostami - vijay shanker

好答案，但重要的是要注意，尽管元组没有sort方法，但实际上可以使用内置的sorted函数对其进行排序：sorted((4, 2, 1))将返回(1, 2, 4)。 - undefined

Answer 6

基本上，元组的不可变性意味着解释器可以使用比列表更轻巧、更快速的数据结构。

- Dan Breslau

Answer 7

列表比元组在从生成器构建时更快，特别是列表推导式比最接近的元组等价物 tuple() 在使用生成器参数时要快得多:

$ python --version
Python 3.6.0rc2
$ python -m timeit 'tuple(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.34 usec per loop
$ python -m timeit 'list(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.41 usec per loop
$ python -m timeit '[x * 2 for x in range(10)]'
1000000 loops, best of 3: 0.864 usec per loop

特别注意，tuple(generator)似乎比list(generator)稍微快一点，但是[elem for elem in generator]比它们两个都要快很多。

- Dan Passaro

Answer 8

元组被Python编译器识别为一个不可变的常量，因此编译器在哈希表中只创建了一个条目，并且从未更改过。

列表是可变对象。当我们更新列表时，编译器会更新条目，因此与元组相比稍微慢一些。

- y durga prasad