Rekursion in Arrays feststellen

[whitesaturn]

Arrays können in PHP rekursiv aufgebaut sein, wie zum Beispiel:

$a = array();
$a[0] = $a;

print_r($a);

//Ausgabe:
//Array
//(
//    [0] => Array
// *RECURSION*
//) 

$GLOBALS ist auch ein rekursives Array.

In meiner Anwendung möchte ich komplette Arrays auslesen und durchlaufen (durch eine rekursive Funktion zum Beispiel).
Handelt es sich dabei um rekursive Arrays rufe ich aber eine Endlosschleife auf.

Wie stelle ich fest, daß ich ein rekursives Array habe, ohne daß ich über den Aufbau des Arrays vorher Bescheid weiß?

Ich hatte die Idee, einfach einen Flag in ein Array zu setzen, und in der tieferen Ebene einfach zu testen ob das Flag vorhanden ist:

//Rekursives Array herstellen
$a = array();
$a[0] = $a;

//Flag setzen
$a['__RECURSION__'] = true;

//Eine Ebene Tiefer gehen in die Rekursion gehen
$b = $a[0];

//Test ob eine Rekursion vorhanden ist.
if ( array_key_exists( '__RECURSION__', $b ) )
      echo "Rekursion vorhanden"; 

Ich war der festen Überzeung daß ich mit dieser Methode feststellen könnte, ob eine Rekursion in einem Array vorliegt, aber es funktioniert leider nicht...

Gibt es denn gar keine Möglichkeit?
Ich habe mich im Internet bereits totgesucht ohne fündig zu werden.

[onemorenerd]

Ich kenne nur diesen einen Weg:

//Rekursives Array herstellen
$a = array();
$a[0] = $a;
//Test ob eine Rekursion vorhanden ist.
if (strpos(print_r($a, true), '*RECURSION*'))
    echo 'Rekursion vorhanden'; 

Das ist sehr unsauber, siehe

$a = array('*RECURSION* is nice!'); 

Aber du kannst die erwartete Ausgabe von print_r() ja in deiner Schleife mitkonstruieren. Dann wird der Test ziemlich sicher, irrt sich dann nur noch bei Arrays, die (fast) ihre eigene print_r()-Ausgabe enthalten.

[jahlives]

Was würde gegen is_array() sprechen ? A la

