Einzelnen Beitrag anzeigen

Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#21

AW: Boyer Moore Algorithmus

  Alt 6. Jun 2013, 21:10
Hallo,

ich habe weiter oben die Vorbereitungsphase in einen Record ausgelagert, weil mir das sehr unsinnig erschien, das ständig neu zu erstellen.
Ich habe Ginko Version 4 mal etwas umgestellt.
Wobei Count seiner Version entspricht, Count_II meiner vorherigen, bei der der vorbereitete Record für das Suchwort BMH mit Offset wiederholt aufruft, falls man eine Liste aufbauen oder etwas sofort verarbeiten will.
Erstaunlicherweise ist Version Count_II wesentlich langsamer.
50 mal in 100000 Zeilen nach Taxi suchen.
Code:
BMH Count II: 100000 in 424ms
BMH Count:    100000 in 353ms
Std Pos Count: 100000 in 343ms
Wieso da 20% verloren gehen, wobei der große Unterschied nur in einem Aufruf pro Fund und Bestimmung der Länge des Suchtextes besteht, alles Kleckerkram für 5 Mio Aufrufe. 58 CPU-Takte mehr.
PosEX ist aber hier, bei solch speziellen Wörtern ( alle sehr unterschiedlich, um möglichst kompakt alle Buchstaben des Alphabetes unterzubringen ), sehr schnell.
Suche nach " im" also mit Leerzeichen vorne
BMH Count II: 100000 in 573ms
BMH Count: 100000 in 450ms
Std Pos Count: 100000 in 1012ms

Falls es aber, wie im ersten Posting angedeutet, um das Durchsuchen von Dateien geht ist eher die Festplatte die herausforderung.

Gruß Horst
Angehängte Dateien
Dateityp: zip boyer_moore4.zip (5,7 KB, 12x aufgerufen)
  Mit Zitat antworten Zitat