Entwickler-Ecke
Algorithmen, Optimierung und Assembler - "rückläufige" Stringverkettung mit +Operator, StrCopy etc.
Lannes - Di 29.09.09 19:09
Titel: "rückläufige" Stringverkettung mit +Operator, StrCopy etc.
Hallo,
"rückläufig" der richtige Begriff :gruebel:
Eine Stringverkettung mittels +Operator ist ja schon recht schnell, eine Verbesserung kann durch setzen der zu erwartenden Stringlänge mit Setlength, sowie StrCopy oder Move erzielt werden.
Beispiel:
5000 Strings < Länge 20
Result := Result + s; = 0,021 Sek
Setlength() und StrCopy() = 0,015 Sek
so und nun das "rückläufige", da wird es richtig langsam:
Result := s + Result; = 43,382 Sek
Ich suche eine Möglichkeit die Performance an dieser Stelle zu verbessern, eine Umstellung meiner Functionen/Prozeduren von
Result := s + Result; auf Result := Result + s; ist sehr schwierig/aufwändig.
Hat jemand einen heißen Tipp oder einen Ansatz?
Xentar - Di 29.09.09 20:00
Naja, das Problem ist: Wenn du eine Zeichenkette davor schreiben willst, muss erst der gesamte String um x-Zeichen nach hinten kopiert / umkopiert werden -> braucht Zeit.
Aber wieso musst du in einer Schleife 5000 Strings aneinanderketten? Vielleicht wäre hier ein Array oder ähnliches sinnvoller?
Und: was sind das für Strings? Haben die z.B. immer eine feste Länge?
Wenn du bei dem Konzept mit den Strings bleiben möchtest, wäre anhängen wohl die bessere Wahl.
nagel - Di 29.09.09 20:13
Die Schleife umgekehrt durchlaufen?
Horst_H - Mi 30.09.09 00:43
Hallo,
die umgekehrte Reihenfolge wäre wohl das einfachste.
Aber mittels Stringlist ist es ja auch nicht unflott:
Ganz stimmen die ersten Zeiuten nicht, weil cool&quite am wirken ist.Deshalb ist die erste Zuweisung doppelt so langsam wie die letzte.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| Ausgabe von Programm Test:
Anzahl 50000
Einfache Zuweisung 00:00:00.013
Hintanstellen 00:00:00.010
Voranstellen 00:00:03.950
Reihenfolge umkehren 00:00:00.001
Neue Reihenfolge zuweisen00:00:00.006 |
Also etwa derart:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| Resultliste:= TSTringlist.create;
for i := 0 to ???
begin
....erzeuge s
ResultListe.add(s);
end;
ListeUmkehren(ResultListe);
result := ResultListe.text;
ResultListe.free; |
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:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
| program test;
{$APPTYPE CONSOLE]
//Freepascal {$H+}{$mode delphi}
uses
sysutils,classes;
const
ANZAHL = 50000;
var
TestListe : TStringlist;
s,k : ansistring;
t0,t1: TDateTime;
j : integer;
procedure ListeUmkehren(Liste:TStringlist);
var
i,j: integer;
begin
j := 0;
i := Liste.count-1;
while j<i do
begin
Liste.exchange(i,j);
inc(j);
dec(i);
end;
end;
function IncString(var s:string):string;
var
i : integer;
pChr : pchar;
begin
result := s;
i := length(result);
pChr := @result[i];
repeat
inc(pChr^);
IF ord(pChr^) >= (ord('0')+10) then
begin
pChr^ := '0';
dec (pChr);
end
else
break;
dec(i);
until i <= 0;
uniquestring(result);
end;
begin
TestListe := TStringlist.create;
S := '0000000000';
For j := 0 to ANZAHL-1 do
begin
testliste.add(IncString(s));
end;
t0 := time;
s := testliste.text;
t1 := time;
writeln('Anzahl ',ANZAHL);
writeln('Einfache Zuweisung ',FormatDateTime('hh:mm:ss.zzz',T1-t0));
k := '';
t0 := time;
S := '0000000000';
For j := 0 to ANZAHL-1 do
begin
k := k+s;
end;
t1 := time;
writeln('Hintanstellen ',FormatDateTime('hh:mm:ss.zzz',T1-t0));
k := '';
t0 := time;
S := '0000000000';
For j := 0 to ANZAHL-1 do
begin
k := s+k;
end;
t1 := time;
writeln('Voranstellen ',FormatDateTime('hh:mm:ss.zzz',T1-t0));
t0 := time;
ListeUmkehren(testliste);
t1 := time;
writeln('Reihenfolge umkehren ',FormatDateTime('hh:mm:ss.zzz',T1-t0));
t0 := time;
s:= testliste.text;
t1 := time;
writeln(s);
writeln('Neue Reihenfolge zuweisen',FormatDateTime('hh:mm:ss.zzz',T1-t0));
testliste.free;
readln
end. |
Lannes - Mi 30.09.09 09:46
Hallo,
erstmal Danke für die Antworten :)
@
Xentar
Die 5000 Strings sind der Wert den ich zum Testen angesetzt habe. Es geht mir bei der Geschichte nicht um keinen speziellen Fall, ich bin dabei mir eine String-Klasse zu erstellen, die ich dann bei Bedarf universell einsetzen kann. Das Aneinanderhängen(in der Klasse mit StrCopy) habe ich, sieht dann so aus:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
| var Str : TStr;
begin
Str := TStr.Create;
Str.Add('Mein String');
|
Mein Ziel ist jetzt ein schnelles
Str.Insert('Mein String'); zum "Voreinanderhängen" zu realisieren.
@
nagel
ja, in die Richtung muss es vermutlich gehen, die ja auch in dem nachfolgenden Beitrag von
Horst_H vorgeschlagen wird.
@
Horst_H
Hab Deinen Vorschlag mal in meiner Testumgebung umgesetzt, erst in eine StringListe schreiben, dann mit DownTo in einen String schreiben, sieht gut aus :zustimm:
Meine aktuellen Ergebnisse:
5000 Strings unterschiedliche Länge(1 bis 20 Zeichen)
Result := s + Result; = 43,382 Sek
mit StringListe, DownTo und StrCopy = 0,019 Sek
Lannes - Mi 30.09.09 15:52
Hallo,
hatte bei der Testausführung(StringList ...) einen Fehler eingebaut, dadurch hat sich die Zeit erhöht.
Mein aktueller Ansatz mit SetLength und Move ist schon besser. :)
Ich setze zu Anfang die Ziel-Stringlänge auf Length(Substring) * 2, mit Move werden dann die Strings vom Ende rückwärts einkopiert. Bei Bedarf wird der Ziel-String verlängert(verdoppelt) und das schon einkopierte ans Ende kopiert/verschoben.
Meine aktuellen Ergebnisse:
5000 Strings unterschiedliche Länge(1 bis 20 Zeichen)
Result := s + Result; = 43,382 Sek
mit StringListe, DownTo und StrCopy = 0,032 Sek
mit SetLength und Move = 0,016 Sek
Die Zeit steigt linear, bei 5.000.000 Strings(ca 660 MB) ergab die Messung 16.588 Sek
So, jetzt noch add und insert kombinieren ...
Vielen Dank nochmal für eure Beiträge.
BenBE - Do 01.10.09 09:33
Also ich würde das auch erstmal eher so sehen, dass man die Größe der Strings berechnet (damit man weiß, wieviel Speicher man braucht) und dann den Zielpuffer von hinten beschreiben.
Wenn man das allgemein halten möchte, kann man sogar so weit gehen, dass man einen Puffer einmal allokiert, und diesen dann immer "von der Mitte aus" beschreibt. Dann sind concatenate und voranstellen gleich schnell; bedürfen dann aber beide zum Produzieren des eigentlichen Ergebnisses etwas nacharbeit.
Lannes - Do 01.10.09 12:28
Hallo,
geschafft, die Kombination aus add und Insert läuft. :)
Mit "von der Mitte aus" ist meine jetzige Vorgehensweise gut beschrieben.
Ich berechne aber nicht im Vorraus den benötigten Platz, damit die Klasse möglichst allgemein nutznbar ist. Die Puffer-Vergrößerung hab ich so realisiert, das mit zunehmender Größe der Bedarf zur Vergrößerung seltener wird.
Meine Werte sind jetzt(5.000.000 Strings):
Add-Klasse = 14,855 Sek
Insert-Klasse = 16,588 Sek
AddInsert-Klasse = 15,650 Sek (2.500.000 Add und 2.500.000 Insert)
Eine Vorrausberechnung der Größe bringt keinen großen Zeitvorteil, sie heben sich annähernd gegeneinander auf
(+ Vorrausberechnung - Zeitvorteil).
Das Bild erklärt es wohl ausreichend:
Lannes - Do 01.10.09 15:23
Hallo,
mal überlegen ... String noch vorn schieben ... Länge setzen ... :arrow:
Delphi-Quelltext
1:
2:
3:
| iLen := SchreibPositionAdd - SchreibPositionInsert;
Move(s[SchreibPositionInsert],s[1],iLen);
SetLength(s,iLen); |
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!