Optimiser une procédure, comparaison listes chaînées

[Octavius]

En ce moment je travaille sur un programme où le temps d'exécution est critique, et le problème c'est que j'ai là une procédure qui est assez longue, je voudrais savoir si vous auriez pas des idées pour l'accélérer.

Code : Tout sélectionner

ForEach CharNames()
  Text$=ReplaceString(CharNames()\In$,"_"," ")
  ForEach Names()
    If Text$=ReplaceString(Names()\In$,"_"," ")
      CharNames()\Out$=Names()\Out$
      Break
    EndIf
  Next
Next

Dans le principe CharNames() et Names() sont deux listes chaînées qui contiennent approximativement 10^4 éléments. Chaque liste chaînée contient les champs In$ et Out$. Ce que je veux faire c'est comparer tous les CharNames()\In$ avec tous les Names()\In$ et lorsqu'ils sont identiques alors CharNames()\Out$=Names()\Out$. Ca semble assez simple, mais vu le nombre d'éléments à traiter ça prend rapidement un peu de temps...

Ah oui, et pour compliquer la chose, les caractères "_" et " " (tiret-bas et espace) ont la même valeur, c'est-à-dire qu'ils ne permettent pas de discriminer deux éléments, donc j'utilise la fonction ReplaceString() pour remplacer tous les tirets-bas par des espaces.

[Fred]

Essaye de creer 2 listes temporaires qui contiennent deja tes noms remplacés, ca devrait dejà accelerer le traitement. Apres quand tu trouves un element, tu peux le supprimer de la liste, ca accelerera ton traitement au fur et à mesure que ton algo progresse.

[Atomo]

Je viens de faire un test de ton code avec des threads.
J'utilise 1 thread par processeur, j'obtient un gain de 50% de vitesse avec un core2duo et 2 threads et il y a sûrement moyen d'améliorer ça.

Code : Tout sélectionner

Structure info
  In$
  Out$
EndStructure

Declare cpu_count()
Declare traitement(core)

Global Max_Core = 1
;Global Max_Core = cpu_count() ;detecte le nombre de processeurs

#Elements = 1000000

