解释大型运行时变化

Question

我有点困惑于下面的分析结果，并希望听到一些解释，以使他们的意义。我想我会把内部产品作为一个简单的函数来比较不同的可能实现：

import numpy as np

def iterprod(a,b):
    for x,y in zip(a,b):
        yield x*y

def dot1(a,b):
    return sum([ x*y for x,y in zip(a,b) ])

def dot2(a,b):
    return sum(iterprod(a,b))

def dot3(a,b):
    return np.dot(a,b)

第一个实现dot1是一个“幼稚”的实现，我们首先创建一个新的成对产品列表，然后对其元素求和。我认为第二个实现dot2会更聪明一些，因为它消除了创建新列表的需要。第三个实现dot3使用Numpy的dot函数。你知道吗

为了分析这些函数，我使用以下方法：

import timeit

def showtime( fun, a, b, rep=500 ):
    def wrapped():
        return fun(a,b)
    t = timeit.Timer( wrapped )
    print( t.timeit(rep) )

---

场景1:Python列表

import random
n = 100000

a = [ random.random() for k in range(n) ]
b = [ random.random() for k in range(n) ]

showtime( dot1, a, b )
showtime( dot2, a, b )
showtime( dot3, a, b )

输出：

3.883254656990175
3.9970695309893927
2.5059548830031417

所以“更聪明”的实现dot2实际上比幼稚的实现dot1性能差，而且Numpy比两者都快得多。但是。。你知道吗

场景2:Python数组

我想也许使用一个数字容器，比如array，可以在引擎盖下实现某些优化。你知道吗

import array
a = array.array( 'd', a )
b = array.array( 'd', b )

showtime( dot1, a, b )
showtime( dot2, a, b )
showtime( dot3, a, b )

输出：

4.048957359002088
5.460344396007713
0.005460165994009003

没有。如果说有什么不同的话，它使纯Python实现的情况变得更糟，突出了“naive”和“smart”版本之间的区别，现在Numpy的速度快了3个数量级！你知道吗

---

问题

问题1。我能理解这些结果的唯一方法是，如果Numpy在场景1中处理数据之前确实复制了数据，而在场景2中它只“指向”数据，这听起来合理吗？你知道吗

问题2。为什么我的“智能”实现系统性地比“幼稚”实现执行得慢？如果我对Q1的预感是正确的，那么如果sum在引擎盖下做了一些聪明的事情，那么创建一个新数组就完全有可能更快。是这样吗？你知道吗

问题3。三个数量级！这怎么可能？我的实现是真的很愚蠢，还是有一些神奇的处理器指令来计算点积？你知道吗

Answer 1

Q1

Python列表包含指向Python对象的指针，而数组直接包含这些数字。然而，底层numpy代码期望它是一个连续数组。因此，当传递一个列表时，它必须将浮点值读入列表中每个元素的新数组。你知道吗

正如评论中提到的，使用numpy的内置数组更好。你知道吗

Q2

从生成器中获取值（从内存中）比python函数调用要便宜得多。这比列表理解要昂贵得多，列表理解除了x*y之外的所有内容都在解释器内部处理。必须制作一份清单，这是昂贵的，但这一成本似乎很快就被量化了。你知道吗

问题3

Numpy的magnitued速度快了三个数量级，因为它是建立在高度优化的底层库之上的。根据使用的后端，它甚至可能使用多个线程。Python必须处理大量的开销，以使程序员在每一步都能更轻松地完成任务，所以这真的不是一场公平的竞赛。你知道吗

奖金

我提出了我的生成器建议，因为通常构造列表的开销很大。但是，在这种情况下，似乎列表上的sum（）比迭代器上的sum（）快，这是没有实际意义的。你知道吗

Answer 2

生成器/屈服机制确实需要一些CPU周期。当您不想一次完成整个序列时，它为您节省的是内存，或者当您想交错几个相关计算以降低序列中第一个项的延迟时间时，它会有所帮助。你知道吗

对数组使用numpy函数只允许它在连续的内存块上运行常规的C代码，而不必从列表中的指针中取消对float对象的引用。所以它变得非常快（这就是numpy的要点）。你知道吗