Autor Beitrag
Lannes
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2352
Erhaltene Danke: 4

Win XP, 95, 3.11, IE6
D3 Prof, D4 Standard, D2005 PE, TurboDelphi, Lazarus, D2010
BeitragVerfasst: Di 29.09.09 19:09 
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?

_________________
MfG Lannes
(Nichts ist nicht Nichts) and ('' <> nil ) and (Pointer('') = nil ) and (@('') <> nil )
Xentar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2077
Erhaltene Danke: 2

Win XP
Delphi 5 Ent., Delphi 2007 Prof
BeitragVerfasst: 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.

_________________
PROGRAMMER: A device for converting coffee into software.
nagel
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 708

Win7, Ubuntu 10.10

BeitragVerfasst: Di 29.09.09 20:13 
Die Schleife umgekehrt durchlaufen?
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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.
ausblenden 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:
ausblenden 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;


ausblenden volle Höhe 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;
//Einen Zahlenstring s wird um 1 erhöhen
// und als uniquestring zurückgegeben
var
  i : integer;
  pChr :  pchar;
begin
   result := s;  
   
   i := length(result);
   pChr := @result[i];
   repeat
     inc(pChr^);
     IF ord(pChr^) >= (ord('0')+10then
       begin
       pChr^ := '0';
       dec (pChr);
       end
     else
       break; 
     dec(i);
   until i <= 0;   
   uniquestring(result);   
end;   

begin
  TestListe := TStringlist.create;
  //Erzeugen
  S := '0000000000';
  For j := 0 to ANZAHL-1 do
    begin
    //testliste.add(format('%10d',[j]));
    testliste.add(IncString(s));
    end;
    
  t0 := time;
  s := testliste.text;  
  t1 := time;
  //writeln(s);
  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(k);
  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(k);
  writeln('Voranstellen ',FormatDateTime('hh:mm:ss.zzz',T1-t0));
  //Umkehren
  t0 := time;
  ListeUmkehren(testliste);
  t1 := time;
  writeln('Reihenfolge umkehren ',FormatDateTime('hh:mm:ss.zzz',T1-t0));
  //Ausgeben  
  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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2352
Erhaltene Danke: 4

Win XP, 95, 3.11, IE6
D3 Prof, D4 Standard, D2005 PE, TurboDelphi, Lazarus, D2010
BeitragVerfasst: Mi 30.09.09 09:46 
Hallo,

erstmal Danke für die Antworten :)

@user profile iconXentar
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:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
var Str : TStr;
begin
  Str := TStr.Create;
  //Klasse nutzen
  Str.Add('Mein String');
  //...

Mein Ziel ist jetzt ein schnelles Str.Insert('Mein String'); zum "Voreinanderhängen" zu realisieren.

@user profile iconnagel
ja, in die Richtung muss es vermutlich gehen, die ja auch in dem nachfolgenden Beitrag von user profile iconHorst_H vorgeschlagen wird.

@user profile iconHorst_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

_________________
MfG Lannes
(Nichts ist nicht Nichts) and ('' <> nil ) and (Pointer('') = nil ) and (@('') <> nil )
Lannes Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2352
Erhaltene Danke: 4

Win XP, 95, 3.11, IE6
D3 Prof, D4 Standard, D2005 PE, TurboDelphi, Lazarus, D2010
BeitragVerfasst: 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.

_________________
MfG Lannes
(Nichts ist nicht Nichts) and ('' <> nil ) and (Pointer('') = nil ) and (@('') <> nil )
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Lannes Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2352
Erhaltene Danke: 4

Win XP, 95, 3.11, IE6
D3 Prof, D4 Standard, D2005 PE, TurboDelphi, Lazarus, D2010
BeitragVerfasst: 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:
AddInsert
Einloggen, um Attachments anzusehen!
_________________
MfG Lannes
(Nichts ist nicht Nichts) and ('' <> nil ) and (Pointer('') = nil ) and (@('') <> nil )
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Do 01.10.09 13:54 
Mit der PChar-Version ist das aber nicht Binary-Safe ... Bitte mit SetLength\Move dann den finalen String bilden ...

Schöne Diskussion dazu: www.heise.de/securit...7/msg-17443553/read/

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Lannes Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2352
Erhaltene Danke: 4

Win XP, 95, 3.11, IE6
D3 Prof, D4 Standard, D2005 PE, TurboDelphi, Lazarus, D2010
BeitragVerfasst: Do 01.10.09 15:23 
Hallo,

mal überlegen ... String noch vorn schieben ... Länge setzen ... :arrow:
ausblenden Delphi-Quelltext
1:
2:
3:
iLen := SchreibPositionAdd - SchreibPositionInsert;
Move(s[SchreibPositionInsert],s[1],iLen);
SetLength(s,iLen);

_________________
MfG Lannes
(Nichts ist nicht Nichts) and ('' <> nil ) and (Pointer('') = nil ) and (@('') <> nil )