[PHP] Refenzen zu Arrays

[Gast]

Bei der Änderung einer rekursiven Funktion zu einer iterativen Variante, bin ich auf ein Problem mit Referenzen zu Arrays gestoßen.
Sie funktionieren nämlich nicht wie erwartet. Die 9 Schritte sind dabei auch die Schritte der Funktion mit den Testdaten.
Ich habe zwar eine Lösung für das Problem unter PHP, aber vielleicht kann mir ja jemand erklären, was das Problem ist.


<?php

$expected_tree = array(
1 => array(
21 => array(
31 => array(),
32 => array(
41 => array(),
42 => array(),
43 => array(),
),
33 => array(),
),
22 => array(),
23 => array(),
)
);


//step 1: current_parent = 1, current_child = 21
$array = array();
$stack[1][21] = &$array;
$stack[21] = &$array;

//step 2: current_parent = 1, current_child = 22
$array = array();
$stack[1][22] = &$array;
$stack[22] = &$array;

//step 3: current_parent = 1, current_child = 23
$array = array();
$stack[1][23] = &$array;
$stack[23] = &$array;

//step 4: current_parent = 21, current_child = 31
$array = array();
$stack[21][31] = &$array;
$stack[31] = &$array;

//step 5: current_parent = 21, current_child = 32
$array = array();
$stack[21][32] = &$array;
$stack[32] = &$array;

//step 6: current_parent = 21, current_child = 33
$array = array();
$stack[21][33] = &$array;
$stack[33] = &$array;

//step 7: current_parent = 32, current_child = 41
$array = array();
$stack[32][41] = &$array;
$stack[41] = &$array;

//step 8: current_parent = 32, current_child = 42
$array = array();
$stack[32][42] = &$array;
$stack[42] = &$array;

//step 9: current_parent = 32, current_child = 43
$array = array();
$stack[32][43] = &$array;
$stack[43] = &$array;

print_r($stack[1]);

// var_dump($expected_tree[1] === $stack[1]); // sollten gleich sein.




Array
(
[21] => Array
(
[43] => Array
*RECURSION*
)

[22] => Array
(
[43] => Array
*RECURSION*
)

[23] => Array
(
[43] => Array
*RECURSION*
)

)





//step 1: current_parent = 1, current_child = 21
$array = new ArrayObject();
$stack[1][21] = $array;
$stack[21] = $array;

//step 2: current_parent = 1, current_child = 22
$array = new ArrayObject();
$stack[1][22] = $array;
$stack[22] = $array;
...

[Gast_samm]

Ist das wirklich 1:1 dein Code? Denn $expected_tree[1] hätte sowieso nicht denselben Aufbau wie $stack[1]. $stack[1] wäre bloss
21 => array(),
22 => array(),
23 => array()

Insofern bitte ein direktes copy/paste des Codes, sonst kann man eh nur raten, was da das Problem ist.

[Gast]

Ist das wirklich 1:1 dein Code? Denn $expected_tree[1] hätte sowieso nicht denselben Aufbau wie $stack[1]. $stack[1] wäre bloss
21 => array(),
22 => array(),
23 => array()


Das stimmt nicht. Die Ausgabe von print_r($stack[1]) hatte ich dazu in zweiten Spoiler im ersten Betrag geschrieben.
Mir ging es auch nicht um meine Funktion, welche nur zum Test in php geschrieben ist, sondern um die Referenzen zu Variablen.

Ich habe extra zur Veranschaulichung genau die Iterationsschritte der Funktion mit den Testdaten gepostet. Und dazu ist das Beispiel absolut ausreichend und leichter zu verstehen.

Das Ergebnis der Funktion und des Beispiels sind identisch!

Was mich interessiert ist, warum die Referenzen kaputt sind.

Hier noch mal zum Testen: das Beispiel mit der Anpassung aus dem 3. Spoiler und Ausgabe.


<?php

function print_tree($tree, $indent = 0) {
$str = str_repeat('..', $indent);
foreach ($tree as $node => $subnodes) {
echo "{$str}node: $node\n";
print_tree($subnodes, $indent+1);
}
}

$expected_tree = array(
1 => array(
21 => array(
31 => array(),
32 => array(
41 => array(),
42 => array(),
43 => array(),
),
33 => array(),
),
22 => array(),
23 => array(),
)
);

print_tree($expected_tree[1]);

//step 1: current_parent = 1, current_child = 21
$array = new ArrayObject();
$stack[1][21] = $array;
$stack[21] = $array;

//step 2: current_parent = 1, current_child = 22
$array = new ArrayObject();
$stack[1][22] = $array;
$stack[22] = $array;

//step 3: current_parent = 1, current_child = 23
$array = new ArrayObject();
$stack[1][23] = $array;
$stack[23] = $array;

//step 4: current_parent = 21, current_child = 31
$array = new ArrayObject();
$stack[21][31] = $array;
$stack[31] = $array;

//step 5: current_parent = 21, current_child = 32
$array = new ArrayObject();
$stack[21][32] = $array;
$stack[32] = $array;

//step 6: current_parent = 21, current_child = 33
$array = new ArrayObject();
$stack[21][33] = $array;
$stack[33] = $array;

