Duplikate in Stringlist

[youuu]

Hi, ich benutze diesen Algorithmus um Duplikate in einer Stringlist zu löschen, allerdings braucht dieser extrem lange bei 100.000 Einträgen und mehr.

Kennt jemand einen schnelleren?

Delphi-Quellcode:

procedure KillDuplicates(s: TStrings);
var
  iLow, iHigh: integer;
begin
  for iLow := 0 to s.Count - 1 do
    for iHigh := Pred(s.Count) downto Succ(iLow) do
      if s[iLow] = s[iHigh] then
        s.Delete(iHigh);
end;

[Klaus01]

Guten Abend,

darst Du die Liste sortieren, oder sollen
alle Einträge in der Reihenfolge beibehalten werden?

Grüße
Klaus

[mkinzler]

Besser wäre es das Einfügen von doppelten Einträgen zu verhindern.

[youuu]

Darfst Sortiert werden

[Klaus01]

Zitat:

Zitat von mkinzler (Beitrag 1036494)

Besser wäre es das Einfügen von doppelten Einträgen zu verhindern.

.. darauf wollte ich hinaus.

Zitat:

Class
TStringList

Syntax

Delphi-Quellcode:

 property Duplicates: TDuplicates read FDuplicates write FDuplicates;

Description
Set Duplicates to specify what should happen when an attempt is made to add a duplicate string to a sorted list. The CaseSensitive property controls whether two strings are considered duplicates if they are identical except for differences in case.

The value of Duplicates should be one of the following.
Value Meaning
dupIgnore
Ignore attempts to add duplicate strings to the list.

dupError
raise an EStringListError exception when an attempt is made to add duplicate strings to the sorted list.

dupAccept
Permit duplicate strings in the sorted list.


Set Duplicates before adding any strings to the list. Setting Duplicates to dupIgnore or dupError does nothing about duplicate strings that are already in the list.
Note:
Duplicates does nothing if the list is not sorted.

Grüße
Klaus

[youuu]

Wenn ich das mache Mkinzler, dann muss ich doch bei jeden Eintrag neu abfragen, ob dieser in der Liste existiert oder nicht, dann geht die Bearbeitungszeit ebenfalls nach oben, bei 100.000 und mehr Einträgen.

Oder versteh ich das falsch?

[mkinzler]

Ja, den eine Tlist hat diese Funktionalität schon (siehe Beitrag von Klaus)

[youuu]

Ah so?

StringList.Duplicates := dupError;
Und dann mit Except anfangen?

[mkinzler]

dupIgnore wäre besser

[Matze]

Ich glaube, das geht nur in Verbindung mit "Sorted" oder?

Das funktioniert:

Delphi-Quellcode:

var
  sl: TStringList;
begin
  sl := TStringList.Create;
  try
    sl.Duplicates := dupIgnore;
    sl.Sorted := true;

    sl.Add('a');
    sl.Add('b');
    sl.Add('a');

    ShowMessage(sl.Text);
  finally
    FreeAndNil(sl);
  end;
end;

Ohne "Sorted := true;" geht es nicht.

Nachtrag: Ah, das steht in Klaus' Zitat am Ende, sehe ich gerade "Duplicates does nothing if the list is not sorted." :wall:

[youuu]

Super danke

[mkinzler]

Ja, das steht aber auch schon in Klaus' Beitrag
Alternativ könnte man mit .IndexOf() auf Vorhandensein prüfen; ist aber langsamer funktioniert aber auch unsortiert

[fatalerror]

Wenn in einer Liste aber bereits vorhandene Duplikate stehen (so wie im ursprünglichen Posting angegeben) würde ich die Liste kopieren, dies sollte bedeutend schneller gehen als das Prüfen mit deiner Routine:

Nur so hingetippt ohne zu überprüfen obs auch funktioniert

Delphi-Quellcode:

var
sl1, sl2:TSTringlist;
i:Integer;
t_start, t_stop:integer;

iLow, iHigh: integer;

begin
sl1:= Tstringlist.Create;
sl2:=TStringlist.Create;

try
  sl1.loadfromFile('c:\temp\testfîle.lst'); //laden einer Stringliste

  //Variante mit neuer Stringliste
  sl2.Duplicates:= dupignore;
  sl2.Sorted:=true;

  t_start := gettickcount;
  sl2.Assign(Sl1); //Einträge der zweiten Stringliste zuordnen
  t_stop := gettickcount;
  showmessage('Variante1; ' +inttostr(t_stop - t_start)+  ' ms');

  //Variante2 kopiert aus dem Originalposting

  t_start := gettickcount;
  for iLow := 0 to sl1.Count - 2 do
    for iHigh := Pred(sl1.Count) downto Succ(iLow) do
      if sl1[iLow] = sl1[iHigh] then
        sl1.Delete(iHigh);

  t_stop := gettickcount;
  showmessage('Variante2: ' +inttostr(t_stop - t_start)+  ' ms');

finally
 sl1.Free;
 sl2.Free;

end;

[alzaimar]

