String in StringList suchen

[alzaimar]

Zitat von kalmi01:

Moin moin Leuts,

mal so, aus dem Handgelenk würde ich das ehr so angehen:

1.) i := Pos('suchtext', MyStringList.Text);
2.) von der Position i rückwärts nach CR/LF suchen
3.) von der Position i vorwärts nach CR/LF oder #00 suchen

Zwischen den Pos. 1. und Pos. 2. liegt der exakte String, mit
dem man dann einIndex := MyStringList.IndexOf('Msg_1001'); füttern könnte.
Dürfte bei langen Listen auch schneller sein.

Das bezweifle ich, denn
1. Die Get-Methode von MyStringList.Text iteriert über alle Strings und
2. bastelt den Text. Dadrin suchst Du
3. per Pos um dann nochmals mittels
4. IndexOf zu suchen.

Hmm... Ein natives "pos" über alle MyStringList.Text dürfte doch wesentlich schneller sein, auch wenn es nicht befriedigend ist.
Um in einer Liste von Zeilen einen zweiten Teilstring zu suchen, eignet sich die TStringlist nur bedingt. Ok, wem es Schnurz ist, ob das nun 10ms oder 5ms dauert (z.B.) der soll das nehmen, denn dafür reicht es allemal (also, wenn nur wenige tausend Einträge in der Liste sind).

Wenn das eine zeitkritische Angelegenheit ist, würde ich:
1. Keine TStringlist nehmen, sondern
2. einen einzigen String S verwenden, ähnlich MyStringList.Text.
3. Für jede Zeile die StartPosition innerhalb S merken (Z : Array Of Integer) (die Liste ist sortiert!)
4. Mit einem schnelleren Pattern-Matching als POS (QS-Search oder Boyer-Moore für sehr lange Suchstrings) die Position P finden
5. P mit binary search in S suchen.

Ich denke, das dürfte recht fix sein, Es geht natürlich noch schneller (z.B. Pos.5), aber das würde zu weit führen.

[oki]

Hi,

Zitat von alzaimar:

Ich denke, das dürfte recht fix sein, Es geht natürlich noch schneller (z.B. Pos.5), aber das würde zu weit führen.

Für meinen aktuellen Fall ist die "lahme" Methode vollkommen ausreichend. Andere Vorgänge sind eh so lahm (server basierende Datenbank; Empfang der Daten via GPRS), dass es hier nicht auf die ms ankommt. Außerdem hab ich nie mehr als 10 Zeilen mit max. 100 Zeichen im Buffer. Trotzdem interessiert es mich schon, wie man die Suchverfahren effizient gestalten kann. Zum einen schadet es nicht schnellen Code zu schreiben (wenn der Aufwand gerechtfertigt ist) und zum zweiten lernt man immer gern dazu.

Also wie ist das mit Pos.5?

Gruß oki

[marabu]

Hi,

Binary Search funktioniert nur auf geordneten Mengen - du müsstest also zuerst eine geordnete Menge von Wörtern aus deinem String erzeugen. Macht Sinn, wenn du wechselnde Worte in einem gleichbleibenden String suchst, nicht aber, wenn du immer das selbe Wort in wechselnden Strings suchst.

Freundliche Grüße

[oki]

Hi marabu,

ich denke das ist dann eher die falsche Richtung für meinen Anwendungsfall und für ein bischen Nachhilfe am Rande wohl zu umfangreich. Somit soll's dabei bleiben.

Dank für die Antworten und beste Grüße

oki

[alzaimar]

Hi oki:
Zunächst mein Ansatz mit einem Beispiel: Die Liste besteht aus drei Zeilen 'ABC', 'DE','FGHI'.
Der String 'S' sieht so aus: 'ABCDEFGHI'.
Die Liste Z sieht so aus: (1,4,6)

Ich suche nach 'E'. Die Position ist 5, liegt also zwischen 4 und 6, ergo ist es die 2.Zeile.

Nun zu meiner Pos.5 Hier hatte ich den Mund etwas zu voll genommen, weil ich an Hash-Verfahren dachte, das wird hier nicht funktionieren. Ich kann mich aber mit einem Bucket- oder einem Lookup-Suchverfahren aus der Affäre ziehen.

Wir müssen das binärse Suchverfahren knacken: Das ist in log2(n) Schritten am Ziel, schon ziemlich fix... Hmmm... Wir brauchen ein Verfahren, das eine Position P auf einen Index i in Z schneller abbildet.

Sei p die gefundene Position des Suchstrings in S

1.Ansatz (Lookup)
Wir definierten ein Hilfsarray H der Länge 5 (so lang wie S): (1,1,2,2,3,3,3,3). Somit ist H[p] = Zeilennummer. Der Aufwand ist O(1), mithin optimal. Nachteil: Verbrät viel Speicher.

2.Ansatz (Bucket)
Wir teilen die möglichen Positionen durch F (F z.B. 3) und erstellen wieder ein Hilfsarray H mit H[p div F] = p, hier also (1,1,3).
Wenn wir eine Position gefunden haben (p), steht die Zeilennummer in H[p div F]? Leider nicht. Denn im Beispiel wird Position 4 in die 1.Zeile gemappt, in Wirklichkeit ist es jedoch in der nächsten Zeile. Wir wenden also binary Search auf die Teilliste H[p div 3], H[p div 3 + 1] an und fertig.

Der Aufwand ist O(log_2(F)), also schon besser.

[oki]

Hi alzaimar,

nun hab ich ja was losgetreten.

Nun im Ernst. Deine Verfahren leuchten ein. Zur Sicherheit folgenden Frage: In deinem Beispiel muss die Menge H korrekt aber so aussehen?
H : (1,1,1,2,2,3,3,3,3)

