PureBasic

Forums PureBasic - Français
http://forums.purebasic.com/french/

Indexer une liste structurée

http://forums.purebasic.com/french/viewtopic.php?t=16515

Page 1 sur 1

Indexer une liste structurée

Publié : mar. 21/févr./2017 0:43
par microdevweb
La fonction sort Pb ne fonctionne que sur une seule donnée de la structure, trié une liste avec une grosse structure pourrait prendre du temps.

Voici une petit exemple avec une liste d'index (clé composée) liée à la liste, en gros on ne trie pas la liste principal mais uniquement la liste indexée, quand on ajoute un record on ajoute la clé à l'index par insertion triée.

Désolé mais le code à un peux été fait à l'arrache , je le replacerais au propre quand j'aurais le temps.

Voici la liste des fonction pour la gestion des index
  • StringCompare(FistChaine.s,TwoChaine.s) -> Compare deux chaines de caractère retourne -1 si la chaîne est plus petite 1 si plus grande 0 équivalente
  • IndexSort() ->Création de la liste d'index d'index
  • AddToIndex(Key.s,*Pos) -> inséré un nouvelle index (conserve le tri)
  • Looking(chaine.s) -> Recherche un élément si trouvé (même si la chaîne comparée est plus petite mais correspond) pointe sur la structure principale

Code : Tout sélectionner

Structure People
  Name.s
  FirstName.s
  Adress.s
  ZipCode.s
  Cyti.s
  Telephone.s
  Celular.s
EndStructure
Structure Index
  *Position
  Key.s
EndStructure
Global NewList myPeople.People()
Global NewList myIndex.Index()
Declare StringCompare(FistChaine.s,TwoChaine.s)
Declare AddData()
Declare IndexSort()
Declare DisplayIndex()
Declare Looking(chaine.s)
Declare AddToIndex(Key.s,*Pos)
Procedure StringCompare(FistChaine.s,TwoChaine.s)
  Protected i,max
  max=Len(FistChaine)
  
  For i=i To max
    If Asc(Mid(FistChaine,i,1))>Asc(Mid(TwoChaine,i,1))
      ProcedureReturn 1
    Else
      If Asc(Mid(FistChaine,i,1))<Asc(Mid(TwoChaine,i,1))
        ProcedureReturn  -1
      EndIf
    EndIf
  Next
  ProcedureReturn 0
EndProcedure
Procedure AddData()
  With myPeople()
    AddElement(myPeople())
    \Name="Zoala"
    \FirstName="Alain"
    AddElement(myPeople())
    \Name="Yatola"
    \FirstName="Halonin"
    AddElement(myPeople())
    \Name="Albinos"
    \FirstName="Bernard"
    AddElement(myPeople())
    \Name="Catorin"
    \FirstName="Brunot"
    AddElement(myPeople())
    \Name="Albinos"
    \FirstName="Pierre"
  EndWith
EndProcedure
Procedure IndexSort()
  Protected i,comp
  ClearList(myIndex())
  ForEach myPeople()
    With myIndex()
      If ListSize(myIndex())=0
        AddElement(myIndex())
      Else
        i=0
        ForEach myIndex()
          i+1
          comp=StringCompare(myPeople()\Name+" "+myPeople()\FirstName,\Key)
          If comp<0
            InsertElement(myIndex())
            Break
          Else
            If i=ListSize(myIndex())
              AddElement(myIndex())
            EndIf
          EndIf
        Next
      EndIf
      \Key=myPeople()\Name+" "+myPeople()\FirstName
      \Position=@myPeople()
    EndWith
  Next
EndProcedure
Procedure DisplayIndex()
  ForEach myIndex()
    With myIndex()
      Debug \Key
    EndWith
  Next
EndProcedure
Procedure Looking(chaine.s)
  Protected *adress=-1
  With myIndex()
    ForEach myIndex()
      If StringCompare(chaine,\Key)=0
        *adress=\Position
        Break
      EndIf
    Next
  EndWith
  If *adress>-1
    With myPeople()
      ChangeCurrentElement(myPeople(),*adress)
      Debug ""
      Debug "Element finding"
      Debug \Name+" "+\FirstName
    EndWith
  EndIf
EndProcedure
Procedure AddToIndex(Key.s,*Pos)
  With myIndex()
    If ListSize(myIndex())=0
      AddElement(myIndex())
    Else
      i=0
      ForEach myIndex()
        i+1
        comp=StringCompare(Key,\Key)
        If comp<0
          InsertElement(myIndex())
          Break
        Else
          If i=ListSize(myIndex())
            AddElement(myIndex())
          EndIf
        EndIf
      Next
    EndIf
    \Key=Key
    \Position=*Pos
  EndWith 
EndProcedure
AddData()
IndexSort()
Debug "Index list"
DisplayIndex()
Looking("Yato")

; Ici j'ajoute un élément
With myPeople()
  AddElement(myPeople())
  \Name="Gradon"
  \FirstName="Gérard"
  AddToIndex(\Name+" "+\FirstName,@myPeople())
EndWith
; J" affiche l'index pour vérifié
Debug "Index list"
DisplayIndex()

; Ici j'ajoute un élément
With myPeople()
  AddElement(myPeople())
  \Name="Gradon"
  \FirstName="Alan"
  AddToIndex(\Name+" "+\FirstName,@myPeople())
EndWith
; J' affiche l'index pour vérifié
Debug "Index list"
DisplayIndex()

Re: Indexer une liste structurée

Publié : mar. 21/févr./2017 1:34
par falsam
Ça me semble compliqué cette technique.

