Une liste -> comparer chaque élément avec chaque élément

Bonjour !
Sous ce titre un peu étrange, se cache un problème simple.
Pour vous situer le contexte, j'essaye de créer un importeur d'objets 3D Wavefront dans un visualisateur OpenGL créé avec OpenTK. Je vous passe les détails, mais à un moment, j'ai une liste de Vertex (qui peut être très grande).
Pour chaque vertex, je dois comparer sa position avec tous les autres vertex de la liste.
Pour y arriver, j'utilise deux boucles For imbriquées et je teste la position avec un pseudo-code du style:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

For i As Integer = 0 To groupVertices.Count - 1 For j As Integer = 0 To groupVertices.Count - 1 If Not i = j Then If groupVertices(i).Position.Equals(groupVertices(j).Position) Then 'les vecteurs de position des deux vertex est identique 'quelques autres calculs peuvent être faits ici End If End If Next Next

---

Tout fonctionne comme espéré ... quand la liste contient peu d'éléments, mais ma liste peut contenir plus de 20000 éléments !!!
Et là, c'est l'horreur. Cette méthode met plus de 20 secondes à tout parcourir, même si je ne fait aucun calcul complexe (à la place des commentaires).

Est-ce qu'il existe un moyen plus rapide pour faire ce genre de comparaison ?

Merci d'avance pour vos idées.

Bonjour,

Avec groupVertices.equals ?
Ou groupVertices.Where ?

Il faut diminuer la plage de recherche à chaque tour, car une fois que l'on a testé un élément avec tous les autres on peut l'exclure le coup d'après.

Si par exemple au premier tour tu testes avec i=0 et j=1. Le coup d'après pas la peine de tester i=1 et j=0 puisque c'est déjà fait.

Code:

---

1 2 3 4 5 6 7 8

For i As Integer = 0 To groupVertices.Count - 2 For j As Integer = i + 1 To groupVertices.Count - 1 If groupVertices(i).Position.Equals(groupVertices(j).Position) Then 'les vecteurs de position des deux vertex est identique 'quelques autres calculs peuvent être faits ici End If Next Next

---

Bonjour Geo2A et StormimOn

J'utilise "Equals" pour comparer des "Vector3" (un vecteur contenant 3 Single).

Merci beaucoup pour l'idée StormimOn ! :ccool: Effectivement, ça serait bien plus simple comme ça et en plus, plus simple que mon idée de départ.
Par contre, autant je comprends le principe, autant j'ai du mal à imaginer les étapes des boucles imbriquées avec les itérations comme tu les as écrites.

Ce n'est pas bien grave, j'ai compris le principe, je vais essayer d'implémenter ça moi même.

Merci beaucoup ;)

Je reviens dans le coin pour parler de mes différents tests, mais surtout pour te dire un grand merci StormimOn :ccool:

Cette méthode est plus que 2x plus rapide !!
Il me semble avoir compris le truc des indices d'itération. Je trouve la syntaxe moins explicite, mais bien astucieuse. Si je comprends bien le "i+1" (dans la boucle interne) permet de ne pas retester le "i" de la boucle externe, et comme on rajoute 1 à "i" dans la boucle interne, on doit aller jusqu'à "count - 2" dans la boucle externe pour ne pas dépassé le maxi.

C'est bien ça ?
J'ai horreur de copier un code sans l'avoir compris.


Sinon j'ai essayé de faire un petit programme pour tester mes différentes méthodes, et j'ai pu remarquer que tester l'égalité de vecteurs avec "Equals" est beaucoup plus lent (environ 2x plus lent) que de le tester avec une fonction de mon cru toute bête du genre:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Private Function IsVector3Equals(ByVal vec1 As Vector3, ByVal vec2 As Vector3) As Boolean Dim isXequal As Boolean = False Dim isYequal As Boolean = False Dim isZequal As Boolean = False   If vec1.X = vec2.X Then isXequal = True End If If vec1.Y = vec2.Y Then isYequal = True End If If vec1.Z = vec2.Z Then isZequal = True End If   If isXequal AndAlso isYequal AndAlso isZequal Then Return True Else Return False End If   End Function

---

y'a-t-il une raison à cela? est-ce que "Equals" fait d'autres tests?

sinon, avec ma méthode, sur une liste de 3000 éléments:
-avec ma méthode et le vrai Equals: 9000000 comparaisons pour 2400 milliseconds.
-avec ma méthode et mon Equals: 9000000 comparaisons pour 1400 ms
-avec ta méthode et mon Equals: 4498500 comparaisons pour 433 ms !

C'est vraiment le genre de tests que je ne fais jamais en tant que programmeur amateur, mais ça montre bien l'importance d'utiliser des méthodes adéquates.