Alternative zu PosEx

[Amateurprofi]

Ich hatte das Problem, zu prüfen, ob und wo in einem bestimmten Bereich eines etwas längeren Strings (SearchIn) ein anderer Text (SearchFor) vorkommt.
Ein weiteres Problem war, alle Fundstellen von SearchFor in SearchIn zu finden und zu speichern.
Für das erste Problem habe ich die Funktion "StrPos" geschrieben, für das zweite die Funktion "StrPosEx".
Beide Funktionen sind für 32bit-Assembler geschrieben.
Alternative 64bit Versionen werde ich demnächst erstellen.
Zum Testen habe ich die kürzlich gefundene 52te Mersenne-Primzahl mit 41.024.320 Ziffern verwendet.
Zum Finden und Speichern der 4.103.481 "0"en benötigt die Funktion ca. 65 ms.
Für die 36 Fundstellen der Ziffernfolge "030366" (Geburtstag einer Freundin) zu finden und zu speichern, werden ca. 60 ms benötigt.
(Windows 7 - Intel Core I7-2600K 3.4 GHz).
Um mich nicht zu sehr mit fremden Federn zu schmücken:
Die Funktionen sind von der Funktion "PosEx" aus System.StrUtils.pas abgeleitet.
Vielleicht hat der eine oder andere Bedarf für solche Funktionen.

Delphi-Quellcode:

{$IFDEF CPUX86}
{------------------------------------------------------------------------------}
{ StrPos                                                                       }
{ Prüft, ob SearchFor in SearchIn innerhalb des Bereiches First..Last          }
{ vorkommt und gibt die gefundene Position. bzw 0 für 'nicht gefunden' zurück. }
{ First<1 heißt ab Anfang von SearchIn suchen.                                 }
{ Last<1 oder Last>Length(SearchIn) heißt bis Ende von SearchIn suchen.        }
{------------------------------------------------------------------------------}
FUNCTION StrPos(const SearchFor,SearchIn:String; First,Last:Integer):Integer;
asm
                  // EAX=@SearchFor, EDX=@SearchIn, ECX=First, Stack=Last
               test  eax,eax
               jz    @Nil              // SearchFor leer
               test  edx,edx
               jz    @Nil              // SearchIn leer
               dec   ecx               // First 0-Based
               jge   @FirstOk          // First>=1
               xor   ecx,ecx
@FirstOK:      push  ebx
               push  edi
               push  esi
               mov   ebp,Last
               mov   ebx,[edx-4]       // Length(SearchIn)
               test  ebp,ebp
               jle   @LastOK           // Last<=0 heißt bis Ende suchen
               cmp   ebp,ebx
               jge   @LastOK           // Last>Length(SearchIn), bis Ende suchen
               mov   ebx,ebp           // Nur bis Last suchen
@LastOK:       // EAX=@SearchFor, EDX=@SearchIn, ECX=First-1, EBX=Last
               mov   edi,[eax-4]       // Length(SearchFor)
               lea   esi,[ecx+edi]     // First+Length(SearchFor)-1
               cmp   esi,ebx
               jg    @Past             // First>Last oder First+Length(SearchFor)>Last
               lea   eax,[eax+edi*2-2] // @SearchFor[Length(SearchFor)]
               lea   ebp,[edx+ebx*2]   // @SearchIn[Last+1]
               lea   edx,[edx+esi*2-2] // @SearchIn[First+Length(SearchFor)-1]
               lea   edi,[edi*2-2]     // 2*(Length(SearchFor)-1)
               neg   edi               // -(2*(Length(SearchFor)-1))
               add   ecx,ecx           // 2*(First-1)
               sub   ecx,edx           // 2*(First-1)-@SearchIn[First+Length(SearchFor)-1]
               push  ecx               // Für spätere Positionsberechnung
               movzx ecx,word[eax]     // letztes Zeichen von SearchFor
               // --------------------------------------------------------------
               // CX = Letztes Zeichen von SearchFor
               // EDX = SearchIn[First+Length(SearchFor)
               // EBP = @SearchIn[Last+1 Zeichen]
               // EDI = -(2*(Length(SearchFor)-1))
               // ESI = First+Length(SearchFor)-1
@Loop:         cmp   cx,[edx]          // Letzes Zeichen von SearchFor an EDX?
               jz    @Test0            // Ja, SearchIn auf voriges Zeichen
