Python 列表与数组：意外性能差异的原因

Question

目前正在学习算法和数据结构

我想我会运行一个快速的 timeit.timeit 测试来迭代 list() 中的 2**30 个随机整数列表与 [=14] 中的相同=]格式。

我期待数组首先完成，因为我在其他帖子中看到的 Python 数组的少数无声好处之一是性能（一开始我误以为list是用链表实现的：谢谢Duncan的指正）

数组应该至少和列表一样快？

import os
import array
l = list(os.urandom(2**30))
a = array.array('I', l)

def test_list():
 for i in l:
  pass

def test_array():
 for i in a:
  pass

>>> timeit.timeit(test_array, number=5)
50.08525877200009
>>> timeit.timeit(test_list, number=5)
37.00491460799958

这是我的平台信息： Python 3.6.5，[GCC 7.3.0] linux x86_64（英特尔 i5 4660）

Answer 1

首先，您将 l 初始化为 2**30 Python int 个值的列表。

然后从列表中初始化 a 以创建一个包含 2**30 个 C 整数的列表。

test_list 遍历 Python int 值的列表。在此过程中没有创建或销毁 Python 个对象，只是每个对象的引用计数器先递增然后递减。

test_array 遍历 C 整数列表，为每个元素创建一个新的 Python int，然后再次销毁它。这就是数组速度较慢的原因：它创建和销毁 2**30 Python 个对象。

在内部，Python 列表只是指向它包含的对象的指针数组。这意味着迭代列表与迭代数组一样简单和快速。这里的 array 类型将使用更少的内存（或者如果你没有保留列表的话），因为 C 整数比 Python 对象小得多，但每次访问数组必须将 C 值转换为 Python 对象，虽然对象的创建已经过大量优化，但它仍然比仅获取对现有对象的另一个引用要花费更多的时间。

Python 列表与数组：意外性能差异的原因

Python list vs. array: reason for the unexpected performance difference

python

instructions

data-structures

python-3.x