Ich nehme jetzt mal an, dass IndexOf schneller als die Schleife mit Pos ist.
Nun drängt sich mir aber folgender Verdacht auf. Dauert das Erstellen des Hilfsarrays mit anschließender Suche zusammen nicht auch wieder länger als die direkte Suche über die Schleife?

Ich glaub ich schreib einfach mal ein kleines Testprog.

Gruß oki

Ach so, die zweite Methode ist für mich grundsätzlich schon klar, aber wie du auf den Divisor 3 kommst ist mir noch nicht ganz aufgegangen.

[alzaimar]

Hi,

Zunächst hast du natürlich Recht: Für die einmalige Suche ist die triviale Suche per Pos über alle Zeilen natürlich das Beste.

Aber wenn Du das sehr oft machen musst, dann empfielt es sich einfach, ein bischen Vorarbeit zu leisten.

Zu deiner Frage, wie ich auf die '3' komme? Ganz einfach: Das Beispiel besteht aus 9 Zeichen besteht: 2 ist zu blöd und 4 zu hoch (für das Beispiel). Und den Schusseligkeitsfehler hast Du sehr richtig korrigiert. Ich äh... wollte nur testen ob Du auch Alles verstanden hast .

Im ernst: Wenn diese Suche immer wieder vorkommt, und die Liste mal etwas länger wird, dann solltest Du eine der Varianten ins Auge fassen. Bei den paar hundert Einträgen würde ich mir nicht die Mühe machen, das lohnt nicht.

Aber Du hast mich gefragt, und ich hab Dir meine Ideen mitgeteilt

[oki]

Zitat von alzaimar:

Im ernst: Wenn diese Suche immer wieder vorkommt, und die Liste mal etwas länger wird, dann solltest Du eine der Varianten ins Auge fassen. Bei den paar hundert Einträgen würde ich mir nicht die Mühe machen, das lohnt nicht.

Aber Du hast mich gefragt, und ich hab Dir meine Ideen mitgeteilt

Sorry wenn meine Antwort nach Kritik klang. Das war es sicher nicht. Ich hab nur laut nachgedacht. Meine Frage war auch schon beantwortet und ich habe weiter gebohrt.

Sonst ganz klar, ich stimme dir voll und ganz zu. Hier zeigt sich auch wieder, dass der konkrete Anwendungsfall den speziellen Weg fordert und schnell nicht immer schnell ist. Man fragt oft nach nem schnellen Verfahren; und ohne konkrete Aufgabenstellung ist die oft nicht korrekt zu beantworten.

In diesem Fall ist es imho so:

Sucht man nacheinander viele Strings (Vorkommen in der Zeile) in einem sehr großen Text (Zeilen-formatiert), so machen die genannten Methoden Sinn. Mit der Lookup-Methode muss man aber mit der doppelten Speicherbelastung rechnen. Wird das zu heftig und man will ein Optimum zwischen Geschwindigkeit und Speicher finden, so ist die Bucket-Methode sicher ein Weg in die Richtige Richtung. Die Größe des Divisors zu finden ist dabei jedoch ein eigenes Thema.

Muss man das alles nur einmal machen, so ist die einfache Suche mit Pos oder IndexOf wohl schneller.

Gruß oki

[alzaimar]

Zitat von oki:

Zitat von alzaimar:

...Aber Du hast mich gefragt, und ich hab Dir meine Ideen mitgeteilt

Sorry wenn meine Antwort nach Kritik klang. Das war es sicher nicht. Ich hab nur laut nachgedacht. Meine Frage war auch schon beantwortet und ich habe weiter gebohrt.

Deine Antwort klang nicht mal im Ansatz nach Kritik, und nur wer bohrt, wird etwas herausfinden, oder?

Den Divisor bei der Bucket-Methode zu finden, ist übrigens sehr leicht: Wenn Du z.B. max. 10MB Speicher für die H-Liste reservieren willst, sind das 2,5Mio Cardinal-Einträge. Also ist

Code:

F = MAX (1, Length (S) div 2.500.000)

[oki]

Moin,

aus der Speicherrichtung hatte ich nicht geschaut. Ich bin mit meinen Gedanken eher aus der Richtung Optimum gekommen. Oft ist es doch so, dass bei verkürzten Verfahren ein bestimmter Wert das optimum darstellt. Also im Moment schwimme ich hier etwas rum und meine Gedanken sind weniger mathematisch als aus dem Bauch heraus.
Geht man aus Richtung Speicher an die Sache, so lässt sich der min. verwendbare Divisor über die von Dir genannte Formel finden. Ist dieser dann aber auch das Optimum?

Ich denke, je größer der Divisor, desto länger der Weg der weiteren Verfeinerung zum Ergebnis.

Hmmm, kann es sein, dass es egal ist? Verwende ich einen Divisor, so läßt sich keine klare Formel ermitteln, sondern nur eine bedeutend kleinere Untermenge in welcher gesucht wird?

Ich würde auch behaupten, dass je größer der divisor wird, je "unschärfer" wird das Ergebnis, ergo je größer die verbleibende Restmenge.

Gemäß deinem Ansatz frag ich mich jetzt aber folgendes: Kann man den Summand n für die Suche in

H[p div 3 +/- n] mathematisch exakt ermitteln?

Ich hab das Gefühl (da war er wieder der mathematisch korrekte Ansatz "Gefühl" ), dass man hier in einer schleife n stufenweise erhöhen muss um sich dem gesuchten Ergebnis anzunähern. also wieder meine erste Methode in einer kleineren Untermenge.

Jo, was sagst du nun!

Gruß oki