@AfterTest0:   cmp   cx,[edx+2]        // Letzes Zeichen von SearchFor an EDX+1 Zeichen
               jz    @TestT            // J,
@AfterTestT:   add   edx,8             // SearchIn+4 Zeichen
               cmp   edx,ebp           // SearchIn noch im zu durchsuchenden Bereich
               jb    @Continue         // Ja
@EndLoop:      add   edx,-4            // SearchIn-2 Zeichen
               cmp   edx,ebp           // SearchIn noch im zu durchsuchenden Bereich
               jb    @Loop             // Ja
               jmp   @False            // Nicht gefunden
@Continue:     cmp   cx,[edx-4]        // Letzes Zeichen von SearchFor an EDX-2 Zeichen?
               jz    @Test2            // Ja, SearchIn -3 Zeichen
               cmp   cx,[edx-2]        // Letzes Zeichen von SearchFor an EDX-1 Zeichen?
               jnz   @Loop             // Nein, nächste Position prüfen
@Test1:        add   edx,2             // SearchIn + 1 Zeichen, durch folgende Adds - 2 Zeichen
@Test2:        add   edx,-4            // SearchIn - 2 Zeichen, durch folgendes Add - 3 Zeichen
@Test0:        add   edx,-2            // SearchIn - 1 Zeichen
@TestT:        mov   esi,edi
               test  esi,esi           // Alle Zeichen von SearchFor gefunden?
               jz    @Found            // Ja, gefunden
@String:       mov   ebx,[eax+esi]     // 2 Zeichen aus SearchFor
               cmp   ebx,[edx+esi+2]   // In SearchIn?
               jnz   @AfterTestT       // Nein, SearchIn+4 Zeichen
               cmp   esi,-4            // Alle Zeichen gefunden?
               jge   @Found            // Ja
               mov   ebx,[eax+esi+4]   // Nächste 2 Zeichen aus SearchFor
               cmp   ebx,[edx+esi+6]   // In SearchIn?
               jnz   @AfterTestT       // Nein, SearchIn+4 Zeichen
               add   esi,8             // Zeichenzahl + 4 Zeichen
               jl    @String           // Nächste 4 Zeichen prüfen
               //---------------------------------------------------------------
@Found:        lea   eax,[edx+4]       // Fundstelle
               cmp   eax,ebp           // Im zu durchsuchenden Bereich?
               ja    @False            // Nein, nicht gefunden.
               add   eax,[esp]         // Endgültige Position in Bytes
               shr   eax,1             // Endgültige Position in Zeichen
               jmp   @End              // Stack bereinigen, Register wieder herstellen
               //---------------------------------------------------------------
@False:        xor   eax,eax           // Nicht gefunden
               jmp   @End              // Stack bereinigen, Register wieder herstellen
               //---------------------------------------------------------------
@Nil:          xor   eax,eax           // Nicht gefunden
               jmp   @Ret              // Return
               //---------------------------------------------------------------
@Past:         xor   eax,eax           // Nicht gefunden
               jmp   @Pop              // Register wieder herstellen
               //---------------------------------------------------------------
@End:          add   esp,4             // Stack bereinigen
@Pop:          pop   esi               // ESI wieder herstellen
               pop   edi               // EDI wieder herstellen
               pop   ebx               // EBX wieder herstellen
@Ret:
end;
{$ENDIF}

Delphi-Quellcode:

