Schnellere Alternative zu PosEx ?

[Solstice Projekt]

Grüsseuch!

Ich hab' eine allgemeine (also nicht nur TextZeichen wie PosEx) MusterSuche geschrieben, welche PosEx um Längen schlägt.

Ich hab' versucht, schnelle Implementationen für Alternativen zu finden,
aber irgendwie kommt dabei nichts Gutes heraus. Ich hab' Libraries gesucht,
welche es mir ermöglichen, anständige Benchmarks zu erstellen, damit ich Vergleiche hab' ... aber ohne Erfolg.

In FPC gibt es eine, oder mehrere?, Implementation eines Such-Algorithmus,
wie zB. FindMatchesBoyerMooreCaseSensitive, aber die ist noch viel langsamer als PosEx.

Ich weiß leider nicht, wie ich mir diesbezüglich selbst helfen kann.
Die letzte Möglichkeit, scheint zu sein, dass ich C installieren muss, damit ich Such-Algorithmen von GitHub zum Vergleich benutzen kann,
aber da ich kein C kann und mich nicht mit den potentiellen Problemen konfrontieren möchte, ist das nur eine letzte Option.

Kann mich da jemand in die richtige Richtung lenken?

Danke!

[mkinzler]

Reguläre Ausdrücke

https://wiki.freepascal.org/Regexpr

[himitsu]

Zitat:

FindMatchesBoyerMooreCaseSensitive, aber die ist noch viel langsamer als PosEx

Wer Äpfel mit Birnen vergleicht und sich dann beschwert, dass die Birne zwar besser ist, aber leider nicht apfelig schmeckt, und sich fragt ob die Pflaume das besser machen könnte ......

In Delphi gibt es auch noch System.Masks, wobei es dieses MatchesMask auch im FreePascal/Lazarus geben sollte. (kann sein dass es anders heißt ... einfach mal beim TMaskEdit suchen)

[Solstice Projekt]

Zitat:

Zitat von mkinzler (Beitrag 1473731)

Reguläre Ausdrücke

https://wiki.freepascal.org/Regexpr

Ah, vielen Dank. Ich seh' mir das an.

Zitat:

Zitat von himitsu (Beitrag 1473734)

Zitat:

FindMatchesBoyerMooreCaseSensitive, aber die ist noch viel langsamer als PosEx

Wer Äpfel mit Birnen vergleicht und sich dann beschwert, dass die Birne zwar besser ist, aber leider nicht apfelig schmeckt, und sich fragt ob die Pflaume das besser machen könnte ......

In Delphi gibt es auch noch System.Masks, wobei es dieses MatchesMask auch im FreePascal/Lazarus geben sollte. (kann sein dass es anders heißt ... einfach mal beim TMaskEdit suchen)

Danke, ich schau mal.

Inwiefern vergleiche ich Äpfel mit Birnen?

Es ist nicht *viel* langsamer als PosEx, aber so weit ich die Messungen in Erinnerung hab', kam's doch vor.
Ich sitz' schon zu lange an dem Ganzen.

[Solstice Projekt]

Zitat:

Zitat von mkinzler (Beitrag 1473731)

Reguläre Ausdrücke

https://wiki.freepascal.org/Regexpr

Hab' in meinem Leben noch nie regex benutzt, um ehrlich zu sein.
Das Beispiel Programm zum Suchen eines Strings hab' ich jetzt ausprobiert.
Viel zu langsam, was aber scheinbar eh zu erwarten war, da das Teil ja hochkomplex zu sein scheint.

Oder ich mach was falsch. Mal sehen. Nein, ist korrekt.

Trotzdem danke!

[himitsu]

Ups, mir war so, dass dieses Boyer-Moore eine "Ähnlichkeitssuche" war,
ähnlich zu Soundex, Levenshtein, Jaccard oder Metaphone.

RegEx ist eine (noch aufwändigere aber hoch optimierte) Mustersuche.

Und Pos sowie PosEx ist eine Binärsuche.



OK, rein vom Ergebnis sind Boyer-Moore und Pos/PosEx (wobei ich glaube Delphi hat seit über 10 Jahren die PosEx vom FastStrings-Projekt übernommen) "gleich".

Aber bei kurzen Texten wird der "Aufwand" für die Such-Optimierung im Boyer-Moore wesentlich mehr Rechenleistung/Zeit verbraten, als die eigentliche Suche,
womit es dann dem "dummen" PosEx unterlegen ist. (außer bei sehr langen/großen Texten)

[sakura]

Um evtl. auch brauchbare Antworten geben zu können:

1. Suchst Du für Delphi oder FPC?
2. Welche Art von Muster magst Du unterstützen (einfach wir * und ?, oder eine LIKE-Implementation, oder komplexe Dinge wie RegEx)?

Zitat:

Zitat von Solstice Projekt (Beitrag 1473737)

Inwiefern vergleiche ich Äpfel mit Birnen?

Du vergleichst eine Mustersuche mit mit PosEx - was keine Mustersuche unterstützt. Daher Äpfel und Birnen.

Im Allgemeinen werden Mustersuchen immer langsamer sein, als eine einfache Pos(Ex) Suche. Für längere Suchstrings ließe sich PosEx sicherlich optimieren. Siehe auch FastStrings.

...:cat:...