StringList oder dynamisches Array.

[MiKaEr]

hallo,

ich würde gerne wissen, welches dieser beiden dinge ressourcenschonender ist.

ich nutze grundsätzlich immer die TStringList. wäre ein dynamisches array nicht vielleicht besser?

[Klaus01]

Guten Abend,

kannst Du ja gerne selbst ausprobieren..

Zeit nehmen:
In einer Schleife 10000 Einträge in eine StringList einfügen,
zufällige Einträge wieder löschen.
Zeit erneut nehmen.

Das gleiche Spiel mit einem dynamischen Array.

Grüße
Klaus

[Sir Rufo]

Ein Blick in die Unit Classes gibt da schon eine ungefähre Auskunft:

Delphi-Quellcode:

unit System.Classes;

...

{ TStringList class }

  TStringList = class;

  PStringItem = ^TStringItem;
  TStringItem = record
    FString: string;
    FObject: TObject;
  end;

  PStringItemList = ^TStringItemList;
  TStringItemList = array of TStringItem;
  TStringListSortCompare = function(List: TStringList; Index1, Index2: Integer): Integer;

  TStringList = class(TStrings)
  private
    FList: TStringItemList;

Die Klasse TStringList kapselt also ein Array ;)

BTW quasi jede List-Klasse kapselt ein Array ;)

Die eigene Verwaltung in einem Array kann evtl. also tatsächlich schneller sein, dadurch wird die Handhabung aber umständlicher.

[Furtbichler]

Es kommt doch darauf an, welche Operation man wie oft benötigt.

Sehr oft lesen : Array besser
Hinten ran hängen: Array besser
Einfügen : StringList besser
Löschen : Stringlist besser
(Array = Array Of String)

Wer allerdings ein 'Array Of PString' verwendet, und alles hochoptimiert selbst umsetzt (quasi ein schnelleres TStringList) der könnte noch ein paar ms rausholen.

[Gausi]

Zitat:

Zitat von Furtbichler (Beitrag 1150013)

Hinten ran hängen: Array besser

Warum ist da ein Array besser? Wenn das Array voll ist, und der Speicher nach dem letzten Eintrag anderweitig belegt ist, muss das Array komplett umkopiert werden. Eine Stringlist ist da besser geeignet, da dort das zugrundeliegende Array bei einem "Überlauf" direkt um 25% vergrößert wird (Eigenschaft Capacity), damit nachfolgende Einfügeoperationen schneller ausgeführt werden können.

Zitat:

Zitat von Furtbichler (Beitrag 1150013)

Einfügen : StringList besser
Löschen : Stringlist besser

Da eine Stringlist ein Array kapselt, ist das egal. Umkopiert wird in jedem Fall.

[Furtbichler]

Zitat:

Zitat von Gausi (Beitrag 1150015)

Zitat:

Zitat von Furtbichler (Beitrag 1150013)

Hinten ran hängen: Array besser

Warum ist da ein Array besser?

Bei einem Array habe ich zwei Anweisungen (N++ und A[N] := S)
Bei einer Stringliste habe ich 4 (Alloc, Copy, N++ und A[N] := P). Eigentlich noch mehr, weil noch etwas mehr befüllt wird.

Von einem dynamischen und sich selbsttändig vergrößerden Array habe ich in Delphi noch nichts gehört.

Zitat:

Zitat:

Zitat von Furtbichler (Beitrag 1150013)

Einfügen : StringList besser
Löschen : Stringlist besser

Da eine Stringlist ein Array kapselt, ist das egal. Umkopiert wird in jedem Fall.

Nein. Bei einer Stringlist werden Pointer bewegt, bei einem Array ganze Strings... Oder? Öh... Na ja egal, jedenfalls öhm... Sie verwirren mich.

Ach nee, ein String ist ja ein Pointer... Aber auf jeden Fall gibts noch bookkeeping. Vielleicht, oder?

Was solls: Teste einfach mal. Ich hab hier auf dem Nettbook kein Delphi.

[Gausi]

Und das Array noch nicht ganz gefüllt ist, stimmt das, ja. Wenn aber Setlength aufgerufen werden muss, muss auch umkopiert werden. (Und weil man gelegentlich Fragen hört wie "Warum dauert for i := 0 to 100000 do setlength(myarray, length(myarray) + 1) so lange", weise ich da immer wieder gerne drauf hin. ;) )

