为什么元组比列表更快？

I've just read in "Dive into Python" that "tuples are faster than lists".

我刚读过“Dive into Python”，“元组比列表更快”。

Tuple is immutable, and list is mutable, but I don't quite understand why tuple is faster.

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

Anyone did a performance test on this?

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

7 个解决方案

#1

The reported "speed of construction" ratio only holds for constant tuples (ones whose items are expressed by literals). Observe carefully (and repeat on your machine -- you just need to type the commands at a shell/command window!)...:

报告的“构造速度”比率仅适用于常量元组（其项目由文字表示）。仔细观察（并在您的机器上重复 - 您只需要在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

I didn't do the measurements on 3.0 because of course I don't have it around -- it's totally obsolete and there is absolutely no reason to keep it around, since 3.1 is superior to it in every way (Python 2.7, if you can upgrade to it, measures as being almost 20% faster than 2.6 in each task -- and 2.6, as you see, is faster than 3.1 -- so, if you care seriously about performance, Python 2.7 is really the only release you should be going for!).

我没有在3.0上进行测量，因为我当然没有它 - 它完全过时了，并且没有理由保持它，因为3.1在各方面都优于它（Python 2.7，如果你可以升级到它，在每项任务中测量速度比2.6快近20％ - 而2.6，如你所见，速度比3.1快 - 所以，如果你认真考虑性能，那么Python 2.7真的是你唯一应该发布的版本要去！）。

Anyway, the key point here is that, in each Python release, building a list out of constant literals is about the same speed, or slightly slower, than building it out of values referenced by variables; but tuples behave very differently -- building a tuple out of constant literals is typically three times as fast as building it out of values referenced by variables! You may wonder how this can be, right?-)

无论如何，这里的关键点在于，在每个Python版本中，使用常量文字构建列表的速度与从变量引用的值构建的速度大致相同或稍慢一些;但是元组的表现非常不同 - 用常量文字构建元组通常比用变量引用的值构建元组*倍！你可能想知道这是怎么回事，对吗？ - ）

Answer: a tuple made out of constant literals can easily be identified by the Python compiler as being one, immutable constant literal itself: so it's essentially built just once, when the compiler turns the source into bytecodes, and stashed away in the "constants table" of the relevant function or module. When those bytecodes execute, they just need to recover the pre-built constant tuple -- hey presto!-)

答案：由常量文字构成的元组很容易被Python编译器识别为一个不可变的常量文字本身：所以它基本上只构建一次，当编译器将源转换为字节码时，并隐藏在“常量表”中“相关功能或模块。当这些字节码执行时，他们只需要恢复预先建立的常量元组 - 嘿presto！ - ）

This easy optimization cannot be applied to lists, because a list is a mutable object, so it's crucial that, if the same expression such as [1, 2, 3] executes twice (in a loop -- the timeit module makes the loop on your behalf;-), a fresh new list object is constructed anew each time -- and that construction (like the construction of a tuple when the compiler cannot trivially identify it as a compile-time constant and immutable object) does take a little while.

这种简单的优化不能应用于列表，因为列表是一个可变对象，所以如果相同的表达式如[1,2,3]执行两次（在循环中 - timeit模块使循环开启）至关重要你的代表;-)，每次都重新构造一个新的列表对象 - 这种构造（如编译器不能简单地将其标识为编译时常量和不可变对象时构造元组）确实需要一段时间。

That being said, tuple construction (when both constructions actually have to occur) still is about twice as fast as list construction -- and that discrepancy can be explained by the tuple's sheer simplicity, which other answers have mentioned repeatedly. But, that simplicity does not account for a speedup of six times or more, as you observe if you only compare the construction of lists and tuples with simple constant literals as their items!_)

话虽这么说，元组结构（当两个结构实际上必须发生时）仍然是列表构造的两倍 - 并且这种差异可以通过元组的简单性来解释，其他答案已经反复提到。但是，这种简单性并没有考虑到六倍或更多的加速，正如您所观察到的，如果您只将列表和元组的结构与简单的常量文字作为项目进行比较！_）

#2

With the power of the timeit module, you can often resolve performance related questions yourself:

借助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

This shows that tuple is negligibly faster than list for iteration. I get similar results for indexing, but for construction, tuple destroys list:

这表明元组的迭代速度可以忽略不计。我得到类似的索引结果，但对于构​​造，元组破坏列表：

$ 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

So if speed of iteration or indexing are the only factors, there's effectively no difference, but for construction, tuples win.