{$IFDEF CPUX86}
{------------------------------------------------------------------------------}
{ StrPosEx                                                                     }
{ Sucht alle Vorkommen von SearchFor in SearchIn und stellt die Positionen     }
{ der Fundstellen in Positions.                                                }
{ Es ist Sache der aufrufenden Stelle, sicherzustellen, daas Positions lang    }
{ genug ist, alle Fundstellen zu speichern.                                    }
{ Parameter                                                                    }
{    SearchFor  : String, nach dem gesucht wird.                               }
{    SearchIn   : String, inem gesucht wird.                                   }
{    Positions  : Array zur Speicherung der Fundstellen.                       }
{    Exceptions : Gibt an, in welchen Fällen Exceptions ausgelöst werden.      }
{                   Bit 0 = 1 : Wenn SearchFor leer ist.                       }
{                   Bit 1 = 1 : Wenn SearchIn leer ist.                        }
{                   Bit 2 = 1 : Wenn SearchFor länger ist, als SearchIn.       }
{                   Bit 3 = 1 : Wenn Positions zu kurz ist.                    }
{                 Wenn ein Fehler auftritt, und das korrespondierende Bit in   }
{                 Exceptions nicht gesetzte ist, werden folgende Fehlercodes   }
{                 zurückgegeben:                                               }
{                    -1 SearchFor leer.                                        }
{                    -2 SearchIn leer.                                         }
{                    -3 SearchFor länger als SearchIn.                         }
{                    -4 Positions zu kurz.                                     }
{ Wenn kein Fehler auftritt, wird die Anzahl der Fundstellen zurückgegeben.    }
{------------------------------------------------------------------------------}
FUNCTION StrPosEx(const SearchFor,SearchIn:String;
   Positions:TIntegerDynArray; Exceptions:Integer=0):Integer;
const
   sSearchForEmpty:String='StrPosEx:'#13'SearchFor ist leer';
   sSearchInEmpty:String='StrPosEx:'#13'SearchIn ist leer';
   sSearchForTooLong:String='StrPosEx:'#13'Searchfo ist länger als SearchIn';
   sPositionsLength:String='StrPosEx:'#13'Das Array "Positions" ist zu kurz '+
                           'um alle Fundstellen zu speichern';
   pExClass:ExceptClass=(Exception);
asm
               // EAX=@SearchFor, EDX=@SearchIn, ECX=Positions
               // Register retten und Platz für lokale Variablen reservieren
               push  ebp
               push  ebx
               push  edi
               push  esi
               sub   esp,12            // Platz für 3 Integers
               // Prüfen, ob SearchFor und SearchIn nicht leer sind
               test  eax,eax           // SearchFor leer?
               jz    @SFNil            // Ja, Fehlermedung
               test  edx,edx           // SearchIn leer?
               jz    @SINil            // Ja, Fehlermeldung
               // Längen von SearchFor und SearchIn laden und prüfen ob
               // SearchFor nicht länger ist, als SearchIn
               mov   edi,[eax-4]       // Length(SearchFor)
               mov   ebx,[edx-4]       // Length(SearchIn)
               cmp   edi,ebx           // SearchFor länger als SearchIn?
               ja    @SFTooLong        // Ja, Fehlermeldung
               cmp   edi,1             // Hat SearchFor nur 1 Zeichen
               je    @Char             // Ja
               // Positions retten, Anzahl Fundstellen auf 0
               mov   [esp+8],ecx       // Positions
               mov   [esp+4],0         // Anzahl Fundstellen
               // Zeiger und Länge von SearchIn initialsieren
               lea   eax,[eax+edi*2-2] // EAX auf letztes Zeichen in SearchFor
               lea   ebp,[edx+ebx*2]   // EBP hinter letztes Zeichen von SearchIn
               lea   edx,[edx+edi*2-2] // EDX auf Ende der ersten potentiellen Fundstelle
               lea   edi,[edi*2-2]     // EDI = 2*(Length(SearchFor)-1)
               neg   edi               // EDI = -(2*(Length(SearchFor)-1))
               xor   ecx,ecx
               sub   ecx,edx           // ECX = -SearchIn[Length(SearchFor)-1]
               mov   [esp],ecx         // Für spätere Positionsberechnung
               // --------------------------------------------------------------
               // EAX     = Zeigt auf letztes Zeichen in SearchFor
               // EDX     = Zeigt auf Ende der nächsten potentiellen Fundstelle
               // EBP     = Zeigt hinter letztes Zeichen von SearchIn
               // EDI     = -(2*(Length(SearchFor)-1))
               // [ESP-8] = Postions
               // [ESP-4] = Anzahl Fundstellen
               // [ESP]   = -SearchIn[Length(SearchFor)-1]
@Start:        mov   cx,[eax]          // letztes Zeichen von SearchFor
@Loop:         cmp   cx,[edx]          // CX an [EDX]?
               jz    @Test0            // Ja, weitere Zeichen ab [EDX-1 Char] prüfen
@AfterTest0:   cmp   cx,[edx+2]        // CX an [EDX + 1 Char]?
               jz    @TestT            // Ja, weitere Zeichen ab [EDX] prüfen
