schnellere Alternative zu StringListe.IndexOf() gesucht

[Helmi]

Hallo,

ich füge in eine StringListe mehrere Einträge hinein.
Nun kann es sein, dass es mehrere gleiche Einträge in den Rohdaten gibt.
Um nur einmal den gleichen Eintrag der Liste hinzu zufügen, prüfe ich
zuvor ob dieser Eintrag in der StringListe schon vorhanden ist.
Dies mache ich via StringListe.IndexOf.

Beispiel:

Delphi-Quellcode:

        If Pos(S_const_Def_Allgemein, S) > 1 then
          If StringList_MN.IndexOf(S) = -1 then
            StringList_MN.Add(S);

Nun sind es leider nicht nur ein paar Einträge sondern gute 6000 - 7000
Einträge. Da hinter "IndexOf" eine Schleife steht wird das Ganze dadurch
sehr langsam.

Nun weiss ich, dass man das Ganze verschnellern könnte, wenn man zuvor
die Schleife sortiert. Aber das geht (meines Erachtens) aus zwei Gründen nicht:
1. Zuvor kann ich nichts sortieren,
2. sortiere ich danach, wenn alle Einträge hinzugefügt wurden, mittels einem
Natürlichen Sortieralgorithmus.

Nun meine Frage:
Gibt es eine schnellere Version von "IndexOf"?
Oder vielleicht hat jemand eine andere Idee für mein Problem

[Namenloser]

Es gibt zumindest eine schnellere Stringliste: THashedStringList

[alzaimar]

Jupp, oder mal mit

Delphi-Quellcode:

MyStringList.Sorted := True;

Die hashed stringlist ist aber schneller.

[himitsu]

in einer sortierten Liste wird schneller gesucht
und dann bietet die Stringlist von sich aus schon eine Duplettenbehandlung. (Duplicates)

Zitat:

Gibt es eine schnellere Version von "IndexOf"?

Ja "Find", aber dieses funktioniert nur mit einer sortierten Stringliste.

PS:

Delphi-Quellcode:

function TStringList.IndexOf(const S: string): Integer;
begin
  if not Sorted then Result := inherited IndexOf(S) else
    if not Find(S, Result) then Result := -1;
end;

[Helmi]

Zitat:

Zitat von himitsu

in einer sortierten Liste wird schneller gesucht
und dann bietet die Stringlist von sich aus schon eine Duplettenbehandlung. (Duplicates)

Zitat:

Gibt es eine schnellere Version von "IndexOf"?

Ja "Find", aber dieses funktioniert nur mit einer sortierten Stringliste.

PS:

Delphi-Quellcode:

function TStringList.IndexOf(const S: string): Integer;
begin
  if not Sorted then Result := inherited IndexOf(S) else
    if not Find(S, Result) then Result := -1;
end;

Hallo,

ich habe es mit Duplicates verwendet, aber trotzdem hab ich doppelte Einträge in der Liste.
Ich hab oben ja geschrieben dass ich es nicht zuvor sortieren kann.

[edit]
Duplicates geht bei mir auch nicht, da dies nur mit einer sortierten Liste funktioniert

[himitsu]

Find funktioniert nur mit einer sortierten Liste, leider gibt es keine Prüfung, ob es sortiert ist und somit liefert Find falsche Werte.
Und Dupplicates funktioniert auch nur mit einer sortierten Liste und ebenfalls kein Prüfung. :wall:

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;

Wenn du dennoch die Liste (Un)Sortierung behalten willst, dann führe einen Index mit und Zersortiere es danach wieder.
z.B. irgendwie so

Delphi-Quellcode:

StringList_MN.Sorted := True;
StringList_MN.Duplicates := dupIgnore;

// alles hinzufügen
StringList_MN.AddObject(S, TObject(StringList_MN.Count));
...

// und zum Schluß nach Index wieder zurücksortieren
StringList_MN.CustomSort(
  function(List: TStringList; Index1, Index2: Integer): Integer
  begin
    Result := Integer(List.Objects[Index1]) - Integer(List.Objects[Index2]);
  end);

[Helmi]

Zitat:

Zitat von himitsu

Delphi-Quellcode:

StringList_MN.Sorted := True;
StringList_MN.Duplicates := dupIgnore;

// alles hinzufügen
StringList_MN.AddObject(S, TObject(StringList_MN.Count));
...

// und zum Schluß nach Index wieder zurücksortieren
StringList_MN.CustomSort(
  function(List: TStringList; Index1, Index2: Integer): Integer
  begin
    Result := Integer(List.Objects[Index1]) - Integer(List.Objects[Index2]);
  end);

Hallo himitsu,

Dein Gebilde schaut recht interessant aus - aber momentan steig ich nicht durch, wie mir das hilft
Kannst mir das kurz erklären?

[himitsu]

Nja, ganz einfach.
Du führst die StringList_MN als sortierte Liste, damit kannst du Sorted, Duplicates verwenden, welche wiederum das schnellere Find nutzen und gleichzeitig automatisch die Duplikate ignorieren.

Delphi-Quellcode:

StringList_MN.Sorted := True;
StringList_MN.Duplicates := dupIgnore;

so fügst du dann die Strings der Liste hinzu und zu jedem String kommt noch ein Index (Reihenfolge des Einfügens)

Delphi-Quellcode:

StringList_MN.AddObject(S, TObject(StringList_MN.Count));

Am Ende wird die Reihenfolge über die Indize wiederhergestellt.

Delphi-Quellcode:

StringList_MN.CustomSort(
  function(List: TStringList; Index1, Index2: Integer): Integer
  begin
    Result := Integer(List.Objects[Index1]) - Integer(List.Objects[Index2]);
  end);

oder passend für dein D7

Delphi-Quellcode:

function MySort(List: TStringList; Index1, Index2: Integer): Integer
begin
  Result := Integer(List.Objects[Index1]) - Integer(List.Objects[Index2]);
 end);

StringList_MN.CustomSort(MySort);

Falls die Reihenfolge egal ist, dann einfach nur

Delphi-Quellcode:

StringList_MN.Sorted := True;
StringList_MN.Duplicates := dupIgnore:

...
StringList_MN.Add(S);

und CustomSort weglassen.

[Helmi]

Hallo Himitsu,

Danke für deinen Tip.

Ich machs jetzt so:

Delphi-Quellcode:

StringList_MN.Sorted := True; 
StringList_MN.Duplicates := dupIgnore: 

{...}

StringList_MN.Add(S);

{...}

StringList_MN.Sorted := false;

//StringListen sortieren (mit natürlichem Sortieralgorithmus)
StringList_MN.CustomSort(Compare_NaturalSort);

Also beim Hinzufügen ist die Liste Sortiert (jedenfalls glaubt sie es)
und vor der natürlichen Sortierung ist sie wieder false, damit man
sie noch sortieren kann.

[himitsu]

ach so ist das :lol:

nja, dann laß die Liste doch gleich richtig sortieren?

Delphi-Quellcode:

type
  TNaturalStringList = class(TStringList)
  protected
    function CompareStrings(const S1, S2: string): Integer; override;
  public
    constructor Create;
  end;

function TNaturalStringList.CompareStrings(const S1, S2: string): Integer;
begin
  Result := YourNaturalCompare(S1, S2);
  // also der Vergleich aus deinem Compare_NaturalSort
end;

constructor TNaturalStringList.Create;
begin
  Sorted := True;
  Duplicates := dupIgnore;
end;

Delphi-Quellcode:

var StringList_MN: TStringList; // oder TStrings oder was auch immer

StringList_MN := TNaturalStringList.Create;

{...}

StringList_MN.Add(S);

{...}