Substring an bestimmter Position im String?

[3_of_8]

Morgen.

Ich habe gerade folgendes Problem:

Ich habe einen String (sagen wir mal 'blubbwuppdiblubbwuppdiblubb') und will jetzt herausfinden, ob an Position 17 ein 'wuppdi' steht. Normalerweise würde ich das so machen:

Delphi-Quellcode:

if copy(str, 17, length('wuppdi'))='wuppdi' then...

Die Frage ist nur: Geht das nicht schneller? Kann ich z.B. mit posex einen Geschwindigkeitsvorteil herausarbeiten?

[Der_Unwissende]

Hi,
ich denke mal dass PosEx dir einen (eher geringen) Vorteil bringen sollte. Beim Suchen von Teilstrings gibt es ein paar sehr effiziente Algorithmen. Die werden sicherlich (behaupte ich mal einfach) auch in Delphi verwendet werden.
Bei einem Copy hingegen wirst du erst den Overhead für das anlegen eines Strings haben und dann müssen natürlich auch die Daten kopiert werden. Dann hast du natürlich noch den Vergleich von Strings, auch der dauert länger als wenn du zwei Integerwerte vergleichst.
Von daher sollte ein PosEx auf eine Position zu vergleichen etwas schneller sein, dass irgendwer von den paar ns profitiert ist allerdings sehr sehr unwahrscheinlich!

[xaromz]

Hallo,

Zitat:

Zitat von 3_of_8

Die Frage ist nur: Geht das nicht schneller? Kann ich z.B. mit posex einen Geschwindigkeitsvorteil herausarbeiten?

PosEx könnte etwas schneller sein, weil eine Kopieraktion entfällt.
Das gilt allerdings nur, wenn der String an der angegebenen Position vorkommt. Sonst sucht PosEx ja den String und dann dauert es natürlich länger.

Gruß
xaromz

[xaromz]

Hallo,

Zitat:

Zitat von Der_Unwissende

Beim Suchen von Teilstrings gibt es ein paar sehr effiziente Algorithmen. Die werden sicherlich (behaupte ich mal einfach) auch in Delphi verwendet werden.

IMHO geht PosEx einfach linear durch den String und vergleicht.

Zitat:

Zitat von Der_Unwissende

Dann hast du natürlich noch den Vergleich von Strings, auch der dauert länger als wenn du zwei Integerwerte vergleichst.

Nein, Du hast ja bei beiden Versionen einen Stringvergleich. Dieser ist aber sehr effizient möglich (solange es geht, immer vier Chars als Integer zusammenfassen und vergleichen).

Zitat:

Zitat von Der_Unwissende

Von daher sollte ein PosEx auf eine Position zu vergleichen etwas schneller sein, dass irgendwer von den paar ns profitiert ist allerdings sehr sehr unwahrscheinlich!

Ob es etwas bringt, hängt immer von den Umständen ab, aber der Vor- oder Nachteil bewegt sich definitiv im Nanosekundenbereich.

Gruß
xaromz

[Der_Unwissende]

Zitat:

Zitat von xaromz

IMHO geht PosEx einfach linear durch den String und vergleicht.

Oh man, da hast du recht. Ist ja Erschreckend schlecht implementiert. Also der geht echt linear durch und versucht den Teilstring von der aktuellen Position aus zu finden, läuft so weit er kommt und wenn der dort nicht vorhanden ist, geht der weiter und macht rekursiv weiter.

Zitat:

Zitat von xaromz

Nein, Du hast ja bei beiden Versionen einen Stringvergleich. Dieser ist aber sehr effizient möglich (solange es geht, immer vier Chars als Integer zusammenfassen und vergleichen).

Ok, stimmt natürlich!

Aber unter den Umstädnen würde ich sagen, dass du eine eigene posEx-Methode posEx vorziehen kannst. Wenn du an einer festen Position suchst, dann brauchst du halt dieses weiterlaufen nicht. Da PosEs echt einfach implentiert ist, wäre auch keine Implementierung wirklich schlechter möglich. Aber auch hier bleibt halt die Frage ob sich das lohnt (für eine Zeit, die wahrscheinlich beim nächsten cache miss schon wieder drauf geht, mal etwas übertrieben gesagt).


Ich denke mal damit gilt

Zitat:

Zitat von xaromz

Das gilt allerdings nur, wenn der String an der angegebenen Position vorkommt. Sonst sucht PosEx ja den String und dann dauert es natürlich länger.

Mit Copy bist du also auf der sicheren Seite, falls der String mal extrem lang wird (wobei auch hier die erwartete Länge << als die max. Länge eines Strings sein dürfte, also auch hier im Durchschnitt kaum unterschiedliche Laufzeit).

[marabu]

Hi folks,

ich habe die Frage vielleicht ganz anders (falsch?) verstanden, aber ich denke dabei an sowas:

Delphi-Quellcode:

uses
  StrUtils;

var
  s, subStr: String;
  bFound: Boolean;

