String in TStringList finden verschnellern?

[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 von a.def:

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 Liste.Sort; dann hast du alle Daten oder vorher 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 von a.def:

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

Das Duplicates wird auch nur beim Hinzufügen ausgewertet, nicht beim Sort . Das Property ist eben keine Garantie für den Inhalt der Stringlist. Es kann insbesondere jederzeit zwischen zwei 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...

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

Geschwindigkeit:
Das Dictionary ist ist schneller.

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. ( 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...

Jetzt könnt ihr es auseinandernehmen.

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 von haentschman:

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

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...

Zitat:

O(1) lookup performance

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

[mjustin]

Zitat von haentschman:

Hallo...

Zitat:

O(1) lookup performance

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

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

Again what learned. (Loddar)

[mjustin]

Zitat von haentschman:

Zitat:

O(1) bedeutet Zugriff in konstanter Zeit

Again what learned. (Loddar)

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