$a = array();
$a[0] = $a;
//foreach verwenden weil wir den Aufbau des Array ned kennen
foreach($a as $wert){
    if(is_array($wert)){
        echo 'Rekursion';
        break;
    else{
        echo 'Keine Rekursion';
        break;
    }
} 

Gruss

tobi

[onemorenerd]

multidimensional != rekursiv

Man könnte auf die Idee kommen, statt deinem is_array mal eben $a == $wert zu prüfen. Aber den Vergleich bricht PHP irgendwann mit einem fatal error ab.

[jahlives]

Und wiedermal was gelernt
Danke und Gruss

tobi

[whitesaturn]

An die Möglichkeit (multidimensionale) Strukturen einfach mit print_r auszuwerten hatte ich mir auch überlegt, aber wie schon erwähnt, ist es keine wirklich sichere Methode.

Aber wie es scheint, gibt es keine Möglichkeit, es sei denn ich schreibe mir eine eigene Extension.

[mrhappiness]

Wie schon erwähnt, ist das, was du in deinem Code fabrizierst, nicht rekursiv.

Wie wäre es, wenn du uns ein Array aufbaust, das du nicht komplett auslesen kannst?

[whitesaturn]

Also laut print_r und var_dump ist das Array in PHP5 durchaus rekursiv.

In PHP4 kann ein rekursives Array folgendermaßen aussehen:

$a = array();
$a[0] = & $a; 

Wertet man $a durch print_r oder var_dump aus wird die Rekursivität angezeigt.

Wie programmiere ich eine Funktion die ein komplettes multidimensionales Array auswertet, ohne daß sie durch solche Rekursivitäten in eine Endlosschleife gerät (und trotzdem das Array korrekt auswertet)?

Ohne Rekursionen in Arrays ist das kein Problem, aber was wenn welche vorhanden sind?

[closure]

Wie programmiere ich eine Funktion die ein komplettes multidimensionales Array auswertet, ohne daß sie durch solche Rekursivitäten in eine Endlosschleife gerät (und trotzdem das Array korrekt auswertet)?

Ich würde gern verstehen wann man eine solche struktur braucht.
Was ist der konkrete anwendungsfall ?

Abgesehen davon: richtig auswerten bedeutet nicht mit dem
abarbeiten aufzuhören sobald man feststellt, dass der wert an
position n eine referenz auf den container selbst ist ?

Viel spaß, der algo läuft ewig.

greets

[onemorenerd]

Original geschrieben von closure
Ich würde gern verstehen wann man eine solche struktur braucht.
Was ist der konkrete anwendungsfall ?

Mir fällt keine sinnvolle Anwendung für rekursive Datenstrukturen ein, aber das heißt noch lange nicht, das man nicht über deren Erkennung nachdenken muß. Wenn der Kunde ein CMS möchte, bei dem er PHP eingeben kann, muß man ihn möglicherweise davor schützen ...

Abgesehen davon: richtig auswerten bedeutet nicht mit dem abarbeiten aufzuhören sobald man feststellt, dass der wert an position n eine referenz auf den container selbst ist ?

Richtig auswerten kann man eine rekursive Datenstruktur nicht. Gerade deswegen ist es wichtig, sie als solche zu erkennen und diese Erkennung ist ja nicht die Frage nach P oder NP: print_r() ist hier ein fast perfekter Entscheider. Der Algorithmus läuft dann nicht ewig sondern ggf. gar nicht.

[closure]

Hi,

ok nun ist mir zu mindest mal klar dass ich das richtig erfasst habe.
Ok, also zur erkennung von rekursion in arrays gibt es eine recht einfache
vorgehensweise.
Es handelt sich um den Hase-und-Schildkröte-Algorithmus.
Auch bekannt als Floyd's cycle-finding algorithm.

Hier eine implementierung, die fast 1 zu 1 nach php übertragen werden kann.


greets

EDIT: hmm mag der URL-BBCode keine Apostrophs in urls ?

[onemorenerd]

Äh? Na das implementiere mir mal in PHP bitte ...

[closure]

Hi,
das ist jetzt nur schnell runtergehackt.
Wenn ich zeit hab schreib ich nochmal nen unittest dafür.

<?php
    error_reporting(E_ALL);

    
    function try_advance_once(&$arr,&$cur){
        return isset($arr[$cur + 1]);
    }
    
    function advance_once(&$arr,&$cur){
        if(is_array($arr[$cur])){
            $arr = $arr[$cur];
            $cur = 0;
        }else{
            $cur++;
        }
    }

    function advance_twice(&$arr,&$cur){
        advance_once($arr,$cur);
        advance_once($arr,$cur);
    }

    function has_cycles($arr){
        $hare = 0;
        $tortoise = 0;

        advance_once($arr,$tortoise);
        advance_twice($arr,$hare);

        
        do{
            if(!isset($arr[$hare])){
                return false;
            }
            
            if(!try_advance_once($arr,$hare)){
                return false;
            }

            if($arr[$hare] === $arr[$tortoise]){
                return true;
            }

            advance_once($arr,$tortoise);
            advance_twice($arr,$hare);

        }while(1);
    }

    $recarr = array(1,2,3,4);
    $recarr[3] = &$recarr;
    
    if(has_cycles($recarr)){
        echo "yes\n";
    }else{
        echo "no\n";
    }

    $nonrecarr = array(1,2,3,4);
    
    if(has_cycles($nonrecarr)){
        echo "yes\n";
    }else{
        echo "no\n";
    }

    
?>

Der specialfall

$arr = array(1);
$arr[0] = &$arr; 

Wird als nicht-cyclisch erkannt, bzw. lösst einen fehler aus. Hier muss man
sich noch was überlegen. TODO for the reader

greets

[onemorenerd]

Dieser Code erkennt nur den Spezialfall "Schleife".

$a = array();
$a[0] = $a;

ist aber keine Schleife, denn $a[0] = &$a; ist nicht das gleiche wie $a[0] = $a;.
Für den PHP-Anwender ist ein Array keine verkettete Liste! Jeder weiß, dass PHP für Funktionen für next() natürlich mit jedem Element einen Zeiger auf dessen Nachfolger speichert. Aber das macht Arrays nur PHP-intern zu verketteten Listen, für den Anwender sind die Zeiger nämlich gar nicht zugänglich. (Funktionen wie next() nutzen ihn, erlauben aber keine Manipulation.) In deinem Fall hast du mit dem Operator & einfach einen Zeiger in einem Element gespeichert und auf den kannst du natürlich zugreifen. Aber genauso gefährlich sind die internen Zeiger, an die man nicht herankommt.

Beispiel:
Der PHP-Anwender programmiert
$a = array();
$a[0] = 0;
$a[1] = $a;
PHP-intern sieht es so aus (nur das "unsichtbare" betrachtet):
$a = array();
$a[0] = 0; -> $a[0] ist SOL und EOL, keine Zeiger
$a[1] = $a; -> $a[1] wird EOL, $a[0] bekommt Zeiger auf Nachfolger $a[1]

PHP kann diese Zeiger offensichtlich zur Rekursionserkennung nutzen:

function test_print($item, $key) {}
array_walk_recursive($a, 'test_print'); 

endet mit der Warnung "recursion detected". Aber nicht bei jedem Zugriff wird dieser Rekursionstest durchgeführt sondern einfach bei einer bestimmten Verschachtelungstiefe abgebrochen:

echo ($a === $a[0]); 

endet mit
Fatal error: Nesting level too deep - recursive dependency?

[closure]

Original geschrieben von onemorenerd
... denn $a[0] = &$a; ist nicht das gleiche wie $a[0] = $a;.

Japp, das hatte ich übersehen. Ich dachte es ginge nur
um den fall $a[n] = &$a;


greets