String in TStringList finden verschnellern?

[Uwe Raabe]

Zitat:

Zitat von p80286 (Beitrag 1358450)

wenn du mit

Delphi-Quellcode:

.sorted:=True;

arbeitest, dann mußt Du noch eine Behandlung von doppelten Datensätzen mit einbauen z.B.

Delphi-Quellcode:

.Duplicates:=dupIgnore;

Das entspricht aber auch der Standardeinstellung. Lediglich für ein anderes Verhalten muss das explizit gesetzt werden.

[DeddyH]

Müssen? War es nicht eher andersherum, wenn Duplikate ausgeschlossen werden sollen, muss Sorted auf true gesetzt werden?

[Uwe Raabe]

Zitat:

Zitat von DeddyH (Beitrag 1358452)

Müssen? War es nicht eher andersherum, wenn Duplikate ausgeschlossen werden sollen, muss Sorted auf true gesetzt werden?

Das Duplicates-Property wird sowieso nur dann ausgewertet, wenn Sorted auf true steht. Erst dann kann man einstellen, ob Duplikate einfach ignoriert werden, aufgenommen werden oder eine Exception generieren.

Das Zulassen von Duplikaten bei einer sortierten Liste ist allerdings etwas zweischneidig: man weiß nie, welches er beim IndexOf/Find zurückliefert.

[p80286]

Zitat:

Zitat von Uwe Raabe (Beitrag 1358451)

Zitat:

Zitat von p80286 (Beitrag 1358450)

wenn du mit

Delphi-Quellcode:

.sorted:=True;

arbeitest, dann mußt Du noch eine Behandlung von doppelten Datensätzen mit einbauen z.B.

Delphi-Quellcode:

.Duplicates:=dupIgnore;

Das entspricht aber auch der Standardeinstellung. Lediglich für ein anderes Verhalten muss das explizit gesetzt werden.

Wobei "Standard" wohl von Version zu Version verschieden ist. Unter D7 war es wohl

Delphi-Quellcode:

dupError

Gruß
K-H

[a.def]

Zitat:

Zitat von p80286 (Beitrag 1358450)

@a.def
wenn du mit

Delphi-Quellcode:

.sorted:=True;

arbeitest, dann mußt Du noch eine Behandlung von doppelten Datensätzen mit einbauen z.B.

Delphi-Quellcode:

.Duplicates:=dupIgnore;

Gruß
K-H

Danke für den Hinweis. Das Schöne ist ja, dass es keine doppelten Einträge geben kann. Jedenfalls theoretisch. Ich habe noch nie zwei identische Dateinamen im selben Verzeichnis auf meiner Festplatte gesehen.

[Uwe Raabe]

Zitat:

Zitat von p80286 (Beitrag 1358461)

Wobei "Standard" wohl von Version zu Version verschieden ist. Unter D7 war es wohl

Delphi-Quellcode:

dupError

Kann ich zumindest bei meinem Delphi 7 nicht bestätigen. Dort ist ebenso

Delphi-Quellcode:

TDuplicates = (dupIgnore, dupAccept, dupError);

und da es im Create oder anderswo nicht gesetzt wird, entspricht der Standardwert auch dort

Delphi-Quellcode:

TDuplicates(0) = dupIgnore

.

[nahpets]

Unter Delphi 7 erfolgt das Einfügen von Daten mit dieser Routine:

Delphi-Quellcode:

function TStringList.Add(const S: string): Integer;
begin
  Result := AddObject(S, nil);
end;

function TStringList.AddObject(const S: string; AObject: TObject): Integer;
begin
  if not Sorted then
    Result := FCount
  else
    if Find(S, Result) then
      case Duplicates of
        dupIgnore: Exit;
        dupError: Error(@SDuplicateString, 0);
      end;
  InsertItem(Result, S, AObject);
end;

dupIgnore ist der "Normalfall", d. h.: Beim Auftreten von Dubletten werden diese nicht eingefügt. Die Stringliste hat also einen eindeutigen Inhalt.
Mit dupError kann man sich aber auch 'nen Fehler ausgeben lassen.

Egal welche Wahl man trifft: Sofern Sorted = True, gibt es keine Dubletten in der Stringliste.

[Uwe Raabe]

Zitat:

Zitat von nahpets (Beitrag 1358474)

Egal welche Wahl man trifft: Sofern Sorted = True, gibt es keine Dubletten in der Stringliste.

Das sehe ich anders! Bei

Delphi-Quellcode:

dupAccept

trifft keines der case-Labels zu und der Code springt direkt zum

