Entwickler-Ecke
Algorithmen, Optimierung und Assembler - CompareText Optimierung
Flamefire - Mo 27.10.08 15:19
Titel: CompareText Optimierung
Ich möchte einen Textvergleich optimieren. Mir geht es dabei um keine logische Anordnung sondern um eine schnelle Aussage, ob ein Text vor einem anderen kommt oder danach oder gleich ist. Geht um eine Vergleichsfunktion.
Also die Folgende Funktion:
//TOrdner ist ein Objekt. FName ein String und FNameL die Länge davon
Delphi-Quelltext
1: 2: 3:
| function Compare(o1,o2:Pointer):Integer; begin CompareText(TOrdner(o1).FName,TOrdner(o1).FName); |
1.Optimierung (Zeitgewinn ca. 15%)
Delphi-Quelltext
1: 2: 3: 4:
| function Compare(o1,o2:Pointer):Integer; begin Result:=TOrdner(o1).FNameL-TOrdner(o1).FNameL; If(Result=0) then CompareText(TOrdner(o1).FName,TOrdner(o1).FName); |
Optimierungsansatz nach feststellen gleicher länge:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:
| var lcomp:Integer; p1,p2:Pointer; begin p1:=Ptr(String1); p2:=Ptr(String2); lcomp:=0; while(lcomp+4<=l) do begin Result:=PInteger(p1)-PInteger(p2); If(Result<>0) then exit; Inc(p1,4);Inc(p2,4);Inc(lcomp,4); end; while(lcomp+1<=l) do begin Result:=PByte(p1)-PByte(p2); If(Result<>0) then exit; Inc(p1);Inc(p2);Inc(lcomp); end; |
würde das so gehen? Könnten Integerüberläufe auftreten und Fehler verursachen? (Besonders bei dem Byte-Vergleich)
Gibt es noch bessere Optimierungen oder Vorschläge?
z.b. könnte man die +4 noch iwie nur einmal ausführen lassen. weiß aber nicht wie.
Und ja solche optimierungen lohnen, da der code SEHR häufig ausgeführt wird.
Gammatester - Mo 27.10.08 16:08
Wenn Du keinen Fastcode nehmen willst, mußt Du die Fälle behandeln, in denen durch den Typecast die Integers negativ werden können. Das kann zB die Vergleichsreihenfolge umkehren, wenn Integer positiv, der andere negativ ist. Außerdem wird's Probleme mit overflows geben (selbst dann wenn $Q-, $R- gesetzt wurde).
Gruß Gammatester
Flamefire - Mo 27.10.08 17:33
selbst der fastcode wird langsamer sein, da er alle fälle behandeln muss und logisch sortieren muss!
ok ich guck mal wo was mit den integern nicht klappt
alzaimar - Mo 27.10.08 22:07
In einer Stringmatch-Implementierung habe ich eine Prüfung der jeweils ersten und letzten Zeichen einer CompareText-Prüfung vorgeschaltet. Die Verbesserungen sind drastisch. Aber Vorsicht: Das lohnt sich nur bei relativ langen Strings. Erstell doch mal ein Beispielprojekt mit Zeitmessung und stelle das hier rein. Dann können Alle mithelfen.
Flamefire - Mi 29.10.08 11:05
Bsp-Projekt: 1 Button + 1 Memo
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94:
| function CompStr(const String1,String2:String;const l:Integer):Integer; var lcomp:Integer; p1,p2:Cardinal; begin p1:=Cardinal(Pointer(String1)); p2:=Cardinal(Pointer(String2)); lcomp:=4; if(lcomp<=l) then begin Repeat Result:=PInteger(p1)^-PInteger(p2)^; If(Result<>0) then exit; If(lcomp=l) then exit; Inc(p1,4);Inc(p2,4); Inc(lcomp,4); If(lcomp>l) then begin Dec(lcomp,4); break; end; Until false; end else lcomp:=0; Inc(lcomp); Repeat Result:=PByte(p1)^-PByte(p2)^; If(Result<>0) then exit; If(lcomp=l) then exit; Inc(p1);Inc(p2); Inc(lcomp); Until false; end;
procedure TForm1.Button1Click(Sender: TObject); var freq,startTime,endTime: Int64; i:Integer; s1,s2,s3,s4,s5,s6:String; l1,l2,l3,l4,l5,l6:Integer; arrayB:Integer; b:Integer; begin Memo1.Clear; s1:='Btdfu%&6554787BGHBtzbTuzGT'; s2:='Btdfu%&6554787BGHBtzbTuzGT'; s3:='Btdfu%&6554787BGHBtzbTuzG'; s4:='Btdfu%&6554787BGHBtzbTuzGA'; s5:='Btdfu%&6554787BGHBtzbTuzGt'; s6:='Atdfu%&6554787BGHBtzbTuzGt'; l1:=Length(s1); l2:=Length(s2); l3:=Length(s3); l4:=Length(s4); l5:=Length(s5); l6:=Length(s6); arrayB:=0; QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime);
for i:=0 to 9999999 do begin b:=l1-l2; if(b=0) then b:=CompStr(s1,s2,l1); b:=l1-l3; if(b=0) then b:=CompStr(s1,s3,l1); b:=l1-l4; if(b=0) then b:=CompStr(s1,s4,l1); b:=l1-l5; if(b=0) then b:=CompStr(s1,s5,l1); b:=l1-l6; if(b=0) then b:=CompStr(s1,s6,l1); end;
QueryPerformanceCounter(endTime);
Memo1.Lines.Add('1.Variante: ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms'); Memo1.Lines.Add(inttostr(arrayB));
arrayB:=0; QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime);
for i:=0 to 9999999 do begin b:=CompareText(s1,s2); b:=CompareText(s1,s3); b:=CompareText(s1,s4); b:=CompareText(s1,s5); b:=CompareText(s1,s6); end;
QueryPerformanceCounter(endTime);
Memo1.Lines.Add('2.Variante: ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms'); Memo1.Lines.Add(inttostr(arrayB)); end; |
Aktuelle Zeiten:
(Variante1;Variante2)
Normal: 1169;4389
FastMM4: 1096;4470
FastMM4+FastCode: 1089;1363
Auskommentieren von s3-->Alle Strings haben gleiche Länge-->1.Variante hat Nachteil
FastMM4: 1090;3620
FastMM4+FastCode: 1073;901
Nur Vergleich von s1 und s2-->Gleiche Strings
FastMM4+FastCode: 196;45
-->Nur bei gleich Langen Strings oder gleichen Strings ist Fastcode schneller
Kann Jemand meine Funktion in ASM übersetzen und optimieren? Sollte einiges bringen
SvenAbeln - Mi 29.10.08 14:29
Flamefire hat folgendes geschrieben : |
-->Nur bei gleich Langen Strings oder gleichen Strings ist Fastcode schneller
|
Und in den anderen Fällen ist dein Vergleich etwas unfair.
Die Länge der Strings wird nur einmal zu Beginn bestimmt und dies geht noch nicht einmal in die gemessene Zeit mit ein.
Bei verschiedenen Längen macht deine Variante 1 in der Schleife nur noch einen Vergleich von L1 und L3 ohne die Längen aber jeweils neu zu berechnen.
Die eigentliche Vergleichfunktion CompStr(s1,s3,l1) wird dann gar nicht mehr aufgerufen.
Wenn der Längenvergleich Teil deiner Optimierung sein soll, dann müssen die Zeiten zum bestimmen der Länge aber auch mit in deine Zeitmessung eingehen.
Ansonsten hätte ich eine schneller Lösung : :twisted: :wink:
Delphi-Quelltext
1: 2: 3: 4:
| b3 := CompareText(s1,s3); for i:=0 to 9999999 do begin b:= b3; end; |
Flamefire - Mi 29.10.08 18:21
es geht aber darum, dass die längenberechnung nur einmal ausgeführt wird, außerhalb der vergleichsmethode...
um genau zu sein, könnte ich aber die längenmessungen mit unter das queryperformance... setzen
ist aber ebn nur einmal! und da es ne simple kopierfunktion von 4 Byte ist sollte das nur 1ms ausmachen
SvenAbeln - Mi 29.10.08 18:54
Aber du willst doch in der Realität doch verschiedene Strings vergleichen und nicht 9999999 mal immer wieder die selben. Daher wirst du dann auch jedesmal die Längenmessungen machen müssen.
Was dein Vergleich im Moment für ungleiche Stringlängen aussagt ist:
9999999 mal
b:=l1-l3;
und prüfen ob b=0 // was es in diesem Fall ja nicht ist
ist schneller als:
9999999 mal compareText
Aber wie sieht es aus wenn du nun 9999999 mal verschiedene Strings vergleichen willst?
alzaimar - Mi 29.10.08 19:01
Nochmal für mich als Hausfrau, zum Mitschreiben: Du willst eine Ordnung auf Strings. Nicht notwendigerweise eine lexikalische Ordnung, aber zumindest eine (totale) Ordnung. Als Performancetrick definierst du, das kürzere Strings stets "kleiner" und längere Strings stets "größer" als ein Referenzstring ist. Soweit richtig?
Wie lautet der Funktionsaufruf (bevor irgendetwas verglichen wird)? Ich schlage vor:
Delphi-Quelltext
1:
| Function FastCompareStrings (Const s1, s2 : String) : integer; |
Wenn Du jedoch z.B. einen String 'X' hast, den Du gegen 1.000.000 andere Strings vergleichen willst, sieht die Sache anders aus. Also?
Flamefire - Mi 29.10.08 19:21
ok es geht um listen von strings
diese listen wird einmal erstellt und muss dann (möglicherweise) sehr oft gegeneinander abgeglichen werden
darum nur einmal die längenberechnung aber der häufige vergleich
trotzdem ist selbst mit längenberechnung jedesmal der stringvergleich über die länge vorher um 100-200ms schneller
was fehlt ist also eine optimierte version meines vergleichs
SvenAbeln - Mi 29.10.08 19:40
Flamefire hat folgendes geschrieben : |
trotzdem ist selbst mit längenberechnung jedesmal der stringvergleich über die länge vorher um 100-200ms schneller
was fehlt ist also eine optimierte version meines vergleichs |
Du hattest doch oben schon geschrieben:
Flamefire hat folgendes geschrieben : |
-->Nur bei gleich Langen Strings oder gleichen Strings ist Fastcode schneller
|
Warum kombinierst du dann nicht beide Varianten?
Deinen Vergleich rufst du ja auch nur bei gleich langen Strings auf.
Also erst Vergleich über die Länge und dann Fastcode.
Delphi-Quelltext
1: 2:
| b:=l1-l2; if(b=0) then b:=FastCode ; |
Flamefire - Mi 29.10.08 19:57
weils es mir am liebsten wäre, den FastCode noch weiter zu optimieren, da die Länge ja schon feststeht
alzaimar - Mi 29.10.08 20:13
Das hier ist eh schneller:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| Function FastCompare (Const s1, s2 : String) : Integer; Var l1, i : Integer;
Begin l1 := Length(s1); Result := l1 - Length(s2); if Result=0 then For i := 1 to l1 do if s1[i]<>s2[i] then begin Result := Ord(s1[i])-Ord(s2[i]); Exit; End; End; |
Vorteil: Die ganze Optimierungslogik ist in einer Routine gekapselt.
SvenAbeln - Mi 29.10.08 20:27
Flamefire hat folgendes geschrieben : |
weils es mir am liebsten wäre, den FastCode noch weiter zu optimieren, da die Länge ja schon feststeht |
Wenn du die Länge schon hast, dann benutze diese Information doch auch beim Fastcode.
Wie eben schon geschrieben, erst die Länge prüfen und nur wenn die gleich ist den Fastcode benutzen, der ja gerade bei gleich langen Strings schneller ist.
Flamefire - Mi 29.10.08 21:09
@alzaimar: diese methode ist auf jeden fall langsamer, da byteweise verglichen wird. bei mir wird 4-byte weise verglichen
@sven: ja hab ich auch vor, aber den fastcode kann man ja weiter optimieren, da der die länge nicht mehr beachten muss
alzaimar - Mi 29.10.08 23:14
Flamefire hat folgendes geschrieben : |
@alzaimar: diese methode ist auf jeden fall langsamer, da byteweise verglichen wird. bei mir wird 4-byte weise verglichen |
Hast Du es auch getestet? :wink: Ich würde nicht behaupten, es sei schneller, wenn ich es nicht selbst... aber was red ich, gegen solch geballtes Fundamentalwissen bin ich machtlos.
Gammatester - Mi 29.10.08 23:17
Flamefire hat folgendes geschrieben : |
@alzaimar: diese methode ist auf jeden fall langsamer, da byteweise verglichen wird. bei mir wird 4-byte weise verglichen
|
Irgendwann mußt Du allerdings mal sagen, wie Du nun die 4-Byte-Problematik lösen willst. Mit dem Integervergleich ist zb 'ÄÄÄÄ'
kleiner als 'aaaa', aber zb nicht 'XXXXÄ' kleiner als 'XXXXa' wenn der letzte Vergleich über ord('Ä') und ord('a') geht. Also insgesamt ziemlich unbefriedigend.
Gammatester
Flamefire - Mi 29.10.08 23:39
mir geht es ja (wie oben beschrieben) nicht um eine lexikalische ordnung sondern nur um irgendeine Ordnung
und da reicht es einen string in 4-byte-pakete zu zerlegen und sich zu nutze zu machen dass der prozessor sowieso mit 4 byte (32bit) arbeitet. sollte um den faktor 3-5 schneller sein (je nachdem wie er intern die byteumwandlung macht)
Fastcode arbeitet ja in gewissem sinne mit dieser methode. allerdings hat er ein paar umwandlungen und rechnerein drin, die für mich nicht nötig sind (groß/kleinschreibung) und eben der lexikalische teil
meine asm kenntniss sind leider nicht so gut um da wirklich durchzusehen
alzaimar - Do 30.10.08 10:42
Also mein Code ist auf meinem Laptop schneller, auf einem AMD64 dagegen viel langsamer... Na ja, ich rudere also 50% zurück.
Egal. Geh nochmal auf die FastCode-Seite und lade Dir die Ergebnisse von 'CompareStr' (nicht CompareText). Hier meine Ergebnisse mit deinem Benchmark:
CompStr: 1465ms
CompareText: 2538ms
Fastcode_CompareStr: 1046ms
Flamefire - Do 30.10.08 12:05
verdammt...ja hab übersehn, dass bei groß/kleinschreibung es langsamer wird, wenn es ignoriert werden soll...
compareStr mit längen-überprüfung vorher ist demnach das schnellste...doppelt so schnell, wie meine bisherige methode
Motzi - Mo 10.11.08 19:38
Du solltest für der Optimierung nicht bei der Implementierung ansetzen, sondern beim Algorithmus..! Ein schlecht implementierter Quicksort ist immer noch um Größenordnungen schneller als ein perfekt implementiert und hochoptimierter Bubblesort - und so ähnlich ist es hier auch.
Daher werfe ich einfach mal
Suffix-Trees [
http://en.wikipedia.org/wiki/Suffix_tree] in die Runde. Ist zwar sicher etwas mehr Implementierungsaufwand, aber dafür baust du diese genau einmal auf (in linearer Zeit) und kannst dann in ebenfalls linearer Zeit darin suchen!
Gruß, Motzi
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!