Optimisation...s #1

[Progi1984]

Voilà, j'ai un code que j'utilise pas mal de fois dans le code, mais je pense qu'il est possible de l'optimiser, mais je sais pas comment :

La première boucle cherche dans la liste chainée de chaines si TrCodeField existe, si oui, il définit bFound à #True sinon il est défini à #False.

Mais bon, pour compiler un code ASM de 180 000 lignes, la bouche foreach et le if sont exécutés quelques 182.000.000 de fois. (Merci le profileur).

Code : Tout sélectionner

  ; add if part doesn't exist
  bFound = #False
  ForEach LL_ASM_extrn()
   If LL_ASM_extrn() = TrCodeField
     bFound = #True
     Break
   EndIf
  Next
  If bFound = #False
    If AddElement(LL_ASM_extrn())
      LL_ASM_extrn() = TrCodeField
    EndIf
    ProcedureReturn #True
  EndIf

Auriez vous une optimisation ou ptet une meilleure technique de stockage de chaines (avec vérification d'erreurs des doublons) ?

Merci d'avance.

[gnozal]

1. Si la liste LL_ASM_extrn() était triée, la recherche serait beaucoup plus rapide par technique dichotomique.

Cette technique est utilisée dans jaPBe avec des listes chaînées structurées ou non [Editor-Core.pbi -> fonction find_var() par exemple].

2. Sinon, un dictionnaire associatif (avec tables de hachage) pourrait aussi faire l'affaire (exemple : ma librairie PureDIC livrée avec sa source [utilise GDSL]).

[Progi1984]

Cette technique de recherche dichotomique devrait me faire gagner pas mal de temps. Je vais essayer de mettre ca en place pour voir le gain de temps.

Juste pour avoir une trace...

Code : Tout sélectionner

Procedure find_var(*name.BYTE)
  ResetList(var())
  half=CountList(var())>>1
  If half
    SelectElement(var(),half)
    Pos=half
    quit=0
  Else
    Pos=0
    If NextElement(var())=0
      quit=2
    Else
      quit=0
    EndIf
  EndIf
  oldcompare=0
  While quit=0
    compare=CompareMemoryString(*name,@var()\s,1)
    If half
      Select compare
        Case -1:half>>1:Pos-half:SelectElement(var(),Pos)
        Case 0:quit=1
        Case 1:half>>1:Pos+half:SelectElement(var(),Pos)
      EndSelect
    Else
      If compare=0
        quit=1
      ElseIf compare=oldcompare Or oldcompare=0
        oldcompare=compare
        If compare=-1
          If PreviousElement(var())=0
            ResetList(var())
            quit=2
          EndIf
        Else
          If NextElement(var())=0
            LastElement(var())
            quit=2
          EndIf
        EndIf
      Else
        If oldcompare=1
          If PreviousElement(var())=0
            ResetList(var())
          EndIf
        EndIf
        quit=2
      EndIf
    EndIf    
  Wend
  If quit=2
    ProcedureReturn 0
  Else
    ProcedureReturn 1
  EndIf  
EndProcedure

[Progi1984]

Est ce que cela devrait etre bon ?

J'ai pas encore testé mais je pense que ce devrait etre bon. Merci de votre aide.

Code : Tout sélectionner

  Protected qIndEnd.q, qIndStart.q, qIndMid.q
  Protected lCompare.l
  ResetList(LL_ASM_extrn())
  bFound = #False
  qIndStart = 0
  qIndEnd = ListSize(LL_ASM_extrn()) -1
  If qIndEnd
    While qIndStart <= qIndEnd
      qIndMid = (qIndStart + qIndEnd +1) >>1
      SelectElement(LL_ASM_extrn(), qIndMid)
      lCompare = CompareMemoryString(@LL_ASM_extrn(), @TrCodeField, #PB_String_NoCase)
      If lCompare = 0
        bFound = #True
        qIndStart = qIndEnd + 1
      ElseIf lCompare > 0
        ;Debug "Chaîne 1 > Chaîne 2"
        qIndEnd = qIndMid -1
      ElseIf lCompare < 0
        ;Debug "Chaîne 1 < Chaîne 2"
        qIndStart = qIndMid +1
      EndIf
    Wend
  EndIf
  If bFound = #False
    AddElement(LL_ASM_extrn())
    LL_ASM_extrn() = TrCodeField
    SortList(LL_ASM_extrn(), #PB_Sort_Ascending | #PB_Sort_NoCase)
  EndIf

[Progi1984]

Mauvais code, voici le bon :

Code : Tout sélectionner

Global NewList LL_ASM_extrn.s()
Procedure Dicho(TrCodeField.s)
  Protected sValue.s
  ResetList(LL_ASM_extrn())
  bFound = #False
  qIndStart = 0
  qIndEnd = ListSize(LL_ASM_extrn()) -1
  If qIndEnd >= 0
    While qIndStart <= qIndEnd
      qIndMid = (qIndStart + qIndEnd +1) >>1
      SelectElement(LL_ASM_extrn(), qIndMid)
      sValue = LL_ASM_extrn()
      lCompare = CompareMemoryString(@sValue, @TrCodeField, #PB_String_NoCase)
      If lCompare = 0
        bFound = #True
        qIndStart = qIndEnd + 1
      ElseIf lCompare > 0
        qIndEnd = qIndMid -1
      ElseIf lCompare < 0
        qIndStart = qIndMid +1
      EndIf
    Wend
  EndIf
  If bFound = #False
    AddElement(LL_ASM_extrn())
    LL_ASM_extrn() = TrCodeField
    SortList(LL_ASM_extrn(), #PB_Sort_Ascending | #PB_Sort_NoCase)
  EndIf
EndProcedure

For Inc = 0 To 1000000
  Sample.s = LSet("", 5, Chr(97+Random(26)))
  Dicho(Sample)
  ;Debug Sample
  ;Debug "-------------------"
Next
Debug "--"
ForEach LL_ASM_extrn()
  Debug LL_ASM_extrn()
Next