Delphi-Quellcode:

InsertItem

. Hast du es mal probiert?

[nahpets]

Upps, Du hast recht.

Da hab' ich wohl mal wieder nur halb gelesen oder nur das gesehen, was ich sehen wollte oder so :-(

[a.def]

Delphi-Quellcode:

procedure TForm1.Button2Click(Sender: TObject);
var
 sl: TStringList;
begin
 sl := TStringList.Create;

 try
  sl.Sorted := False;

  sl.Add('123');
  sl.Add('456');
  sl.Add('123');

  ShowMessage('Sorted False:' + sLineBreak + sl.Text);

  sl.Sorted := True;
  ShowMessage('Sorted True:' + sLineBreak + sl.Text);
 finally
  sl.Free;
 end;

Keinerlei Fehler beim Setzen von Sorted True im Nachhinein, selbst wenn Einträge Doppelt vorhanden sind.

[Fritzew]

Zitat:

Keinerlei Fehler beim Setzen von Sorted True im Nachhinein, selbst wenn Einträge Doppelt vorhanden sind.

Das ist auch richtig so da ja nur sortiert wird beim setzen von sorted.
Irgendwann muss man sich halt entscheiden ob man duplicate will oder nicht.
Wenn ja kann man sorted später setzen, im anderen Fall entweder von Anfang an sorted oder selber prüfen. Dann sind wir wieder am Anfang :-)

[p80286]

Zitat:

Zitat von a.def (Beitrag 1358479)

Keinerlei Fehler beim Setzen von Sorted True im Nachhinein, selbst wenn Einträge Doppelt vorhanden sind.

Das setzen von Sorted im Nachhinein ist ja auch nicht der "Standardfall". Entweder, Du machst es hinterher

Delphi-Quellcode:

Liste.Sort;

dann hast du alle Daten oder vorher

Delphi-Quellcode:

Liste.Sorted:=true;

.
Und es gibt bestimmt viele Möglichkeiten beides zu kombinieren und möglichst viel Chaos anzurichten.

Gruß
K-H

[Uwe Raabe]

Zitat:

Zitat von a.def (Beitrag 1358479)

Keinerlei Fehler beim Setzen von Sorted True im Nachhinein, selbst wenn Einträge Doppelt vorhanden sind.

Das

Delphi-Quellcode:

Duplicates

wird auch nur beim Hinzufügen ausgewertet, nicht beim

Delphi-Quellcode:

Sort

. Das Property ist eben keine Garantie für den Inhalt der Stringlist. Es kann insbesondere jederzeit zwischen zwei

Delphi-Quellcode:

Add

-Aufrufen geändert werden.

[a.def]

Das Sorted setze ich nur im Nachhinein auf True, damit ich Find() benutzen kann.
Ob es doppelte Einträge gibt oder nicht ist unwichtig. Es dürfte aber normalerweise eh keine geben.

[haentschman]

Hallöle...:P

Weil keiner Erbarmen hatte des TDictionary mit der TStringList zu vergleichen mache ich das mal... Ich wollte es auch mal wissen. :wink:

Geschwindigkeit:
Das Dictionary ist ist schneller. :thumb:

Vorgaben:
Range: 10000000 Items
TStringList: unsortiert. (die Werte liegen sortiert vor)
Ergebnis:
Bei der TStringList liegen die Zeiten bei ca. 100 - 950 Milisekunden.
Beim TDictionary stabil bei 0 ms. (:gruebel: Ich wollte es gar nicht glauben.)

Natürlich muß man die Zeit berücksichtigen in der die Listen aufgebaut werden. Das stand aber nicht zur Debatte...:thumb:

Jetzt könnt ihr es auseinandernehmen. :thumb:

Delphi-Quellcode:

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages,
  System.SysUtils, System.Variants, System.Classes, System.UITypes, System.Generics.Collections, System.Generics.Defaults,
  Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  TBlubb = class
  strict private
    FItemValue: Integer;
  public
    constructor Create(ItemValue: Integer);
    property ItemValue: Integer read FItemValue write FItemValue;
  end;

  TfmTest = class(TForm)
    btnStringList: TButton;
    btnDictionary: TButton;
    edtCount: TEdit;
    btnGenerate: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure btnStringListClick(Sender: TObject);
    procedure btnGenerateClick(Sender: TObject);
    procedure btnDictionaryClick(Sender: TObject);
  private
    FDictionary: TObjectDictionary<string, TBlubb>;
    FStringList: TStringList;
    procedure Generate;
    function Count(StartValue: Cardinal): Cardinal;
  public
  end;

