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);

{...}

[Helmi]

Danke!

Werd ich morgen mal ausprobieren!

[Medium]

Habe ich was überlesen, oder wurde sortiert einfügen noch nicht vorgeschlagen? Ein schlanker Binary-Search vorm Einfügen erschlägt 2 Fliegen mit einer Klappe: Entweder wird der Eintrag gefunden (-> Duplikat), oder du bekommst gleich den Index zurück, an dem einzufügen ist um die Liste sortiert zu halten, was nachfolgende binäre Suchen möglich macht.

Edit: Und das ganze mit einer Worst-Case Komplexität von O(log(n)) pro Eintragungsversuch.

[alzaimar]

Zitat:

Zitat von Medium

Habe ich was überlesen, oder wurde sortiert einfügen noch nicht vorgeschlagen?

Delphi-Quellcode:

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

erfüllt den gleichen Zweck. Er will aber nach seinen eigenen Regeln sortieren.

[himitsu]

Wurde mehrfach vorgeschlagen, aber wollte er erst nicht nehmen, weil er seine Liste nicht extra zweimal umsortieren wollte, da sie schon "anders" sortiert ist (CustomSort).

[Medium]

Okay, dann ist mir entgangen, dass die ursprüngliche Sortierung beibehalten werden muss. Scusi :)

[Neumann]

Wie ist es, wenn man die immerhin 6000 Strings in einem Clientdataset speichert ? Dann könnte man dies indizieren und mit Locate suchen.

Könnte schneller sein, sicher bin ich mir aber nicht.

Gruß

Ralf

[rollstuhlfahrer]

bei 6000 Zeilen lohnt sich schon ne kleine Datenbank. Access z.B. wird sich darin viel viel schneller zurecht finden als du mit Delphi und Stringvergleichen.

Bernhard

[himitsu]

Und wie groß wäre der Aufwand den Stringlisteninhalt in die DB und nach den Einfügeaktionen wieder da rauszuholen, wenn es doch reichen würde der Stringliste einfach nur das gewünschte Sortierverfahren beizubringen, welches dann die schnelleren Suchfunktionen der Stringliste nutzbar macht?

[Medium]

6000 Strings sind doch ruckizucki da rein-SQL-t. Das muss ja wenn überhaupt nur ein Mal gemacht werden, und auch nur, wenn schon eine bestehende Liste übernommen werden muss. Die Einfügeoperation pro weiterem String dürfte durch die optimierten Suchstrategien in den meisten DBMS sehr schnell aufgewogen, und ab einem gewissen Punkt unterboten werden. Die Idee ist nicht wirklich schlecht, auch wenn es im ersten Moment wie Kanone->Spatz anmutet.

Edit: Vor allem besticht der geringe Implementierungsaufwand durch Benutzung bestehender Dinge sehr.

[Helmi]

Hallo,

danke für die Antworten!
Aber eine Datenbank find ich dafür ein wenig übertrieben.

Ich versuche jetzt gerade himitsu´s Vorschlag in die Tat umzusetzen, aber ich scheitere an der Vergleichs-function.

Zitat:

Zitat von 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);

{...}

Ich kann gerade nichts mit der function

Delphi-Quellcode:

function TNaturalStringList.CompareStrings(const S1, S2: string): Integer;

anfangen.

Momentan ruf ich so eine Sortierroutine so auf:

Delphi-Quellcode:

    StringList_MN.CustomSort(Compare_NaturalSort);

Wobei "Compare_NaturalSort" so

Delphi-Quellcode:

function Compare_NaturalSort(List: TStringList; Index1, Index2: Integer): Integer;
begin
  //Natürlich sortieren (Nummern aufsteigend)
  //benötigt "StrNatComp.pas"
  Result := StrNatCompare(List[Index1], List[Index2]);
end;

ausschaut. Und nun weiss ich leider nicht wie ich das in die obere function einfügen soll.
(Ich muss dazusagen, dass die Sortierroutine nicht von mir ist, sondern aus dem I-Netz)

[himitsu]

CompareStrings ist eine interne Funktion, welche die Stringliste für die Vergleiche verwendet.

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 := StrNatCompare(S1, S2);
end;

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

[Helmi]

Danke fürs Erklären!
Hat funktioniert!