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

这种差异的原因是什么？

- Valentin Lorentz

---

NumPy工具可以高效利用您的数组: %timeit np.sum(A) ：100个循环，3次中的最佳结果：每次循环8.87毫秒 - B. M.

我从未遇到需要使用“array”包的情况。如果您想进行大量数学计算，Numpy以闪电般的速度运行（即C语言），通常比诸如“sum()”之类的天真实现更好。 - Nick T

投票关闭的人：为什么这个问题被认为是基于意见的？原帖似乎在问一个关于可测量且可重复的现象的具体技术问题。 - Kevin

@NickT 阅读一个优化轶事。结果发现，array在将表示ASCII字节的整数字符串转换为str对象时非常快速。即使是Guido自己也经过了许多其他解决方案后才想出这个方法，并对其性能感到相当惊讶。无论如何，在我记忆中只有这里看到它被用到了。处理数组问题上，numpy更好，但它是第三方依赖项。 - Bakuriu

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对象都是指向结构体的指针，其初始段符合struct PyObject的布局）。

以下是类型代码为l的array的__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 包装在 Python long 对象中（在 Python 3 中，消除了 Python 2 中 int 和 long 的区别，实际上显示为类型 int）。

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

这就是 CPython 实现中速度差异的来源，一直都是如此，而且永远都会如此。

- Tim Peters

---

抱歉，我是个新手，我不明白你们如何使用那个%timeit运算符。Python有类似%timeit的东西吗？ - OmGanesh

@OmGanesh %timeit 是 IPython 的魔法命令：https://ipython.readthedocs.io/en/stable/interactive/magics.html#magic-timeit - Arne

Answer 2

为了补充Tim Peters的出色回答，数组实现了缓冲区协议，而列表则没有。这意味着，如果你正在编写C扩展（或道德等价物，比如编写Cython模块），那么你可以比Python能做的更快地访问和处理数组的元素。这将给你带来相当大的速度提升，可能超过一个数量级。然而，它也有一些缺点：

1. 您现在需要编写C代码而不是Python。 Cython 是改善这一问题的一种方式，但它并不能消除语言之间的许多基本差异；您需要熟悉C语义并理解它正在做什么。
2. PyPy的C API在一定程度上可以工作（链接1），但速度不太快。 如果您的目标是PyPy，则应编写带有常规列表的简单代码，然后让JITter为您进行优化。
3. C扩展比纯Python代码更难分发，因为它们需要被编译。 编译往往与体系结构和操作系统有关，因此您需要确保为目标平台进行编译。

根据您的用例，直接使用C扩展可能有点大材小用。 您应该先调查NumPy，看看它是否足够强大以执行您要执行的任何数学运算。 如果正确使用，它也将比本机Python快得多。

- Kevin

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进行装箱/拆箱，这会增加额外的开销。要使其快速，必须在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位整数更快，因此只有在受到内存/带宽限制时才值得这样做。

- Robin Roth

Answer 4

我注意到typecode L比l更快，而且它也适用于I和Q。

Python 3.8.5

这是测试代码。 检查一下吧，d_d。

#!/usr/bin/python3
import inspect
from tqdm import tqdm
from array import array


def get_var_name(var):
    """
    Gets the name of var. Does it from the out most frame inner-wards.
    :param var: variable to get name from.
    :return: string
    """
    for fi in reversed(inspect.stack()):
        names = [var_name for var_name, var_val in fi.frame.f_locals.items() if var_val is var]
        if len(names) > 0:
            return names[0]

def performtest(func, n, *args, **kwargs):

    times = array('f')
    times_append = times.append
    for i in tqdm(range(n)):
        st = time.time()
        func(*args, **kwargs)
        times_append(time.time() - st)
    print(
        f"Func {func.__name__} with {[get_var_name(i) for i in args]} run {n} rounds consuming |"
        f" Mean: {sum(times)/len(times)}s | Max: {max(times)}s | Min: {min(times)}s"
    )

def list_int(start, end, step=1):
    return [i for i in range(start, end, step)]

def list_float(start, end, step=1):
    return [i + 1e-1 for i in range(start, end, step)]

def array_int(start, end, step=1):
    return array("I", range(start, end, step)) # speed I > i, H > h, Q > q, I~=H~=Q

def array_float(start, end, step=1):
    return array("f", [i + 1e-1 for i in range(start, end, step)]) # speed f > d


if __name__ == "__main__":

    performtest(list_int, 1000, 0, 10000)
    performtest(array_int, 1000, 0, 10000)

    performtest(list_float, 1000, 0, 10000)
    performtest(array_float, 1000, 0, 10000)

结果

测试结果

- Ian Lee

---

欢迎来到Stack Overflow。请阅读[答案]。特别是，请确保您的答案实际上解决了所提出的问题。OP正在询问某些缓慢的原因。您评论了一些代码比其他代码更快，但没有说明它为什么可能会变慢。 - Chris

感谢您友好的提醒。我会阅读指南并记在心里。 - Ian Lee

Answer 5

请注意，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

- S. Cheraghifar