|
Alternative zu PosEx
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} |
AW: Alternative zu PosEx
Lies besser nicht meine Signatur. :stupid:
OK, bei dem alten Delphi solltest du das überall das "Pos" in "PosEx" umbenennen .... ist aber eigentlich sieit vielen Jahren nicht mehr nötig. :angle:
Delphi-Quellcode:
:duck:
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; |
AW: Alternative zu PosEx
Zitat:
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:lol: ... was ich leider auch so angedacht hatte. |
AW: Alternative zu PosEx
Zitat:
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. |
AW: Alternative zu PosEx
War Pos nicht früher (vor Äonen) mal langsamer?
Ich glaub dort wurde auch was vom FastStrings mal mit übernommen. |
AW: Alternative zu PosEx
Zitat:
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." |
AW: Alternative zu PosEx
Zitat:
|
AW: Alternative zu PosEx
Zitat:
|
AW: Alternative zu PosEx
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 :duck:)
|
AW: Alternative zu PosEx
Zitat:
Das Prinzip nennt sich bei Boyer-Moore die "Bad-Character-Heuristik", siehe  https://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus. |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 23: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