Schnellster Stringmatching-Algorithmus in ASM übersetzen

[Gausi]

Ich hab ja auch nicht von der Theorie gesprochen, sondern von der Praxis. In der Theorie ist Knuth-Morris-Pratt super, weil er ne lineare Worst-Case-Laufzeit hat. Praktisch nutzbar ist er nicht. Boyer-Moore kann man prima analysieren, aber wenn man davon den Teil weglässt, der dafür sorgt, dass die Laufzeit auch im Worst-Case linear wird (und nicht n*m), dann wirds in der Praxis fast doppelt so schnell.

Mal ein paar Beispiel-Zeiten von meinen aktuellen Tests, einfache Implementierungen ohne besondere Optimierung (Textlänge: 1MB, Alphabetgröße: 25, Musterlänge: 100 Zeichen, Zufallstexte/-Muster):

Naiver Algorithmus (nicht pos, sondern was selbstgebautes): 4ms
Knuth-Morris-Pratt (standard/verbessert): 5,3ms/3,5ms
Boyer-Moore (standard/verbessert): 520µs/321µs
Quicksearch (das Dingen hier): 318µs
Boyer-Moore-Horspool: 299µs

Die "verbesserten" Varianten setzen die Ideen zu "schnellen Implementierung" aus den entsprechenden Original-Artikeln um. In der Regel sind die letzten drei fast gleichwertig, aber sehr häufig hat der letzte die Nase ein paar µs vorne. Wenn das Nadelöhr allerdings eh woanders liegt, ist das natürlich alles wurscht.