doppelte elemente löschen

[glkgereon]

moin

ich möchte aus einer ListBox doppelte elemente löschen...
ich hatte mir das so gedacht(vielleicht nicht das schönste...):

Delphi-Quellcode:

//anlegen
  temp:=TStringList.Create;
//für alle elemente
  while i<ListBox1.Items.Count-1 do
    begin
//wenn neu
    if temp.IndexOf(ListBox1.Items[i])=-1
//dann dazutun
    then temp.Add(ListBox1.Items[i])
//sonst eins runterzählen
    else dec(gesamt);
    inc(i);
    end;
//zurückübertragen
  ListBox1.Items:=temp;
//anzahl anzeigen
  Label1.Caption:=inttostr(gesamt);
  temp.Free;

aber wenn ich nu öfter draufklicke werden es immer weniger....
aber eigentlich müssten es doch gleichviel elemente bleiben nach dem ersten mal

[Shaman]

Hoi

while i<ListBox1.Items.Count-1 Lass das -1 weg.

Gruss
Shaman

[xineohp]

moin,

wenn du eine Stringlist verwendest kannst du es auch einfacher haben: scha dir mal die Eigenschaft Duplicates an. (Einziger Nachteil ist, dass die Liste sortiert sein muss bzw. sortiert wird)

Delphi-Quellcode:

var SL: tstringlist;
begin
  SL := tstringlist.Create;
  SL.Sorted := true;
  SL.Duplicates := dupIgnore;
  SL.AddStrings( Listbox1.Items );
  Listbox1.Clear;
  Listbox1.Items := SL;
  SL.Free;
end;

[glkgereon]

supi ...die liste SOLL sortiert sein...ich werdsa testen

[glkgereon]

ich grab jetzt einfach diesen thread nochma aus....

wie mache ich das ganze mit einer datei von ca. 1,5 Millionen einträgen in einer begrenzten zeit?
(am besten <10 sek)

diesmal isses egal, obs sortiert is

also ich hab folgende möglichkeiten im auge:

1) in neue stringlist, mit indexof prüfen und doppelte draußen lassen
2) Methode von oben
3) Methode die hier beschrieben ist:
http://delphipraxis.net/topic38901_d...+loeschen.html
oder noch eine andere?


wie würdet ihr es lösen?

[xineohp]

moin,

ich an deiner Stelle würde es so machen wie von mir weiter oben beschrieben, und zwar weil, es die Methode mit dem gringsten Aufwand ist Und außerdem macht die Stringlist eh nichts anderes als das, was in dem von dir genannten Thread beschrieben ist:

.AddStrings(Strings: TStings) besteht lediglich aus einer Schleife, die für jedes Element aus Strings die Funktion AddObject(const S: string; AObject: TObject) aufruft. (AddObject ist im Prinzip gleichbedeutend mit der Funktion Add(const S: string). Add(const S: string) ruft nämlich lediglich AddObject mit S und nil auf.)
Diese wiederum überprüft, sofern Sorted=true, mittels der Funktion Find(const S: string; var Index: Integer) ob der String bereits vorhanden ist. Duplicates legt hierbei fest ob, falls dem so ist, ein Fehler aufgerufen wird oder nicht.
Find ist wie folgt implementiert:

Delphi-Quellcode:

function TStringList.Find(const S: string; var Index: Integer): Boolean;
var
  L, H, I, C: Integer;
begin
  Result := False;
  L := 0;
  H := FCount - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := CompareStrings(FList^[I].FString, S);
    if C < 0 then L := I + 1 else
    begin
      H := I - 1;
      if C = 0 then
      begin
        Result := True;
        if Duplicates <> dupAccept then L := I;
      end;
    end;
  end;
  Index := L;
end;

Wenn du also das ganze schneller machen willst, musst du überprüfen, ob es günstiger ist eine n Elementige Liste zu sortiern und anschließend aufeinanderfolgende Elemente auf Gleichheit zu prüfen oder die Funktion Find n mal auf eine Liste anzuwenden deren Elemente von 0 bis maximal n ansteigen.

[xineohp]

Die besten Sortierverfahren benötigen im ungünstigsten Fall n*log(n) Schritte. Hinzu kommen n Vergleiche zur Überprüfung auf Duplikaten. Diese Verfahrenskette benötigt also rund n*log(n)+n Schritte.

Die Effizienz des Find-Algorithmuses liegt unter Voraussetzung einer sortierten Liste bei maximal log(n)/log(2) Schritten. Die Find Funktion wird n mal aufgerufen und zwar auf eine Liste deren Elementenzanzahl von 1 bis n ansteigt. Daraus ergeben sich log(n!)/log(2) Schritte für diese Verfahrenskette.

So und nun müsste man noch wissen was kleiner ist: n*log(n)+n oder log(n!)/log(2)

Durch empirische Erhebungen (=Ausprobieren ) habe ich herausgefunden, dass Methode2 rund doppelt soviele Schritte braucht wie Methode1 ... hätte ich ehrlich gesagt nicht erwartet, aber es ist ja auch nicht gesagt das mein Beweis fehlerfrei ist

[Hansa]

Zitat von glkgereon:

ich möchte aus einer ListBox doppelte elemente löschen...
ich hatte mir das so gedacht(vielleicht nicht das schönste...):

Jaja. 8) Die effektivste Methode ein Unheil zu verhindern ist es immer noch, mal zu sehen, daß es gar nicht so weit kommt. Siehe Verhütung.

Da es sich nur um eine Listbox handelt würde ich vorerst mal davon absehen, eine verkettete Liste zu verwenden oder irgendwelche Sortier-Algorithmen. Besser zuerst mal beim Eintragen nachsehen, ob der Eintrag schon da ist. Bei > 10.000 Einträgen wäre es wohl zu überlegen, aber wer scrollt solche Listboxen durch ?

Wie ich das sehe ist in diesem Fall selbst das lineare durchackern der Listbox angebracht.

[glkgereon]

also, bei meinen 1,5 millionen einträgen handelt es sich praktisch um ein wörterbuch, mit dem ich permutationen auf "gültigkeit" überprüfe....

diese datei soll NICHT angezeigt werden...

sortiert ist diese größtenteils, aber leider sind auch viele einträge doppelt....

ich werd mir xineohps beträge nochma genau angucken....

also du empfiehlst die implementierten service von TStringList zu nutzen?

[Hansa]

1,5 Mio. Elemente in einer Listbox ? Wo kommen die denn her ? Da würde ich ansetzen. UNd was sollen die in der Listbox ? Da kann man nur raten. Mit diesem Delphi/Pseudogemisch würde es theor. gehen :

Delphi-Quellcode:

var st : TStringList;
    ind : integer;
begin
  st := TStringList.Create;
  if Listenanfang / Dateianfang then
  repeat
    if not st.Find(Listenelement,ind) then
      st.Insert(1);
    nächstes Element;
  until kein Element mehr / Dateiende;
end;

Jetzt kommt es nur noch auf die Sortierung an, aber die ist ja auch nicht bekannt. 8)