Doppel schnell aus Liste löschen.

[Dejan Vu]

So, das hier ist 20x(*) schneller als deine Methode.

Delphi-Quellcode:

Procedure TFloatPoints.FastRemoveDoubles;
Var
  i,j : Integer;

Begin
  sort;
  j := 0;
  for i:=1 to Count-1 do
    if not SameFloatPoint(Fitems[i],FItems[j]) then begin
      inc(j);
      Fitems[j] := fItems[i];
    End;
  FCount := j;
End;

Die Variante mit der Hashmap hab ich mir geschenkt. Da dürften erst bei > 1 Mio spürbare Unterschiede auffallen: Quicksort ist ja schön schnell.

Davon abgesehen ist auch in 'AddPoints' noch mächtig Luft nach oben.

Delphi-Quellcode:

procedure TFloatPoints.FastAddPoints(Value: TFloatPoints);
var
  newCount, newCapacity : integer;

begin
  newCount := Self.Count + Value.Count;
  if newCount = Self.Count then exit;
  while fCapacity < newCount do fCapacity := fCapacity + DeltaCapacity;
  SetCapacity(fCapacity);
  Move(value.FItems[0],FItems[Count+1], value.Count*SizeOf(value[0]));
  self.FCount := newCount;
end;

Den Rest habe ich mir nicht mehr angeschaut, aber ich frage mich, wieso Du die Quellen von TList kopiert hast, wo Du doch dein TFloatPoint einfach in eine TList packen kannst. Dann kannst du dir das ganze Gedöns sparen. Na ja. Mach wie Du denkst.


(*) 20x bei 100.000 Elementen. Sind es mehr, ist der Unterschied noch drastischer. Sind es weniger, dann ist der Unterschied auch nicht mehr so hoch.

[Bjoerk]

Nicht schlecht. Aber, was soll das if newCount = Self.Count then exit in der FastAddPoints?

[Dejan Vu]

Zitat von Bjoerk:

Nicht schlecht. Aber, was soll das if newCount = Self.Count then exit in der FastAddPoints?

Na, wenn es nix zu tun gibt, dann tschüss.

[Bjoerk]

Das soll doch analog AddStrings sein. Die Zeile muß natürlich raus.

[Dejan Vu]

Ok. Die Sleep-Anweisungen von Himitsu rein und dafür die Abfrage, ob es etwas zu tun gibt, raus.

[Bjoerk]

Hab ich schon eingebaut. Sonst wäre mein Software ja so schnell wie "richtige" Software.

[Dejan Vu]

Du bist einfach der Software-Gott.

[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?

[Dejan Vu]

Zitat von Namenloser:

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

Stimmt nicht. A,B und C wird als A,B,C sortiert. Der X-Wert ist für A,B und C wird als "identisch" angesehen, also wird nach Y sortiert und dann stimmt es.

Das ganze Verfahren hat einen ganz anderen Haken: Nehmen wir an, wir haben 3 Punkte (P1 - P3), die alle um 1E-4 (=eps) von einander entfernt sind. Sagen wir, in X-Richtung. Y ist überall identisch. (also P[i+1].X = P[i].X + eps*0.99). Welche Punkte sollen übrigbleiben? Es kommt darauf an, welchen Punkt ich als 'Referenz nehme'.
A) P1 ist Referenz. Dann ist P2 nahe an P1, also weg. P3 ist zu weit von P1 weg, bleibt also => (P1,P2,P3) => (P1,P3)
B) P2 ist Referenz. Sowohl P1 als auch P3 sind nahe an P2, also weg => (P1,P2,P3)=> (P2)

Hashmap funktioniert dann auch nicht, weil zwei eng nebeneinanderliegende Punkte in unterschiedliche Raster fallen könnten. Der eine Punkt P1 liegt ganz rechts im Quadrant X, und der andere Punkt P2 ganz links im Quadranten X+1 (also dem rechts daneben) und obwohl P2.X-P1.X < Eps, sind die Quadranten unterschiedlich: Mein Nachbar ist in einem anderen Bezirk (Berlin) als ich, genauso blöd, d.h. wir haben unterschiedliche Postleitzahlen

Wenn man das 'richtig' machen will, muss man die von Namenlosen erwähnten Ansätze verwenden.

Als grobe 'Entdoppelung' sollte das Rasterverfahren (nichts anderes ist ja die Sortierung und die Eliminierung mit Epsilon) jedoch ausreichen.

Man kann auch das zweistufige Verfahren von Horst_ nehmen, wobei man nach der Sortierung nach X die von mir o.g. Problematik berücksichtigen könnte. Aber ob das jetzt was bringt, glaube ich nicht, weil man ja wieder rastert.

Das Quicksort nicht stabil ist, ist hier unerheblich: Wenn A und B 'identisch' sind, ist es egal, ob erst A vor B ist oder umgekehrt. Nicht die Sortierung ist das Problem, sondern die Ordnungsfunktion ('Compare'), die eine willkürliche Rasterung vornimmt sowie die willkürliche Wahl eines 'Referenzpunktes' für die Bestimmung von Clustern. Hier müsste man für jeden Cluster den Punkt 'in der Mitte' nehmen und von dem aus alle Nachbarn (dx<eps und dy<eps) eliminieren.