var
  fmTest: TfmTest;

implementation

{$R *.dfm}

procedure TfmTest.FormCreate(Sender: TObject);
begin
  FDictionary := TObjectDictionary<string, TBlubb>.Create([doOwnsValues]);
  FStringList := TStringList.Create;
  Randomize;
end;

procedure TfmTest.FormDestroy(Sender: TObject);
begin
  FDictionary.Free;
  FStringList.Free;
end;

procedure TfmTest.Generate;
var
  I: Integer;
  ItemsCount: Integer;
  Value: TBlubb;
begin
  FDictionary.Clear;
  FStringList.Clear;

  ItemsCount := Random(StrToInt(edtCount.Text));
  for I := 0 to ItemsCount - 1 do
  begin
    Value := TBlubb.Create(I);
    FDictionary.Add(IntToStr(I), Value);
    FStringList.AddObject(IntToStr(I), Value);
  end;
  MessageDlg(Format('%d values generiert.', [ItemsCount]), mtInformation, [mbOK], 0);
end;

function TfmTest.Count(StartValue: Cardinal): Cardinal;
begin
  Result := GetTickCount - StartValue;
end;

procedure TfmTest.btnGenerateClick(Sender: TObject);
begin
  Generate;
end;

procedure TfmTest.btnStringListClick(Sender: TObject);
var
  Start: Integer;
  SearchKey: Integer;
  SearchValue: TBlubb;
  ItemPosition: Integer;
begin
  Start := GetTickCount;
  SearchKey := Random(FStringList.Count - 1);
  ItemPosition := FStringList.IndexOf(IntToStr(SearchKey));
  SearchValue := TBlubb(FStringList.Objects[ItemPosition]);
  MessageDlg(Format('TStringList: Zeit in Milisekunden (Item # %s, Value: %d):  %d', [IntToStr(SearchKey), SearchValue.ItemValue, Count(Start)]), mtInformation, [mbOK], 0);
end;

procedure TfmTest.btnDictionaryClick(Sender: TObject);
var
  Start: Integer;
  SearchKey: Integer;
  SearchValue: TBlubb;
begin
  Start := GetTickCount;
  SearchKey := Random(FStringList.Count - 1);
  FDictionary.TryGetValue(IntToStr(SearchKey), SearchValue);
  MessageDlg(Format('TDictonary: Zeit in Milisekunden (Item # %s, Value: %d):  %d', [IntToStr(SearchKey), SearchValue.ItemValue, Count(Start)]), mtInformation, [mbOK], 0);
end;

{ TBlubb }

constructor TBlubb.Create(ItemValue: Integer);
begin
  inherited Create;
  FItemValue := ItemValue;
end;

end.

[mjustin]

Zitat:

Zitat von haentschman (Beitrag 1358494)

Weil keiner Erbarmen hatte des TDictionary mit der TStringList zu vergleichen mache ich das mal... Ich wollte es auch mal wissen. :wink:

Danke für den Blick über den Tellerrand. Dass ein TDictionary schneller ist ist leicht erklärt - sobald über den Hashwert die Position des Eintrags berechnet wird, ist es nur noch ein Speicherzugriff (wenn man keine Kollision hat). Wegen des Hash-Zugriffs hat TDictionary eine O(1) lookup performance, so sagt man :)

[haentschman]

Hallo... :P

Zitat:

O(1) lookup performance

...Bitte um Erklärung für Ü40. Den Begriff kannte ich noch nicht. :P

[mjustin]

Zitat:

Zitat von haentschman (Beitrag 1358502)

Hallo... :P

Zitat:

O(1) lookup performance

...Bitte um Erklärung für Ü40. Den Begriff kannte ich noch nicht. :P

O(1) bedeutet Zugriff in konstanter Zeit, unabhängig von der Anzahl (der Elemente die durchsucht werden).

Ich kann es zwar auch nicht in drei Worten erklären (ebenfalls Ü40), aber hier es gibt in der Wikipedia diesen Artikel :

https://de.wikipedia.org/wiki/Landau...e_und_Notation

Bei binärer Suche (TStringList zum Beispiel) hat man O (log n), die Zugriffszeit wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt.

[haentschman]

Zitat:

O(1) bedeutet Zugriff in konstanter Zeit

:P
Again what learned. (Loddar) :lol:

[mjustin]

Zitat:

Zitat von haentschman (Beitrag 1358507)

Zitat:

O(1) bedeutet Zugriff in konstanter Zeit

:P
Again what learned. (Loddar) :lol:

