Produit scalaire optimisé en Python

Question

Le produit scalaire de deux vecteurs n-dimensionnels u=[u1,u2,...un] et v=[v1,v2,...,vn] est donné par u1*v1 + u2*v2 + ... + un*vn.

Une question posted yesterday m'a encouragé à trouver le moyen le plus rapide de calculer des produits scalaires en Python en utilisant seulement la bibliothèque standard, pas de modules tiers ou des appels C/Fortran/C++.

J'ai chronométré quatre approches différentes; jusqu'à présent, le plus rapide semble être sum(starmap(mul,izip(v1,v2))) (où starmap et izip proviennent du module itertools).

Pour le code présenté ci-dessous, ce sont les temps écoulés (en quelques secondes, pour un million de courses):

d0: 12.01215 
d1: 11.76151 
d2: 12.54092 
d3: 09.58523 

Pouvez-vous penser à une façon plus rapide de le faire?

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() 

Notez que le nom du fichier doit être dot_product.py pour le script à exécuter; J'ai utilisé Python 2.5.1 sur Mac OS X Version 10.5.8.

EDIT:

J'ai couru le script N = 1000 et ceux-ci sont les résultats (en secondes, pour un million de courses):

d0: 205.35457 
d1: 208.13006 
d2: 230.07463 
d3: 155.29670 

Je pense qu'il est raisonnable de supposer que, en effet , l'option trois est la plus rapide et l'option deux la plus lente (sur les quatre présentées).

Answer 1

Juste pour le fun j'ai écrit un "d4" qui utilise numpy:

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

Mes résultats (Python 2.5.1, XP Pro sp3, 2GHz Core 2 Duo T7200):

d0 elapsed: 12.1977242918 
d1 elapsed: 13.885232341 
d2 elapsed: 13.7929552499 
d3 elapsed: 11.0952246724 

d4 écoulé: 56.3278584289 # va numpy!

Et, pour encore plus de plaisir, je me tournai sur psyco:

d0 elapsed: 0.965477735299 
d1 elapsed: 12.5354792299 
d2 elapsed: 12.9748163524 
d3 elapsed: 9.78255448667 

d4 écoula: 54,4599059378

Sur cette base, je déclare D0 le gagnant :)

---

Mettre à jour

@kaiser.se: Je devrais probablement avoir dit que je ne convertissait tout à numpy tableaux premier:

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") 

Et je compris check(v1, v2) car il est inclus dans les autres tests. Le laisser de côté donnerait un avantage injuste (bien qu'il semble qu'il pourrait en utiliser un). La conversion du tableau s'est réduite d'environ une seconde (beaucoup moins que je ne le pensais).

Tous mes tests ont été exécutés avec N = 50.

@nikow: J'utilise numpy 1.0.4, qui est sans doute vieux, il est certainement possible qu'ils aient amélioré leurs performances depuis un an et demi depuis que je les ai installés.

---

Mise à jour # 2

@ kaiser.se Wow, vous êtes tout à fait raison. Je devais penser que c'étaient des listes de listes ou quelque chose (je n'ai vraiment aucune idée de ce que je pensais ... +1 pour la programmation en binôme).

Comment ce regard:

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

Nouveaux résultats:

d4 elapsed: 3.22535741274 

Avec Psyco:

d4 elapsed: 2.09182619579 

D0 gagne encore avec Psyco, mais numpy est probablement mieux dans l'ensemble, en particulier avec des ensembles de données plus volumineux.

Hier, j'étais un peu dérangé mon résultat lent numpy, puisque vraisemblablement numpy est utilisé pour beaucoup de calcul et a eu beaucoup d'optimisation. Évidemment, cependant, pas assez dérangé pour vérifier mon résultat :)

Answer 2

Je ne sais pas plus vite, mais je vous suggère:

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

il est beaucoup plus facile à lire et ne nécessite même pas des modules standard bibliothèque.

Answer 3

Voici une comparaison avec numpy. Nous comparons l'approche Starmap rapide avec numpy.dot

D'abord, l'itération sur les listes Python normales:

$ 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 

Puis 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 

Voyant cela, il semble numpy sur les tableaux numpy est le plus rapide, suivi de constructions fonctionnelles python travaillant avec des listes.

Answer 4

Veuillez comparer cette fonction "d2a" et la comparer à votre fonction "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 (sur Python 2.x, qui est ce que je suppose que vous utilisez) crée inutilement une liste fictive avant le calcul.