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

Question

我刚读过"Dive into Python","元组比列表更快".

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

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

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,如果你可以升级到它,在每项任务中测量速度比2.6快近20% - 而且,如你所见,2.6比3.1更快 - 所以,如果你认真考虑性能,那么Python 2.7真的是你唯一应该发布的版本要去!).

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

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

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

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

Answer 2

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

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

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

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

Answer 3

执行摘要

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

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

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

Answer 5

列表明显更快的一个领域是从生成器构建，特别是，列表推导式比带有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]比两者都快得多。

Answer 6

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

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

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

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

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

使用元组的优点：

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

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

• 我们可以通过元组和列表中的索引来访问元素。

元组的缺点：

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

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

• 我们无法删除元组中的元素，但在列表中，我们可以删除元素。

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

来源

Answer 7

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