Global Dim CharNames.info(#Elements)
Global Dim Names.info(#Elements)
NewList Thread.l() ;liste des threads

;Remplissage des listes
For x=0 To #Elements
  CharNames(x)\In$ = "String"
  CharNames(x)\Out$ = "String"
  Names(x)\In$ = "String"
  Names(x)\Out$ = "String"
Next x

Temps.l = ElapsedMilliseconds() ;initialisation timer

;lancement des threads
For x=0 To Max_Core-1
  Thread = CreateThread(@traitement(), x)
  AddElement(Thread())
    Thread() = Thread
Next x

;attente de la fin de l'execution de tous les threads
ForEach Thread()
  WaitThread(Thread())
Next

MessageRequester("Temps", Str(ElapsedMilliseconds()-Temps))

Procedure traitement(core)
  x=core
  While x < #Elements
    ;Debug "Core_"+Str(core)+"=élement_"+Str(x) ;décommenter pour voir l'agissement des threads
    Text$=ReplaceString(CharNames(x)\In$,"_"," ")

    For y=0 To #Elements
      If Text$=ReplaceString(Names(y)\In$,"_"," ")
        CharNames(x)\Out$=Names(y)\Out$
        Break
      EndIf
    Next y
    x+Max_Core
  Wend
EndProcedure

Procedure.l cpu_count()
    Protected SI.SYSTEM_INFO 
     GetSystemInfo_ (@SI) 
     ProcedureReturn SI\dwNumberOfProcessors 
EndProcedure

Il faut compiler avec l'option threadsafe, test d'abord avec 1 Thread comme sur cet exemple puis commente la ligne 9 et décommente la 10, il devrait détecter automatiquement le nombre de processeurs sur ta machine et s'adapater en fonction.

[Ollivier]

Visiblement, c'est une C.A.M. (Component Access Memory) qu'il te faut simuler. La dernière que j'ai faite, ça a fait marrer Brossden! Il m'a pondu un code bien plus simple sans se rendre compte de la subtilité (la liste contenait une quarantaine d'expressions donc, au final c'était inutile de sortir l'arme lourde pour si peu).

Pour résumer, il me faut pas mal de détails. Peux-tu poster deux liens vers 2 fichiers Textes contenant deux listes exemplaires (l'un pour les Names\In$ et l'autre pour les CharNames\In$) avec un bon paquet de chaînes (le plus possible serait le mieux).

Il me faut de surcroît savoir combien de MégaOctets je peux allouer sur ta RAM (je pars sur un max de un demi Giga) + combien de GigaOctets je peux allouer sur ton disque dur (je pars sur un max de 32 Giga).

Ollivier

[Octavius]

Essaye de creer 2 listes temporaires qui contiennent deja tes noms remplacés, ca devrait dejà accelerer le traitement.

OK je vais tester ça.

Apres quand tu trouves un element, tu peux le supprimer de la liste, ca accelerera ton traitement au fur et à mesure que ton algo progresse.

Ca m'embête parce que il peut y avoir plusieurs éléments identiques dans la liste CharNames() mais pas dans la liste Names(). Je ne peux donc pas supprimer des éléments de la liste Names().

@ Atomo : Je ne comprends pas très bien le principe de ton code, mais je remarque que tu as déclaré des tableaux et non des listes chaînées. Est-ce que c'est important ? J'utilise ForEach, mais peut-être que cette fonction est plus lente qu'un For ou un While combinés avec un NextElement() ?

@ Ollivier : Est-ce que tu peux expliquer ce que c'est une CAM et comment la mettre en oeuvre dans le principe ? Je ne vois pas le rapport avec la RAM pour l'instant.

[Atomo]

L'utilisation de listes chainées dans de multiples thread peut causer des soucis, ça serait faisable avec des mutex mais ça ralentirait le traitement, c'est pour ça que j'utilise des tableaux.
Le principe du code est simple et a l'air de fonctionner (du moins chez moi), imaginons que tu as 3 processeurs sur ton PC, je créer 3 threads qui se répartirons le traitement de la boucle ensemble, par exemple :
-Thread 1 = element(1)
-Thread 2 = element(2)
-Thread 3 = element(3)
-Thread 1 = element(4)
-Thread 2 = element(5)
-Thread 3 = element(6)
etc...

[Ollivier]

Tout d'abord, un petit bonjour à Fred, ça fait toujours plaisir de voir la présence du concepteur!

Atomo, idem : bonjour. J'aimerais te dire que ma méthode est complètement différente au point tel que les deux sont cumulables!

@Octavius

Ton problème c'est d'accéder rapidement à deux données égales.

Voici une version "soft" pour que tu t'amuses un peu...

1) formaliser tes chaînes (Ce que dit Fred avec les remplacements des tirets par les espaces, etc...)
2) récupérer l'empreinte MD5 de chacune des chaînes
3) tronquer l'empreinte à 24 bits
4) se servir de l'empreinte de 24 bits comme d'une adresse sur 24 bits donc dans une table de plus de 16 millions de cellules. Pour chaque cellule, un entier long (4 octets) d'où une allocation de 4 * 16 millions d'octets (je pense que dire que ça fait 64Mo ne t'apprendra rien!).

Pour une cellule lambda, si l'entier est nul, c'est ce que je pourrais appeler un état vide. C'est-à-dire que toutes les chaînes de l'Univers qui peuvent avoir comme préfixe 24 bits d'empreinte MD5 la position de la cellule n'existent pas dans ta base de donnée.

Pour une cellule lambda, si l'entier est non nul, il s'agit alors d'un pointeur. Il pointe vers un descripteur. Et ce descripteur est un buffer mémoire structuré à ta guise.

Seules restrictions au sein de cette structure, posséder :
1) Un drapeau d'état d'égalité (la fameuse égalité que tu vérifies)
2) Un drapeau d'état de corruption (le Numéro (3) > 1)
3) Le nombre précis de chaînes que cette cellule alloue (>0)
4) Un pointeur vers la table des pointeurs de chaînes

