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

Why is tuple faster than list in Python?

提问by Quan Mai

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

我刚刚在“深入 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?

有人做过性能测试吗？

采纳答案by Alex Martelli

The reported "speed of construction" ratio only holds for constanttuples (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 编译器识别为一个不可变常量字面量本身：所以它基本上只构建一次，当编译器将源代码转换为字节码并隐藏在“常量表”中时”的相关功能或模块。当这些字节码执行时，他们只需要恢复预先构建的常量元组——嘿，快！-)

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 timeitmodule 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 thatdiscrepancy 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!_)

话虽如此，元组构造（当两种构造实际上都必须发生时）仍然是列表构造的两倍左右——这种差异可以用元组的纯粹简单来解释，其他答案已经反复提到。但是，这种简单并不能解释六倍或更多的加速，正如您所观察到的，如果您仅将列表和元组的构造与简单的常量文字作为它们的项目进行比较！_)

回答by Dan Breslau

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

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

回答by Alec Thomas

With the power of the timeitmodule, 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.

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

回答by Duncan

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 这样的东西，内存分配的工作方式完全不同。

回答by Dan Passaro

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.

请特别注意，这tuple(generator)似乎比 快一点list(generator)，但[elem for elem in generator]比两者都快得多。

回答by y durga prasad

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

列表是可变对象。所以当我们更新列表时，编译器会更新条目，所以它比元组慢一点

回答by Raymond Hettinger

Executive Summary

执行摘要

Tuples tend to perform better than listsin 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:

运行tuple(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.cthat 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

Hereis 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;

Hereis 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.

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

回答by M. Rostami

In python, we have two types of objects. 1. Mutable, 2. Immutable.
In python, lists come under mutable objects and tuples comes under immutable objects.

在python中，我们有两种类型的对象。1. 可变的， 2. 不可变的。
在python中，列表属于可变对象，而元组属于不可变对象。

• Tuples are stored in a single block of memory. Tuples are immutable so, It doesn't require extra space to store new objects.

• Lists are allocated in two blocks: the fixed one with all the Python object information and a variable-sized block for the data.

• It is the reason creating a tuple is faster than List.

• It also explains the slight difference in indexing speed is faster than lists, because in tuples for indexing it follows fewer pointers.

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

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

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

• 它还解释了索引速度比列表更快的细微差异，因为在用于索引的元组中，它遵循更少的指针。

Advantages of using tuples:

使用元组的优点：

• Tuples are that they use less memory where lists use more memory.

• We can use tuples in a dictionary as a key but it's not possible with lists.

• We can access elements with an index in both tuples and lists.

• 元组是它们使用更少的内存，而列表使用更多的内存。

• 我们可以将字典中的元组用作键，但不能使用列表。

• 我们可以在元组和列表中访问带有索引的元素。

Disadvantages of tuples:

元组的缺点：

• We cannot add an element to tuple but we can add an element to list.

• We can't sort a tuple but in a list, we can sort by calling list.sort()method.

• We can't remove an element in tuple but in a list, we can remove an element.

• We can't replace an element in tuple but you can in a list.

• 我们不能向元组添加元素，但可以向列表添加元素。

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

• 我们不能删除元组中的元素，但在列表中，我们可以删除一个元素。

• 我们无法替换元组中的元素，但您可以替换列表中的元素。

---

---

Source

来源