Hash mit Arrays zu langsam - wie sortieren und suchen? (Seite 2) (Allgemeines zu Perl)

[thread]13064[/thread]

Hash mit Arrays zu langsam - wie sortieren und suchen? (Seite 2)

Leser: 1

Crian

2009-01-29 09:55

User since
2003-08-04
5866 Artikel
ModeratorIn

Geht es darum, das einmal zu berechnen?

Ansonsten könntest du einmal alle paarweisen Abstände bestimmen und diese Informationen speichern. Sowas würde Sinn machen, wenn Benutzer (oder wer oder was auch immer) aus einem laufenden System Informationen abfragen wollen.

s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite

Taulmarill

2009-01-29 11:57

User since
2004-02-19
1750 Artikel
BenutzerIn

user image

Gast+2009-01-28 19:43:20--
@Taulmarill: Das geht eben nicht, was ich mit dem einen Beispiel zeigen wollte.

Geht alles :-)
Hier mal der Beispielcode, mit dem ich gestern herumgespielt habe.

Code (perl): (dl )

use strict;
use warnings;

use Time::HiRes qw/time/;

my ( @data1, @data2 );
push @data1, [rand(10), rand(10), rand(10), rand(10)] for 1 .. 100_000;
push @data2, [rand(10), rand(10), rand(10), rand(10)] for 1 ..     100;

for my $point2 ( @data2 ) {
    my %nearest = (
        distance => 1_000_000,
        point    => [0,0,0,0],
    );
    for my $point1 ( @data1 ) {
        next if abs( $point1->[0] - $point2->[0] ) > $nearest{distance};
        next if abs( $point1->[1] - $point2->[1] ) > $nearest{distance};
        next if abs( $point1->[2] - $point2->[2] ) > $nearest{distance};
        next if abs( $point1->[3] - $point2->[3] ) > $nearest{distance};
        my $distance = sqrt(
            ($point1->[0]-$point2->[0]) ** 2 +
            ($point1->[1]-$point2->[1]) ** 2 +
            ($point1->[2]-$point2->[2]) ** 2 +
            ($point1->[3]-$point2->[3]) ** 2
        );
        if ( $distance < $nearest{distance} ) {
            $nearest{distance} = $distance;
            $nearest{point   } = [ @$point1 ];
        }
    }
    #print $nearest{distance} . "\n";
}

Man beachte die Zeilen 16 bis 19. Diese verkürzen die Laufzeit des Programms auf weniger als ein drittel, da sie sehr schnell testen können, ob die bisher gefundene, kürzeste Entfernung kleiner ist, als die Entfernung zum momentan betrachteten Punkt in einer einzelnen Dimension.

$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78 0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0 F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B

Gast Gast

2009-01-29 12:06

Ich hab mich gestern damit beschäftigt, und denke das So ein R-Tree, oder besser noch PR-Tree. Ich denke aber dieser Algorithmus ist zu kompliziert, um ihn 1.) schnell zu verstehen und 2.) zu implementieren.

@Struppi + Alle
Danke! Das R-Tree Perl Modul ist geradezu verführerisch. Kannte ich ngar nicht! Schade nur, dass er auf 2D beschränkt ist. Die vergleichsroutinen sind hardgecoded. ICh müsste also den ganzen Code umschreiben. Es wäre schön, wenn man dort lediglich eine Sub übergibt die als Rückgabewert größer oder kleiner zurückgibt. ICh bin jetzt in Perl nicht sooo vertraut, aber in JAva würde man halt verschiedene INterfaces schreiben, so dass der Algrithmus muss allen möglichen Datenstrukturen aufgerufen werden kann.

Und ja, gern geschehen :)

@Lanx:
ICh muss dich leider enttäuschen, so ganz verstanden hab ich deinen Ansatz nicht. Aber ich möchte fast wetten, dass die Sortierung nach einzelnen Achsen noch irgendwelche Probleme beinhaltet. Aber vielleicht kannst du deinen Ansatz doch noch mal etwas mehr ausführen. Du musst natürlich kein Listing abliefern, aber vielleicht eine Art PSeudo-Code a là:
1.)Sortiere A nach [x1]
2.) ...
3.) Wenn x1 < dann gehezu 7.)
...
Natürlich nur, wenn es nicht zuviel aufwand macht.

Und ich sehe noch nicht ganz den ZUsammehang zuum Quadtree. Der Quadtree ist ein Sonderfall des R-Tree bei dem die Rechtecke klar definiert zu zerteilen sind. Beim R-Tree ist lediglich die Berechnung der optimalen Rechtecke komplizierter. Bei beiden wird aber eine Hierarchische Sortierung verwendet die ich bei deinem Ansatz nicht sehe!?

Gruß Jan

Taulmarill

2009-01-29 12:07

User since
2004-02-19
1750 Artikel
BenutzerIn

user image

Crian+2009-01-29 08:55:00--
Geht es darum, das einmal zu berechnen?

Ansonsten könntest du einmal alle paarweisen Abstände bestimmen und diese Informationen speichern. Sowas würde Sinn machen, wenn Benutzer (oder wer oder was auch immer) aus einem laufenden System Informationen abfragen wollen.

Ähm, währe fraglich ob das umsetzbar ist. Bei 200.000 Datensätzen auf beiden Seiten hat man bei Vollvermaschung 40.000.000.000 Verknüpfungen. Selbst wenn jede dieser Verknüpfungen nur jeweils einen Integer (der wohl 32bit sein muss, mit 16bit kann man nicht bis 200.000 zählen) für jede Seite enthält komme ich auf eine Gesamtgröße von fast 300GB. Das muss man erst mal dafür übrig haben.

