两个类似的实现退出了运行时间的巨大差异

Question

我在这里尝试了基本的cython教程，看看加速有多重要。我还制作了两个不同的python实现，它们在运行时有很大的不同。我已经测试了差异的运行时间，据我所见，它们并不能解释整个运行时间的差异。

代码正在计算第一个kmax素数：

def pyprimes1(kmax):
p=[]
result = []
if kmax > 1000:
kmax = 1000
k = 0
n = 2
while k < kmax:
i = 0
while i < k and n % p[i] != 0:
i = i + 1
if i == k:
p.append(n)
k = k + 1
result.append(n)
n = n + 1
return result
def pyprimes2(kmax):
p=zeros(kmax)
result = []
if kmax > 1000:
kmax = 1000
p=zeros(kmax)
k = 0
n = 2
while k < kmax:
i = 0
while i < k and n % p[i] != 0:
i = i + 1
if i == k:
p[k] = n
k = k + 1
result.append(n)
n = n + 1
return result  

正如您所看到的，这两种实现之间的唯一区别在于p变量的使用，第一种是python列表，另一种是numpy数组。我使用了IPython%timeit魔术来测试计时。你认为谁表现得更好？这是我得到的：

%timeit pyprimes1(1000)
10 loops, best of 3: 79.4 ms per loop
%timeit pyprimes2(1000)
1 loops, best of 3: 1.14 s per loop

这很奇怪，也很令人惊讶，因为我认为预分配的numpy数组可能会更快，并且实现C。

我还测试了：阵列分配：

%timeit p[100]=5
10000000 loops, best of 3: 116 ns per loop

阵列选择：

%timeit p[100]
1000000 loops, best of 3: 252 ns per loop

速度慢了一倍。。也没想到。阵列初始化：

%timeit zeros(1000)
1000000 loops, best of 3: 1.65 µs per loop

列表附加：

%timeit p.append(1)
10000000 loops, best of 3: 164 ns per loop

列表选择：

%timeit p[100]
10000000 loops, best of 3: 56 ns per loop

因此，列表选择似乎比数组选择快5倍。我看不出这些数字是如何加起来超过10倍的时差的。当我们在每次迭代中进行选择时，它只快了5倍。

将给出关于数组和列表之间的时间差以及两种实现之间的总体时间差的解释。还是我在增加长度列表中测量时间时使用%timeit错误？

顺便说一句，cython代码在3.5ms时表现最好。

Answer 1

第1000个素数是7919。因此，如果内部循环平均迭代kmax/2次(非常粗略)，您的程序将从数组/列表中执行大约7919*(1000/2)~=4*10⁶的选择。如果从第一个版本的列表中进行单个选择需要56 ns，则即使是这些选择也不适合79 ms(0.056µs*4*10⁶~=0.22秒)。

也许这些纳秒时间不是很准确。

顺便说一下，append的性能取决于列表的大小。在某些情况下，它可能会导致重新分配，但在大多数情况下，列表有足够的可用空间，而且速度极快。

Answer 2

Numpy的主要用例是对整个数组和切片执行操作，而不是对单个元素执行操作。这些操作是用C语言实现的，因此比等效的Python代码快得多。例如，

c = a + b

将比快得多

for i in xrange(len(a)):
c[i] = a[i] + b[i]

即使在这两种情况下变量都是CCD_ 3阵列。

然而，像您正在测试的单元素操作可能比Python列表更糟糕。Python列表是结构的纯C数组，访问起来非常简单。

另一方面，访问numpy数组中的元素会带来大量开销，以支持多种原始数据格式和高级索引选项等原因。