Esc*_*alo 12 python algorithm math
两个n维向量的点积u=[u1,u2,...un]和v=[v1,v2,...,vn]被由下式给出u1*v1 + u2*v2 + ... + un*vn.
昨天发布的一个问题鼓励我找到使用标准库,没有第三方模块或C/Fortran/C++调用来在Python中计算点积的最快方法.
我计时了四种不同的方法; 到目前为止,最快的似乎是sum(starmap(mul,izip(v1,v2)))(来自模块的地方starmap和izip来自itertools).
对于下面给出的代码,这些是经过的时间(以秒为单位,一百万次运行):
d0: 12.01215
d1: 11.76151
d2: 12.54092
d3: 09.58523
你能想到更快的方法吗？
import timeit # module with timing subroutines
import random # module to generate random numnbers
from itertools import imap,starmap,izip
from operator import mul
def v(N=50,min=-10,max=10):
"""Generates a random vector (in an array) of dimension N; the
values are integers in the range [min,max]."""
out = []
for k in range(N):
out.append(random.randint(min,max))
return out
def check(v1,v2):
if len(v1)!=len(v2):
raise ValueError,"the lenght of both arrays must be the same"
pass
def d0(v1,v2):
"""
d0 is Nominal approach:
multiply/add in a loop
"""
check(v1,v2)
out = 0
for k in range(len(v1)):
out += v1[k] * v2[k]
return out
def d1(v1,v2):
"""
d1 uses an imap (from itertools)
"""
check(v1,v2)
return sum(imap(mul,v1,v2))
def d2(v1,v2):
"""
d2 uses a conventional map
"""
check(v1,v2)
return sum(map(mul,v1,v2))
def d3(v1,v2):
"""
d3 uses a starmap (itertools) to apply the mul operator on an izipped (v1,v2)
"""
check(v1,v2)
return sum(starmap(mul,izip(v1,v2)))
# generate the test vectors
v1 = v()
v2 = v()
if __name__ == '__main__':
# Generate two test vectors of dimension N
t0 = timeit.Timer("d0(v1,v2)","from dot_product import d0,v1,v2")
t1 = timeit.Timer("d1(v1,v2)","from dot_product import d1,v1,v2")
t2 = timeit.Timer("d2(v1,v2)","from dot_product import d2,v1,v2")
t3 = timeit.Timer("d3(v1,v2)","from dot_product import d3,v1,v2")
print "d0 elapsed: ", t0.timeit()
print "d1 elapsed: ", t1.timeit()
print "d2 elapsed: ", t2.timeit()
print "d3 elapsed: ", t3.timeit()
请注意,文件的名称必须是dot_product.py脚本运行的; 我在Mac OS X版本10.5.8上使用了Python 2.5.1.
编辑:
我运行N = 1000的脚本,这些是结果(以秒为单位,运行一百万次):
d0: 205.35457
d1: 208.13006
d2: 230.07463
d3: 155.29670
我想可以安全地假设,实际上,选项三是最快的,选项二是最慢的(四个中提到的).
为了好玩,我写了一个使用numpy的"d4":
from numpy import dot
def d4(v1, v2):
check(v1, v2)
return dot(v1, v2)
我的结果(Python 2.5.1,XP Pro sp3,2GHz Core2 Duo T7200):
d0 elapsed: 12.1977242918
d1 elapsed: 13.885232341
d2 elapsed: 13.7929552499
d3 elapsed: 11.0952246724
d4逝去了:56.3278584289#去numpy!
而且,为了更有趣,我打开了psyco:
d0 elapsed: 0.965477735299
d1 elapsed: 12.5354792299
d2 elapsed: 12.9748163524
d3 elapsed: 9.78255448667
d4逝去时间:54.4599059378
基于此,我宣布d0为胜利者:)
更新
@ kaiser.se:我可能应该首先提到我确实将所有内容转换为numpy数组:
from numpy import array
v3 = [array(vec) for vec in v1]
v4 = [array(vec) for vec in v2]
# then
t4 = timeit.Timer("d4(v3,v4)","from dot_product import d4,v3,v4")
我包括在内,check(v1, v2)因为它包含在其他测试中.离开它会给numpy一个不公平的优势(虽然看起来它可以使用一个).数组转换削减了大约一秒钟(比我想象的要少得多).
我的所有测试均以N = 50运行.
@nikow:我正在使用numpy 1.0.4,这无疑是旧的,它确实有可能在我安装它的过去一年半的时间里提高了性能.
@ kaiser.se哇,你完全正确.我一定以为这些是列表或者其他东西(我真的不知道我在想什么......对于编程来说+1).
这看起来如何:
v3 = array(v1)
v4 = array(v2)
新结果:
d4 elapsed: 3.22535741274
使用Psyco:
d4 elapsed: 2.09182619579
d0仍然赢得Psyco,但numpy可能总体上更好,特别是对于更大的数据集.
昨天我有点困扰我缓慢的numpy结果,因为可能numpy用于大量的计算并且有很多优化.显然,不要打扰我的结果:)
这是与numpy的比较。我们将快速星图方法与numpy.dot
首先，通过普通的Python列表进行迭代：
$ python -mtimeit "import numpy as np; r = range(100)" "np.dot(r,r)"
10 loops, best of 3: 316 usec per loop
$ python -mtimeit "import operator; r = range(100); from itertools import izip, starmap" "sum(starmap(operator.mul, izip(r,r)))"
10000 loops, best of 3: 81.5 usec per loop
然后是numpy ndarray：
$ python -mtimeit "import numpy as np; r = np.arange(100)" "np.dot(r,r)"
10 loops, best of 3: 20.2 usec per loop
$ python -mtimeit "import operator; import numpy as np; r = np.arange(100); from itertools import izip, starmap;" "sum(starmap(operator.mul, izip(r,r)))"
10 loops, best of 3: 405 usec per loop
看到这一点，似乎在numpy数组上执行numpy最快，其次是使用列表的python函数构造。