Discussion :

[Gantz007]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !!

[wiztricks]

Salut,

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 ?

Vous avez d'abord un problème d'algorithme. Et la bonne rubrique pour çà est algorithmique. C'est l'algorithme qui va imposer des structures de données et des bibliothèques adaptées.

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...

La complexité d'un algorithme n'est pas un "truc": çà se calcule et c'est indépendant du langage.

- W

[lg_53]

Et même dans le cas où votre algorithme serait bon, vous n'utiliser quasiment rien de numpy et donc vous en tuez toutes les performances...

Il faut éviter les boucles for, ne pas se servir de min mais de np.min, ne pas réinventer une fonction distance puisque np.norm existe (ou à la rigueur se contenter d'écrire X**2+Y**2, pour trouver le min sur la norme au carré, ce qui évite d'avoir à appliquer la racine carré dans le calcul de la distance) ...

Avant de parler performance, commencez sur un cas bateau avec 3 ou 4 points dans chaque liste seulement et vérifier que vous obtenez le résultat attendu. Notez que vous n'avez pas nécéssairement (à priori) la meme taille pour A et B.

[Bktero]

L'algo ci-dessus fonctionne mais peut être très long

C'est combien très long ?

Quand on veut optimiser un code, il faut faire des mesures de temps à chaque modification pour voir les impacts.

Il faut aussi une cible : "le plus rapidement possible" est des fois ce qu'on cherche, mais pas toujours.

[Gantz007]

Bonjour,

Vous avez d'abord un problème d'algorithme. Et la bonne rubrique pour çà est algorithmique. C'est l'algorithme qui va imposer des structures de données et des bibliothèques adaptées.
- W

Effectivement c'est ce que je devrais faire plutôt que d'essayer de trouver une fonction ou module magique en python. Regarder comment je pourrais améliorer ca avec des algo type tri, plus proche voisin, etc. DSL pour la mauvaise rubrique, j'ai pas trouvé comment changer de catégorie le post.

l faut éviter les boucles for, ne pas se servir de min mais de np.min, ne pas réinventer une fonction distance puisque np.norm existe (ou à la rigueur se contenter d'écrire X**2+Y**2, pour trouver le min sur la norme au carré, ce qui évite d'avoir à appliquer la racine carré dans le calcul de la distance) ...
Avant de parler performance, commencez sur un cas bateau avec 3 ou 4 points dans chaque liste seulement et vérifier que vous obtenez le résultat attendu. Notez que vous n'avez pas nécéssairement (à priori) la meme taille pour A et B.

Oui j'utilise bien le np.min mais effectivement la racine carré était inutile dans mon cas. Je me suis bien sur limité à quelques points sur la matrice A pour faire mes tests.

C'est combien très long ?

De l'ordre de l'heure voir 2 pour comparer 80 000 points à 4 000 000 de points mais je ne suis pas allé au bout (et il me faudra comparer des millions à d'autres millions!). Là je suis à 7s pour comparer 100 points (A) à 4 000 000 (B). En fait je cherche à faire ce que font plus rapidement les SIG. Mais comme le dit wiztricks, c'est un problème d'algorithme avant tout et pas de python -> Post à changer de catégorie

[wiztricks]

Mais comme le dit wiztricks, c'est un problème d'algorithme avant tout et pas de python -> Post à changer de catégorie

Parfois on peut pousser une discussion dans un autre forum sans soucis. Parfois, il est clair que vous ne formuleriez pas questions et problèmes de la même façon qu'en le postant directement dans un forum Algorithme....
Et c'est certainement pas la modération qui va reformuler votre problème pour qu'il soit un peu plus comestible par ceux qui vous liront.

- W

[Gantz007]

Et c'est certainement pas la modération qui va reformuler votre problème pour qu'il soit un peu plus comestible par ceux qui vous liront.

Je ne le demandais pas. Il faut certainement que je reformule en effet. Sur ce, je m'en vais sur d'autres forums.

[Gantz007]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.