Bei der Stringlist wird das Setlength "intelligenter" aufgerufen, da die Kapazität (length) nicht nur um 1 erhöht wird, sondern um 25%. Damit kommt man amortisiert auch auf eine konstante Laufzeit zum Einfügen eines Elements. Wenn man capacity vor dem Füllen passend setzt, dürfte das Verhalten im Wesentlichen mit dem eines normalen Arrays übereinstimmen.

Dass beim Array ganze Strings kopiert werden, glaube ich auch nicht. Wie das intern genau funktioniert, weiß ich zwar nicht, aber ein "Array", bei dem jeder Eintrag eine andere Länge haben kann, würde das Ansprechen eines beleibigen Elements per Index etwas aufwändiger machen. ;-)

[Luckie]

Zitat:

Zitat von MiKaEr (Beitrag 1149982)

ich würde gerne wissen, welches dieser beiden dinge ressourcenschonender ist.

Ich denke, dass man das heute vernachlässigen kann. Und bevor man an diesen Stellen seinen Quellcode optimiert, sollte man sein Augenmerk und seine Zeit auf andere Aspekte der Programmierung richten. Als da wären: Sicherheit, Stabilität, Nutzerfreundlichkeit. Und was den Quellcode angeht: Einfachheit, Wiederverwendbarkeit, Wartbarkeit, Leserlichkeit.

[Gausi]

Um das nochmal klarzustellen: Wenn man mit einem dynamischen Array of String vernünftig umgeht, und beim Befüllen des Arrays nicht ständig setLength aufruft, ist das voll und ganz in Ordnung.
Bei einer Stringlist passiert das von alleine. Allerdings gibt es da z.B. den Stolperstein mit "sorted". Wenn man das am Anfang auf True setzt, und dann die Liste Stück für Stück befüllt, ist das keine gute Idee.

Da im Prinzip beide Strukturen gleich sind (dynamische Arrays halt), sind sie von der grundlegenden Kopmplexität her gleichwertig. Man sollte nur bei einigen Dingen aufpassen bzw. etwas über die Funktionsweise wissen, um nicht auf die Nase zu fallen.

Ob die eine oder andere Struktur ein paar ms schneller ist oder ein paar Bytes spart ist in den allermeisten Fällen zu vernachlässigen. Da sind andere Dinge wichtiger, wie Luckie schon sagte. Ich arbeite in den meisten Fällen mit der Stringlist, da diese eine Reihe Methoden bietet, die ich für das Array of String selber implementieren müsste. :)

[Iwo Asnet]

Ich habe mal getestet: Ein Array ist (logischerweise) in jedem Fall schneller, und zwar um 5-40%.
(Append, ca 5%, Insert/Delete ca. 40%).

Ich habe dabei ein Array of String mit 10000 Elementen genommen. Für das Insert/Delete habe ich die Move-Operation mit einem Insert/Delete verglichen (immer das 0.te Element). Hier scheint sich der Overhead der Methode negativ auszuwirken.

Fazit: Der Preis, den man für eine sichere und dynamisch wachsende Liste bezahlt, ist hinreichend gering.

Wer oft löscht bzw. einfügt, sollte eh eine andere Struktur verwenden (verkettete Liste, Baum, Dictionary etc.)

[Luckie]

Da wäre jetzt dein Code interessant wie du befüllst und wie du die Zeit misst.

[Iwo Asnet]

Delphi-Quellcode:

program TestStringLists;

{$APPTYPE CONSOLE}

uses
  Windows, Classes, SysUtils;
Const
  R = 1000;

