Discussion :

[Jayme65]

Bonjour,

J'ai une liste d'objet

Code :

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

Public romIndex As New List(Of Games)

Voici classe objet 'game' dans laquelle j'ai intégré une fonction de comparaison basée sur 'descript'.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Public Class Games
    Public Shared ReadOnly DescriptComparer As New DescriptComparerClass
    Public rom As String
    Public descript As String
    Public genre As String
    Sub New()
    End Sub
    Public Class DescriptComparerClass
        Implements IComparer(Of Games)
        Public Function Compare(ByVal x As Games, ByVal y As Games) As Integer Implements System.Collections.Generic.IComparer(Of Games).Compare
            Return String.Compare(x.descript, y.descript, True)
        End Function
    End Class
End Class

Ce qui me permet de faire du tri et BinarySearch basé sur 'descript' dans la liste

Code :

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

1
2
3
4
5
6
7
romIndex.Sort
Dim ng As New Games
ng.descript = "test"
Dim ndx As Int32 = romIndex.BinarySearch(0, romIndex.Count, ng, Games.DescriptComparer)
If ndx >= 0 Then
   Debug.Print ("Trouvé")
End If

Alors, voila ma question:
=================

Comment pourrais-je faire une recherche dans la liste en partant uniquement des lettres du début du string. Donc pour reprendre l'exemple, trouver dans la liste le premier élément qui commencerait par "Te" (et qu'il me trouve "Test").

Pour l'instant j'ai simplement une boucle, mais je voudrais quelque chose de plus abouti car cela concerne des dizaines de milliers d'éléments et je sais qu'il doit y avoir plus performant que ma boucle

Code :

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

1
2
3
4
5
6
7
For Each ri As Games In romIndex
 If ri.descript.ToUpper.StartsWith(texteàtrouver) Then
  ...
  ...
  Exit For
 End If
Next

Que puis je utiliser (et comment) qui ait la même "rapidité" qu'un BinarySearch (sur le string complet) avec uniquement le début d'un string?



J'espère que j'ai pu me faire comprendre ;-) et je vous remercie d'avance de l'aide que vous voudrez bien m'apporter

[mactwist69]

Bonjour,

D'abord, la liste de tes jeux... tu la charge depuis une base de données ? Auquel cas une requête sera beaucoup plus rapide.

si pas de base de données, alors j'imagine que tu vas stockés tes informations dans un ou plusieurs fichier que tu vas chargé dans le programme.

Dans ce cas là, oui il y a plus rapide qu'une boucle: Trié tes jeux par ordre alphabétique sur la description, et faire une recherche dichotomique.

[Jayme65]

mactwist69,
Merci pour ta réponse!
Non, la liste des éléments à afficher est en mémoire.
Et oui, les éléments sont déjà trié ('romIndex.Sort' dans le code posté) et trié sur '.descript' de la classe 'Games'..
Ce que je voudrais maintenant c'est faire une recherche sur le premier éléments qui commence par les quelques lettres du début.
En clair, si dans ma 'list(of Games)' j'ai des élément dont la propriété '.descript' = "TestA", "TestB", TostA", TostB",
je veux pouvoir, si j'entre "Te", trouver le premier, à savoir "TestA" et avoir son index en retour.

J’espère que je suis clair ;-) Merci pour ton aide

[StringBuilder]

Tu veux "le premier" (TestA) ou "n'importe lequel" (TestA, TestB ou TestC) des jeux qui commencent par "Te" ?

Si c'est "le premier", alors la dichotomie ne marchera pas.
Tu pourras éventuellement représenter ta liste sous forme d'un arbre, utilisant les lettres comme noeuds.

Si c'est "n'importe lequel", alors la dichotomie sera la plus rapide en effet.

[Jayme65]

Non, c'est bien le premier que je veux trouver
Comment est ce que cela se traduirait en code, stp? Car "représenter ta liste sous forme d'un arbre" ne me parle pas ;-)

[mactwist69]

Un exemple serait que tu fasses une liste par lettre de l'alphabet, ainsi avec un select case, tu "jump" direct sur la bonne première lettre.

Ça peut être une forme de division dans la recherche.

[DonQuiche]

Non, c'est bien le premier que je veux trouver
Comment est ce que cela se traduirait en code, stp? Car "représenter ta liste sous forme d'un arbre" ne me parle pas ;-)

Bonjour.

Voici un exemple naïf (simple) pour une structure de données contenant les mots "bol", "bou" et "boule". On utilise en général '\0' comme marqueur de fin de chaîne mais je l'ai remplacé par '@' par souci de clarté.

              @
             / 
           E
          /
         L
        /  
      U  
     /  \ 
B - O    @
     \
      L
       \ 
        @

Personnellement, pour quelques dizaines de milliers d'éléments, je resterais tout de même sur une approche dichotomique pour trouver n'importe quel élément commençant pas "bo" puis je reviendrais en arrière avc un scan linéaire pour trouver le premier. Plus simple à écrire, moins gourmand en mémoire. Et sans doute plus rapide aussi, question de localité des références.

Cela dit, n'est-ce pas de l'optimisation prématurée ? Un traitement de 50ms est instantané aux yeux de l'utilisateur. Pour 50k éléments cela laisse 1000 ns par élément ! A raison de 1ns par opération basique, 5ns par appel de fonction virtuelle et 10ns par défaut de cache L1, on a de la marge ! Un bête scan linéaire pourrait donc suffire.

PS : Aujourd'hui, avec cet autre post, c'est officiellement ma journée dessin. Très récréatif ce vendredi.