为什么 Python 的数组很慢？

Question

我预计 array.array 比列表更快，因为数组似乎是未装箱的。

但是，我得到以下结果：

In [1]: import array

In [2]: L = list(range(100000000))

In [3]: A = array.array('l', range(100000000))

In [4]: %timeit sum(L)
1 loop, best of 3: 667 ms per loop

In [5]: %timeit sum(A)
1 loop, best of 3: 1.41 s per loop

In [6]: %timeit sum(L)
1 loop, best of 3: 627 ms per loop

In [7]: %timeit sum(A)
1 loop, best of 3: 1.39 s per loop

造成这种差异的原因是什么？

Answer 1

存储是"unboxed"，但每次访问元素Python都必须"box"它（将其嵌入常规Python 对象）以便对其进行任何操作。例如，您的 sum(A) 遍历数组，并在常规 Python int 对象中一次将每个整数装箱。那要花时间。在您的 sum(L) 中，所有装箱都是在创建列表时完成的。

所以，最后，数组通常较慢，但需要的内存却少得多。

这是 Python 3 最新版本的相关代码，但自 Python 首次发布以来，相同的基本思想适用于所有 CPython 实现。

这是访问列表项的代码：

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    /* error checking omitted */
    return ((PyListObject *)op) -> ob_item[i];
}

几乎没有什么：somelist[i] 只是 returns 列表中的第 i 个对象（以及 CPython 中的所有 Python 个对象是指向其初始段符合 struct PyObject).

布局的结构的指针

这里是 array 类型代码 l 的 __getitem__ 实现：

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

原始内存被视为平台原生 C long 整数的向量；第 i 个 C long 已读完；然后调用 PyLong_FromLong() 将原生 C long 包装 ("box") 在 Python long 对象中（在 Python 3 中，消除了Python 2对int和long的区分，实际显示为类型int).

此装箱必须为 Python int 对象分配新内存，并将本机 C long 的位喷入其中。在原始示例的上下文中，此对象的生命周期非常短暂（仅够 sum() 将内容添加到运行总数），然后需要更多时间来释放新的 int对象。

在 CPython 实现中，这就是速度差异的来源，过去一直存在，将来也会存在。

Answer 2

添加到 Tim Peters 的出色答案中，数组实现了 buffer protocol, while lists do not. This means that, if you are writing a C extension (or the moral equivalent, such as writing a Cython 模块），然后您可以比任何 Python 更快地访问和使用数组的元素。这会给你相当大的速度提升，可能超过一个数量级。但是，它有一些缺点：

您现在正在编写 C 而不是 Python。 Cython 是改善这种情况的一种方法，但它并没有消除语言之间的许多根本差异；您需要熟悉 C 语义并理解它在做什么。
PyPy 的 C API 工作 to some extent，但不是很快。如果您的目标是 PyPy，您可能应该只编写带有常规列表的简单代码，然后让 JITter 为您优化它。
C 扩展比纯 Python 代码更难分发，因为它们需要编译。编译往往依赖于体系结构和操作系统，因此您需要确保针对目标平台进行编译。

直接使用 C 扩展可能是用大锤打苍蝇，这取决于您的用例。您应该首先调查 NumPy 并查看它是否足够强大以执行您尝试执行的任何数学运算。如果使用得当，它也会比原生 Python 快得多。

Answer 3

Tim Peters 回答了为什么 这很慢，但让我们看看如何改进。

坚持您的 sum(range(...)) 示例（比您的示例小 10 倍以适合此处的内存）：

import numpy
import array
L = list(range(10**7))
A = array.array('l', L)
N = numpy.array(L)

%timeit sum(L)
10 loops, best of 3: 101 ms per loop

%timeit sum(A)
1 loop, best of 3: 237 ms per loop

%timeit sum(N)
1 loop, best of 3: 743 ms per loop

这种方式也需要 numpy box/unbox，这会产生额外的开销。为了让它更快，必须留在 numpy c 代码中：

%timeit N.sum()
100 loops, best of 3: 6.27 ms per loop

因此，从列表解决方案到 numpy 版本，这是运行时的 16 倍。

我们也来看看创建这些数据结构需要多长时间

%timeit list(range(10**7))
1 loop, best of 3: 283 ms per loop

%timeit array.array('l', range(10**7))
1 loop, best of 3: 884 ms per loop

%timeit numpy.array(range(10**7))
1 loop, best of 3: 1.49 s per loop

%timeit numpy.arange(10**7)
10 loops, best of 3: 21.7 ms per loop

明显的赢家：Numpy

另请注意，创建数据结构所花费的时间与求和所花费的时间差不多，甚至更多。分配内存很慢。

内存使用情况：

sys.getsizeof(L)
90000112
sys.getsizeof(A)
81940352
sys.getsizeof(N)
80000096

因此每个数字占用 8 个字节，开销各不相同。对于范围我们使用 32 位整数就足够了，所以我们可以保护一些内存。

N=numpy.arange(10**7, dtype=numpy.int32)

sys.getsizeof(N)
40000096

%timeit N.sum()
100 loops, best of 3: 8.35 ms per loop

但事实证明，在我的机器上添加 64 位整数比添加 32 位整数要快，所以只有在您受到 memory/bandwidth.

的限制时才值得这样做

Answer 4

请注意100000000等于10^8而不是10^7，我的结果如下：

100000000 == 10**8

# my test results on a Linux virtual machine:
#<L = list(range(100000000))> Time: 0:00:03.263585
#<A = array.array('l', range(100000000))> Time: 0:00:16.728709
#<L = list(range(10**8))> Time: 0:00:03.119379
#<A = array.array('l', range(10**8))> Time: 0:00:18.042187
#<A = array.array('l', L)> Time: 0:00:07.524478
#<sum(L)> Time: 0:00:01.640671
#<np.sum(L)> Time: 0:00:20.762153

为什么 Python 的数组很慢？

Why are Python's arrays slow?

python

arrays

performance

boxing

python-internals