Stefan Richter: PHP - Mysql -> Zweidimensionales Array erzeugen

Hallo,

habe folgende Problematik und hoffe mal das ihr mir da ein wenig helfen könnt ;-)

Okay, ich habe eine MySQL Tabelle, welche Koordinaten einer Karte beinhaltet und folgendermaßen aufgebaut ist:

1. id       -> PRIMARY KEY
2. pos_x    -> pos_x + pos_y = UNIQUE KEY
3. pos_y
4. username -> INDEX
5. ...

(Die nachfolgenden Spalten sind für die Problematik unwichtig.)

So, anhand dieser Tabelle kann ich nun eine Karte erstellen, welche in Felder x/y unterteilt sind... in der Tabelle sind nur die belegten Felder hinterlegt...

Also bspw.

id pos_x pos_y username
-----------------------
01 1000  1000  1
02 1005  1008  1
03 1009  1025  2
04 ...

Da nicht alle Felder belegt sind, kann ich mit Hilfe des A-Stern Algorithmus den kürzesten Weg von A nach B berechnen lassen. Dieser Algorithmus gibt dann den Pfad in einem zweidimensionalen Array $pfad['pos_x']['pos_y'] zurück... verlangt aber zur Berechnung des Weges auch ein zweidimensionales Array...

Zur Zeit setze ich dieses Array folgendermaßen: (Ich möchte diese Vorgehensweise gern verbessern, da diese bei 10000 Feldern und mehr, allein schon für das Erstellen des Arrays eine hohe Zeit benötigt.)

-----------------------------------------------------------
$field = array();

$strSQL = "SELECT pos_x, pos_y FROM field;";

$db->query($strSQL);

while ($row = $db->getResult()) {

$field[$row['pos_x']][$row['pos_y']] = true;

}
-----------------------------------------------------------

Die Tabelle wird komplett ausgelesen und in einer Schleife zeilenweise komplett durchlaufen... die Werte pos_x und pos_y werden im Array $field als true (besetztes Feld) gesetzt.

Meine Frage ist nun, ob es dafür eine einfachere und schnellere Variante gibt, da diese bei 10000 Feldern und mehr, allein schon mehrere Sekunden benötigt...

Vielen Dank schonmal im Voraus.

