Bonjour a tous,
 
J'ai un petit probleme de vitesse. Suffisament pour passer a un truc plus serieux, mais pas assez pour me mettre au C.
 
J'ai une liste de 10'000 vecteur 3D.
J'aurais besoin de calculer la norme entre chacun d'entre eux (ou une partie d'entre eux).
J'ai deja ma fonction norm().
 
Comment faire ca rapidement ?
 
Je l'ai fait comme ca:
 
(list_vecteur_short est un sous-ensemble reduit de list_vecteur (qui contient les 10'000 objet)).
 
for i in list_vecteur_short:
   for j in list_vecteur:
       norm(i, j)
 
Mais bon, c'est pas rapide et je soupconne qu'on peut aller plus vite.
 
Genre avec Numpy ? Mais je ne sais pas par ou commencer.
 
 
 
D'avance merci,    
Rasthor

petit up...

Essaye d'utiliser psyco déjà, c'est plus simple et sur des boucles serrées de calcul ça marche pas mal.
 
Ensuite numpy, mais il faut bien l'utiliser, à quoi ressemble ta fonction norm ?
 

bah, c'est bêtement la racine carrée de la somme des différences au carré (si mes souvenirs sont bons).
sqrt((x1-x2)**2 + (y1-y2)**2 + (z1-z2)**2)

T'as vraiment besoin de calculer la racine carrée pour ce que tu veux faire ?

En fait, faudrait plutôt que tu dises pourquoi tu as besoin de calculer ces normes. C'est quoi le but ? Si ça se trouve, il existe un algo performant pour faire ce que tu veux faire. Et avec de la chance, qq le connait.

C'est pour faire un truc comme ça:
http://www.biopython.org/DIST/docs [...] odule.html
 
http://www.biopython.org/DIST/docs [...] odule.html
 
 
Mais le KDTree n'est pas installable (problème de fiabilité je crois).

Donc tu veux chercher les vecteurs qui sont à une certaine distance les uns des autres, c'est ça ?
Visiblement, l'algo efficace est le KD tree (celui de ta lib), qui est une partition de l'espace qui te permet d'éviter la plupart des calculs de distance (pour lesquels tu n'es pas obligé de calculer la racine carrée, au passage).
Le premier lien Google est un papier exceptionnellement clair sur cette structure: http://citeseerx.ist.psu.edu/viewd [...] 1&type=pdf
http://www.inf.ed.ac.uk/teaching/c [...] 06-lec.pdf

Et Google "Python KD tree" retourne plusieurs implémentations en Python sur le net. T'as plus qu'à les essayer une à une. Le problème, c'est qu'en Python, ça sera de toute façon relativement lent, probablement de l'ordre de grandeur de 100x plus lent qu'une implémentation en C.
Apparemment la lib CGAL a un wrapper en Python.

 
Il n'a pas forcément besoin d'implémenter l'algo le plus efficace, et KD tree ne sera pas forcément le plus efficace en python (la complexité améliorée sera explosée par le coût des appels de fonctions et des indirections).
 
Par contre, éviter de faire ses boucles en python, faire des grands vecteurs ou matrices en numpy puis utiliser les fonctions d'algèbres linéaires, et ce sera un seul appel python pour la totalité de ses vecteurs. Le gros du calcul sera entièrement en C, et profitera des libs de calcul existantes (BLAS par ex.), qui sont sacrément difficile à battre pour un dev C débutant.

Oui, tout dépend du nombre de couples de points à comparer.S"il n'y a qu'un ou deux points à comparer à tous les autres, ça ne vaut pas le coup. Si par contre cette recherche de plus proche voisin est très répétitive, l'algo de KD tree est gagnant.

Cela va de soi.

Bon, merci pour vos informations.
 
Me demande si je ne vais pas me mettre au C, pour le fun.

Le problème que je vois ce sont tes boucles imbriquées, avec une absence de parallélisme alors que les calculs de normes sont indépendants les uns des autres et pourraient tirer parti d'un GPU, d'un CPU multicore ou de multiples CPU.
 
L'autre problème est certainement le surcout du python: l'utilisation de psyco et de NumPy pourrait arranger ce problème.
 
L'utilisation d'un GPU permettrait à mon sens d'atteindre les meilleures perfs, c'est typiquement le genre de calcul adapté aux GPUs.

Si j'ai 10'000 points, tirer parti d'un multi-cpu ne baissera que d'un facteur 4, 8 ou 16.
 
Par contre, en GPU, ça pourrait effectivement être plus intéressant.  

SciPy (qui repose sur Numpy donc C ) implémente KDTree : http://docs.scipy.org/doc/scipy/reference/spatial.html

Tu cherche à faire de la classification ?