Pour de très grosses listes je passerais plutôt par un tri base de données en mémoire ou pas. Mais ce n'est pas le sujet.

Reste deux solutions :
- La clé dans la structure avec un tri final sur la clé.
- L'algorithme de tri fusion en natif dans PureBasic depuis la version 4.30.

Voyons voir ces deux cas avec un exemple

■ La clé dans la structure avec un tri final sur la clé.

Code : Tout sélectionner

Structure Test
  Clef.s
  
  Champs1.s
  Champs2.s
EndStructure

NewList Tableau.Test()

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Tomates"
  \Clef = LSet(\Champs1, 30, " ") + LSet(\Champs2, 30, " ") 
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Oranges"
  \Clef = LSet(\Champs1, 30, " ") + LSet(\Champs2, 30, " ") 
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Abricots"
  \Clef = LSet(\Champs1, 30, " ") + LSet(\Champs2, 30, " ") 
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Pommes de terre"
  \Clef = LSet(\Champs1, 30, " ") + LSet(\Champs2, 30, " ") 
EndWith

SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Clef), #PB_String)

ForEach Tableau()
  Debug Tableau()\Champs1 + " - " + Tableau()\Champs2
Next
■ L'algorithme de tri fusion en natif dans PureBasic depuis la version 4.30.

Code : Tout sélectionner

Structure Test
  Champs1.s
  Champs2.s
EndStructure

NewList Tableau.Test()

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Tomates"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Oranges"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Abricots"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Pommes de terre"
EndWith

SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Champs1), #PB_String)
SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Champs2), #PB_String)

ForEach Tableau()
  Debug Tableau()\Champs1 + " - " + Tableau()\Champs2
Next
Le résultat dans les deux cas est le même.

Re: Indexer une liste structurée

Publié : mar. 21/févr./2017 7:18
par Micoute
Plus facile à comprendre pour les novices :

Code : Tout sélectionner

Structure Test
 Categorie.s
 Nom.s
EndStructure

NewList Tableau.Test()

AddElement(Tableau())
With Tableau()
 \Categorie = "Legumes"
 \Nom = "Tomates"
EndWith

AddElement(Tableau())
With Tableau()
 \Categorie = "Fruits"
 \Nom = "Oranges"
EndWith

AddElement(Tableau())
With Tableau()
 \Categorie = "Fruits"
 \Nom = "Abricots"
EndWith

AddElement(Tableau())
With Tableau()
 \Categorie = "Legumes"
 \Nom = "Pommes de terre"
EndWith

SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Categorie), #PB_String)
SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Nom), #PB_String)

ForEach Tableau()
 Debug Tableau()\Categorie + " - " + Tableau()\Nom
Next
J'ai juste changé champs1 par categorie et champs2 par nom.
Merci falsam pour le partage

Re: Indexer une liste structurée

Publié : mar. 21/févr./2017 8:55
par microdevweb
Bonjour Falsam,

C'est juste le partage d'une technique (langage C) pour l'indexage qui est employé surtout pour par exemple une gestion de fichiers. Maintenant je ne sait pas comment fonctionne exactement en interne la function sort de Pb et la rapidité qui en résulte avec une grosse structure bien chargée.

Par contre je sais que Sql en mémoire fonctionne très bien.

Edit: (Je ferais peut être un petit exemple avec une gestion de fichier)

Re: Indexer une liste structurée

Publié : mer. 07/juin/2017 10:41
par falsam
je vais devoir faire un mea-culpa. Le tri fusion de List ne fonctionne pas avec PureBasic comme le montre ce contre exemple.

Code : Tout sélectionner

Structure Test
  Champs1.s
  Champs2.s
EndStructure

NewList Tableau.Test()

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Tomates"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Oranges"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Abricots"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Pommes de terre"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Papaye"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Courgettes"
EndWith

;Tri par famille et par produit
SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Champs1), #PB_String)
SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Champs2), #PB_String)

ForEach Tableau()
  Debug Tableau()\Champs1 + " - " + Tableau()\Champs2
Next
La méthode avec une clé dans la structure est la plus appropriée.

Code : Tout sélectionner

Structure Test
  Champs1.s
  Champs2.s
  Clef.s
EndStructure

NewList Tableau.Test()

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Tomates"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Oranges"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Abricots"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Pommes de terre"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Fruits"
  \Champs2 = "Papaye"
EndWith

AddElement(Tableau())
With Tableau()
  \Champs1 = "Legumes"
  \Champs2 = "Courgettes"
EndWith

;Creation des clés de tri
ForEach Tableau()
  With Tableau()
    \Clef = LSet(\Champs1, 30, " ") + LSet(\Champs2, 30, " ") 
  EndWith
Next

;Tri par famille et par produit
SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Clef), #PB_String)

;Vérification
ForEach Tableau()
  Debug Tableau()\Champs1 + " - " + Tableau()\Champs2
Next

Re: Indexer une liste structurée

Publié : jeu. 08/juin/2017 1:55
par Demivec
falsam a écrit :je vais devoir faire un mea-culpa. Le tri fusion de List ne fonctionne pas avec PureBasic comme le montre ce contre exemple.
Utilisez ceci:

Code : Tout sélectionner

;Tri par famille et par produit
;(Trier la clé secondaire d'abord et la clé principale en dernier)
SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Champs2), #PB_String)
SortStructuredList(Tableau(), #PB_Sort_Ascending, OffsetOf(Test\Champs1), #PB_String)
Fuseau horaire sur UTC+01:00
Page 1 sur 1

Développé par phpBB® Forum Software © phpBB Limited

Traduction française officielle © Qiaeru