stelzbock

2009-01-29 12:24

User since
2009-01-29
17 Artikel
BenutzerIn
[default_avatar]

So Leute,

ich hab mich mal angemeldet! Das Forum und die Antworten sind wirklich gut, qualitativ wie quantitativ und auch vor allem schnell :)

So, wieder zurück zum Thema:

@Crian:
Nein, ich muss das nur einmal machen und daraus ein XML erzeugen.

@ Taulmarill:
Hmm, selbst wenn das funktioniert (und damit meine ich auch, dass der Algorithmus in jedem Fall den optimalen Wert zurückliefert), dann wäre 1/3 in meinem Fall immernoch 3-4Tage! :( Ok, ich könnt mir mal nen schnelleren Rechner suchen... :)

stelzbock

2009-01-29 12:31

User since
2009-01-29
17 Artikel
BenutzerIn
[default_avatar]

Den Quad-Tree gibt es übrigens auch schon in Perl:
QuadTree

Ist allerdings auch für 2-Dimensionale Problem. Aber ich glaube, dass man diesen Algorithmus noch am einfachsten umsetzen kann.

Weitere IDeen sind erwünscht :)

Jan

LanX-

2009-01-29 12:51

User since
2008-07-15
1000 Artikel
BenutzerIn

user image

Gast+2009-01-29 11:06:36--
@Lanx:
Aber vielleicht kannst du deinen Ansatz doch noch mal etwas mehr ausführen.

Ich denke du solltest erstmal deine Aufgabenstellung mehr ausführen, die Gefahr ist sonst zu groß für die Tonne zu produzieren.

Wie groß ist die Punktmenge?
Was soll wann, wie oft berechnet werden?

Das muss man alles wissen, auch die Sortierung beeinhaltet Aufwand!

Mein Ansatz ist nur theoretisch interessant, für ne konkrete Umsetzung würd ich an deiner Stelle das Quadtree-Modul an 4D anpassen im wesentlichen heißt das überall wo Variablen x und y steht auch u und v hinzuschreiben.

me and my writeups

Crian

2009-01-29 13:00

User since
2003-08-04
5866 Artikel
ModeratorIn

Wenn die Vergleichsmenge so riesig ist, wird man sich auch mit der schwartzschen Transformation schwertun. So ein 300GB Hasch passt vermutlich in kaum einen Hauptspeicher.

s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite

stelzbock

2009-01-29 13:15

User since
2009-01-29
17 Artikel
BenutzerIn
[default_avatar]

@LanX + alle

Um dem ganzen etwas Leben einzuhauchen:
Es sind Kartendaten. Zwei Karten mit Straßen des selben Gebietes. Straßen sind in Edges unterteilt. Jedes Edge besteht aus Start X,Y und und End X,Y. Da eine Straße mehrere Spuren in verschiedene Richtungen hat, muss ich Start und Endpunkt als einheit betrachten, um so die Richtungsinformation zu erhalten - deswegen 4-dim Punkt.
Mein Ausgangsproblem war, dass ich gute Routendaten für eine Simulation hatte, aber schlechtes KArtenmaterial. Jetzt muss ich die alten Routen von der alten Karte auf die neue übertragen.

Also,
momentan habe ich ein 2 Hashes (A und B), bestehend jeweils aus einem eindeutigen Key (Edge ID zb. "ab3495") und einem Value-Array aus 4 Punkten welche Start und Endkoordinate des Edge darstellen. Diese Punkte sind Dezimalwerte, in Größenordnungen von 700.000, falls von Bedeutung. Jedes Hash hat etwa um die 100.000-150.000 Einträge.

Ich muss das ganze genau einmal machen, um dann eine Mappingtabelle zu erstellen, sprich ein neuer Hash C in dem alle Edges des alten Kartenmaterials (Hash A) einem Edge aus dem neuen Material (Hash B) zugerodnet werden. Diese Zuordnung soll eben durch einen Algorithmus hergestellt werden, der das nächste Punktepaar finden.

Zum Thema QuadTree:
Der vorliegende Algorithmus hat noch den NAchteil das der Hierarchielevel fest angegeben wird und so all Knoten immer Children habe auch wenn gar keine Punkte vorhanden sind. Warscheinlich wird das eine riesiege Datenmenge in meinem Fall. Zweitens lässt sich nur nachschauen, welche Punkte in einer Angegebenen Region befinden, aber nicht den nächsten Punkt zu einem vorgegebenen PUnkt.

IMO müsste man intelligenter vorgehen, und nur verzweigen, wenn auch ein Punkt in dieser region ist. UNd dann auch soweit verzeigen, dass am Ende nur noch ein oder wenige Punkte in einem Leaf stecken!

LanX-

2009-01-29 13:35

User since
2008-07-15
1000 Artikel
BenutzerIn

user image

So, gut das ich gefragt habe, was du machst ist ein 2D-Problem künstlich auf 4D aufzublasen.

Auch dein Abstandsbegriff ist ziemlich angreifbar, wieso sollte man den Abstand im 4D heranziehen? Wieso nicht das Mittel der Abstände der Start udn Endpunkte?

Du kannst als Datenstruktur also einfach eine der vielen 2D Lösungen im CPAN heranziehen, und die nächsten Nachbarn von Start- udn Endpunkt untersuchen.

EDIT:
tatsächlich müsste man sicherheitshalber tiefer gehen und auch kriterien für den Richtungsvektor betrachten, was hilft es wenn die "nächste" Straße orthogonal verläuft?

me and my writeups

View all threads created 2009-01-28 14:02.