@AfterTestT:   add   edx,8             // SearchIn + 4 Chars
               cmp   edx,ebp           // SearchIn noch im zu durchsuchenden Bereich
               jb    @Continue         // Ja
@EndLoop:      add   edx,-4            // SearchIn - 2 Chars
               cmp   edx,ebp           // SearchIn noch im zu durchsuchenden Bereich
               jb    @Loop             // Ja
               jmp   @NoFurther        // Keine weiteren Fundstellen
@Continue:     cmp   cx,[edx-4]        // CX an [EDX - 2 Chars]?
               jz    @Test2            // Ja, SearchIn - 3 Chars
               cmp   cx,[edx-2]        // Letzes Zeichen von SearchFor an EDX-1 Zeichen?
               jnz   @Loop             // Nein, nächste Position prüfen
@Test1:        add   edx,2             // SearchIn + 1 Char, durch folgende Adds - 2 Chars
@Test2:        add   edx,-4            // SearchIn - 2 Chars, durch folgendes Add - 3 Chars
@Test0:        add   edx,-2            // SearchIn - 1 Char
@TestT:        mov   esi,edi           // -(2*(Length(SearchFor)-1))
               test  esi,esi           // Alle Zeichen von SearchFor gefunden?
               jz    @Found            // Ja, gefunden
@String:       mov   ebx,[eax+esi]     // 2 Zeichen aus SearchFor
               cmp   ebx,[edx+esi+2]   // In SearchIn?
               jnz   @AfterTestT       // Nein, SearchIn + 4 Chars
               cmp   esi,-4            // Alle Zeichen gefunden?
               jge   @Found            // Ja
               mov   ebx,[eax+esi+4]   // Nächste 2 Zeichen aus SearchFor
               cmp   ebx,[edx+esi+6]   // In SearchIn?
               jnz   @AfterTestT       // Nein, SearchIn + 4 Chars
               add   esi,8             // Zeichenzahl + 4 Chars
               jl    @String           // Nächste 4 Zeichen prüfen
               //---------------------------------------------------------------
               // Gefunden. EDX zeigt auf Fundstelle - 1 Zeichen
@Found:        lea   ecx,[edx+4]       // Fundstelle + 1 Zeichen
               cmp   ecx,ebp           // Im zu durchsuchenden Bereich?
               ja    @NoFurther        // Nein, keine weiteren Fundstellen
               add   ecx,[esp]         // Position in Bytes
               shr   ecx,1             // Position in Zeichen
               mov   esi,[esp+8]       // Positions
               mov   ebx,[esp+4]       // Bisherige Anzahl Fundstellen
               cmp   ebx,[esi-4]       // Noch Platz in Positions?
               jae   @OutOfMem         // Nein
               mov   [esi+ebx*4],ecx   // Fundstelle speichern
               inc   ebx               // Anzahl Fundstellen + 1
               mov   [esp+4],ebx       // Anzahl Fundstellen speichern
               // EDX auf nächste potentielle Fundstelle
               mov   esi,edi           // -(2*(Length(SearchFor)-1))
               neg   esi               //   2*(Length(SearchFor)-1)
               lea   edx,[edx+esi+4]   // EDX=nächste potentielle Fundstelle
               cmp   edx,ebp           // Noch im gültigen Bereich?
               jb    @Start            // Ja, weiter suchen
               jmp   @NoFurther        // Nein, keine weiteren Fundstellen
               // --------------------------------------------------------------
               // Suche nach nur einem Zeichen
               // EAX = SearchFor
               // EDX = SearchIn
               // ECX = Positions
               // EBX = Lenght(SearchIn)
@Char:         mov   ebp,ecx           // Positions
               xor   ecx,ecx           // Anzahl Fundstellen
               lea   edx,[edx+ebx*2]   // Hinter letztes Zeichen von SearchIn
               lea   edi,[ebx+1]       // für spötere Positionsermittlung
               neg   ebx
               mov   ax,[eax]          // gesuchtes Zeichen
@CharLoop:     cmp   ax,[edx+ebx*2]    // AX an aktueller Position?
               jz    @CharFound1       // Ja
               cmp   ax,[edx+ebx*2+2]  // AX an nächster Position?
               jz    @CharFound2       // Ja
               add   ebx,2             // 2 Zeichen weiter
               jl    @CharLoop
               jmp   @NoFurtherC       // Keine weiteren Fundstellen
               // An [EDX+EBX*2] gefunden
