AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Substring an bestimmter Position im String?
Thema durchsuchen
Ansicht
Themen-Optionen

Substring an bestimmter Position im String?

Ein Thema von 3_of_8 · begonnen am 3. Aug 2006 · letzter Beitrag vom 4. Aug 2006
Antwort Antwort
Seite 1 von 2  1 2      
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#1

Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 10:50
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:
if copy(str, 17, length('wuppdi'))='wuppdithen... Die Frage ist nur: Geht das nicht schneller? Kann ich z.B. mit posex einen Geschwindigkeitsvorteil herausarbeiten?
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#2

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 11:11
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!
  Mit Zitat antworten Zitat
xaromz

Registriert seit: 18. Mär 2005
1.682 Beiträge
 
Delphi 2006 Enterprise
 
#3

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 11:11
Hallo,
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
I am a leaf on the wind - watch how I soar
  Mit Zitat antworten Zitat
xaromz

Registriert seit: 18. Mär 2005
1.682 Beiträge
 
Delphi 2006 Enterprise
 
#4

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 11:17
Hallo,
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 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 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
I am a leaf on the wind - watch how I soar
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#5

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 11:34
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 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 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).
  Mit Zitat antworten Zitat
marabu

Registriert seit: 6. Apr 2005
10.109 Beiträge
 
#6

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 13:36
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
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.041 Beiträge
 
Delphi XE2 Professional
 
#7

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 14:15
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;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#8

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 15:15
OMG, Assembler... Ich probiers mal aus.
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#9

Re: Substring an bestimmter Position im String?

  Alt 3. Aug 2006, 21:42
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;
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.041 Beiträge
 
Delphi XE2 Professional
 
#10

Re: Substring an bestimmter Position im String?

  Alt 4. Aug 2006, 19:23
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;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 10:23 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz