Python 列表与数组 : reason for the unexpected performance difference

Question

我目前正在研究算法和数据结构。

我想我会运行一个快速的 timeit.timeit 测试来遍历 list() 中 2**30 个随机整数的列表，比较相同的array.array 格式。

我期待数组首先完成，因为我在其他帖子中看到的 Python 数组的几个无声的好处之一是性能(一开始我误以为列表是作为链表实现的:谢谢邓肯的指正)

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

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

这是我的平台信息:Linux x86_64 (Intel i5 4660) 上的 Python 3.6.5、[GCC 7.3.0]

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 对象，虽然对象创建已得到高度优化，但它仍然比仅获取对现有对象的另一个引用需要更多时间。