//step 7: current_parent = 32, current_child = 41
$array = new ArrayObject();
$stack[32][41] = $array;
$stack[41] = $array;

//step 8: current_parent = 32, current_child = 42
$array = new ArrayObject();
$stack[32][42] = $array;
$stack[42] = $array;

//step 9: current_parent = 32, current_child = 43
$array = new ArrayObject();
$stack[32][43] = $array;
$stack[43] = $array;

print_tree($stack[1]);

[Gast]

Erläuterung warum das Beispiel grundsätzlich funktioniert.
Im fünften Schritt (L5) haben wir mit $stack[21] Zugriff auf das ArrayObject aus dem ersten Schritt (L3),
welches nun einen neuen Eintrag (L5: 32 => ArrayObject) erhält.
Durch das erneute Einfügen des selben Arrays in die erste Ebene (L6)
haben wir bei einer späteren Iteration wieder Zugriff auf den Teilbaum (L8).


//step 1: current_parent = 1, current_child = 21
L1: $array = new ArrayObject();
L2: $stack[1][21] = $array;
L3: $stack[21] = $array;
// ...
//step 5: current_parent = 21, current_child = 32
L4: $array = new ArrayObject();
L5: $stack[21][32] = $array;
L6: $stack[32] = $array;
// ...
//step 7: current_parent = 32, current_child = 41
L7: $array = new ArrayObject();
L8: $stack[32][41] = $array;
L9: $stack[41] = $array;

[Gast_samm]

Ok, got it. Weshalb die Referenzen kaputt sind, weiss ich dennoch nicht ;) Das müsste ich auch mal testen - es könnte etwas mit Optimierungen zu tun haben (z.B. array() bewirkt eigentlich erstmal erst das zeigen auf eine Dummy-Adresse, erst wenn Elemente hinzugefügt werden, wird wirklich eigener Speicher für das Array verwendet, was erklären würde, weshalb Element [43] statt [31] als letztzugewiesenes auf die Dummy-Adresse zeigendes angezeigt wird - wobei, da müsste dann "43" wie bei einem assoziativen array mitgespeichert werden. Sind in PHP alle (auch numerisch indizierte) Arrays assoziativ? Die recursion-meldung käme dann *grübel* wenn das nächste Element, nämlich [32] [41] wiederum auf die dummy-Adresse verweist, die momentan [43] ist, wodurch ein iterieren unmöglich wird: [43], nächstes element ist [32] [41], was aber == [43] ist, sodass es eine unendliche Rekursion gäbe.)

[Gast]

So etwas mit an wie Dummy-Adresse hab ich auch schon gedacht. Es kommt wohl auch zum Tragen, dass es keinen eigenen Scope für for/while/if gibt. Vllt wird da etwas falsch optimiert.
Es riecht auf jeden Fall nach Fehler.

Bei der Erinnerung an den Scopes von Variablen, ist mir einfach das Löschen der Variable eingefallen :D

$array = array();
$stack[1][21] = &$array;
$stack[21] = &$array;
unset($array);

// oder einfach ohne Variable
$stack[1][21] = array();
$stack[21] = &$stack[1][21];




mysql_query('
CREATE TEMPORARY TABLE t1 (parent INT NOT NULL, child INT NOT NULL, PRIMARY KEY (parent, child));
');

mysql_query('
INSERT INTO t1 (parent, child) VALUES (1, 21), (1, 22), (1, 23), (21, 31), (21, 32), (21, 33), (32, 41), (32, 42), (32, 43);
');

function fetch_children($parent) {
$res = mysql_query('SELECT parent, child FROM t1 WHERE parent =' . intval($parent));
$result = array();
while (($row = mysql_fetch_row($res)) !== false) {
$result[] = $row;
}
return $result;
}

$expected_tree = array(
1 => array(
21 => array(
31 => array(),
32 => array(
41 => array(),
42 => array(),
43 => array(),
),
33 => array(),
),
22 => array(),
23 => array(),
)
);

$expected_tree = $expected_tree[1];

function tree_recursive($id) {
$tree = array();
foreach (fetch_children($id) as $node) {
$tree[$node[1]] = tree_recursive($node[1]);
}
return $tree;
}

function tree_iterative($id) {
$stack = array();
$elements = fetch_children($id);
while (count($elements)) {
list($parent_node, $node) = array_shift($elements);
$result = fetch_children($node);
$elements = array_merge($elements, $result);

$stack[$parent_node][$node] = array();
$stack[$node] = &$stack[$parent_node][$node];
}
return $stack[$id] ?: array();
}

function print_tree($tree, $indent = 0) {
$str = str_repeat('..', $indent);
foreach ($tree as $node => $subnodes) {
echo "{$str}node: $node\n";
print_tree($subnodes, $indent+1);
}
}

$recursive_tree = tree_recursive(1);
$iterative_tree = tree_iterative(1);

var_dump($expected_tree === $iterative_tree);

echo "\nexpected_tree\n";
print_tree($expected_tree);

echo "\nrecursive_tree:\n";
print_tree($recursive_tree);

echo "\niterative_tree:\n";
print_tree($iterative_tree);