Discussion :

[Norris]

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 :

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

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.

[Geo2A]

Bonjour,

Avec groupVertices.equals ?
Ou groupVertices.Where ?

[StormimOn]

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 :

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

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

[Norris]

Bonjour Geo2A et StormimOn

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

Merci beaucoup pour l'idée StormimOn ! 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

[Norris]

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

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 :

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

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.