Hi Leute!

Ich habe folgendes Problem:

Ich habe aus mehreren XML Files die Daten in zwei große Hash-Listen eingelesen (etwa 100.000-200.000 Werte). Die Schlüssel sind eindeutige IDs (Strings), die Werte bestehen aus jeweils einem Array, das wiederum 4 Zahlen enthält.
Etwa so:


Das Skript soll eine Mapping Tabelle erstellen. Dazu nehme ich momentan ein Eintrag aus dem einen Hash, gehe dann in einer Schleife durch alle Einträge aus dem zweiten hash und Suche nach dem besten Treffer. Der muss nicht gleich sein, sondern am nähsten dran. Das erreiche ich über den 4-dimensionalen euklidischen Abstand=sqrt((x1[0]-x2[0])^2 + (x1[1]-x2[1]) + ...)
x1 ist in diesem Fall das Array aus Hash 1 und x2 entsprechend das aus Hash 2. Ich muss aber inmmer die ganze Liste durch gehen, weil es ja immer noch einen besseren Treffer geben könnte. Das dauert ewig. Ich habe das mal Laufen lassen, und auf meinem Rechner würde das Mapping mit dem Algorithmus ca. 14TAGE(!!) dauern.

Ich muss mir also etwas besseres Ausdenken, und mir fällt nix ein. Es wäre schön, wenn man die eine LIste sortieren könnte und danach darin suchen könnte.
Aber mir fällt kein guter Sortieralgorithmus ein. Denn einfach nur nach dem ersten Array-Eintrag zu sortieren geht nicht, da es ja auf den eukl. Abstand Ankommt, und nicht auf die Gleichheit einzelner Werte. Hier ein Beispiel für das Problem:

Such Array: [5, 1, 1, 1]
Hash, in dem gesucht wird:
[1, 1, 1, 1] Abstand: 4
[2, 2, 2, 2] Abstand: 3,5
[3, 3, 3, 3] Abstand: 4
[4, 4, 4, 4] Abstand: 5,3
[5, 5, 5, 5] Abstand: 6,9
[6, 6, 6, 6] Abstand: 8,7

Daran sieht man, sortieren nach z.B. der ersten Zahl hätte als Ergebnis das Array [5,5,5,5] gebracht. Das Array mit dem geringsten Abstand ist allerdings [2,2,2,2].

Bitte um Hilfe!! Hat jemand eine Idee?

Gruß Jan

Das läßt sich vermutlich so allgemein nicht sagen. Kannst du ein kleines Beispiel zeigen?

Ganz einfach könnte man das ganze beschleunigen indem man Werte überspringt bei denen der lineare Abstand in einer Dimension schon größer ist als der bisher gefundene, kleinste euklidische Abstand.

... Ich weiß jetzt nicht genau, ob der obige Absatz mathematisch korrekt formuliert ist, aber ich meine auf jeden Fall schon mal das richtige :-)

Ich bin zwar vom Verständnis noch nicht ganz durch, aber vielleicht könnte dies PDF weiter helfen.

Ist zwar 'nur' im 2D-Raum, aber das kann man bestimmt auch erweitern.

Hast du in der Abstandsfunktion mal die Quadratwurzel weggelassen?
Das sollte in der Sortierung nichts ändern, da die Wurzel stetig steigend ist.

Ich wuerde da einen R-Tree als Index empfehlen.

@ Struppi:
Ähm, noch nicht Beispiel genug? :) Ich weiß nicht so recht, was du noch sehen möchtest?

@Taulmarill: Das geht eben nicht, was ich mit dem einen Beispiel zeigen wollte.

@Hagen: Wow, jep, das ist genau das Problem. Eigentlich sind meine 4 Werte auch genau 2 XY Punktepaare die ich der Einfachheit halber als 4-dim Wert behandelt habe. Ich muss mir das noch mal genau angucken, aber danke schon mal.

@ barney: Das stimmt schon. Aber die Wurzel ist IMHO nicht das Problem obwohl sie natürlich stnädig aufgerufen wird, sondern dass immer die Gesamte LIste durchgegangen wird. Das heißt also Die Abstandsberechnung wird 100.000*100.000=10.000.000.000 aufgerufen!!! Das Ziel ist es durch vorherige Sortierung und/oder einen Besseren Algorithmus das Problem zu vereinfachen.

@ murphy: Jep auch deine Lösung scheint mir dem Problem sehr nahe zu kommen. Am Besten wäre es in der Tat einen Index zu haben der sich schnell berechnen ließe, quasi ein Hash-Wert der einen 4-Dim Punkt abbildet und nicht nur exakt sondern auch Näherungswerte zulässt.

