Doppel schnell aus Liste löschen.

[Dejan Vu]

1. Vorschlag: Sortiere die Liste und dann lösche beim einmaligen Durchlaufen alle Punkte raus, die "gleich! dem vorherigen Wert sind. Das 'löschen' geht so, das man das entstehenden Loch einfach mit dem nächsten Element auffüllt. etwa so:

Delphi-Quellcode:

procedure RemoveDuplicates (aList : TSomeList);
Var
  i,j : Integer;

Begin
  aList.Sort();
  j := 0;
  for i := 1 to aList.Length - 1 do 
    if aList[i].CompareTo(aList[j]) <> TCompareResult.Equal then begin 
      inc(j);
      aList[j] := aList[i];
    end;

  aList.Length := j;
end;

Sortieren ist vom Aufwand O(n log n), ergo ist das Verfahren vom gleichen Aufwand. Besser als O(n^2), wie beim zu optimierenden Verfahren.
Es geht aber noch schneller: Verwende dazu eine Dictionary und übertrage mit o.g. Pattern nur die Werte, die noch nicht in der Dictionary sind.

Delphi-Quellcode:

procedure RemoveDuplicates<TElement> (aList : TSomeList);
Var
  i,j : Integer;
   lookup : THashMap<TElement>;
Begin
  j := 0;
  lookup := THashmap<TElement>.Create;
  try
    for i := 1 to aList.Length - 1 do 
      if not lookup.Contains(aList[i]) then begin 
        lookup.Add(aList[i]);
        inc(j);
        aList[j] := aList[i];
      end;
  finally
    lookup.Free;
  end;
  aList.Length := j;
end;

K.a. ob es in Delphi eine THashmap gibt. Das ist eine Dictionary, aber nur für Schlüssel (ohne Nutzdaten)

Der Aufwand ist hier O(n), wenn das Nachschlagen ('Contains') und Anfügen ('Add') an eine THashmap vom Aufwand O(1) ist. Das sollte aber so sein, da hier idR Hashlisten zum Einsatz kommen. Wegen der Floatwerte muss der Comparator der THashmap vermutlich angepasst werden.