Python中的優化點積

Question

兩個n維向量u=[u1,u2,...un]和v=[v1,v2,...,vn]的點積由u1*v1 + u2*v2 + ... + un*vn給出。

posted yesterdayposted yesterday這個問題鼓勵我找到使用標準庫，沒有第三方模塊或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 

我想這是安全的假設，的確，選項三是最快的，選項二是最慢的（提出的四個）。

Answer 1

只是爲了好玩，我寫了 「D4」，它採用numpy的：

from numpy import dot 
def d4(v1, v2): 
    check(v1, v2) 
    return dot(v1, v2) 

我的結果（Python的2.5.1，XP專業版SP3，2GHz的酷睿雙核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)因爲它包含在其他測試。離開它會給不公平的優勢（儘管看起來它可以使用一個）。數組轉換削減了大約一秒（比我想象的要少得多）。

我所有的測試都運行N = 50。

@nikow：我使用的是numpy 1.0.4，這無疑是舊的，它肯定有可能在我安裝它之後的一年半內改進了性能。

---

更新＃2

@ kaiser.se哇，你是完全正確的。我一直認爲這些是列表或其他東西（我真的不知道我在想什麼...... +1配對編程）。

這個怎麼樣：

v3 = array(v1) 
v4 = array(v2) 

新的結果：

d4 elapsed: 3.22535741274 

隨着Psyco是：

d4 elapsed: 2.09182619579 

D0與Psyco的還是贏了，但numpy的可能是更好的整體，尤其是具有更大的數據集。

昨天我有點困擾我慢numpy的結果，因爲據推測numpy的用於計算的很多並且已經有很多的優化。很顯然，沒有足夠的檢查我的結果:)

Answer 2

我不知道快，但我建議：

sum(i*j for i, j in zip(v1, v2)) 

它更容易閱讀，甚至不需要標準庫模塊。

Answer 3

這是一個比較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函數結構。

Answer 4

請對此「d2a」功能進行基準測試，並將其與「d3」功能進行比較。

from itertools import imap, starmap 
from operator import mul 

def d2a(v1,v2): 
    """ 
    d2a uses itertools.imap 
    """ 
    check(v1,v2) 
    return sum(imap(mul, v1, v2)) 

map（關於Python 2.x中，這是我假設你使用）不必要創建之前計算的虛擬目錄。