La CAM, concrètement c'est ça!

Résultat: ta base de chaînes est, comme par magie "scindée" par catégories (=type d'empreinte). Tu as 20000 chaînes? Pas de problème! Avec une CAM de 64Mo d'indexation, tu offres donc en proportion pour chaque chaîne 800 empreintes. Donc un taux de corruption faible (une corruption = plusieurs chaînes existant dans la base avec le même préfixe 24 bits MD5, donc adressées à la même cellule).

Si tu ne veux pas d'erreur (chose qui n'est pas indispensable : c'est selon le but gourmand ou non en temps et en ressources), c'est 32 GigaOctets pour simuler une CAM + une analyse approfondie des chaînes existantes.
Sinon pour valider cette méthode expliquée ici, tout en vérifiant et corrigeant les erreurs, c'est la petite bidouille que tu es en train de faire au-dessus avec les ForEach() MAIS avec très peu de chaînes, tout simplement!

[Octavius]

J'ai réfléchis et ta méthode m'a donné une idée ! Comparer deux chaînes de caractères ça veut dire comparer tous les caractères et ça prend du temps. Comparer le MD5 ça prend moins de temps. Alors du coup je me suis dis que j'allais déjà commencé par comparer tout simplement la longueur de la chaîne.

Code : Tout sélectionner

ForEach CharNames()
  Text$=ReplaceString(CharNames()\In$,"_"," ")
  Lg=Len(Text$)
  ForEach Names()
    If Len(Names()\In$)<>Lg : Continue : EndIf
    If Text$=ReplaceString(Names()\In$,"_"," ")
      CharNames()\Out$=Names()\Out$
      Break
    EndIf
  Next
Next

Cette procédure est 2 fois plus rapide que la première que j'ai posté ! Je n'y aurais jamais cru. C'est une première étape, je vais essayer de continuer à bidouiller avec les threads et les MD5.

[Ollivier]

Ben si tu piges le principe expliqué plus haut, tu verras que c'est 100 à mille fois plus rapide... Tu risques d'avoir un gros gourdin, c'est moi qui te le dis!!!

Ollivier

[Fred]

En gros, c'est d'une hashmap que t'as besoin, y'a quelques exemples sur le forum anglais.

[Ollivier]

@Fred

Merci d'avoir trouvé le terme technique adéquat!
Grâce à ça, on trouve une explication plus conventionnelle sur wikipedia.

Ollivier

[Kwai chang caine]

FRED y dit un mot et ça decoince
Trop fort

Grâce à ça, on trouve une explication plus conventionnelle sur wikipedia.

Heureusement que tu n'as pas dit :
"Grâce à ça, on trouve une explication plus claire sur wikipedia."
Car avec WIKIPEDIA, c'est ou ça t'aide et tu comprend, ou alors ça te fait regretter d'etre venu au monde si bete
Pas la peine de te dire quelle sensation je viens de ressentir en lisant les premieres lignes

Bon en tout cas ça fera un mot de plus que je pourrais sortir en société pour me la peter
Et comme beaucoup en société sans rien comprendre à ce dernier

[Ollivier]

@Kcc

Maitre OLLIVIER

Je ne suis pas un maître.

Ne t'inquiète pas, un code va être pondu incessamment sous peu.

PS: J'en profite sans te froisser pour te dire que ton avatar me pose des problèmes depuis pas mal de temps. Pourrais-tu s'il te plaît mettre un truc "statique" à la place? (temporairement) Ce serait vraiment super cool de ta part...

Ollivier

[Ollivier]

Pondu...

Problèmes de communication, donc désolé pour le manque actuel d'explications...

Code : Tout sélectionner

#None     = 0
#Direct   = 1
#Indirect = 2

#NoNeedNode  = 1
#NodeCreated = 2
#NodeUpdated = 3

Procedure.I InitCAM()
   Protected Result.I
   Result = AllocateMemory(1 << 24 * SizeOf(integer) )
   ProcedureReturn Result
EndProcedure


Procedure.I CpnAccess(*Cam, *StrAdr)
   Protected Result.I
   Protected *Cell
   Protected *CellCpn
   *Cell = *Cam + (Val("$" + Left(MD5Fingerprint(*StrAdr, Len(PeekS(*StrAdr) ) ), 6) ) * SizeOf(integer) )
   *CellCpn = PeekI(*Cell)
   If *CellCpn = 0
      Result = #None
   Else
      If PeekI(*CellCpn) = *CellCpn
         Result = #Indirect
      Else
         Result = #Direct
      EndIf    
   EndIf
   ProcedureReturn Result
EndProcedure


Procedure.I AddCpn(*Cam, *StrAdr)
   Protected Result.I

   Protected *Cell
   Protected *CellCpn
   Protected *Node
   Protected Count.I
   *Cell = *Cam + (Val("$" + Left(MD5Fingerprint(*StrAdr, Len(PeekS(*StrAdr) ) ), 6) ) * SizeOf(integer) )
   *CellCpn = PeekI(*Cell)
   If *CellCpn = 0
      PokeI(*Cell, *StrAdr)
      Result = #NoNeedNode
   Else
      If PeekI(*CellCpn) = *CellCpn
         Count = PeekI(*Node + SizeOf(integer) )
         Count + 1
         *Node = ReAllocateMemory(*Node, SizeOf(integer) * (2 + Count) )
         PokeI(*Cell, *Node)
         PokeI(*Node, *Node)
         PokeI(*Node + SizeOf(integer), Count + 1)
         PokeI(*Node + (SizeOf(integer) * (1 + Count) ), *StrAdr)
         Result = #NodeUpdated
      Else
         *Node = AllocateMemory(4 * SizeOf(integer) )
         PokeI(*Cell, *Node)
         PokeI(*Node, *Node)
         PokeI(*Node + SizeOf(integer), 2)
         PokeI(*Node + SizeOf(integer) * 2, *CellCpn)
         PokeI(*Node + SizeOf(integer) * 3, *StrAdr)
         Result = #NodeCreated
      EndIf    
   EndIf
   ProcedureReturn Result
EndProcedure


Procedure.I RemoveCpn(*Cam, *StrAdr)
   Protected Result.I

   Protected *Cell
   Protected *CellCpn
   Protected *Node
   Protected Count.I
   Protected I.I
   Protected J.I
   Protected Str2Del.S
   Protected *Adr
   *Cell = *Cam + (Val("$" + Left(MD5Fingerprint(*StrAdr, Len(PeekS(*StrAdr) ) ), 6) ) * SizeOf(integer) )
   *CellCpn = PeekI(*Cell)
   Result = #None
   If *CellCpn = 0
      Result = #None
   Else
      Str2Del = PeekS(*StrAdr)
      If PeekI(*CellCpn) = *CellCpn
         Count = PeekI(*Node + SizeOf(integer) )
         If Count = 2            
            For I = 0 To 1
               If PeekS(PeekI(*Node + SizeOf(integer) * (2 + I) ) ) = Str2Del
                  Result = PeekI(*Node + SizeOf(integer) * (2 + I) )
                  PokeI(*Cell, PeekI(*Node + SizeOf(integer) * (2 + (1 - I) ) ) )
                  FreeMemory(*Node)
                  Break
               EndIf
            Next I
         Else
            For I = 1 To Count
               If PeekS(PeekI(*Node + SizeOf(integer) * (1 + I) ) ) = Str2Del
                  Result = PeekI(*Node + SizeOf(integer) * (1 + I) )
                  Count - 1
                  For J = I To Count
                      Adr = *Node + SizeOf(integer) * (1 + J)
                      PokeI(Adr, PeekI(Adr + SizeOf(integer) ) )
                  Next J
                  *Node = ReAllocateMemory(*Node, SizeOf(integer) * (2 + Count) )
                  PokeI(*Node, *Node)
                  PokeI(*Node + SizeOf(integer), Count)
                  Break
               EndIf
            Next I
                  
            *Node = ReAllocateMemory(*Node, SizeOf(integer) * (2 + Count) )
            PokeI(*Node, *Node)
            PokeI(*Node + SizeOf(integer), Count + 1)
            PokeI(*Node + (SizeOf(integer) * (1 + Count) ), *StrAdr)
            Result = #NodeUpdated
         
         EndIf
      Else
         If PeekS(*CellCpn) = Str2Del
            Result = *CellCpn
            PokeI(*Cell, 0)
         EndIf         
      EndIf    
   EndIf

   ProcedureReturn Result ; Retourne l'adresse de la chaîne supprimée
EndProcedure

   Define *Cam = InitCAM()

[Octavius]

Waw merci Ollivier, je vais me plonger dans ton code pour essayer de le comprendre.

Parallèlement j'ai essayé de bidouiller qqch moi aussi de mon côté. Je ne pense pas vraiment être tout à fait au point théoriquement sur les tables de hachage et les CAM, mais avec les principes que vous m'avez expliqué j'ai pondu ça :

Code : Tout sélectionner

Structure name
  In$
  Out$
EndStructure

Structure rebel Extends name
  Item
EndStructure

NewList CharNames.name()
NewList Names.rebel()

Dim HashNames.l(30)

;... Remplissage la liste CharNames()
;... Remplissage de la liste Names()

;Je formalise mes chaînes de caractère et je calcule un index
ForEach Names()
  Names()\In$=ReplaceString(Names()\In$,"_"," ")
  Names()\Item=Len(Names()\In$)*100+Asc(Left(Names()\In$,1))
Next

;Je range ma liste en fonction de cet index
SortStructuredList(Names(),0,OffsetOf(rebel\Item),#PB_Sort_Long)

;Je fabrique une table où je référence l'adresse mémoire de qqs index
ForEach Names()
  i=1
  For j=i To 30
    If Names()\Item>100*(j-1) And Names()\Item<100*j
      HashNames(j)=@Names()
      i=j+1
      Break
    EndIf
  Next j
Next

;Voici la deuxième liste avec laquelle je veux rapidement
;faire correspondre les éléments de la première liste

ForEach CharNames()
  
  ;Formalisation et calcul d'un index
  Text$=ReplaceString(CharNames()\In$,"_"," ")
  Item=Len(Text$)*100+Asc(Left(Text$,1))
  
  ;Je cherche dans ma table une adresse proche de cet index
  If HashNames(Item/100)=0
    ;Par défaut, s'il n'y a rien de référencé dans la table à cet endroit
    ;Je commence mes recherches au début de la liste
    ResetList(Names())
  Else
    ;Je commence ma recherche juste un peu en amont de l'élément à trouver
    ChangeCurrentElement(Names(),HashNames(Item/100))
  EndIf
  
  ;Je teste plusieurs éléments jusqu'à ce que je trouve le bon
  While NextElement(Names())
    ;Je commence par tester l'index, s'il n'est pas identique je passe à l'élément suivant
    If Names()\Item<>Item : Continue : EndIf
    ;Si l'index est identique je teste le texte
    If Text$=Names()\In$
      CharNames()\Out$=Names()\Out$
      ;Je casse la boucle quand j'ai enfin trouvé le bon élément
      Break
    EndIf
  Wend
  
Next

Résultat : 12 fois plus rapide que le tout premier code ! Bon ça fait encore un peu amateur comme code.