begin
  s := '1234567890123456demo1234567890';
  subStr := 'demo';
  bFound := CompareMem(@s[17], @subStr[1], Length(subStr));
  ShowMessage(IfThen(bFound, 'found', 'not found'));
end;

Grüße vom marabu

[Amateurprofi]

Nicht ausgiebig getestet, sollte aber funktionieren - und auch recht schnell.

Gibt True zurück wenn in s ab zeichen p ein mit substr identischer text steht. wenn p=0 dann wird p=1 angenommen
Gibt False zürück wenn s oder substr leer sind oder p>Length(s) ist oder nicht die obige bedingung zutrifft.

Delphi-Quellcode:

FUNCTION StrAtPos(const substr,s:string; p:integer):boolean;
asm
         push     edi
         push     esi
         test     eax,eax
         je       @Fail             // substring leer
         test     edx,edx
         je       @Fail             // s leer
         test     ecx,ecx
         jne      @1
         mov      ecx,1
@1:      mov      esi,eax           // @substr
         lea      edi,[edx+ecx-1]   // @s[p]
         mov      eax,ecx           // p
         mov      ecx,[esi-4]       // Lenght(substr)
         test     ecx,ecx
         je       @Fail             // Lenght(substr)=0
         lea      eax,[eax+ecx-1]   // p+Length(substr)-1
         cmp      eax,[edx-4]
         jbe      @Cmp              // Lenght ok
@Fail:   xor      eax,eax
         jmp      @End
@Cmp:    mov      edx,ecx
         shr      ecx,2
         repe     cmpsd             // (Lenght(substr) div 4) mal 4 Bytes vergleichen
         jne      @SetRes
@Bytes:  mov      ecx,edx
         and      ecx,3
         repe     cmpsb             // (Lenght(substr) and 3) Bytes vergleichen
@SetRes: sete     al
@End:    pop      esi
         pop      edi
end;

[3_of_8]

OMG, Assembler... Ich probiers mal aus.

[3_of_8]

Funktioniert, aber wie kriege ich das Case Insensitive? Ich weiß nicht, wir man in Assembler Funktionen aufruft. (Also Parameter übergibt)

Meine Idee wäre jetzt sowas gewesen:
Ich rufe AnsiLowerCase auf, denn substr steht in eax.
Dann pushe ich eax auf den Stack und lade edx (wo s steht) nach eax, rufe wieder AnsiLowerCase auf und lade eax nach edx.
Dann poppe ich eax wieder runter.
Gibt nur ne AV. Warum? Was mache ich falsch?

Delphi-Quellcode:

function StrAtPos(substr, s: string; p: integer): boolean;
asm
         call     AnsiLowerCase
         push     eax
         mov      eax, edx
         call     AnsiLowerCase
         mov      edx, eax
         pop      eax
         push     edi
         push     esi
         test     eax,eax
         je       @Fail
         test     edx,edx
         je       @Fail
         test     ecx,ecx
         jne      @1
         mov      ecx,1
@1:      mov      esi,eax
         lea      edi,[edx+ecx-1]
         mov      eax,ecx
         mov      ecx,[esi-4]
         test     ecx,ecx
         je       @Fail
         lea      eax,[eax+ecx-1]
         cmp      eax,[edx-4]
         jbe      @Cmp
@Fail:   xor      eax,eax
         jmp      @End
@Cmp:    mov      edx,ecx
         shr      ecx,2
         repe     cmpsd
         jne      @SetRes
@Bytes:  mov      ecx,edx
         and      ecx,3
         repe     cmpsb
@SetRes: sete     al
@End:    pop      esi
         pop      edi
end;

[Amateurprofi]

Zitat:

Zitat von 3_of_8

Meine Idee wäre jetzt sowas gewesen:
Ich rufe AnsiLowerCase auf, denn substr steht in eax.
Dann pushe ich eax auf den Stack und lade edx (wo s steht) nach eax, rufe wieder AnsiLowerCase auf und lade eax nach edx.
Dann poppe ich eax wieder runter.
Gibt nur ne AV. Warum? Was mache ich falsch?

@Manuel,
Wenn Du AnsiLowerCase aufrufst, dann werden dort EDX und auch ECX verändert, d.h. sowohl @s und p sind nicht mehr verfügbar.
Du könntest das lösen, indem Du vor Aufruf von AnsiLowerCase die Register rettest, z.B.

push ecx
push edx
call AnsiLowerCase
xchg [esp],eax // @LowerCase(substr) auf Stack, EAX=@s
call AnsiLowerCase
mov edx, eax // @LowerCase(s)
pop eax // @LowerCase(substr)
pop ecx // p

Aber das wäre eher kontraproduktiv weil damit die Performance im Eimer ist.

Ich hab das mal ungeschrieben in 3 Funktionen

1) StrAtPos = binärer Vergleich
2) TextAtPos = arbeitet case insensitiv für A..Z / a..z
3) AnsiTextPos = arbeitet komplett case insensitiv

