为什么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

该存储是"拆箱",但每次你访问一个元素的Python有"盒子"是为了对它做任何事(在常规的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]只返回i列表中的第一个对象(CPython中的所有Python对象都是指向一个结构的指针,该结构的初始段符合a的布局struct PyObject).

这__getitem__是arraywith类型代码的实现l:

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在Python long对象(其在Python 3中,这消除之间的Python 2的区别int和long,实际上是示为类型int).

这个拳击必须为Python int对象分配新的内存,并将本机C long的位喷入其中.在原始示例的上下文中,此对象的生命周期非常简短(仅足以sum()将内容添加到运行总计中),然后需要更多时间来释放新int对象.

这是速度差异的来源,始终来自,并且始终将来自CPython实现.

Answer 2

为了增加Tim Peters的优秀答案,数组实现了缓冲协议,而列表却没有.这意味着,如果您正在编写C扩展(或道德等效,例如编写Cython模块),那么您可以比Python可以做的任何事情更快地访问和使用数组元素.这将为您提供相当大的速度改进,可能超过一个数量级.但是,它有许多缺点:

1. 您现在正在编写C而不是Python.Cython是改善这种情况的一种方法,但它并没有消除语言之间的许多根本差异; 你需要熟悉C语义并理解它在做什么.
2. PyPy的C API 在某种程度上起作用,但速度不是很快.如果您的目标是PyPy,您应该只使用常规列表编写简单代码,然后让JITter为您优化它.
3. C扩展比纯Python代码更难分发,因为它们需要编译.编译往往依赖于体系结构和操作系统,因此您需要确保为目标平台进行编译.

直接使用C扩展可能会使用大锤来拍打苍蝇,具体取决于您的使用情况.你应该首先调查NumPy,看看它是否足够强大,可以做你想做的任何数学运算.如果使用正确,它也将比原生Python快得多.

Answer 3

蒂姆·彼得斯回答了为什么这么慢,但让我们看看如何改进它.

坚持你的例子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

这种方式也需要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位整数更快,所以如果你受到内存/带宽的限制,这是值得的.