Doppel schnell aus Liste löschen.

[Dejan Vu]

Ich weiß, ihr glaubt mir nicht, aber das hier funktioniert und ist zudem noch schneller:

Delphi-Quellcode:

Procedure TFloatPoints.DejainRemove;
var
  n,i : Integer;
  r : TFloatPoint;

Begin
  Sort();
  n := 0;
  r := FItems[n];
  for i:=1 to FCount-1 do
    if not SameFloatPoint(fitems[i],r) then begin
      inc(n);
      FItems[n]:=fItems[i];
      r := FItems[n];
      End;
  fCount := n+1;
End;

Das Ergebnis ist jedenfalls beim Testprojekt stets 'OK'. Aber ich scheine mir hier den Mund fusselig zu reden.
Auf jeden Fall ist das hier einfach Quark (tut mir leid)

Zitat von Kommentar in uFloatPoints.pas:

Delphi-Quellcode:

  // Koordinaten können mit einem instabilen Sortierverfahren nicht eindimensional sortiert werden;
  // Wir wollen aber mit dem QuickSort sortieren, weil eben schnell;
  // Deshalb sortieren wir zuerst nach X (SortByX) und anschließend alle Punkte
  // mit den gleichen X-Werten nach Y (SortByY);
  // Wir sortieren auch desshalb, weil wir Doppel schnell rauslöschen wollen;
  // Wir sortieren also zunächst (die ganze Liste) nach X;
  // Danach suchen wir alle Punkte mit den gleichen X-Werten und sortieren diese nach Y;

Viel Spass dann noch.

[Bjoerk]

Zitat von Dejan Vu:

Ich weiß, ihr glaubt mir nicht, aber das hier funktioniert und ist zudem noch schneller: Das Ergebnis ist jedenfalls beim Testprojekt stets 'OK'. Aber ich scheine mir hier den Mund fusselig zu reden.
Auf jeden Fall ist das hier einfach Quark (tut mir leid)

No problem, bin für klare Ansagen zu haben. Weißt du warum es auch Quark ist? Weil der Quicksort die ganze Zeit falsch war. Es geht sogar so. Der Thread Titel müßte eigentlich lauten, Auf welche Ideen man so kommt, wenn man von falschen Voraussetzungen ausgeht?

Delphi-Quellcode:

function SortCompareXY(const A, B: TFloatPoint): integer;
begin
  Result := SortCompareX(A, B);
  if Result = 0 then
    Result := SortCompareY(A, B);
end;

procedure TFloatPoints.RemoveDoubles2;
var
  I, J: integer;
  P: TFloatPoint;
begin
  QuickSort(0, FCount - 1, SortCompareXY);
  J := 0;
  P := FItems[J];
  for I := 1 to FCount - 1 do
    if not SameFloatPoint(FItems[I], P) then
    begin
      Inc(J);
      FItems[J] := FItems[I];
      P := FItems[J];
    end;
  FCount := J + 1;
end;

[Lyan]

habe jetzt nichts gelesen was hier so posted wurde, aber ich würde sowieso mit quicksort alles sortieren und dann einmel durchlaufen um alle doppelten einträge rauszuwerfen..

O(n*log(n)) + 1x durchlaufen .. dauert bestimmt nicht lange bei nur 100k

[Bjoerk]

Nicht schon wieder, dieser Thread verfolgt mich langsam.

Der Thread beruhte auf einem Fehler in meinem Quicksort. Man kann Koordinaten "ganz normal" sortieren. Das hätte man auch um 03:57 bemerken können (Der Beitrag direkt über deinem).