Codeoptimierung beim Durchsuchen von LL

[mueckerich]

Hallo, die folgende Prozedur habe ich schon geschrieben. Nur ist das ganze bei großen Dateien ziemlich langsam, da ich bei jedem neuen Wort in einer Textliste innerhalb der Prozedur die Befehlsliste wieder neu durchlaufen werden muss.
Leider habe ich keine Ahnung wie ich das ganze so abändern kann das nicht immer die ganze Befehlsliste durchgearbeitet werden muss. Wenn ich in meiner Wortliste so 10000 Worte habe und innerhalb der Befehlsliste so ca. 400 dann kommen so einige Schleifendurchläufe zusammen und die Ausführungszeit wir sehr lang.
Vielleicht hat der ein oder andere Guru von euch eine Idee.

Edit: Die Befehlsliste ist nicht alphabetisch sortiert und die Zeichenkette (aus MeineTextListe()) die der Prozedur übergeben wird enthält nicht zwingend nur exakt einen Befehl aus der Befehlsliste sondern kann auch länger sein.

Codebeispiel:

Code: Alles auswählen

EnableExplicit

Procedure.l GetInstuctions(Value.S, List InstructionList.s())
  Protected Instruction.s, TmpStr.s, NextChar.c
  Protected I_Length.l, S_Length.l
  
  S_Length = Len(Value)
  ForEach InstructionList()
    Instruction = InstructionList
    I_Length = InstructionList
    If S_Length >= I_Length
       ;   |
       ;   | Hier passiert noch irgendwas.
       ;   |     
       ProcedureReturn I_Length
    EndIf
  Next
EndProcedure

NewList Befehlsliste.s()    ;Diese Liste wird mit ca. 400 Schlüsselwörten befüllt
NewList MeineTextListe.s() ; Diese Liste wird mit Wörtern aus einer Datei befüllt.

ForEach MeineTextListe()
  GetInstuctions(MeineTextListe(), Befehlsliste())
Next

[NicTheQuick]

Ich würde die Befehlsliste als Array machen und alphabetisch sortieren. Dann kannst du nach dem Teile-und-Herrsche-Verfahren viele unnötige Vergleiche einsparen und es sollte sehr flott gehen.
Das einmalige Sortieren wird man gar nicht erst merken. Wenn die Befehlsliste dynamisch erweiterbar sein soll, dann gibt es auch dafür eine Lösung, indem man alle Befehle in einen balancierten und sortierten Baum einträgt. Ausbalancieren geht meistens in O(1) oder O(log(n)).

[Rokur]

Da fallen mir spontan folgende Möglichkeiten ein:

1. Sortiere die Befehlsliste nach der statistischen Wahrscheinlichkeit mit der ein Befehl auftritt und beende die Schleife, wenn du eine Übereinstimmung hast. Am Beispiel von PureBasic: "If" kommt statistisch gesehen häufiger vor als "Dim".

2. Wenn die Reihenfolge von MeineTextListe() egal ist, dann sortiere beide Listen alphabetisch und arbeite dich mit NextElement() durch, dabei gehst du in der Befehlsliste nur weiter, wenn in der anderen Liste keine Übereinstimmung mehr gefunden wird. Durch die Sortierung musst du jede Liste damit maximal einmal durchlaufen.
Das dürfte die schnellste Möglichkeit sein, funktioniert aber eben nur wenn du beide Listen sortieren kannst.

3. Benutze für die Befehlsliste ein alphabetisch sortiertes Array und greife über einen Suchalgorithmus zu:
a) on-the-fly:
Restmenge = gesamte Liste
Wiederhole bis du eine Übereinstimmung oder keine Restmenge mehr hast:
* Springe zum mittlersten Element der Restmenge und prüfe folgende Fälle:
* Übereinstimmung => Treffer, Schleife beenden
* Element ist größer als Suchbegriff => Restmenge = der Teil unterhalb des geprüften Elements
* Element ist größer als Suchbegriff => Restmenge = der Teil überhalb des geprüften Elements
Dadurch halbierst du ständig den zu durchsuchenden Teil des Arrays und kommst schneller zum gesuchten Element, falls vorhanden.
b) index:
Leg dir einen Suchindex an, wie es z.B. Datenbanken machen.