Eine Hashmap prüft das Vorhandensein eines Strings wesentlich effektiver, als das in der TStringList eingebaute 'Duplicates'. Beim Einfügen dürfte das die bei weitem schnellste Möglichkeit sein.

Du kannst Dir auch die THashedStringList aus der Unit 'IniFiles' nehmen, die hier vielleicht auch schnell genug sein könnte.

[youuu]

Habe noch eine Frage.

Ich hab nun 2 Stringlisten.

1. Duplikate die nicht in die neue Strinlit aufgenommen werden soll
und
2. die neue Stringlist.

Delphi-Quellcode:

        Try
          sOld.Duplicates := dupError;
          sOld.Sorted := true;

          sOld.Add(url); // Abgleich Stringlist
          s.Add(url); // Neu Link Stringlist
        except
          on EStringListError do      

        end;

Habe also "sOld" = Duplikate die nicht in die neue Stringlist "s" aufgenommen werden sollen.
Allerdings funktioniert das auch, jedoch statt 2 Sekunden, normaler ab Arbeitungszeit, der Procedure nun 9-15 Sekunden, nur durch diesen Codeteil.

[mkinzler]

Wie gesagt ist es besser dupIgnore zu setzen. Denn so wird ja bei jedem doppelten Vorkommen eine Exception ausgelöst!
dupError benötigst du nur, wenn du auf dies in irgendeiner Form reagieren willst.

Btw.: das mit dem Delphi-Tag statt Code-Tag gilt für alle Beiträge

[youuu]

Das Problem bei Dupignor ist allerdings nun das ich in der Stinglist "s" keine Einträge aus der Stringlist sOld haben möchte, sowie die duplikate aus der sOld.

Daher hab ich dies mit einer Exception versucht zulösen, da dann ja "s.add()" übersprungen wird sobald in sOld ein Duplikat eingetragen werden sollte.

[mkinzler]

Rate mal was dupIgnore macht? Oder schau in der Hilfe nach.

[youuu]

Ich weiß schon was dupignore macht, aber ich habe 2 Stringlisten.

Eine mit duplikaten und eine leere und in der leeren sollen auch keine duplicate aus der 1. eingeführt werden.

Das heißt ich muss ja testen ob ein duplikate in der 1. eingefügt werden sollte, wenn ja füge es nicht in die 2. Liste ein.

Nur weiß ich nicht wie ich das anders als über die exception in Erfahrung bringe.

[mkinzler]

Delphi-Quellcode:

          if sOld.IndexOf( url) = -1 then
              s.Add(url); // Neu Link Stringlist

[youuu]

Super funktioniert, kostet allerdings immernoch etwas Performance statt 9-15 Sekunden, sind es nun 3 Sekunden von damals 2 - 2,6 Sekunden.

Schneller wird es nicht möglich sein oder?

[mkinzler]

Möglicherweise mit einer THashedStringList

[youuu]

Ok gerade mit größeren Datensätzen probiert mit IndexOf und bei sovielen Datensätzen wie ich in der Liste haber, dauert das 20-40 Sekunden.

Das ist einfach nicht tragbar.

[Bernhard Geyer]

Zitat:

Zitat von youuu (Beitrag 1036580)

Schneller wird es nicht möglich sein oder?

Doch. HashTree/BTree sind bei großen Datenmengen um Welten schneller.

[youuu]

Soeben mit THashedStringList probiert und das gab wirklich einen extremen Performance boost.

[xZise]

Moin,

Zitat:

Zitat von youuu (Beitrag 1036602)

Soeben mit THashedStringList probiert und das gab wirklich einen extremen Performance boost.

Weil es ein anderes Verfahren ist. In einer Liste mit 100.000 Einträgen, weißt du ja nicht sofort ob ein Eintrag bereits vorhanden ist, sondern musst im schlimmsten Fall alle Einträge überprüfen.

Eine HashedStringList (wenn das sowas ähnliches ist wie eine Hashmap ist), hingegen definiert, wo ein Wert steht, anhand des Inhalts (z.B.). Also wenn du den Text Foo hast, dann weiß er wo das so ungefähr ist.

MfG
Fabian

[Sandi007]

Zitat:

Zitat von Matze (Beitrag 1036501)

...

Delphi-Quellcode:

var
    sl.Add('a');

Ohne "Sorted := true;" geht es nicht.
...

ja, und auch nur mit .Add, mit .Append geht es auch nicht.

[Dejan Vu]

Zitat:

Zitat von alzaimar (Beitrag 1036509)

Eine Hashmap prüft das Vorhandensein eines Strings wesentlich effektiver, als das in der TStringList eingebaute 'Duplicates'. Beim Einfügen dürfte das die bei weitem schnellste Möglichkeit sein.

Du kannst Dir auch die THashedStringList aus der Unit 'IniFiles' nehmen, die hier vielleicht auch schnell genug sein könnte.

Lustig. Auch 5 Jahre alte Tipps sind immer noch gültig.

EDIT: Unnötige Bemerkung entfernt.