Zitat:
Ich habe hier einen wirklich schnellen Stringmatching-Algorithmus (also, sowas wie 'POS'), der aber wesentlich schneller als POS ist (2-20x).
alllsooo
bevor man mit
ASM optimiert, von dem ich sowieso keine Ahnung habe *grien* .. muss man sich erst einmal fragen, was man tun möchte, damit man nicht auf eine falsche Fährte gelockt wird.
Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).
m ist die Länge des zu durchsuchenden Textes und n die Länge des Suchstrings. Die Laufzeit wird also besser, je länger der zu suchende String ist.
Eine Laufzeit O(m) zum Beispiel wäre ja eine lineare Abhängigkeit der Laufzeit vom zu durchsuchendem Text. (Wenn der Text doppelt so lang wird, brauch ich doppelt so lange Zeit zum Suchen)
Wenn also m=n wäre und der Suchtext gleich lang dem zu durchzuchendem Text, dann hättest Du eine Laufzeit von O(1) .. egal wie lang der Text wäre, der Algorithmus wäre gleich schnell (weil Du wahrscheinlich nur das erste und letzte Zeichen vergleichen könntest)
Der Bayer Moor Algorithmus wäre also bei Aufgaben interessant, wenn man die gesamte Festplatte unindiziert nach Vorkommen eines bestimmten Wortes durchsucht.
Das macht Windows irgendwie in annehmbarer Zeit, naja ... geht so
. Jetzt wäre also die Frage, wie oft will und braucht man das ...
Vor allen Dingen, weil in der realen Umsetzung bei Deiner explode Funktion der Algorithmus gar nicht das wahre Nadelöhr ist, sondern die häufigen String-Kopien..
http://www.delphipraxis.net/internal...=849704#849704
Wenn man eine einfache Suche mit Deiner Explode Funktion intelligent programmiert und noch etwas umgeschrieben in die eigene Klasse bastelt, hat man die Daten in der doppelten Geschwindigkeit verarbeitet, wie man braucht, um sie nur roh von der Festplatte zu lesen. (lesen von
CSV Dateien)
750 ms als Beispiel um 100 MB Daten von der Festplatte zu lesen, und weitere 750 ms um sie auseinander zu dividieren.
Ich finde, dafür ist es nicht wert, den Algorithmus noch stark auf
ASM zu optimieren. Gut, dann würen man irgendwann fast mit Festplattengeschwindigkeit. hmmm .. na gut, mir fällt dazu im Moment kein Anwendungsfall ein.
Ich denke, viel interessanter ist die Frage, wie durchsucht man einen relativ festen Datenbestand oder einen langen String, nach immer wieder anderen Texten. (Dictionary) (Typischer Anwendungsfall wäre die Suchmaschine Google. Die Zeit für eine Suche ist ja nicht abhängig von der Größe des Internets, also KEINE Laufzeit O(m) sondern nur abhängig von der Länge des Suchbegriffs (also O(n) )
Oder man will alle Vorkommen von Gensequenzen in einem ewig langem String durchsuchen ...
Und dafür gibts sehr moderne Algorithmen, wie Suffix-trees .. oder besser Suffix-Arrays, die zwar ein klein wenig langsamer sind als die Trees, aber dafür nicht soviel Speicher verbraten (bei intelligenter PRogrammierung stehen die Arrays den Trees sogar in nix nach)
Außerdem kann man so einen Suffixarray auf der Festplatte speichern, so einen Baum muss man immer neu aufbauchen.
(eine SuffixArray implementierung in Delphi hab ich leider nicht)
Ich hatte mir mal vor einiger Zeit einen SuffixTree von einem C-Quelltext umgeschrieben. wir könnten das ja mal vergleichen, im direkten Vergleich. Wenn Du Lust hast, können wir uns mal kurzschließen
Aufgabe also: Wie durchsuche ich einen Datenbestand auf alle Vorkommen eines Subtextes, möglichst schnell ... (mit Indizierung)
Nur, wenn Du das für Deinen Anwendungsfall benötigst ...
Gruß stoxx