0x90 → | el muchacho a écrit :
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. ---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
|