Um die Längenprüfung nicht in allen Funktionen vornehmen zu müssen, habe diese in eine separate Prozedur _CheckLengths ausgelagert.
Das Retten der Register EDI und ESI wird in _CheckLengths vorgenommen, d.h. EDI und ESI müssen in ..AtPos nicht auf den Stack gelegt, jedoch am Ende vom Stack genommen werden.
Wenn bereits die Längenprüfung ein False ergibt, dann wird nicht in die ..AtPos Funtionen zurückgekehrt sondern dorthin von wo ..AtPos aufgerufen wurde (und es wird natürlich False zurückgegeben).
Damit entfällt auch in den ..AtPos Funktionen die Prüfung des Resultates von _CheckLengths.
Ist ein bischen trickie, funktioniert aber.
Wenn mir nicht grobe Fehler unterlaufen sind, sollten die Funktionen das tun was sie tun sollen.

Delphi-Quellcode:

// Subroutine für die Funktionen StrAtPos, TextAtPos, AnsiTextAtPos
// --> EAX=@substr, EDX=@s, ECX=p
// Prüft ob die strings s und subst nicht leer sind und ob s lang genug ist,
// um ab s[p] substr enthalten zu können. Wenn p=0 ist, wird p=1 angenommen.
// Mögliche Resultate:
// 1) Einer der Stings ist leer oder s nicht lang genug:
//    Rücksprung zu der Adresse, von der die aufrufende Funktion aufgerufen
//    wurde mit dem Resultat False
// 2) Längenprüfung OK
//    <-- EDI=@s[p], ESI=@Substr, ECX=Length(substr)
//    EDI und ESI wurden auf den Stack gelegt und müssen von der aufrufenden
//    Routine vom Stack genommen werden
PROCEDURE _CheckLengths;
asm
         xchg     [esp],edi         // EDI auf Stack, EDI=Returnadresse
         push     esi               // ESI auf Stack
         push     edi               // Returnadresse auf Stack
         test     eax,eax
         je       @Fail             // substring leer
         test     edx,edx
         je       @Fail             // s leer
         test     ecx,ecx
         jne      @1
         mov      ecx,1
@1:      mov      esi,eax           // @substr
         lea      edi,[edx+ecx-1]   // @s[p]
         mov      eax,ecx           // p
         mov      ecx,[esi-4]       // Lenght(substr)
         test     ecx,ecx
         je       @Fail             // Lenght(substr)=0
         lea      eax,[eax+ecx-1]   // p+Length(substr)-1
         cmp      eax,[edx-4]
         jbe      @End
@Fail:   xor      eax,eax
         pop      ecx               // Resturnadresse der aufrufenden Funktion
         pop      esi
         pop      edi
@End:
end;


FUNCTION StrAtPos(const substr,s:string; p:integer):boolean;
asm
         call     _CheckLengths
         mov      edx,ecx
         shr      ecx,2
         repe     cmpsd             // (Lenght(substr) div 4) mal 4 Bytes vergleichen
         jne      @SetRes
@Bytes:  mov      ecx,edx
         and      ecx,3
         repe     cmpsb             // (Lenght(substr) and 3) Bytes vergleichen
@SetRes: sete     al
@End:    pop      esi
         pop      edi
end;

FUNCTION TextAtPos(const substr,s:string; p:integer):boolean;
asm
         call     _CheckLengths
@Loop:   sub      ecx,1
         jc       @SetRes
         mov      al,[esi+ecx]      // Char aus substr
         mov      dl,[edi+ecx]      // Char aus s
         xor      al,dl
         je       @Loop             // identisch
         cmp      al,$20
         jne      @Fail             // nicht nur Bit 5 unterschiedlich
         and      dl,$DF            // Bit 5 in DL löschen (=UpperCase)
         cmp      dl,'A'
         jb       @Fail
         cmp      dl,'Z'
         jbe      @Loop
@Fail:   clc
@SetRes: setc     al
@End:    pop      esi
         pop      edi
end;

FUNCTION AnsiTextAtPos(const substr,s:string; p:integer):boolean;
asm
         call     _CheckLengths
@Loop:   sub      ecx,1
         jc       @SetRes
         mov      al,[esi+ecx]      // Char aus substr
         mov      dl,[edi+ecx]      // Char aus s
         xor      al,dl
         je       @Loop             // identisch
         cmp      al,$20
         jne      @Fail             // nicht nur Bit 5 unterschiedlich
         and      dl,$DF            // Bit 5 in DL löschen (=UpperCase)
         cmp      dl,'A'
         jb       @Fail
         cmp      dl,'Z'
         jbe      @Loop
         cmp      dl,$C0
         jb       @Fail
         cmp      dl,$D7
         je       @Fail
         cmp      dl,$df
         jne      @Loop
@Fail:   clc
@SetRes: setc     al
@End:    pop      esi
         pop      edi
end;