Was andererseits zu der Frage führt: was fangen wir nun mit den eingesparten 100-950 Millisekunden an? :-D

[haentschman]

Das müssen den TE fragen. Er kämpft mit den Milisekunden... :wink:

[a.def]

Zitat:

Zitat von mjustin (Beitrag 1358508)

Was andererseits zu der Frage führt: was fangen wir nun mit den eingesparten 100-950 Millisekunden an? :-D

Mit

Delphi-Quellcode:

Sleep(600);

sollte das Problem erledigt sein :stupid:

[p80286]

Zitat:

Zitat von haentschman (Beitrag 1358494)

Natürlich muß man die Zeit berücksichtigen in der die Listen aufgebaut werden. Das stand aber nicht zur Debatte...:thumb:

Was habe ich davon wenn der Zugriff in 0,001 MS erfolgt, aber vorher 2 h vorbereitet wird?

Gruß
K-H

[a.def]

Zitat:

Zitat von haentschman (Beitrag 1358511)

Das müssen den TE fragen. Er kämpft mit den Milisekunden... :wink:

Nee ;) Mir ging es um eine relativ große Dauer welche ich vernichten wollte.
Denn der Unterschied zwischen 1 Minute und 5 Sekunden ist schon gewaltig.

[himitsu]

Zitat:

Zitat von p80286 (Beitrag 1358526)

Was habe ich davon wenn der Zugriff in 0,001 MS erfolgt, aber vorher 2 h vorbereitet wird?

Es kommt auf den Verwendungsfall drauf an.

Wenn sich die Liste oft ändert, aber nur selten darauf zugegriffen wird, dann kann die Suche langsamer sein, aber das Hinzufügen/Löschen/Ändern sollte schnell sein,
aber wenn die Liste sich selten ändert und oft gesucht wird, dann natürlich andersrum.

Und dann kann man noch unterscheiden wie die Liste gefüllt wird.
Wird sie einmal schnell gefüllt und es gibt zwischendrin keine Zugriffe, dann kann man dabei die Sortierung/Indizierung aus lassen (falls möglich) und führt das erst nach dem Befüllen durch. (beim Dictionary nicht möglich, aber bei der TStringList, wenn man beim Befüllen selber auf Dupplikate achtet)

[mjustin]

Zitat:

Zitat von himitsu (Beitrag 1358528)

Wird sie einmal schnell gefüllt und es gibt zwischendrin keine Zugriffe, dann kann man dabei die Sortierung/Indizierung aus lassen (falls möglich) und führt das erst nach dem Befüllen durch. (beim Dictionary nicht möglich, aber bei der TStringList, wenn man beim Befüllen selber auf Dupplikate achtet)

Beim TDictionary ist es nicht möglich, aber auch nicht notwendig, da jedes neue Element ohne Sortierung einfach an der Stelle abgelegt wird, die sich aus dem Hashwert ergibt.

[himitsu]

Jain.
Bei der Vergrößerung der Liste müssen ab und an mal alle Einträge neu positioniert werden, wenn der interne Speicher die Größe ändert.

[freimatz]

Hat noch keiner einen AVL-Baum ausprobiert? :-D
Der ist beim Einfügen und beim Suchen recht schnell.

[EmWieMichael]

Zitat:

Zitat von freimatz (Beitrag 1358604)

Hat noch keiner einen AVL-Baum ausprobiert? :-D
Der ist beim Einfügen und beim Suchen recht schnell.

Ich habe zwar keinen AVL-Baum getestet, aber ich habe mal eine Zeigerliste gegen TStringlist mit 1.000.000 20stelligen Zufallsstrings antreten lassen (unsortiert) und dabei in den Listen den vorletzten String gesucht. Die zeigerverkettete Liste ist rund sechsmal schneller.

[Zacherl]

Zitat:

Zitat von EmWieMichael (Beitrag 1358612)

Zitat:

Zitat von freimatz (Beitrag 1358604)

Hat noch keiner einen AVL-Baum ausprobiert? :-D
Der ist beim Einfügen und beim Suchen recht schnell.

Ich habe zwar keinen AVL-Baum getestet, aber ich habe mal eine Zeigerliste gegen TStringlist mit 1.000.000 20stelligen Zufallsstrings antreten lassen (unsortiert) und dabei in den Listen den vorletzten String gesucht. Die zeigerverkettete Liste ist rund sechsmal schneller.

Das wundert mich ehrlich gesagt. Linked-Lists sollten bei sequenzieller Suche in etwa gleich schnell sein wie ein Array (bzw. eine intern als Array implementierte List).