Var
  A : Array [0..10000] Of String;
  S : TStringList;
  
  Procedure ArrayProc;
  Var
    T : Cardinal;
    i : Integer;
    Procedure AppendProc;
    Var i : Integer;
    Begin
      for I := 0 to High(a) do A[i] := '123123123123';
    End;

    Procedure FetchProc;
    Var i : Integer; s: String;
    Begin
      for I := 0 to High(a) do s := A[i];
      if S='123' then A[0] := '';
    End;

    Procedure InsertProc;
    Var i : Integer;
    Begin
      for I := 0 to High(A) do
        Move(A[0], A[1], High(A)*SizeOf(A[0]));
    End;

    Procedure DeleteProc;
    Var i : Integer;
    Begin
      for I := 0 to High(A) do
        Move(A[1], A[0], High(A)*SizeOf(A[0]));
    End;
  Begin
    T := GetTickCount;
    For i:=1 to R do AppendProc;
    Writeln('Array - Add : ',GetTickcount-t);
    T := GetTickCount;
    For i:=1 to R do FetchProc;
    Writeln('Array - Fetch : ',GetTickcount-t);
    T := GetTickCount;
    For i:=1 to R div 100 do Begin InsertProc; DeleteProc; End;
    Writeln('Array - Ins/Del : ',GetTickcount-t);
  End;
  Procedure StringListProc;
  Var
    T : Cardinal;
    i : Integer;
    Procedure AppendProc;
    Var i : Integer;
    Begin
      for I := 0 to High(a) do S.Add('123123123123');
    End;

    Procedure FetchProc;
    Var i : Integer; x: String;
    Begin
      for I := 0 to High(a) do x := S[i];
      if x='123' then S[0] := '';
    End;

    Procedure InsertProc;
    Var i : Integer;
    Begin
      for i := 0 to High(A) do begin
        S.Insert(0,'1^23123123');
        s.Delete(0);
      end;
    End;

    Procedure DeleteProc;
    Var i : Integer;
    Begin
      for i := 0 to High(A) do
        S.Delete(0);
    End;
  Begin
    s:= TStringlist.Create;
    T := GetTickCount;
    For i:=1 to R do AppendProc;
    Writeln('StrLst - Add : ',GetTickcount-t);

    T := GetTickCount;
    For i:=1 to R do FetchProc;
    Writeln('StrLst - Fetch : ',GetTickcount-t);
    s.clear;
    AppendProc; // damit die Stringlist auch 10000 elemente zum Testen hat
    T := GetTickCount;
    For i:=1 to R div 100 do InsertProc;
    Writeln('StrLst - In/Del : ',GetTickcount-t);
   s.free;
 End;
begin
  ArrayProc;
  StringListProc;
  ReadLn;
end.

[Luckie]

Also GetTickCount ist dazu schon mal ungeeignet. Wenn dann sollte man mit GetThreadTimes, um genauere Werte zu erhalten.

[jaenicke]

Und davon ganz abgesehen ist das hier kein dynamisches Array. Ein festes Array zu nehmen um festzustellen wie sich ein dynamisches Array zu einer TStringList verhält, ist schon reichlich seltsam... :roll:
Denn die Operationen, die dabei eigentlich interessieren, kann man so ja gar nicht testen...

[Iwo Asnet]

@Luckie: Ob nun GetTickCount oder etwas anderes ist bei 500-700ms egal, oder etwa nicht?
@Jaenicke: Ob nun Array oder dynamisches Array ist eigentlich auch egal, auch wenn ich deine Ansicht im Prinzip teile. Ein dynamisches Array wird bei Zugriff über eine Dereferenzierung vermutlich etwas langsamer werden.

Aber wer mag, kann ja ein dynamisches Array einbauen und einen ultragenauen Zeitmesser obendrauf. Ob das Ergebnis -speziell durch eine Atomuhr- nun anders ausfällt, wage ich zwar zu bezweifeln, aber ich lasse mich gern eines besseren belehren. Hier wird der CPU-Cache eine viel größere Rolle spielen.

Interessant für mich ist der Overhead bei den Insert/Delete-Operationen, die man vielleicht optimieren kann. Wenn man will.

[mkinzler]

Zitat:

@Jaenicke: Ob nun Array oder dynamisches Array ist eigentlich auch egal, auch wenn ich deine Ansicht im Prinzip teile. Ein dynamisches Array wird bei Zugriff über eine Dereferenzierung vermutlich etwas langsamer werden.

Aber nur wenn man den dynamischen Array anfänglich auzch auf einen sehr großen Wert dimensioniert. Im Normalfall macht man das ja nicht ( sonst bräucht man keinen dynamischen Array, dessen Vorteil es ja ist, dass die Größe änderbar ist.)