Doppel schnell aus Liste löschen.

[Bjoerk]

Zitat von Horst_:

Hallo,

wie kannst Du Dir so sicher sein?

Also, ich weiß nicht was du machst? Anbei mein letztes Test Projekt.

Da man weiß, daß das

Delphi-Quellcode:

procedure TFloatPoints.DeleteDoubles;
var
  I, J: integer;
begin
  for I := FCount - 2 downto 0 do
    for J := FCount - 1 downto I + 1 do
      if SameFloatPoint(FItems[I], FItems[J]) then
        Delete(J);
end;

auf jedenfall funzt, kann man so auf Plausibilität prüfen.

Delphi-Quellcode:

procedure TFloatPointsTestForm.CompareButtonClick(Sender: TObject);
begin
  CompareButton.Enabled := false;
  Application.ProcessMessages;
  
  FList2.Sort;
  if FList1.Compare(FList2) then
    StatusLabel.Caption := 'OK'
  else
    StatusLabel.Caption := 'Failed';
end;

[EgonHugeist]

Zitat von #78 Bjoerk:

Also, ich verabschiede mich mal an der Stelle hier und danke allen für die freundliche Unterstützung. Mit ca.
100.000 Punkten und ca. 30.000 Doppel bin ich mit #61 bei 100 ms.
...
LG
Thomas

Zitat von #66 Bjoerk:

....
Bin eigentlich mit meinem Code #61 zufrieden. 100.000 Punkte 1..2 sec.

Edit: Man kann sich die zuzsätzlichen Listen auch sparen, wenn man direkt QuickSort(Von, Bis) durchführt. So fand ich's aber übersichtlicher.

LG
Thomas

Bin nur neugierig.. Welche Optimierung des gleichen Codes hat zu den drastisch unterschiedlichen Messungen geführt? Der Sort kanns nicht gewesen sein..

[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 EgonHugeist:

Bin nur neugierig.. Welche Optimierung des gleichen Codes hat zu den drastisch unterschiedlichen Messungen geführt? Der Sort kanns nicht gewesen sein..

Sytem.Move. In #61 wird Delete ja auf die sehr viel kleinere SortList angewendet (SortList.Count << Self.Count).

[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).