array of string und die Performance-Schraube

**Meflin**

Moin moin!

Folgende Situation: ich habe mehrere Instanzen einer Klasse (sg. "Nodes"). Jede dieser Nodes hat ein array of string sowie einen Tickcounter, der einen Array-Index repräsentiert.

Nun müssen die jeweiligen Werte aus jedem Node ausgelesen und zu einem string zusammen gesetzt werden. Bis jetzt mache ich das schlicht und einfach so:

markieren

Delphi-Quellcode:

			Result := '';

for i := Low(FNodes) to High(FNodes) do begin

  Result := FNodes[i].ElementList[FNodes[i].IncCount] + Result;

end;

Doch nun habe ich das Projekt mal durch einen Profiler gejagt und da hat sich diese Operation ganz klar als Flaschenhals herausgestellt. Nun ist es auch so, dass das Millionenfach ausgeführt wird, also es sich durchaus um eine Stelle handelt, an der sich Optimieriungen lohnen würden.

Nur fehlt mir da gerade jegliche Idee, wie man das anders gestalten könnte. Vorschläge sind also sehr erbeten

**Christian Seehase**

Moin Leo,

also ein Ansatzpunkt wäre es, erst einmal die erforderliche Gesamtlänge zu errechnen (vielleicht kannst Du Dir die Änderungen ja irgendwo bei jedem hinzufügen eines Strings merken), dann Result auf die erforderliche Gesamtlänge initialisieren, und anschliessend per CopyMemory die Inhalte in Result übertragen.
Dann fällt schon mal das, Performance fressende, "Addieren" der Strings weg.

**thkerkmann**

Hi,

ich würde mal über die Datenstruktur nachdenken.

Für mich sieht das so aus, als ob aus jedem Node nur noch der letzte String interessiert.
Frage also:
werden die anderen nicht mehr gebraucht - warum werden sie dann gespeichert.

Falls doch, habe ich leider auch keinen anderen Ansatz, jedoch würde ich dem Node eine Methode spendieren, die mir diesen letzen string zurückliefert. Dann schaut die Schleife schon mal netter aus

Gruss

**Meflin**

Zitat von thkerkmann:

Für mich sieht das so aus, als ob aus jedem Node nur noch der letzte String interessiert.
Frage also:
werden die anderen nicht mehr gebraucht - warum werden sie dann gespeichert.

Doch, die werden gebraucht, da der Inccounter auch reseted werden kann (und auch wird), sodass es in dem Node wieder von vorne losgeht.

@Christian: Danke für den Tipp, das werde ich ausprobieren.

Im Moment verlangsamt o.g. Ansatz den Vorgang ca. um den Faktor 50

**alzaimar**

Zitat von Meflin:

Im Moment verlangsamt o.g. Ansatz den Vorgang ca. um den Faktor 50

Fallst Du mit 'o.g.Ansatz' das meinst, was Christian vorgeschlagen hat, dann hast Du was falsch gemacht.

Die werden vorne immer rangebepselt? Hmm.

zusammenfalten · markieren

Delphi-Quellcode:

			// 1. Maximal mögliche Länge ausrechnen

MaxLength := (High(FNodes) - Low(FNodes) + 1)*MaxLengthOfElementList;

SetLength (Result, MaxLength);

// 2. Das Zeugs am Ende von Result beginnend nach vorne auffüllen

j := MaxLength+1;

for i := Low(FNodes) to High(FNodes) do begin

  // Einzufügenden String holen

  sTmp := FNodes[i].ElementList[FNodes[i].IncCount]; 

  If Length (sTmp)>0 Then Begin // wenn der nicht leer ist

    // Einfügeposition nach vorne schieben

    dec (j,Length (sTmp));  

    // String vorne ranbepseln

    Move (s[1], Result[j], Length (sTmp));

  End

End;

// Wenn wir noch nicht vorne angekommen sind, verschieben wir unser Resultat an Position 1.

If j>1 Then Begin

  Dec (MaxLength, j-1); // Länge anpassen

  Move (Result[j], Result[1], MaxLength); // Verschieben

End;

SetLength (Result, MaxLength); // Fertig.

Ungetestet, vielleicht die üblichen +/-1 Fehler. Sollte aber weeesentlich schneller sein.

**SirThornberry**

ist ElementList ein Property hinter dem eine Funktion steckt oder ist es wirklich ein richtiges Array?
@alzaimar: Anstelle von verschieben würde ich die Schleife einfach andersrum laufen lassen und somit den String von vorne auffüllen.
Ich persönlich würde auch nicht mehr speicher anfordern als benötigt sondern einmal die Schleife durchlaufen lassen und mit length die jeweiligen Längen abfragen und addieren und dann nochmal die Schleife her nehmen und dann in den genau reservierten Speicher kopieren. (Ich glaube meine Variante wäre langsamer, wollte nur anmerken wie ich es machen würde um zu vermeiden das man an die Speichergrenzen kommt)

**alzaimar**

@Thornberry:

logisch, natürlich.

**Meflin**

@alzaimar: Nein, ich meinte meinen eigenen Code

Habe jetzt mal ein bisschen gemessen. Was verbrauchts ohne die string-Zusammensetzung, wie lange dauerts mit "string-Addition" und wie lange mit alzaimars Methode. Es fehlen noch sirThornberrys und Christians Vorschlag.

Die Ergebnisse gibts im Anhang, aber alzaimar, dein Vorschlag ist nochmal gut 1/4 langsamer als die string-Addition

**alzaimar**

So hätte es Sir Thornberry wohl gemacht.

zusammenfalten · markieren

Delphi-Quellcode:

			MaxLength := 0;

For i:= Low(FNodes) To High (FNodes) Do 

  Inc (MaxLength, Length (FNodes[i].ElementList[FNodes[i].IncCount]));

SetLength (Result, MaxLength);

j := 0;

For i := Hight(FNodes) Downto High(FNodes) do begin

  sTmp := FNodes[i].ElementList[FNodes[i].IncCount]);

  If Length (sTmp)>0 Then Begin 

    Move (s[1], Result[j], Length (sTmp));

    inc (j,Length (sTmp)); 

  End

End;

Das müsste aber eigentlich viel schneller sein, als Deine Methode...

Wie ist den der Getter von 'IncCount'?

**Meflin**

Zitat von alzaimar:

Wie ist den der Getter von 'IncCount'?

IncCount ist keine property, der Zugriff auf den Wert erfolgt also direkt.
ElementList ist zwar eine property, aber der Zugriff erfolgt direkt auf das array (inzwischen, anfangs war ElementList das "echte" array, jetzt wird mit FElementList gearbeitet)

Der letzte Algo ist katastrophal: nochmal fast dreimal langsamer als dein erster Vorschlag

Bis jetzt ist also immernoch string-Addition (deutlich) am schnellsten

array of string und die Performance-Schraube

array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Re: array of string und die Performance-Schraube

Forumregeln

alzaimar (Moderator) Registriert seit: 6. Mai 2005 Ort: Berlin 4.956 Beiträge Delphi 2007 Enterprise	#7 Re: array of string und die Performance-Schraube 18. Mär 2008, 17:35 @Thornberry: logisch, natürlich. "Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!" (Monty Python "Joke Warefare")
	Zitat