Sản phẩm chấm của hai vectơ n chiều u=[u1,u2,...un]
và v=[v1,v2,...,vn]
được cho bởi u1*v1 + u2*v2 + ... + un*vn
.Sản phẩm chấm được tối ưu hóa trong Python
Câu hỏi posted yesterday khuyến khích tôi tìm cách nhanh nhất để tính toán các sản phẩm chấm trong Python chỉ sử dụng thư viện chuẩn, không có mô-đun bên thứ ba hoặc C/Fortran/C++.
Tôi đã định thời gian bốn phương pháp khác nhau; cho đến nay nhanh nhất có vẻ là sum(starmap(mul,izip(v1,v2)))
(trong đó starmap
và izip
đến từ mô-đun itertools
).
Đối với mã trình bày dưới đây, đó là những lần trôi qua (tính bằng giây, cho một triệu chạy):
d0: 12.01215
d1: 11.76151
d2: 12.54092
d3: 09.58523
bạn có thể nghĩ ra một cách nhanh hơn để làm điều này?
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()
Lưu ý rằng tên của tệp phải là dot_product.py
để chạy tập lệnh; Tôi đã sử dụng Python 2.5.1 trên Mac OS X Phiên bản 10.5.8.
EDIT:
Tôi chạy kịch bản cho N = 1000 và đây là những kết quả (tính bằng giây, cho một triệu chạy):
d0: 205.35457
d1: 208.13006
d2: 230.07463
d3: 155.29670
Tôi đoán nó là an toàn để giả định rằng, thực sự , tùy chọn ba là nhanh nhất và lựa chọn hai chậm nhất (trong số bốn trình bày).
@Arrieta: Bạn có thể xóa yêu cầu rằng tệp được gọi là dot_product.py bằng cách thay thế 'từ dot_product' bằng 'từ __main__'. – unutbu
@unutbu: Chắc chắn, tôi chỉ nghĩ đơn giản hơn là lưu tệp với tên đó để chạy nhanh hơn là thay đổi tập lệnh. Cảm ơn bạn. – Escualo
Kết quả của tôi là: d0 đã trôi qua: 13.4328830242 d1 đã trôi qua: 9.52215504646 d2 đã trôi qua: 10.1050257683 d3 trôi qua: 9.16764998436 Hãy chắc chắn kiểm tra xem sự khác biệt giữa d1 và d3 có ý nghĩa thống kê hay không. – liori