AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Multimedia Delphi entwickeltes boyer-moore program läuft nich
Thema durchsuchen
Ansicht
Themen-Optionen

entwickeltes boyer-moore program läuft nich

Ein Thema von Görly · begonnen am 7. Apr 2008 · letzter Beitrag vom 9. Apr 2008
Antwort Antwort
Benutzerbild von Gausi
Gausi

Registriert seit: 17. Jul 2005
913 Beiträge
 
Delphi 12 Athens
 
#1

Re: entwickeltes boyer-moore program läuft nich

  Alt 8. Apr 2008, 07:37
Bist du sicher, dass deine Implementierung von KMP den Text ganz durchsucht hat, und nicht (wie pos) beim ersten Treffer aufgehört hat? Bei meinen Tests ist KMP um den Faktor 2-3 schneller. Selbst eine einfache Implementierung des "naiven Verfahrens" ist schneller als pos.
KMP ist aber wirklich eher theoretisch interessant, weil das einer der ersten Stringsuche-Algorithmen ist, die eine linare Worst-Case Laufzeit haben. Gegen einen anständig programmierten Boyer-Moore-Horspool oder Sunday kann es nichts ausrichten - zumindest nicht dann, wenn die gesuchten Substrings eine gewisse Länge überschreiten (so 5-10 Zeichen vielleicht).

Pos ist natürlich dann schneller, wenn man in sehr kurzen Texten sucht - dann schlägt die Vorbereitungszeit für KMP durch. Aber ansonsten ist pos was die Performance angeht, ab Texten von 50kb deutlich allen anderen Verfahren unterlegen. Und wenn man in vielen kurzen Texten sucht (z.B. ne Stringlist zeilenweise durchsucht), kann man die Vorbereitung für kmp einmal machen und nur die Suchphase wiederholen.

Zwei Beispiele:

10mb DNS-Sequenz, 300 Zeichen langes Muster. pos: ca. 200ms, kmp: ca. 70ms, "akademischer Kramladen-Algorithmus": knapp 4ms. [edit: hier ist die Einheit natürlich ms, nicht µs]

10kb langer Text, 15 Zeichen langes Muster. pos: 70µs, kmp: 63µs, "anderer akademischer Kramladen-Algorithmus": knapp 7µs.
  Mit Zitat antworten Zitat
Antwort Antwort


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:14 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz