Forum: Object-Pascal / Delphi-Language
by Namenloser,
9. Dez 2014
@Dejan Vu: Das war jetzt nicht auf das Beispiel bezogen sondern allgemein.
Solange es immer nur Paare von zusammengehörenden Punkten gibt, sollte es wohl kein Problem geben. Problematisch könnte es aber werden, wenn es mehr als zwei zusammengehörige Punkte gibt.
Könnte sein, dass du z.B. irgendwie in einer Reihe die Punkte a b c d hast, wobei jeder Punkt zu seinen Nachbarn, und nur zu...
Forum: Object-Pascal / Delphi-Language
by Namenloser,
9. Dez 2014
Das Problem ist: Quicksort setzt eigentlich eine Halbordnung voraus. Der Fuzzy-Vergleich ist aber keine, da die Transitivität (a ≤ b und b ≤ c ⇒ a ≤ c) nicht erfüllt ist. Und zwar ist sie das dann nicht, wenn a und b nahe genug bei einander liegen um als „gleich“ zu gelten, und b und c auch, aber a und c nicht.
Ich bin mir nicht sicher, inwieweit einem das auf die Füße fallen kann. Aber man...
Forum: Object-Pascal / Delphi-Language
by Namenloser,
9. Dez 2014
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.
Forum: Object-Pascal / Delphi-Language
by Namenloser,
8. Dez 2014
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...
Forum: Object-Pascal / Delphi-Language
by Namenloser,
8. Dez 2014
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:
|-----|-----|-----|---
|x | | |
| | | |...
Forum: Object-Pascal / Delphi-Language
by Namenloser,
8. Dez 2014
Ich muss eure Euphorie leider trüben. Die Methode von Dejan Vu liefert unter Umständen falsche Ergebnisse.
Stellt euch mal folgende Punktkonstellation vor:
A B
Forum: Object-Pascal / Delphi-Language
by Namenloser,
8. Dez 2014
Das ist deshalb so langsam, weil du für jeden Punkt im Schnitt die Hälfte oder so aller anderen Punkte durchläufst, um die Koordinaten zu vergleichen. Dadurch explodiert natürlich die Laufzeit bei größerem n. Du musst also das Nachschlagen von in der Nähe liegenden Punkten beschleunigen.
Wenn die Werte der Koordinaten alle in der gleichen Größenordnung sind, wäre eine Möglichkeit, sie durch...
