Calculs sur de grandes matrices
Bonjour,
Alors je me trouve dans le cas où je veux comparer chaque élément d'une première liste à chaque élément d'une deuxième liste afin de faire des stats. Sauf que le nombre d'éléments à comparer est potentiellement énorme !
Concrètement, mes 2 listes sont des matrices 2 colonnes contenant les coordonnées XY de nombreux points. Je chercher à calculer la distance entre chaque point de la liste A avec chaque point de la liste B afin de trouver, pour chaque point de A, la distance minimale avec B.
De façon simple en travaillant avec numpy et en simplifiant :
Code:
1
2
3
4
5
| for i in range(len(A)):
#La jextrai les difference en X et Y pour calculer la distance :
xdiff= A[i,0]-B[:,0] #la ja une liste de differences en X entre le ieme point de A et tous les points de B
ydiff= A[i,1]-B[:,1] #idem en Y
distanceMini=min(distance(xdiff, y diff)) # "distance" est une fonction qui va calculer la distance entre les 2 points a partir des difference de coordonnees X, Y. |
L'algo ci-dessus fonctionne mais peut être très long dès lors que les matrice A et/ou B contiennent des dizaines de milliers de points. J'ai fait pas mal de recherche sur google pour trouver d'autres façons (thread, multiprocessing, map, etc.) mais je n'arrive pas à optimiser ces calculs.
D'où ma question : avez-vous des fonctions, modules, algo à me conseiller pour faire ce genre de calculs sur un grand nombre de points en python ?
J'ai l'impression que c'est un truc de base mais vraiment je suis bloqué ! Je précise que je débute en python...
Merci d'avance !!
Recherche du plus proche voisin
Bonjour,
Après avoir codé des algorithmes de tri et différentes possibilités offertes par numpy (jusqu'à gagner un facteur 10 sur le temps de calcul), j'ai finit par trouver ce que je cherchais dans la librairie SciPy : scipy.spatial.cKDTree qui est une implémentation de l'algorithme de recherche des plus proches voisins de Maneewongvatana et Mount (1999).
Pour faire court :
Code:
1
2
3
4
5
6
7
8
9
|
Import scipy.spatial
def findPlusProcheVoisin(matriceA,MatriceB,rayonDeRechercheVoulu):
arbre=scipy.spatial.cKDTree(MatriceB)
distance,indices=arbre.query(matriceA,k=1,distance_upper_bound=rayonDeRechercheVoulu)
return indices
indicesRecherches=findPlusProcheVoisin(A,B,2) |
De cette façon on récupère, pour chaque point XY de A, l'indice du plus proche voisin dans B.
distance_upper_bound permet de limiter le rayon de recherche (mis à 2 dans le cas présenté). Attention, dans le cas où un point de A est à une distance de tout point de B supérieure à distance_upper_bound, le query renvoi une distance infinie et un indice égal à la taille de la matrice B en entrée.
Pour info j'ai divisé le temps de calcul sur plusieurs millions de points par environ 250 en utilisant cKDTree.
Pour finir, un post intéressant sur cette problématique.
