@Sirius: Die Optimierung von Raita (und von mir) liegt darin, das man nicht jedesmal 'CompareMem' aufruft, sondern eben nur dann, wenn die ersten und letzten Zeichen übereinstimmen. Es gibt sogar noch eine Optimierung, die das letzte, das erste und das mittlere Zeichen vergleichen, und erst dann CompareMem aufrufen. Da hatte ich bei meinem Szenario (Tags in
XML-Dateien finden) keinen Geschwindigkeitsvorteil.
Wenn ich das weglasse, also direkt CompareMem aufrufe, dauert das bei meinem Testprogramm 3x so lange. Aber ich gebe zu, der Suchstring ist 8 Zeichen lang.
Angeblich ist Boyer-Moore ja noch schneller, ich konnte das aber nicht verifizieren. Im Gegenteil, er ist aufgrund des Overheads in der Schleife doch langsamer (jedenfalls in Delphi).
Ich habe eben mal den Gewinner der FastCode-Challenge (Pos) eingebaut und selbst der Code ist 1,5x langsamer.
Bevor das hier ausartet, sollte ich gleich mal Folgendes sagen:
Der QuickSearch-Algorithmus spielt seine Stärken umso stärker aus, je länger der Suchtext ist. Weiterhin sollte der zu suchende Text nicht zu kurz sein, da der Overhead im Berechnen der Sprungtabelle sonst den Performancegewinn zunichte macht.
QS eignet sich also für lange Texte und Suchstrings mit mehr als 4 Zeichen. Wenn man QS also in seinem Code verwenden möchte, dann sollte man für kurze Strings (PI x Daumen: 1000 Zeichen) und Suchstrings mit weniger als 4 Zeichen zu dem FastCode-Pos greifen, ansonsten zum QS.
Übrigens verwendet man Stringmatching-Algorithmen bei der Suche nach Gensequenzen. Ich hatte das Problem, in mehreren MB großen
XML-Strings nach bestimmten Tags zu suchen. Daher die Optimierung "erst erstes und letztes Zeichen vergleichen", denn das ist '<' und '>' und das kommt im
XML ja relativ selten vor.
So wie ich das sehe, wird man nur marginal etwas herausholen können. Ich denke, ich poste heute abend mal ein verbessertes Pos, das den FCC-Gewinner und QS vereint.
@ProgMan: Nicht die Sprache ist entscheidend, sondern der Algorithmus. Selbst die POS-Funktion der
RTL ist lahm, gegenüber dem Gewinner der Fastcode-Challenge (Faktor 3 ungefähr).