@CharFound1:   cmp   ecx,[ebp-4]       // Noch Platz in Positions?
               jae   @OutOfMem         // Nein
               lea   esi,[edi+ebx]     // Fundstelle
               mov   [ebp+ecx*4],esi   // In Positions speichern
               inc   ecx               // Anzahl Fundstellen
               inc   ebx               // 1 Zeichen weiter
               jl    @CharLoop
               jmp   @NoFurtherC       // Keine weiteren Fundstellen
               // An [EDX+EBX*2+2] gefunden
@CharFound2:   cmp   ecx,[ebp-4]       // Noch Platz in Positions?
               jae   @OutOfMem         // Nein
               lea   esi,[edi+ebx+1]   // Fundstelle * 2
               mov   [ebp+ecx*4],esi   // In Positions speichern
               inc   ecx               // Anzahl Fundstellen
               add   ebx,2             // 2 Zeichen weiter
               jl    @CharLoop
               jmp   @NoFurtherC       // Keine weiteren Fundstellen
               //---------------------------------------------------------------
               // SearchFor ist leer
@SFNil:        mov   eax,sSearchForEmpty
               mov   ecx,1             // Fehlercode
               jmp   @End
               //---------------------------------------------------------------
               // SearchIn ist leer
@SINil:        mov   eax,sSearchInEmpty
               mov   ecx,2             // Fehlercode
               jmp   @End
               //---------------------------------------------------------------
               // SearchFor ist länger als SearchIn
@SFTooLong:    mov   eax,sSearchForTooLong
               mov   ecx,3             // Fehlercode
               jmp   @End
               //---------------------------------------------------------------
               // Positions nicht lang genug um neue Fundstelle zu speichern
@OutOfMem:     mov   eax,sPositionsLength
               mov   ecx,4             // Fehlercode
               jmp   @End              // Fehlermeldung
               //---------------------------------------------------------------
               // Keine weiteren Fundstellen
@NoFurther:    mov   ecx,[esp+4]       // Anzahl Fundstellen
@NoFurtherC:   xor   eax,eax           // ´Kein Fehler
               //---------------------------------------------------------------
               // Stack bereinigen und Register restaurieren
@End:          add   esp,12            // Stack bereinigen
               pop   esi               // ESI wieder herstellen
               pop   edi               // EDI wieder herstellen
               pop   ebx               // EBX wieder herstellen
               pop   ebp               // EBP wieder herstellen
               //---------------------------------------------------------------
               // Prüfen ob Fehler vorliegt und ggfs. Exception auslösen
               test  eax,eax           // Fehler ?
               jz    @NoError          // Nein, Anzahl Fundstellen zurückgeben
               mov   edx,1
               shl   edx,cl
               neg   ecx               // Fehlercode
               shr   edx,1
               test  [ebp+8],edx       // Exception werfen?
               jz    @NoError          // Nein, nur Fehlercode zurückgeben
               mov   ecx,eax           // Fehlertext
               mov   eax,pExClass      // InstanceOrVMT
               mov   edx,1             // Alloc
               call  Exception.Create
               call  System.@RaiseExcept
               //---------------------------------------------------------------
               // Anzahl Fundstellen bzw. Fehlercode in Result
@NoError:      mov   eax,ecx           // Anzahl Fundstellen bzw. FehlerCode
end;
{$ENDIF}

[himitsu]

Lies besser nicht meine Signatur.

OK, bei dem alten Delphi solltest du das überall das "Pos" in "PosEx" umbenennen .... ist aber eigentlich sieit vielen Jahren nicht mehr nötig.

Delphi-Quellcode:

function Pos(const SubStr, Str: String; Offset, LastOffset: Integer): Integer; overload;
begin
  //if Offset > 0 then
  //  Result := Pos(SubStr, Str, Offset)
  //else
  //  Result := Pos(SubStr, Str);
  Result := Pos(SubStr, Str, Offset);
  if Result > LastOffset then
    Result := 0;    
end;

[Sinspin]

Zitat von Amateurprofi:

{$IFDEF CPUX86} ...