Vielen Dank euch allen! Ich wollte schon fast zu einem Mathematiker gehen, das es in der Tat einen mathematisches Problem ist. Um so dankbarer bin ich, dass ihr mir so schnell helfen konntet!

Ich werde eure Ideen umsetzen und dann berichten, was und wie ich es gemacht habe und falls es nicht geht noch mal um Rat fragen!

Gruß Jan

Sorry für meinen Kommentar. Mir war Euklid bis heute unbekannt und versuche Tree::R gerade zu analysieren. Wenn ich das richtig verstanden habe steckt dieser Euklid in der Funktion ChooseSubTree(). Aber die Funktionsweise von QuadraticSplit() heb' ich mir für morgen auf.

Danke für den anregenden Thread.

Ich weiß nicht was du unter einer "Mapping-Tabelle" verstehst...

wenn dein Problem lautet: Wie kann ich die 4D-Koordinaten so sortieren, dass ich zu einem beliebigen Punkt den euklidisch nächsten Punkt möglischt schnell finden kann, hätte ich nen naiven Vorschlag:

Lege zu jeder Dimension danach sortierte Arrays A1,A2,A3 und A4 an und untersuche nur die jeweils in der Dimension nächsten Punkte. Der jeweils geringste gefundeen Abstand gibt dir dann ein Abbruchkriterium, gewisserweise einen schrumpfenden Suchradius.

In deinem Beispiel würdest du zuerst [5,5,5,5] in A1 und [1,1,1,1] in A2,A3,A4 untersuchen.
der minimal gefundene Abstand wäre dann 4. D.h. man braucht nur noch Punkte mit x1 in 1 bis 9 und x2,x3,x4 in -3 bis 5 zu untersuchen.
Dann untersuchst du die nächsten Punkt in A1-A4, also [4,4,4,4] und [2,2,2,2], dabei letzteres mit minimalem Abstand, d.h Suchradius schrumpft auf 3.5,

Der Radius pro Achse ist sogar noch kleiner, weil du weist ja jetzt dass ein minimales Ergebnis in den Achsen 2, 3 und 4 mindestens einen Abstand von 1 hat, weil [2,2,2,2] einen kleineren Abstand als alle vorherigen Punkte in diesen Achsen hatte.

D.H der Suchradius in Achse 1 schrumpft auf sqrt(12-1²-1²-1²)=3

Gerade das letzte Argument mit dem Mindestabstand sollte helfen den Suchradius schnell schrumpfen zu lassen, sodass die Suche auch schnell beendet wird.

Das ist bestimmt nicht so effizient wie R-Trees wird aber leichter zu proggen sein und keine 14 Tage brauchen.

Also ich merk gerade das man das mathematisch sauberer hinschreiben könnte, aber ich hoffe die Idee wird klar ohen dass ich den kompletten Code hinschreiben muss.

Natürlich müsstest du die Arrays A1-A4 auch bzgl der anderen Achsen sortieren, lexikografisch gewissermaßen.

Struppi+2009-01-29 00:49:50--

Mir war Euklid bis heute unbekannt und versuche Tree::R gerade zu analysieren.

Euklidischer Abstand ist nichts anderes als der triviale Abstand im (euklidischen) Anschauungsraum (also so wie man's "kennt") und das mit nem verallgemeinerten Pythagoras ausgerechnet.
Im R² trivialerweise der normale Pythagoras also Abstand²=delta_x²+delta_y².

Mathematiker kennen halt diverse Räume und Abstandsbegriffe, deswegen ziehen sie den Schöpfer der antiken Geometrie zur Bezeichnung des "trivialen Falles" heran.

R-Trees teilen den Raum schrittweise in immer kleinere Teilräume auf, z.B. den R² in 4 Quadranten um den Mittelpukt im ersten Schritt dann diese wiederum in Quadranten usw. Im R³ wärens dann entsprechend 8 Quader usw. Die Idee ist dabei im Suchbaum nur noch wenige Quadranten weiter unterteilen zu müssen, weil der Suchradius schnell schrumpft und entfernte Quadranten fix ausschließt.

Ich denke R-Trees sind wahrscheinlich cleverer als einfach nur mittig zu teilen, aber ich hoffe die Idee wird klar.
EDIT: Schau an der von mir beschriebene Sonderfall ist als Quadtree bei WP bekannt!