因此，如果迭代速度或索引是唯一因素，那么实际上没有区别，但对于构​​造而言，元组获胜。

#3

Alex gave a great answer, but I'm going to try to expand on a few things I think worth mentioning. Any performance differences are generally small and implementation specific: so don't bet the farm on them.

亚历克斯给出了一个很好的答案，但我会尝试扩展一些我认为值得一提的事情。任何性能差异通常很小并且具体实现：所以不要在农场上赌它们。

In CPython, tuples are stored in a single block of memory, so creating a new tuple involves at worst a single call to allocate memory. Lists are allocated in two blocks: the fixed one with all the Python object information and a variable sized block for the data. That's part of the reason why creating a tuple is faster, but it probably also explains the slight difference in indexing speed as there is one fewer pointer to follow.

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

There are also optimisations in CPython to reduce memory allocations: de-allocated list objects are saved on a free list so they can be reused, but allocating a non-empty list still requires a memory allocation for the data. Tuples are saved on 20 free lists for different sized tuples so allocating a small tuple will often not require any memory allocation calls at all.

CPython中还有一些优化可以减少内存分配：取消分配的列表对象保存在空闲列表中，因此可以重用它们，但是分配非空列表仍然需要为数据分配内存。元组保存在20个不同大小元组的空闲列表中，因此分配一个小元组通常根本不需要任何内存分配调用。

Optimisations like this are helpful in practice, but they may also make it risky to depend too much on the results of 'timeit' and of course are completely different if you move to something like IronPython where memory allocation works quite differently.

像这样的优化在实践中是有帮助的，但它们也可能使得过多地依赖于'timeit'的结果存在风险，当然如果你转向像IronPython那样内存分配工作方式完全不同的东西则完全不同。

#4

Essentially because tuple's immutability means that the interpreter can use a leaner, faster data structure for it, compared to list.

基本上因为元组的不变性意味着解释器可以使用更精简，更快速的数据结构，与列表相比。

#5

Executive Summary

Tuples tend to perform better than lists in almost every category:

元组往往比几乎每个类别中的列表表现更好：

1) Tuples can be constant folded.

1）元组可以不断折叠。

2) Tuples can be reused instead of copied.

2）可以重用元组而不是复制元组。

3) Tuples are compact and don't over-allocate.

3）元组是紧凑的，不会过度分配。

4) Tuples directly reference their elements.

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

Tuples can be constant folded

Tuples of constants can be precomputed by Python's peephole optimizer or AST-optimizer. Lists, on the other hand, get built-up from scratch:

常量元组可以通过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 

Tuples do not need to be copied

Running tuple(some_tuple) returns immediately itself. Since tuples are immutable, they do not have to be copied:

运行元组（some_tuple）会立即返回。由于元组是不可变的，因此不必复制它们：

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

In contrast, list(some_list) requires all the data to be copied to a new list:

相反，list（some_list）要求将所有数据复制到新列表：

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

Tuples do not over-allocate

Since a tuple's size is fixed, it can be stored more compactly than lists which need to over-allocate to make append() operations efficient.

由于元组的大小是固定的，因此它可以比需要过度分配以使append（）操作有效的列表更紧凑地存储。

This gives tuples a nice space advantage:

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

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

Here is the comment from Objects/listobject.c that explains what lists are doing:

以下是来自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.
 */

Tuples refer directly to their elements

References to objects are incorporated directly in a tuple object. In contrast, lists have an extra layer of indirection to an external array of pointers.

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

This gives tuples a small speed advantage for indexed lookups and unpacking:

这为元组提供了索引查找和解包的小速度优势：

$ 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

Here is how the tuple (10, 20) is stored:

以下是元组（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;

Here is how the list [10, 20] is stored:

以下是列表[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;

Note that the tuple object incorporates the two data pointers directly while the list object has an additional layer of indirection to an external array holding the two data pointers.

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

#6

One area where a list is notably faster is construction from a generator, and in particular, list comprehensions are much faster than the closest tuple equivalent, tuple() with a generator argument:

列表明显更快的一个区域是来自生成器的构造，特别是，列表推导比最接近的元组等效，使用生成器参数的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

Note in particular that tuple(generator) seems to be a tiny bit faster than list(generator), but [elem for elem in generator] is much faster than both of them.

特别注意，元组（生成器）似乎比列表（生成器）快一点，但[生成器中elem的元素]比它们快得多。

#7

Tuples are identified by python compiler as one immutable constant so compiler created only one entry in hash table and never changed

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

Lists are mutable objects.So compiler update the entry when we update the list so it is little bit slower compare to tuple

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