Doppel schnell aus Liste löschen.

[Namenloser]

Ich muss eure Euphorie leider trüben. Die Methode von Dejan Vu liefert unter Umständen falsche Ergebnisse.

Stellt euch mal folgende Punktkonstellation vor:

Code:

            A B





            C

Die Koordinaten sind z.B. A(10.0, 2.0), B(10.001, 2.0), C(10.0, 5.0). A und B sollen im Rahmen des Epsilons als identisch gelten.

Wenn du das jetzt lexikographisch nach sortierst (nach der X-Koordinate zuerst), dann kommt die Reihenfolge A, C, B heraus. A und B werden also nie als Duplikate erkannt, weil sie nach der Sortierung nicht hintereinander stehen.

Das funktioniert leider so nur im Eindimensionalen.

Im Mehrdimensionalen braucht man andere Indexstrukturen, wie K-d-Bäume. Genau für solche Anwendungsfälle, wie die nächsten Nachbarn eines Punktes suchen, wurden die erfunden.

[Bjoerk]

Zitat von Namenloser:

Ich muss eure Euphorie leider trüben. Die Methode von Dejan Vu liefert unter Umständen falsche Ergebnisse.

Ok. Was denkst du denn über # 16?

Edit: Vergiss es. Genasu so falsch..

Hast du ein Beispiel für K-d-Bäume?

[Namenloser]

Ich habe leider kein Beispiel dafür. Es muss aber auch kein K-d-Baum sein, es gibt ja noch andere mehrdimensionale Indexstrukturen.

Die einfachste wäre hier denke ich die Hashmap-Lösung. Im Grunde ist die Idee, dass man ein grobes Raster über die Punkte legt, und pro Kästchen abspeichert, welche Punkte darin liegen:

Code:

|-----|-----|-----|---
|x    |     |     |
|     |     |     |
|-----|-----|-----|---
|     | xx  |     |
|     |     |     |
|-----|-----|-----|---
|     |     |    x|
|    x|x    |     |
|-----|-----|-----|---

(Sorry, die DP zerstört mal wieder das Layout, aber ich denke es ist klar, wie es gemeint ist.)

Dann muss man, um „identische“ Punkte zu finden, nur noch die Punkte aus dem gleichen Kästchen und aus den 8 Nachbarkästchen überprüfen.

Im Grunde braucht man nicht mal eine Hashmap, sondern ein einfaches 2D-Array tut es auch, ist nur u.U. weniger speichereffizient, wenn es größere, Bereiche gibt, die leer stehen.

Ein genereller Nachteil dieser Lösung ist, dass man die Kästchengröße irgendwie von Hand tunen muss.

[Bjoerk]

Ok. Thanx. Schau ich mir an.

Als letzter Versuch fäll tmir noch das ein? Der Quicksort ist ja unfassbar schnell. Ist das so korrekt?

Delphi-Quellcode:

function SortCompareX(const A, B: TFLoatPoint): integer;
const
  Eps = 1E-4;
begin
  Result := CompareValue(A.X, B.X, Eps);
end;

function SortCompareY(const A, B: TFLoatPoint): integer;
const
  Eps = 1E-4;
begin
  Result := CompareValue(A.Y, B.Y, Eps);
end;

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

procedure TFloatPoints.Sort;
begin
  if FCount > 1 then
  begin
    QuickSort(0, FCount - 1, SortCompareX);
    QuickSort(0, FCount - 1, SortCompareXY);
  end;
end;

[Namenloser]

Ich bezweifel es, aber einen Gegenbeweis kann ich jetzt nicht direkt liefern.

Ein paar Dinge, die man berücksichtigen sollte:
- Du hast bei Quicksort keinen Einfluss darauf, welche Paare miteinander verglichen werden und in welcher Reihenfolge
- Die „Gleichheit“ von Float-Werten ist keine Äquivalenzrelation, die Transitivität ist nicht erfüllt. Also macht es eben wohl einen Unterschied in welcher Reihenfolge die Elemente verglichen werden.
- Quicksort ist nicht stabil. Bei mir schrillen deshalb die Alarmglocken, wenn ich sehe, dass du zwei Sortiervorgänge direkt hintereinander ausführst. Was auch immer du dir davon erhoffst, wird nicht erfüllt sein.

Ich denke, man kann dieses Problem prinzipiell nicht mit eindimensionaler Sortierung lösen, egal was für eine ausgeklügelte Sortierung man sich einfallen lässt.

[Bjoerk]

Der QuickSort hat die unangenehme Angewohnheit, daß wenn es Beispielsweise in einer Adressenverwaltung 2 Hans Müller in 12345 Berlin gibt, und man die Adressen nach Postleitzahl sortiert, daß einmal der eine und einmal der andere Müller vorne stehen kann. M.E. hat das hier aber keinen Einfluß, weil identisch und hintereinander (Wenn 2 Durchläufe). Ich weiß es aber eben auch nicht genau ..

[Namenloser]

Das Ding ist, dass durch deinen zweiten Sortiervorgang der erste theoretisch komplett zunichte gemacht wird. Instabil heißt ja gerade, dass eine wie auch immer geartetet Vorsortierung nicht erhalten bleibt. Wenn der erste Sortiervorgang also irgendeinen Einfluss hat, dann ist das lediglich Zufall, und du kannst dich im Allgemeinen nicht darauf verlassen.

[EgonHugeist]

Zitat von Bjoerk:

Ok. Thanx. Schau ich mir an.

Als letzter Versuch fäll tmir noch das ein? Der Quicksort ist ja unfassbar schnell. Ist das so korrekt?

HybridSort oder RadixSort? Es geht so einiges, wenn man keinen zusätzlichen Code oder Speicher-Verbrauch in Betracht zieht.

[Bjoerk]

Ok. Sagt mir aber leider nix.

Hab doch noch Bock.

Ungetestet:

Delphi-Quellcode:

procedure TFloatPoints.RemoveDoubles;
const
  Eps = 1E-4;
var
  X: double;
  I, J: integer;
  NewList, SortList: TFloatPoints;
begin
  NewList := TFloatPoints.Create;
  try
    SortList := TFloatPoints.Create;
    try
      SortByX;
      I := 0;
      while I < FCount do
      begin
        SortList.Clear;
        X := FItems[I].X;
        while (I < FCount) and (SameValue(X, FItems[I].X, Eps)) do
        begin
          SortList.Add(FItems[I]);
          Inc(I);
        end;
        SortList.SortByY;
        for J := SortList.Count - 1 downto 1 do
          if SameFloatPoint(SortList[J], SortList[J - 1]) then
            SortList.Delete(J);
        NewList.AddPoints(SortList);
      end;
      Assign(NewList);
    finally
      SortList.Free;
    end;
  finally
    NewList.Free;
  end;
end;

[EgonHugeist]

Zitat von Bjoerk:

Ok. Sagt mir aber leider nix.

Macht nix, google es mal. Radix baut eine zweite Liste auf(Speicher x2) aber die Raten sind unglaublich! Es existieren so einige Radix Übersetzunengen.
Alexandr's HybridSort schlägt die "kleine/niedliche" QuickSort Variante um's 1,5fache. Radix dagegen ... kommt auf den Fall an.. x10 oder viiiel mehr!

@Nameloser: QSort ist in der Lage "unendlich" sogar mit Zufalls Ergebnissen zu arbeiten! e.g. FastCode-Project -> SortBV(Ein validation Test betrachtet diese Variante), Alle noch X-mal schnelleren Interpretationen/Replacements können jedoch nur mit "exakten" Ergebnissen umgehen.