Das ist aber nur für 32 Bit?
Wie sieht es denn mit einer 64Bit Variante aus?
Ich arbeite in letzter Zeit häufiger mit Lazarus FPC und 64Bit um ein bisschen mehr Speicher verballern zu können.
Ich habe aber bisher noch keinen Anwendungsfall gehabt bei dem die Untersuchung eines Strings zeitkritisch gewesen wäre.

Nebenbei, POS, auch mal als Point Of Sale kennengelernt, hat mir mal eine Verwarnung von Apple eingebracht als ich eine App bewertet habe.
Die haben wohl was anderes verstanden ... was ich leider auch so angedacht hatte.

[Gausi]

Zitat von Sinspin:

Ich habe aber bisher noch keinen Anwendungsfall gehabt bei dem die Untersuchung eines Strings zeitkritisch gewesen wäre.

Wenn die Strings größer werden, und man oft (oder viele) Teilstrings in vielen verschiedenen Texten suchen will, dann wird das schon interessant. Aber dann nimmt man ggf. auch andere Suchalgorithmen. Knuth-Morris-Pratt, Boyer-Moore, QuickSearch oder ein paar weitere, die ggf. auf bestimmte Spezialfälle hin optimiert sind. Parameter dafür sind u.a.

• Länge der gesuchten Teilstrings
• Größe des verwendeten Alphabets (also Anzahl der verschiedenen Zeichen)

Pos und PosEx laufen dabei unter "naive Verfahren".

Ein Anwendungsfall ist z.B. das Durchsuchen eines Genoms nach einer bestimmten DNA-Sequenz. Zumindest war das öfter ein Beispiel in der Literatur, als ich damals meine Diplomarbeit über "Algorithmen zur Mustersuche in Zeichenketten" geschrieben habe.

Aber es stimmt schon, dass das meistens irrelevant ist - denn selbst der "naive Algorithmus" hat eine (erwartete) lineare Laufzeit. KMP ist interessant, weil da auch die Worst-Case-Laufzeit linear ist (im Gegensatz zu quadratisch bzw. "rechteckig", d.h. Textlänge*Musterlänge im Worst Case bei Pos). Boyer-Moore z.B. wird schneller, wenn die Suchmuster länger werden.

Oder halt komplette andere Ansätze, wie z.B. vorher einen Suchindex über die zu durchsuchenden Texte aufbauen, aber das ist dann wirklich was komplett anderes.

[himitsu]

War Pos nicht früher (vor Äonen) mal langsamer?
Ich glaub dort wurde auch was vom FastStrings mal mit übernommen.

[Amateurprofi]

Zitat von Sinspin:

Zitat von Amateurprofi:

{$IFDEF CPUX86} ...

Das ist aber nur für 32 Bit?
Wie sieht es denn mit einer 64Bit Variante aus?
Ich arbeite in letzter Zeit häufiger mit Lazarus FPC und 64Bit um ein bisschen mehr Speicher verballern zu können.
Ich habe aber bisher noch keinen Anwendungsfall gehabt bei dem die Untersuchung eines Strings zeitkritisch gewesen wäre.

Nebenbei, POS, auch mal als Point Of Sale kennengelernt, hat mir mal eine Verwarnung von Apple eingebracht als ich eine App bewertet habe.
Die haben wohl was anderes verstanden ... was ich leider auch so angedacht hatte.

Zu "Das ist aber nur für 32 Bit?" und "Wie sieht es denn mit einer 64Bit Variante aus?"
Aus #1
"Beide Funktionen sind für 32bit-Assembler geschrieben.
Alternative 64bit Versionen werde ich demnächst erstellen".

Zu "Ich habe aber bisher noch keinen Anwendungsfall gehabt bei dem die Untersuchung eines Strings zeitkritisch gewesen wäre."
Nicht verzagen, kommt irgendwann.

Bei mir geht es um Mersenne-Primzahlen und aus diesen abgeleiteten Perfekten Zahlen, die, Stand 10/2024, bis zu ca. 41 Mio bzw. 82 Mio Ziffern haben.
Das Programm in dem die Funktionen benutze, kann diese Zahlen errechnen, speichern, laden, in einem Listenfeld anzeigen, und in ihnen Ziffern oder Ziffernfolgen suchen.
Der Suchtext wird in ein TEdit eingegeben und bei jeder Veränderung des Eingabefeldes werden alle Fundstellen ermittelt und im Listenfeld farbig markiert.
Bei der Eingabe einer Ziffernfolge wird die Funktion also nach jedem Tastendruck ausgeführt, und ich möchte eine Ziffernfolge zügig eingeben können, und keine unschönen Wartezeiten hinnehmen.
Na klar habe ich früher die von himitsu skizzierte Lösung verwendet, aber gemerkt, dass dabei die erwähnten "unschönen Wartezeiten" auftraten.

