AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Doppel schnell aus Liste löschen.

Ein Thema von Bjoerk · begonnen am 7. Dez 2014 · letzter Beitrag vom 14. Dez 2014
Antwort Antwort
Seite 1 von 2  1 2      
Dejan Vu
(Gast)

n/a Beiträge
 
#1

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 18:54
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.

Geändert von Dejan Vu ( 8. Dez 2014 um 19:40 Uhr) Grund: Zusatz für 20x.... Denn bei 1 Mio Elementen dürfte das 100x schneller sein(?)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#2

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 19:30
Nicht schlecht. Aber, was soll das if newCount = Self.Count then exit in der FastAddPoints?
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#3

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 19:37
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.
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#4

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 20:09
Das soll doch analog AddStrings sein. Die Zeile muß natürlich raus.
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#5

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 20:45
Ok. Die Sleep-Anweisungen von Himitsu rein und dafür die Abfrage, ob es etwas zu tun gibt, raus.
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 21:06
Hab ich schon eingebaut. Sonst wäre mein Software ja so schnell wie "richtige" Software.
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#7

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 21:13
Du bist einfach der Software-Gott.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#8

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 21:22
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.

Geändert von Namenloser ( 8. Dez 2014 um 21:24 Uhr)
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#9

AW: Doppel schnell aus Lise löschen.

  Alt 8. Dez 2014, 22:10
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?

Geändert von Bjoerk ( 8. Dez 2014 um 22:13 Uhr) Grund: Edit:
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#10

AW: Doppel schnell aus Lise löschen.

  Alt 9. Dez 2014, 07:29
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.

Geändert von Dejan Vu ( 9. Dez 2014 um 07:39 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:47 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz