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

storage 是“未装箱”的，但每次您访问一个元素时，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 对象都是指向一个结构的指针，其初始段符合 struct PyObject) 的布局。

这里是 __getitem__ 实现，用于类型代码 l 的 array:

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() 将 native C long 包装(“框”)在 Python long 对象中(在 Python 3 中，它消除了 Python 2 在 int 和 long 之间的区别，实际上显示为类型 int)。

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

这就是速度差异的来源，在 CPython 实现中始终来自，并且将永远来自。