列表(numpy.array)变慢的原因是什么？

Question

众所周知，如果a是一个numpy数组，那么a.tolist()比list(a)更快，例如：

>>> import numpy as np
>>> big_np=np.random.randint(1,10**7,(10**7,))

>>> %timeit list(big_np)
1 loop, best of 3: 869 ms per loop
>>> %timeit big_np.tolist()
1 loop, best of 3: 306 ms per loop

那意味着，天真的list(a)版本比特殊函数tolist()慢大约3倍。然而，与内置的array模块的性能相比：

>>> import array
>>> big_arr=array.array('i', big_np)
>>> %timeit list(big_arr)
1 loop, best of 3: 312 ms per loop

我们可以看到，应该说list(a)很慢而不是tolist()很快，因为array.array和特殊函数一样快。

另一个观察结果是：array.array模块和tolist从small-integer-pool（即值在[-5, 256]范围内）中受益，但对于list(a)则不是这种情况。

##only small integers:
>>> small_np=np.random.randint(1,250, (10**7,))
>>> small_arr=array.array('i', small_np)

>>> %timeit list(small_np)
1 loop, best of 3: 873 ms per loop
>>> %timeit small_np.tolist()
10 loops, best of 3: 188 ms per loop
>>> %timeit list(small_arr)
10 loops, best of 3: 150 ms per loop

正如我们所看到的，更快的版本大约快了两倍，但慢速版本与以前一样慢。

我的问题是：相对于list(array.array)，什么使list(numpy.array)变慢？

编辑：

另一个观察结果是，在Python2.7中，如果整数更大（即不能由int32保存），则需要更长时间：

>>> very_big=np.random.randint(1,10**7,(10**7,))+10**17
>>> not_so_big=np.random.randint(1,10**7,(10**7,))+10**9
>>> %timeit very_big.tolist()
1 loop, best of 3: 627 ms per loop
>>> %timeit not_so_big.tolist()
1 loop, best of 3: 302 ms per loop

但仍然比缓慢的列表版本快。

- ead

---

tolist（）递归地将所有值转换为Python原始类型 list（）从可迭代对象创建一个Python列表更多信息：https://dev59.com/K14c5IYBdhLWcg3weaP8 - Olaf Górski

@OlafGórski array.array使用迭代器，速度仍然很快吗？ - ead

在不同情况下，列表元素的类型是什么？ - hpaulj

@hpaulj 对于 list(numpy-array)，它是 <type 'numpy.int32'>，否则为 int。 - ead

list 迭代第一维。如果数组是二维的，则结果是一个由一维数组组成的列表。通常情况下，list 和 tolist 不会产生相同的结果，并且不应该期望它们在速度上可比较。 - hpaulj

Answer 1

以下是部分答案，解释了您观察到的小整数池的情况：

>>> a = np.arange(10)
>>> type(list(a)[0])
<class 'numpy.int64'>
>>> type(a.tolist()[0])
<class 'int'>

我们可以看到tolist似乎试图创建本地Python类型的元素，而数组迭代器（这是列表构造函数使用的）则不会。

事实上，tolist的C实现（源代码在这里）使用PyArray_GETITEM它相当于Python的arr[index].item()，而不是 - 人们可能会认为的 - arr[index]

- Paul Panzer

---

你认为创建一个 numpy.int64 对象比创建一个 int 对象慢吗？ - ead

@ead 我真的不知道。如果你强迫我猜的话，我会倾向于是的，但这只是基于“所有numpy相关的事情都带有开销”的模糊经验的迷信。 - Paul Panzer

我认为大部分时间用于创建int对象。请查看我的最后一次编辑，其中显示对于更大的值，它变得更慢，因为内部使用了另一种“整数”类型。 - ead

在Python中，小于256的int对象被缓存（参见此处），这使得使用它们相对便宜。 - MB-F

很有趣，你是否知道在Windows上的Python是否直接切换到任意大小的整数（我猜测这会更加昂贵），还是首先切换到类似于int64的东西？（假设它对小整数使用平台C int。） - Paul Panzer

据我所知，要么是PyLong_FromLong(long ival)，要么就是“最坏情况”下的_PyLong_FromNbInt——两者之间没有其他选择。对于Windows系统，long类型是32位的，因此对于更大的数字，将采用较慢的版本。 - ead

Answer 2

基本上，Paul Panzer的答案解释了发生了什么：在慢速list(...)版本中，列表的结果元素不是Python整数，而是numpy标量，例如numpy.int64。这个答案只是稍微详细说明了一下，并连接了一些点。

我没有进行系统的分析，但在调试器中停止时，每次两个版本都在创建整数对象的例程中，因此很可能大部分执行时间都花在这里，而开销并不起到很大的作用。 < p > list(..) 版本，迭代器调用 array_item ，它对一维数组有特殊处理，并调用 PyArray_Scalar ，这是一个非常通用的函数，不使用 Python 整数创建机制。 它比 Python 版本慢，也没有小值整数池。

.tolist()版本调用recursive_tolist，该函数最终使用Python的PyLong_FromLong(long)，它显示所有观察到的行为，并且比numpy功能更快（可能是因为这不是使用numpy的正常方式，没有进行太多优化）。

对于Python2和Python3有一点小差异：Python2有两个不同的整数类别：一个更高效，适用于32位以下的数字，另一个适用于任意大的数字 - 因此对于更大的数字必须采取最常规的（因此成本更高）路径 - 这也可以观察到。

- ead

Answer 3

使用list(something)构建一个列表，迭代something并将迭代结果收集到一个新的列表中。

如果list(small_np)比list(small_arr)慢，那么可以假设迭代small_np比迭代small_arr慢。让我们验证一下：

%timeit for i in small_np: pass   # 1 loop, best of 3: 916 ms per loop
%timeit for i in small_arr: pass  # 1 loop, best of 3: 261 ms per loop

是的，迭代numpy数组似乎更慢。这就是我必须开始推测的地方。Numpy数组很灵活。它们可以具有任意数量的维度和各种步幅。而数组则总是平坦的。这种灵活性可能会带来一些代价，表现为更复杂的迭代。

- MB-F

---

我不相信（没有进一步的证明）迭代因为步幅或类似原因而变慢。它可能会变慢，因为返回对象的创建速度较慢（问题是，为什么在这种情况下会出现这种情况）。 - ead

在迭代 numpy.ndarray 时，可能会迭代子数组，而在迭代 array.array 时始终会迭代元素。这将至少需要在 numpy 中进行额外的检查。 - MB-F

对于list(a)和a.tolist，通过查看源代码我们可以看出，list(a)会遵循迭代器协议，而a.tolist则使用简单的直接循环。似乎没有对array.array进行任何特殊处理（列表和元组是特殊情况），因此我认为这可能归结于迭代器的差异。 - Paul Panzer