Maximale effiziente Hashgroesse in Perl

[LanX]

Hi

Ich hab mir gerade Q&D ein Perlskript geprogt das einen kürzeste Wege Algorithmus für eine Denksportquiz umsetzt und überschrittenen Knoten in einen Perl-Hash ablegt.

Ab 1.000.000 Einträgen (je ein 32 Bit Langwörter) fängt die Festplatte aber massivst zu rödeln an und die Performance hundertstelt sich.

Da ich jetzt zu faul bin eine eigene Hashstruktur umzusetzen und mir 4 MB Daten jetzt nicht allzuviel erscheinen, gibt es in Perl optionen die Hashfeatures zu tunen? Weiß jmd in welchem Bereich Perlhashes effizient arbeiten?

Die Struktur sollte 16*10^6 Einträge a 4 Byte schlucken können.

Alternativ habe ich jetzt die Idee die Daten in 256 kleinere Hashes mit 3 Byte Einträgen aufzuspalten. Kann ich davon ausgehen das der Interpreter so intelligent ist die Einzelhashes auszulagern und bei Bedarf von der Platte zu holen???

Tschau
Rolf

[Dominic]

Hallo Rolf,

so 100%ig weiß ich nicht, was du vorhast, aber wenn du es statt eines Hashes evtl. auch mit einem Array erledigen könntest, dann versuch, darauf umzusteigen. Ansonsten stell deine Frage einfach mal bei http://board.perl-community.de/ - dort sind viele Perl-Fachleute, die sich in der Materie auskennen.

Dominic

[LanX!]

Hi

so 100%ig weiß ich nicht, was du vorhast, aber wenn du es statt eines Hashes

wenns interessiert, das Spiel kann man als "Rasende Roboter" kaufen.
Man hat 4 Roboter (Gelb(Y),Rot,Grün,Blau) die sich nur senkrecht und wagerecht auf einem 16x16 Spielfeld bewegen dürfen, bis sie auf ein Hinderniss stoßen, d.h. ne Wand oder ein anderer Roboter. Ziel ist es in minimalen Zügen Y ins Ziel C9 (*) zu bringen.

A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P
   --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
.1|                   |                 R |                       |1
      .   .---.   .   .   .   .   .   .   .   .   .   .   .---.   .
.2|       |                                               |       |2
      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
.3|                                           |                   |3
      .   .   .   .   .   .   .   .   .   .   .---.   .   .   .   .
.4|                       |                                       |4
      .   .   .   .   .   .---.   .   .   .   .   .   .   .   .---.
.5|                                                               |5
   ---.   .   .   .---.   .   .   .   .   .   .   .   .   .   .   .
.6|                   |                                           |6
      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
.7|       |                                               |       |7
      .---.   .   .   .   .   .---.---.   .---.   .   .---.   .   .
.8|                           |       |       |                   |8
      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
.9|         *                 |       |                           |9
      .   .   .   .   .   .   .---.---.   .   .   .---.   .   .   .
10|               |                                 B |           |10
      .   .   .   .---.   .---.   .   .   .   .   .   .   .   .---.
11|                       |                                       |11
   ---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
12|                                                               |12
      .   .   .   .   .   .   .---.   .---.   .   .   .   .   .   .
13|                               |   |                           |13
      .---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .
14|     Y |                                               |       |14
      .   .   .   .   .   .   .   .   .   .   .   .   .   .---.   .
15|               |                               |               |15
      .   .   .---.   .   .   .   .   .   .   .---.   .   .   .   .
16|                   | G                                 |       |16
   --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
    A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P

Mit Hirnschmalz habe ich einige Lösungen in 18 Zügen gefunden, gibts bessere???

evtl. auch mit einem Array erledigen könntest, dann versuch, darauf umzusteigen.

Nein es muss ein Hash sein! Weil ein Array der bereits errecihten Stellungen mit bis zu (16*16)^4 Möglichkeiten mitdestens 4 GB bräuchte.

Ansonsten stell deine Frage einfach mal bei http://board.perl-community.de/ - dort sind viele Perl-Fachleute, die sich in der Materie auskennen.

Danke für den Tip.

Tschau
  Rolf

[at]

Hallo.

gibts bessere???

Spiele? Kaum.
MfG, at

[LanX!]

Hi

gibts bessere???

Spiele? Kaum.

das Optimum liegt übrigens bei 16 Zügen... :)

Tschö
Rolf

[Struppi]

Ab 1.000.000 Einträgen (je ein 32 Bit Langwörter) fängt die Festplatte aber massivst zu rödeln an und die Performance hundertstelt sich.

32 Bit Langwörter?
Meines wissens, kannst du in Perl keine Datentypen festlegen.

Die Struktur sollte 16*10^6 Einträge a 4 Byte schlucken können.

Du solltest in C oder C++ programmieren, mir ist nicht klar wie du in Perl mit Bytes arbeitest.

Alternativ habe ich jetzt die Idee die Daten in 256 kleinere Hashes mit 3 Byte Einträgen aufzuspalten. Kann ich davon ausgehen das der Interpreter so intelligent ist die Einzelhashes auszulagern und bei Bedarf von der Platte zu holen???

Das Swapping steht wohl eher in der Verantwortung des Betriebsystem und wird wohl kaum vom Interpreter beeinflußt werden.

Struppi.