Doppel schnell aus Liste löschen.

[himitsu]

Das Verhalten von Capacity und blockweiser Vergrößerung ist doch bereits im TList eingebaut?
PS: TList.Insert

Zitat:

Zitat von Dejan Vu (Beitrag 1282672)

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

Da müssen dringend ein paar Sleep in den Code, denn es soll ja nur doppelt so schnell werden!

[Dejan Vu]

Zitat:

Zitat von Bjoerk (Beitrag 1282673)

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. :mrgreen:

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

Zitat von Dejan Vu (Beitrag 1282688)

Du bist einfach der Software-Gott.

Wo du grad zu Höchstform aufläufst. Ich poste mal noch ein anderes Problem.

[Bjoerk]

Zitat:

Zitat von Namenloser (Beitrag 1282690)

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.