Grüße

  1. echo $begrüßung;

    habe folgende Problematik und hoffe mal das ihr mir da ein wenig helfen könnt ;-)

    Viel Hoffnung mach ich dir nicht. Ich kann dir nur zum Verständnis ein wenig erklären.

    [... "zweidimensionales" Array ...]

    Im Grunde genommen gibt es keine mehrdimensionalen Arrays unter PHP. Ein Array in PHP ist eine Liste, die Elemente beliebigen Typs aufnehmen kann. Darunter zählt auch der Array-Typ. Du hast also am Ende ein Array mit Arrays drin.
    Da die Typen der Elemente beliebige sein können, ist es auch die Größe der Daten. Außerdem kann die Anordnung der Schlüssel beliebig sein. Das bedeutet nun, dass man die Speicherposition der Koordinate (x,y) nicht anhand von x·y·Elementgröße errechnen kann, sondern für den Zugriff immer einzeln das äußere Array und dann eins der inneren Arrays nach den jeweiligen x- und y-Schlüsseln durchsucht werden müssen. Eine andere, einfachere, letzlich schnellere Möglichkeit bietet PHP nicht von sich aus an. Die Universalität von PHP-Arrays ist an dieser Stelle dein Nachteil.

    echo "$verabschiedung $name";

    1. Moin!

      Da die Typen der Elemente beliebige sein können, ist es auch die Größe der Daten. Außerdem kann die Anordnung der Schlüssel beliebig sein. Das bedeutet nun, dass man die Speicherposition der Koordinate (x,y) nicht anhand von x·y·Elementgröße errechnen kann, sondern für den Zugriff immer einzeln das äußere Array und dann eins der inneren Arrays nach den jeweiligen x- und y-Schlüsseln durchsucht werden müssen. Eine andere, einfachere, letzlich schnellere Möglichkeit bietet PHP nicht von sich aus an. Die Universalität von PHP-Arrays ist an dieser Stelle dein Nachteil.

      Zur Speicherung einfacher Datentypen bei fester Arraydimension würde es sich ja anbieten, einfach einen schlichten String der Länge (breite * höhe * 1) herzustellen, der die ja/nein-Information des Spielfeldes speichert.

      Bzw., da die Stringinhalte ja Zeichen sind, ließen sich 256 unterschiedliche Informationen speichern.

      Der Direktzugriff auf eine Speicherstelle im String würde ja mit $stringvar[position] klappen (also genau wie beim eindimensionalen Array), man muß halt vorher position ausrechnen, indem man die Koordinaten X und Y in eine Formel packt.

      - Sven Rautenberg

      --
      "Love your nation - respect the others."
      1. echo $begrüßung;

        Bzw., da die Stringinhalte ja Zeichen sind, ließen sich 256 unterschiedliche Informationen speichern.

        Mehr. Die Länge eines Strings ist unter PHP nicht begrenzt.

        echo "$verabschiedung $name";

        1. Moin!

          Bzw., da die Stringinhalte ja Zeichen sind, ließen sich 256 unterschiedliche Informationen speichern.

          Mehr. Die Länge eines Strings ist unter PHP nicht begrenzt.

          Aber wenn ich pro Arrayposition nur ein Zeichen nehme, dann schon.

          Klar gingen auch mehr Zeichen pro Position, aber das machte die Sache dann schon wieder komplizierter.

          - Sven Rautenberg

          --
          "Love your nation - respect the others."
          1. Naja gut... aber macht es denn einen Unterschied, ob ich ein Array oder einen String nehme (rein von der Geschwindigkeit her?)

            Der String wäre ja dann, wenn man annimmt das die Ausdehnung der Karte 1000x1000 Felder groß ist, auch enorm groß: 1.000.000 Zeichen...
            Außerdem müsste ich dann bei jedem Schleifendurchlauf die Position ermitteln, was wieder mehr Rechenaufwand verursacht...

            Meine Frage war ja nur, ob es schon eine vorhandene Funktion in PHP gibt, welches das Result einer MySQL Abfrage gleich als zweidimensionales Array ausgibt: $array['pos_x']['pos_y'] ??

            Achja, den A* Algorithmus per MySQL, ich denke mal, dass das zuviel Rechenaufwand für die Datenbank beinhaltet... außerdem wie sollte man in einer Select Abfrage (ohne Procedures) eine komplette Funktion mit mehreren Schleifendurchläufen reinpacken?

            Grüße

            1. Moin!

              Der String wäre ja dann, wenn man annimmt das die Ausdehnung der Karte 1000x1000 Felder groß ist, auch enorm groß: 1.000.000 Zeichen...

              Nur eine Million Zeichen.

              Wenn du das vergleichst mit dem riesigen Overhead, den ein Array von Arrays in PHP benötigt. Da hast du mindestens auch ein Byte pro Feld für true/false. Außerdem für jedes Feld den Index (1, 2, 3). Sind, wenn man Strings verwendet, zwischen ein und vier Byte pro Feld, bei Integern immer vier Byte (32 Bit). Macht also schon mal 5 Millionen Bytes.

              Dann fehlen noch Speicherzeiger, denn die PHP-Arrays sind in Wirklichkeit eine Liste.

              Du siehst: Der String ist wirklich extrem speichersparend im Vergleich zu Arrays.

              Außerdem müsste ich dann bei jedem Schleifendurchlauf die Position ermitteln, was wieder mehr Rechenaufwand verursacht...

              Rechenaufwand gegen Speicheraufwand. Wenn der reale Speicher nicht mehr ausreicht, wird ausgelagert (oder das Skript wegen zu großer Speichernutzung abgebrochen).

              Hast du den Rechenaufwand schon mal nachgemessen? Wieviel Prozent langsamer ist das?

              Meine Frage war ja nur, ob es schon eine vorhandene Funktion in PHP gibt, welches das Result einer MySQL Abfrage gleich als zweidimensionales Array ausgibt: $array['pos_x']['pos_y'] ??

              Und die Antwort war, dass so riesige mehrdimensionale Arrays in PHP nicht wirklich ideal zu handhaben sind. Wenn du auf Performance Wert legst, mußt du optimieren. Und das geht eben nicht mit normalen Arrays, sondern mit spezialisierteren Speichermethoden.

              - Sven Rautenberg

              --
              "Love your nation - respect the others."
              1. Nur eine Million Zeichen.

                Könnten auch mehr sein... war halt nur als Beispiel, wenn die Karte 1000 x 1000 Felder groß ist...

                Du siehst: Der String ist wirklich extrem speichersparend im Vergleich zu Arrays.

                Ja, das kann ich mir vorstellen, dass Strings in der Hinsicht speichersparender sind...

                Rechenaufwand gegen Speicheraufwand. Wenn der reale Speicher nicht mehr ausreicht, wird ausgelagert (oder das Skript wegen zu großer Speichernutzung abgebrochen).

                Genau das Problem besteht, wenn die Feldanzahl zu groß ist...

                Hast du den Rechenaufwand schon mal nachgemessen? Wieviel Prozent langsamer ist das?

                Nein, bisher noch nicht, da ich auf die Idee mit dem String noch nicht gekommen bin... aber scheint eine gute Lösung zu sein, da ich ja maximal nur 1 Zeichen pro Feldkoordinate speichere...

                Ich habe eine $x und eine $y Variable, welche jeweils die aktuelle Position angeben... da müsste ich bei jedem Schleifendurchlauf die x/y Koordinate in die jeweilige Stelle umrechnen:

                Angenommen das Feld geht von x: 0-1000 und y: 0-1000, dann würde die Berechnung ja folgendermaßen lauten: $string[$x*1000 + $y]. Achso plus die Berechnung, wenn das erste Feld bspw. erst bei 500 beginnt... da müsste ich dann zusätzlich noch die kleinste Koordinate ermitteln und jedesmal Minus diesen Wert rechnen.

                Wie lange nun die Berechnung $x*1000 + $y bei vielleicht 10000 Schleifendurchläufen länger braucht als ohne, muss ich mal mit einem kleinen Testscript ausprobieren und die Zeit messen.

                Grüße

            2. Tach.

              Warum antwortest du nicht direkt auf meinen Beitrag? Wäre viel übersichtlicher ...

              Achja, den A* Algorithmus per MySQL, ich denke mal, dass das zuviel Rechenaufwand für die Datenbank beinhaltet...

              Wie gesagt, ich bin kein Fachmann auf diesem Gebiet, aber auf einen Versuch würde ich es schon ankommen lassen, anstatt es bei einem "ich denke mal" bewenden zu lassen. Möglicherweise äußert sich ja auch noch einer der DB-Auskenner hier im Forum zu den Erfolgsaussichten dieser Variante.

              außerdem wie sollte man in einer Select Abfrage (ohne Procedures) eine komplette Funktion mit mehreren Schleifendurchläufen reinpacken?

              Warum ohne Procedures? Ist das eine Vorgabe, die durch deine Version von MySql gemacht wird oder dein persönlicher Geschmack?

              --
              Once is a mistake, twice is jazz.
    2. Tach.

      Im Grunde genommen gibt es keine mehrdimensionalen Arrays unter PHP. Ein Array in PHP ist eine Liste, die Elemente beliebigen Typs aufnehmen kann. Darunter zählt auch der Array-Typ. Du hast also am Ende ein Array mit Arrays drin.

      Du hast in letzter Zeit häufiger auf diesen "Unterschied" hingewiesen, und ich fragte mich jedesmal, warum dir das so wichtig ist bzw. was daraus für Konsequenzen für den Programmierer folgen sollen. Nun schreibst du etwas mehr dazu ...

      Da die Typen der Elemente beliebige sein können, ist es auch die Größe der Daten.

      In PHP werden Variablen intern durch ein C-Struct repräsentiert, welches u. a. den Wert und den (aktuellen) Typ der Variablen speichert. Es gibt also keine Unterschiede in der Größe, nur weil die Typen unterschiedlich sind. Arrays werden in PHP über Hashmaps verwaltet, die eben solche Structs enthalten.

      Außerdem kann die Anordnung der Schlüssel beliebig sein. Das bedeutet nun, dass man die Speicherposition der Koordinate (x,y) nicht anhand von x·y·Elementgröße errechnen kann, sondern für den Zugriff immer einzeln das äußere Array und dann eins der inneren Arrays nach den jeweiligen x- und y-Schlüsseln durchsucht werden müssen.

      Das klingt gefährlicher als es wirklich ist, denn das Finden des Wertes an der "Koordinate (x,y)" bedeutet in diesem konkreten Beispiel bloß das Abfragen jeweils eines Werte aus zwei Hashmaps. Es müssen also nicht die einzelnen Arrays Schritt für Schritt durchsucht werden, wie du andeutest -- zumindest habe ich deinen letzten Satz oben so verstanden.

      --
      Once is a mistake, twice is jazz.
      1. echo $begrüßung;

        ["mehrdimensionale" Arrays unter PHP]
        Du hast in letzter Zeit häufiger auf diesen "Unterschied" hingewiesen, und ich fragte mich jedesmal, warum dir das so wichtig ist bzw. was daraus für Konsequenzen für den Programmierer folgen sollen.

        Meiner Meinung nach hilft es beim Verständnis von PHP-Arrays, ein solches mit all seinen Eigenschaften zu betrachten, als es auf einen Spezialfall zu reduzieren.
        In typstrengen Sprachen sind Arrays Auflistungen von Elementen gleichen Typs. Die Position eines Werts lässt sich anhand des Schlüssels multipliziert mit der Elementgröße ermitteln. Das bedeutet, dass der Schlüssel sich aus der Position des Elements ergibt, und damit lückenlos von 0 bis n geht. Das gilt auch für weitere Dimensionen. Jedes Element der ersten Dimension ist eine gleich lange Liste von Elementen der zweiten Dimension. Unterschiedlich lange Listen wären unterschiedliche Typen.

        Man kann nun ein PHP-Array genauso nachbilden, dass der Eindruck eines mehrdimensionalen Arrays entsteht, doch nichts hindert einen daran, gegen die Gleichmäßigkeit eines oben erwähnten mehrdimensionalen Arrays zu verstößen. Man kann Elemente mittendrin entfernen, kann statt eines einfachen Elements eine komplizierte Struktur speichern, kann eine Baumstruktur unterschiedlich tiefer Verästelungen erstellen usw. usw. Am Ende bleibt es aber immer eine Auflistung, die beliebige einfache Werte oder auch Auflistungen (die ihrerseits wieder ...) aufnehmen kann.

        Damit ergibt sich, dass die Position eines Elements mal hier, mal da, mal dort sein kann (der Abstand zwischen den Elementen $a[0][$x], $a[1][$x] und $a[2][$x] nicht immer gleich ist), und sich nicht so einfach berechnen lässt.

        Selbst wenn man selbst so diszipliniert ist und die Gleichmäßigkeit aufrecht erhält, kann PHP nicht davon ausgehen, dass das so bleibt und seinerseits intern eine Struktur verwenden, dessen Elementposition man mit einer Multiplikation ermitteln kann.

        Da die Typen der Elemente beliebige sein können, ist es auch die Größe der Daten.

        In PHP werden Variablen intern durch ein C-Struct repräsentiert, welches u. a. den Wert und den (aktuellen) Typ der Variablen speichert. Es gibt also keine Unterschiede in der Größe, nur weil die Typen unterschiedlich sind.

        Du willst mir jetzt nicht sagen, dass ein String der Länge 1 und ein String der Länge "no practical bound" den gleichen Speicherplatz verbraucht? Es mag ja sein, dass die Verwaltungsstruktur einer Variable stets gleich groß ist, aber dass das auch für ihren Inhalt gilt, wage ich zu bezweifeln.

        Arrays werden in PHP über Hashmaps verwaltet, die eben solche Structs enthalten.

        Gut, hier hab ich anscheinend noch ein Wissensdefizit. Wenn vom Schlüssel ein Hashwert gebildet wird, damit, wie ich annehme, die Elemente der Schlüssel-Liste eine gleiche Länge haben, wie kommt dann PHP an den ungehashten Wert des Schlüssels ($key) bei einem foreach ($array as $key => $value)? Meines Wissens nach ist Hashwert-Bilden eine unumkehrbare Operation.

        Außerdem kann die Anordnung der Schlüssel beliebig sein. Das bedeutet nun, dass man die Speicherposition der Koordinate (x,y) nicht anhand von x·y·Elementgröße errechnen kann, sondern für den Zugriff immer einzeln das äußere Array und dann eins der inneren Arrays nach den jeweiligen x- und y-Schlüsseln durchsucht werden müssen.

        Das klingt gefährlicher als es wirklich ist, denn das Finden des Wertes an der "Koordinate (x,y)" bedeutet in diesem konkreten Beispiel bloß das Abfragen jeweils eines Werte aus zwei Hashmaps. Es müssen also nicht die einzelnen Arrays Schritt für Schritt durchsucht werden, wie du andeutest -- zumindest habe ich deinen letzten Satz oben so verstanden.

        Die Schlüsselauflistung - ob nun mit gehashten Werten oder nicht - muss durchsucht werden. Die Schlüssel können, wie erwähnt, in beliebiger Reihenfolge abgelegt sein, so dass die Position eines Elements sich nicht mit einer vergleichsweise einfachen Multiplikation errechnen lässt. Hat PHP den Schlüssel in der ersten "Dimension" gefunden, hat es nun ein weiteres Array vor sich (die zweite "Dimension"), dessen Schlüssel-Liste es nun durchsuchen muss.

        echo "$verabschiedung $name";

        1. Tach.

          In PHP werden Variablen intern durch ein C-Struct repräsentiert, welches u. a. den Wert und den (aktuellen) Typ der Variablen speichert. Es gibt also keine Unterschiede in der Größe, nur weil die Typen unterschiedlich sind.

          Du willst mir jetzt nicht sagen, dass ein String der Länge 1 und ein String der Länge "no practical bound" den gleichen Speicherplatz verbraucht?

          Nein, will ich nicht. Ich bezog mich auf deine Aussage zu Arrays, und in denen ist intern nunmal z. B. nicht der String gespeichert, sondern das Struct. Daß in diesem Struct der entsprechende Zeiger natürlich auf eine Stelle im Speicher verweist, an dem die sich tatsächliche Zeichenkette befindet (und daß die natürlich sehr wohl unterschiedlich viel Platz verbraucht, je nach Inhalt), stellt ich ja gar nicht in Abrede.

          Es mag ja sein, dass die Verwaltungsstruktur einer Variable stets gleich groß ist, aber dass das auch für ihren Inhalt gilt, wage ich zu bezweifeln.

          Das war, wie oben erklärt, auch nicht meine Aussage.

          Arrays werden in PHP über Hashmaps verwaltet, die eben solche Structs enthalten.

          Gut, hier hab ich anscheinend noch ein Wissensdefizit. Wenn vom Schlüssel ein Hashwert gebildet wird, damit, wie ich annehme, die Elemente der Schlüssel-Liste eine gleiche Länge haben ...

          Der eigentliche Sinn einer solche Hashmap ist es, den Zugriff auf seine Elemente mit O(1) zu ermöglichen. Was genau du jetzt mit der Länge der Elemente meinst, weiß ich nicht.

          ... wie kommt dann PHP an den ungehashten Wert des Schlüssels ($key) bei einem foreach ($array as $key => $value)? Meines Wissens nach ist Hashwert-Bilden eine unumkehrbare Operation.

          Das kann ich dir aus dem Kopf leider auch nicht beantworten. Dazu müßte ich nachschauen, wie foreach intern umgesetzt wurde.

          Die Schlüsselauflistung - ob nun mit gehashten Werten oder nicht - muss durchsucht werden. Die Schlüssel können, wie erwähnt, in beliebiger Reihenfolge abgelegt sein, so dass die Position eines Elements sich nicht mit einer vergleichsweise einfachen Multiplikation errechnen lässt.

          Deshalb benutzt man ja eine Hashmap. Der Hash beschreibt dann eindeutig die Position des Elements -- eben *ohne* die gesamte Liste zu durchsuchen. Wie gesagt, O(1).

          Hat PHP den Schlüssel in der ersten "Dimension" gefunden, hat es nun ein weiteres Array vor sich (die zweite "Dimension"), dessen Schlüssel-Liste es nun durchsuchen muss.

          Daß tatsächlich zwei Strukturen (bei diesem konkreten zweidimensionalen Beispiel) hintereinander bearbeitet werden müssen, ist richtig. Sagte ich ja auch schon. Nur müssen diese Strukturen eben nicht aufwendig durchsucht werden.

          Interessantes Thema jedenfalls ... Allerdings muß ich jetzt zu einem langen, computerlosen Wochenende ins Ausland aufbrechen. Mal sehen, ob der Thread am Sonntagabend noch da ist. ;)

          --
          Once is a mistake, twice is jazz.
          1. echo $begrüßung;

            Wenn vom Schlüssel ein Hashwert gebildet wird, damit, wie ich annehme, die Elemente der Schlüssel-Liste eine gleiche Länge haben ...
            Der eigentliche Sinn einer solche Hashmap ist es, den Zugriff auf seine Elemente mit O(1) zu ermöglichen.

            Ich bin kein Informatiker und habe auch nicht Mathematik studiert. Erklärst du (oder jemand anderes) (mir) deshalb bitte kurz, was es mit O(1) auf sich hat. Es hat etwas mit Komplexität und Aufwand zu tun, soviel weiß ich immerhin. :-) Ein Verweis auf eine Quelle reicht auch, aber http://de.wikipedia.org/wiki/Landau-Symbole habe ich nicht verstanden, weil mir dazu die Grundlagen fehlen.

            Was genau du jetzt mit der Länge der Elemente meinst, weiß ich nicht.

            0  1  2  3  4  <- Keys
              |oo|oo|oo|oo|oo|...
               01 23 45 67 89 ...

            o ist jeweils eine Speicherzelle, Die | sind nur der Optik wegen eingefügt. Jedes Element belegt hier zwei Zellen. Die Position eines Elements lässt sich mit key·2 berechnen, weil die Elemente gleich groß sind, jeweils 2 o belegen. Man kann also genau voraussagen, wo die Elemente liegen und muss sich nicht an ihnen entlanghangeln.

            0   1     2  3
              |ooo|ooooo|oo|o...
               012 34567 89 0...

            E(lement) 0 hat eine Länge von 3, also ist E.1 an Position 3 zu finden. E.3s Position ergibt sich nur aus der Länge der Elemente 0, 1 und 2.

            ... wie kommt dann PHP an den ungehashten Wert des Schlüssels ($key) bei einem foreach ($array as $key => $value)? Meines Wissens nach ist Hashwert-Bilden eine unumkehrbare Operation.
            Das kann ich dir aus dem Kopf leider auch nicht beantworten. Dazu müßte ich nachschauen, wie foreach intern umgesetzt wurde.

            Lass ich mal als Erinnerung stehen.

            Die Schlüsselauflistung - ob nun mit gehashten Werten oder nicht - muss durchsucht werden. Die Schlüssel können, wie erwähnt, in beliebiger Reihenfolge abgelegt sein, so dass die Position eines Elements sich nicht mit einer vergleichsweise einfachen Multiplikation errechnen lässt.
            Deshalb benutzt man ja eine Hashmap. Der Hash beschreibt dann eindeutig die Position des Elements -- eben *ohne* die gesamte Liste zu durchsuchen. Wie gesagt, O(1).

            Dann brauch ich jetzt auch noch eine Erklärung (oder Link zu einer), wie man einen Hashwert findet, ohne die Sammlung der Hashwerte (vollständig, teilweise, wie auch immer) durchsuchen zu müssen.

            Nur müssen diese Strukturen eben nicht aufwendig durchsucht werden.

            Vielleicht ist es nicht aufwendig, die Hash-Liste zu durchsuchen, aber deutlich komplexer als eine Multiplikation stelle ich mir das schon vor.

            echo "$verabschiedung $name";

            1. Moin!

              Der eigentliche Sinn einer solche Hashmap ist es, den Zugriff auf seine Elemente mit O(1) zu ermöglichen.

              Ich bin kein Informatiker und habe auch nicht Mathematik studiert. Erklärst du (oder jemand anderes) (mir) deshalb bitte kurz, was es mit O(1) auf sich hat. Es hat etwas mit Komplexität und Aufwand zu tun, soviel weiß ich immerhin. :-) Ein Verweis auf eine Quelle reicht auch, aber http://de.wikipedia.org/wiki/Landau-Symbole habe ich nicht verstanden, weil mir dazu die Grundlagen fehlen.

              Du solltest eher hier gucken: http://de.wikipedia.org/wiki/Komplexitätstheorie#Anforderungen_an_Schrankenfunktionen - direkt mit Link zu den gebräuchlichsten Angaben.

              Soll heißen: O(1) erfordert konstanten Zeitaufwand, egal wieviele Elemente zu berücksichtigen sind.

              O(log n) erfordert logarithmisch von n abhängigen Zeitaufwand. Mehr Elemente bedeuten mehr Zeit, aber der Bedarf steigt nur logarithmisch an. Bei 10 Elementen benötige ich z.B. eine Zeiteinheit, bei 100 nur zwei, bei 1000 drei Einheiten.

              Entsprechend verhalten sich die anderen Angaben.

              - Sven Rautenberg

              --
              "Love your nation - respect the others."
            2. Tach.

              Dann brauch ich jetzt auch noch eine Erklärung (oder Link zu einer), wie man einen Hashwert findet, ohne die Sammlung der Hashwerte (vollständig, teilweise, wie auch immer) durchsuchen zu müssen.

              Man steckt den Schlüssel in die Hashfunktion, welche als Ergebnis einen Index in den Hashtable (selber ein Array) liefert. Dort ist die Speicheradresse zu finden, an der sich die gewünschten Daten befinden. Deshalb können diese Datensätze, im Gegensatz zum herkömmlichen Array, auch kreuz und quer im Speicher verteilt sein.

              Dadurch, daß man die Schlüssel auf einen festgelegten Bereich abbildet (die Indizes des Hashtables), kann man nun z. B. auch Zeichenketten als Schlüssel verwenden und assoziative Arrays implementieren, wie wir sie auch aus PHP kennen. Die eigentliche Arbeit steckt also im Entwurf einer vernünftigen Hashfunktion. [1]

              Eine ziemlich einfache (und nicht besonders gute) Hashfunktion für Strings wäre z. B. eine, die die Länge des Schlüssels bestimmt und mit einer Modulodivision auf die Größe des Hashtables reduziert. Der Schlüssel "dedlfix" verweist dann auf den letzten Eintrag eines 8-Elemente-Hashtables, wärend "Blaubart" zum ersten Eintrag führt.

              Nur müssen diese Strukturen eben nicht aufwendig durchsucht werden.

              Vielleicht ist es nicht aufwendig, die Hash-Liste zu durchsuchen, aber deutlich komplexer als eine Multiplikation stelle ich mir das schon vor.

              Das ist richtig; hängt eben von der Komplexität der Hashfunktion ab. Daß das trotzdem viel "billiger" zu haben ist als eine Suche, bei der erstmal die Arrayelemente aus dem Speicher gelesen werden müssen (im ungünstigsten Fall sogar alle), sollte klar sein.

              [1] Mindestens genauso wichtig sind wahrscheinlich die Mechanismen zur Behandlung von Kollisionen. Aber das bringt dieses Thema so langsam an einen Punkt, wo ich die Lektüre eines Fachbuchs vorschlagen würde, anstatt hier im Forum weiter darüber zu referieren. ;)

              --
              Once is a mistake, twice is jazz.
              1. echo $begrüßung;

                Nicht dass wir beide aneinander vorbeireden: array('schlüssel' => 'element', ...). Die Elemente interessieren nicht weiter, die ergeben sich, wenn man in der Liste der Schlüssel den richtigen gefunden hat.

                Dann brauch ich jetzt auch noch eine Erklärung (oder Link zu einer), wie man einen Hashwert findet, ohne die Sammlung der Hashwerte (vollständig, teilweise, wie auch immer) durchsuchen zu müssen.
                Man steckt den Schlüssel in die Hashfunktion, welche als Ergebnis einen Index in den Hashtable (selber ein Array) liefert. Dort ist die Speicheradresse zu finden, an der sich die gewünschten Daten befinden. Deshalb können diese Datensätze, im Gegensatz zum herkömmlichen Array, auch kreuz und quer im Speicher verteilt sein.

                Um die Daten geht es (mir) nicht, sondern darum, den Schlüssel zu finden, bzw. wie PHP anhand eines Strings, der einen Schlüssel darstellt, in der Auslistung der Schlüssel eines Arrays diesen Schlüssel findet.
                Ich nehme also mit, dass man den String in die Hash-Funktion steckt, und heraus kommt eine Positionsangabe in der Schlüsselauflistung.

                Nur müssen diese Strukturen eben nicht aufwendig durchsucht werden.
                Vielleicht ist es nicht aufwendig, die Hash-Liste zu durchsuchen, aber deutlich komplexer als eine Multiplikation stelle ich mir das schon vor.
                Das ist richtig; hängt eben von der Komplexität der Hashfunktion ab. Daß das trotzdem viel "billiger" zu haben ist als eine Suche, bei der erstmal die Arrayelemente aus dem Speicher gelesen werden müssen (im ungünstigsten Fall sogar alle), sollte klar sein.

                Halten wir also fest, und kommen damit wieder auf das Laufzeit-Problem des OPs zurück: Ob die Hash-Funktion nun komplex oder weniger komplex ist, (deutlich) aufwendiger als eine Positionsbestimmung per Multiplikation ist sie. Da das aber PHP-Interna sind, die man als Anwender sowieso nicht beeinflussen kann, hat man schlechte Karten.
                Alternativ zu einem PHP-Array könnte man nun einen String verwenden und dessen Zeichen als fortlaufend angeordnete Array-Elemente betrachten/missbrauchen/wieauchimmer. Ein Zugriff auf ein Zeichen anhand einer Position sollte von PHP mit einfachen Rechenoperationen bewerkstelligt werden können. Das setzt natürlich voraus, dass man nicht mehr als 256 verschiedene Werte pro Feld speichern muss. Doch ob das wirklich eine brauchbare Lösung ist, müsste im Versuch ermittelt werden, da dieser String auch erst einmal aus dem Datenbankinhalt generiert werden muss.

                [1] Mindestens genauso wichtig sind wahrscheinlich die Mechanismen zur Behandlung von Kollisionen. Aber das bringt dieses Thema so langsam an einen Punkt, wo ich die Lektüre eines Fachbuchs vorschlagen würde, anstatt hier im Forum weiter darüber zu referieren. ;)

                Bei einem PHP-Array kann es keine zwei Schlüssel mit dem gleichen Wert geben. Wenn die Hash-Funktion für unterschiedliche Schlüssel den gleichen Hashwert errechnet, war sie nicht optimal. Aber das ist ein anderes Thema.

                echo "$verabschiedung $name";

                1. Tach.

                  Ich nehme also mit, dass man den String in die Hash-Funktion steckt, und heraus kommt eine Positionsangabe in der Schlüsselauflistung.

                  Richtig.

                  Halten wir also fest, und kommen damit wieder auf das Laufzeit-Problem des OPs zurück: Ob die Hash-Funktion nun komplex oder weniger komplex ist, (deutlich) aufwendiger als eine Positionsbestimmung per Multiplikation ist sie.

                  Damit du dir selber ein Bild von der Komplexität machen kannst, kopier ich dir mal PHP4s Hashfunktion für Strings -- numerische Schlüssel werden ja nicht gehasht -- direkt aus der zend_hash.h:

                    
                  static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)  
                  {  
                   ulong h = 5381;  
                   char *arEnd = arKey + nKeyLength;  
                    
                   while (arKey < arEnd) {  
                    h += (h << 5);  
                    h ^= (ulong) *arKey++;  
                   }  
                   return h;  
                  }  
                  
                  

                  Mehr als eine Multiplikation und Addition, wie du siehst; aber eben "nichts" im Vergleich zum Durchsuchen der gesamten Tabelle. Man *berechnet* ja direkt den Index in den Hashtable, anstatt Daten einzulesen und mit der Vorgabe zu vergleichen.

                  Da das aber PHP-Interna sind, die man als Anwender sowieso nicht beeinflussen kann, hat man schlechte Karten.

                  So sieht's wohl aus, ja. Der wirklich aufwendige Teil dürfte aber in der Tat das Erstellen der Arrays aus den MySql-Daten sein, nicht die späteren Zugriffe auf einzelne Elemente.

                  [1] Mindestens genauso wichtig sind wahrscheinlich die Mechanismen zur Behandlung von Kollisionen. Aber das bringt dieses Thema so langsam an einen Punkt, wo ich die Lektüre eines Fachbuchs vorschlagen würde, anstatt hier im Forum weiter darüber zu referieren. ;)

                  Bei einem PHP-Array kann es keine zwei Schlüssel mit dem gleichen Wert geben.

                  Richtig. Aber -- wie du selber schon feststellst -- zwei unterschiedliche Werte, die den gleichen Hash liefern.

                  Wenn die Hash-Funktion für unterschiedliche Schlüssel den gleichen Hashwert errechnet, war sie nicht optimal.

                  Es ist zwar möglich, solche "perfekten" Hashfunktionen zu entwerfen, aber man kriegt damit z. B. Probleme, wenn man die Größe der Hashmap dynamisch verändern möchte. Und da die Informatiker eingesehen haben, daß es auf lange Sicht zu aufwendig ist, immer dieses Optimum anzupeilen, nahmen sie die Kollisionen in Kauf und entwickelten vernünftige Möglichkeiten, um diese zu handhaben.

                  --
                  Once is a mistake, twice is jazz.
                  1. Tach.

                    Ich nehme also mit, dass man den String in die Hash-Funktion steckt, und heraus kommt eine Positionsangabe in der Schlüsselauflistung.

                    Richtig.

                    Äh-- warte! Wenn ich das nochmal so lese, habe ich dein Eindruck, wir reden doch aneinander vorbei.

                    array('schlüssel' => 'element', ...)

                    Das, was du als "schlüssel" bezeichnest, ist nicht in der Hashmap aufgelistet. Die Hashmap ist ein Array, welches die Speicheradressen der "element"e enthält. Die Hashfunktion transformiert den "schlüssel" in einen numerischen Wert aus dem Bereich der Arrayindizes, weist somit also direkt den Weg zu einem "element".

                    Jetzt alle Klarheiten beseitigt?

                    --
                    Once is a mistake, twice is jazz.
                    1. echo $begrüßung;

                      Jetzt alle Klarheiten beseitigt?

                      Ja, ich glaube schon. Wenn ich mal groß bin, und dann das Interesse an PHP noch nicht ganz abgestorben ist, werde ich mir das mal selbst in den Quellen zu erarbeiten versuchen.

                      print "%s %s" % (verabschiedung, name)

        2. Tach.

          In typstrengen Sprachen sind Arrays Auflistungen von Elementen gleichen Typs. Die Position eines Werts lässt sich anhand des Schlüssels multipliziert mit der Elementgröße ermitteln. Das bedeutet, dass der Schlüssel sich aus der Position des Elements ergibt, und damit lückenlos von 0 bis n geht. Das gilt auch für weitere Dimensionen.

          Hier wäre ich übrigens vorsichtig. Nicht alle Sprachen speichern, nur weil sie mit streng typisierten Variablen hantieren, mehrdimensionale Arrays so wie du beschreibst. Auch ein Array von Pointern ist eine gängige Methode, um mehrere Dimensionen darzustellen. Dabei zeigen die Pointer der "ersten Dimension" auf Arrays der "zweiten Dimension", die im Speicher aber nicht alle zwangsweise direkt hintereinander angeordnet sein müssen. Mit einer einfachen Multiplikation und Addition zur Speicheradresse, die deine Variable "mehrdimensionales Array" beschreibt, kannst du in diesem Fall auch nicht hantieren. So hardwarenah wilst du das in Hochsprachen aber in vielen Fällen sowieso nicht ...

          Wenn vom Schlüssel ein Hashwert gebildet wird, [...] wie kommt dann PHP an den ungehashten Wert des Schlüssels ($key) bei einem foreach ($array as $key => $value)? Meines Wissens nach ist Hashwert-Bilden eine unumkehrbare Operation.

          Ich habe eine PHP4-Source überflogen, die ich noch auf der Festplatte hatte. Es sieht folgendermaßen aus:

          PHP berechnet beim Einfügen einer Variablen in die Hashmap einen Hash nur für Schlüssel, die nicht ausschließlich numerisch sind -- also Zeichenketten, die in PHP ja als Schlüssel zugelassen sind. *Zusätzlich* zum Hash wird auch der eigentliche Schlüssel gespeichert. Rein numerische Schlüssel werden hingegen direkt für die Indexbestimmung benutzt; das Original wird also gar nicht erst verändert. In beiden Fällen ist somit der Originalschlüssel noch bekannt und kann dazu verwendet werden, um den Schlüssel zu einem bekannten Wert zu bestimmen -- quasi die Gegenrichtung des normalen Lookups. Um möglichst einfach durch alle gespeicherten Elemente laufen zu können (z. B. mit foreach), wird zusätzlich eine verkettete Liste der Elemente verwaltet.

          --
          Once is a mistake, twice is jazz.
  2. Tach.

    Meine Frage ist nun, ob es dafür eine einfachere und schnellere Variante gibt, da diese bei 10000 Feldern und mehr, allein schon mehrere Sekunden benötigt...

    Ich bin bei weitem kein Datenbankfachmann, habe aber die Vermutung, daß sich dein A* auch in MySQL selber implementieren ließe. Vielleicht wäre das ja was, da die größte Bremse das Erstellen und Beackern der Arrays in PHP ist.

    --
    Once is a mistake, twice is jazz.