Nochmal zu "Wie sieht es denn mit einer 64Bit Variante aus?"
Warum fragst du dass wenn du sagst "Ich habe aber bisher noch keinen Anwendungsfall gehabt bei dem die Untersuchung eines Strings zeitkritisch gewesen wäre."

[Amateurprofi]

Zitat von himitsu:

War Pos nicht früher (vor Äonen) mal langsamer?
Ich glaub dort wurde auch was vom FastStrings mal mit übernommen.

Ja. Das lag daran, dass in der "alten", bei mir (Delphi XE2) "aktuellen" Version mit dem bummeligen "REPNE SCASB" gearbeitet wird.

[Amateurprofi]

Zitat von Gausi:

Zitat von Sinspin:

Ich habe aber bisher noch keinen Anwendungsfall gehabt bei dem die Untersuchung eines Strings zeitkritisch gewesen wäre.

Wenn die Strings größer werden, und man oft (oder viele) Teilstrings in vielen verschiedenen Texten suchen will, dann wird das schon interessant. Aber dann nimmt man ggf. auch andere Suchalgorithmen. Knuth-Morris-Pratt, Boyer-Moore, QuickSearch oder ein paar weitere, die ggf. auf bestimmte Spezialfälle hin optimiert sind. Parameter dafür sind u.a.

• Länge der gesuchten Teilstrings
• Größe des verwendeten Alphabets (also Anzahl der verschiedenen Zeichen)

Pos und PosEx laufen dabei unter "naive Verfahren".

Ein Anwendungsfall ist z.B. das Durchsuchen eines Genoms nach einer bestimmten DNA-Sequenz. Zumindest war das öfter ein Beispiel in der Literatur, als ich damals meine Diplomarbeit über "Algorithmen zur Mustersuche in Zeichenketten" geschrieben habe.

Aber es stimmt schon, dass das meistens irrelevant ist - denn selbst der "naive Algorithmus" hat eine (erwartete) lineare Laufzeit. KMP ist interessant, weil da auch die Worst-Case-Laufzeit linear ist (im Gegensatz zu quadratisch bzw. "rechteckig", d.h. Textlänge*Musterlänge im Worst Case bei Pos). Boyer-Moore z.B. wird schneller, wenn die Suchmuster länger werden.

Oder halt komplette andere Ansätze, wie z.B. vorher einen Suchindex über die zu durchsuchenden Texte aufbauen, aber das ist dann wirklich was komplett anderes.

Ich glaube, weiß es aber nicht, wenn es darum geht, alle Fundstellen (in aufsteigender Reihenfolge) zu finden, wird man um eine lineare Suche nicht herumkommen.

[himitsu]

Da gab es auf der EKON einen Vortrag, wo eine 1 Billionen-Zeilen-CSV binnen kürzester Zeit gelesen/verarbeitet wird. (war im anderen Raum, wo ich nicht drin war )

[Gausi]

Zitat von Amateurprofi:

Ich glaube, weiß es aber nicht, wenn es darum geht, alle Fundstellen (in aufsteigender Reihenfolge) zu finden, wird man um eine lineare Suche nicht herumkommen.

Wenn du ein einzelnes Zeichen suchst (z.B. die "0"), dann stimmt das. Wenn du aber z.B. alle Vorkommen der ersten 10 Stellen von Pi suchen willst (um mal bei Zahlen zu bleiben), dann muss man nicht unbedingt jedes einzelne Zeichen im Suchtext angucken und mit einem Zeichen im Muster vergleichen. So auf Anhieb würde ich wetten, dass man in dem Beispiel nur ungefähr jedes 5. Zeichen vergleichen muss. Statt 80 Millionen Vergleichen hätte man dann nur 16 Millionen.

Das Prinzip nennt sich bei Boyer-Moore die "Bad-Character-Heuristik", siehe https://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus.