PHP: estrarre un ramo da un albero a liste di adiacenza senza ricorsione

Esempio di struttura ad albero
Esempio di struttura ad albero
Supponiamo di avere un archivio con una struttura ad albero di tipo a liste di adiacenza. Ogni record sarà necessariamente caratterizzato da un identificativo univoco e da un attributo che serve a riconoscere il proprio genitore. Per esempio, nella figura accanto, l’elemento 4 avrà id = 4, e parentId = 1, l’elemento 9 avrà id = 9, e parentId = 4, e così via. Questo modello offre alcuni vantaggi, che sono principalmente la semplicità della struttura e la velocità negli inserimenti. D’altro canto, risultano piuttosto onerosi processi come l’estrazione o la cancellazione di interi rami. Le query risultano quindi, complesse e spesso ricorsive.

Sebbene l’utilizzo di una struttura di tipo nested tree model ideata da Joe Celko sia quasi sempre preferibile, alle volte è necessario cimentarsi con gli algoritmi per la manipolazione delle liste di adiacenza.

Se si deve salire da una foglia fino alla root, non è troppo difficile, basta risalire, attraverso il parentId, il genitore finché parentId = NULL. Il procedimento naturalmente ricorsivo, per questo motivo spesso si indica l’attributo parentId anche con il nome di ricorsore.

Il gioco si fa duro quando si deve estrarre un ramo a partire da un certo genitore… ma come disse John Belushi: “When the going gets tough, the toughs get going!”. Vediamo come fare evitando di farci del male con stored procedure, query ricorsive o tabelle temporanee.
La soluzione che ho adottato prende spunto dagli algoritmi di attraversamento dei grafi: Breadth-first search e Depth-first search. Questi sono procedimenti non ricorsivi che utilizzano stack di tipo FIFO e LIFO per l’esplorazione dei nodi.

L’operazione di fetching da un archivio che rappresenta l’albero della figura in alto produrrà un’array di questo tipo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$arrTest = array (
                    0 => array ("id"=>1, "parent_id"=>NULL),
                    1 => array ("id"=>2, "parent_id"=>1),
                    2 => array ("id"=>3, "parent_id"=>1),
                    3 => array ("id"=>4, "parent_id"=>1),
                    4 => array ("id"=>5, "parent_id"=>2),
                    5 => array ("id"=>6, "parent_id"=>2),
                    6 => array ("id"=>7, "parent_id"=>3),
                    7 => array ("id"=>8, "parent_id"=>3),
                    8 => array ("id"=>9, "parent_id"=>4),
                    9 => array ("id"=>10, "parent_id"=>4),
                    10 => array ("id"=>11, "parent_id"=>4),
                    11 => array ("id"=>12, "parent_id"=>5),
                    12 => array ("id"=>13, "parent_id"=>5),
                    13 => array ("id"=>14, "parent_id"=>6),
                    14 => array ("id"=>15, "parent_id"=>7),
                    15 => array ("id"=>16, "parent_id"=>7),
                    16 => array ("id"=>17, "parent_id"=>9),
                    17 => array ("id"=>18, "parent_id"=>9),
                    18 => array ("id"=>19, "parent_id"=>10),
                    19 => array ("id"=>20, "parent_id"=>11),
                    20 => array ("id"=>21, "parent_id"=>11)
                  );

Ammettiamo ora di voler estrarre l’intero ramo che ha come radice l’elemento 4. La funzione seguente utilizza un nuovo array che viene costruito utilizzando come chiave gli id e come valori i parent_id. Questo ci permette di utilizzare la funzione PHP: array_keys() per le ricerche dei figli, che è piuttosto efficiente.

Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function getBranch ($arr,$pk,$recursor,$idBranch)
{
  $pksArr = array();
  foreach ($arr as $rec) {
    $pksArr[$rec[$pk]]=$rec[$recursor];
  }
  $branchIds = array($idBranch);
  $i=0;
  while ($i<count($branchIds)) {
    $newKeys = array_keys($pksArr,$branchIds[$i]);
    if (!empty($newKeys)) {
      foreach ($newKeys as $newKey){
        array_push($branchIds, $newKey);
      }
    }
    ++$i;
  }
  $res = array();
  foreach ($arr as $child) {
    if (in_array($child[$pk], $branchIds)) {
      $res[] = $child;
    }
  }
  return $res;
}

Certo, il codice di questa funzione non è troppo ottimizzato: utilizza tre array (anche se $pksArr e $branchIds sono monodimensionali e quindi “leggeri”) ed esegue tre cicli. In particolare il ciclo (righe 19-23) è piuttosto lento, ma è necessario se si vuole recuperare tutti gli attributi degli elementi estratti oltre agli indispensabili id già presenti in $branchIds. Dalle prove che ho fatto, per archivi fino a 10-15000 records risulta comunque abbastanza efficiente.

Questo è il risultato dell’estrazione del ramo con radice 4 (si nota che l’andamento è di tipo “breadth-first-search” ricerca in ampiezza, seguendo i colori: rosso-verde-blu-giallo):

Array
(
    [0] => Array
        (
            [id] => 4
            [parent_id] => 1
        )

    [1] => Array
        (
            [id] => 9
            [parent_id] => 4
        )

    [2] => Array
        (
            [id] => 10
            [parent_id] => 4
        )

    [3] => Array
        (
            [id] => 11
            [parent_id] => 4
        )

    [4] => Array
        (
            [id] => 17
            [parent_id] => 9
        )

    [5] => Array
        (
            [id] => 18
            [parent_id] => 9
        )

    [6] => Array
        (
            [id] => 19
            [parent_id] => 10
        )

    [7] => Array
        (
            [id] => 20
            [parent_id] => 11
        )

    [8] => Array
        (
            [id] => 21
            [parent_id] => 11
        )

)
// Tempo di esecuzione: 0.2388 msecs

Conclusioni

Personalmente, ho una certa ritrosia nell’uso di funzioni ricorsive, per questo ho perso del tempo a cercare soluzioni alternative e cicliche, ciò non toglie che, ad esempio per recuperare il percorso di una foglia (risalendo quindi verso la root), la ricorsione sia la soluzione più adatta.

Riferimenti ed approfondimenti:

PHP: test di algoritmi per generare permutazioni con e senza ricorsione

Benchmarks di algoritmi per le permutazioni
Benchmarks di algoritmi per le permutazioni
Una definizione abbastanza intuitiva delle permutazioni potrebbe essere: “Le permutazioni semplici di n elementi distinti sono tutti i diversi gruppi che si possono formare con gli elementi dati, che rispettino le seguenti clausole:

  1. Ogni gruppo deve essere composto da n elementi.
  2. Un elemento non può essere duplicato in un gruppo.
  3. Due gruppi sono distinti quando differiscono solo per l’ordine con cui sono disposti gli elementi.

La matematica, in particolare il calcolo combinatorio ci insegna che tutte le possibili combinazioni di n elementi sono n!. Per fare un esempio, tutte le possibili permutazioni delle lettere che compongono la parola “mare“, sono 4!, ovvero 4*3*2*1 = 24.
In questo caso, e in tutti i casi in cui tutte le lettere che compongono una certa parola sono distinte, le permutazioni equivalgono agli anagrammi. Nel caso in cui vi siano lettere ripetute, il numero di anagrammi sarà minore. Ad esempio gli anagrammi della parola “olio” sono 4! / 2! = 12

L’implementazione non è banale, ma di algoritmi per la risoluzione del problema “permutazioni” ce ne sono parecchi anche perché l’argomento è quasi sempre presente nei programmi di studio ad indirizzo informatico, quindi è inutile scervellarsi, basta cercarli e cercare di capire la logica con la quale sono stati composti. Cosa più interessante, invece è cercare quello più efficiente.

Per la comparazione ho scelto tre degli algoritmi più noti e comuni, due di essi utilizzano la ricorsione mentre il terzo no. Normalmente il linguaggio con cui vengono presentati questi algoritmi è il C, oppure uno pseudocodice, quindi ho provveduto ad effettuare la traduzione in PHP.

Il primo algoritmo preso in considerazione è quello ricorsivo tradizionale, forse il più conosciuto, tratto da “Appunti di informatica libera” capitolo 595.4 (Algoritmi tradizionali) Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Funzione ricorsiva
function Perm($lista, $k, $m) {
  if ($k == $m){
    $parola = "";
    for ($i=0; $i<=$m; $i++){
      $parola .= $lista[$i];
    }
  echo ($parola."<br />");
  }
  else{
    for ($i=$k; $i<=$m; $i++){
      $tmp = $lista[$k];
      $lista[$k] = $lista[$i];
      $lista[$i] = $tmp;
      Perm($lista, $k+1, $m);          
      $tmp = $lista[$k];
      $lista[$k] = $lista[$i];
      $lista[$i] = $tmp;
    }
  }   
}

Il secondo preso in esame, sempre ricorsivo, è pubblicato negli “user contribs” del manuale PHP. Si tratta di una versione modificata da alejandro dot garza at itesm dot mx di un algoritmo presentato su uno dei libri del noto editore O’Reilly. Sebbene non sia efficientissimo in termini di prestazioni, si tratta comunque di un esempio interessante per chi programma in PHP, in quanto utilizza alcune funzioni native del linguaggio. Ho commentato le istruzioni per la restituzione del risultato in un array, perché sebbene comodo, lo avrebbe penalizzato eccessivamente.
Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function array_2D_permute($items, $perms = array( )) {
//static $permuted_array;
    if (empty($items)) {
        //$permuted_array[]=$perms;
        //print_r($new);
      print join('', $perms) . "<br />";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             array_2D_permute($newitems, $newperms);
         }
         //return $permuted_array;
    }
}

Infine un algoritmo non ricorsivo ideato da Phillip Paul Fuchs, il riferimento è: Scalable Permutations, in particolare ho tradotto in PHP l’esempio descritto in The Counting QuickPerm Algorithm. Phillip Paul Fuchs è un vero esperto di queste tematiche e ha scritto anche un libro sull’argomento. Non a caso, dunque, il suo algoritmo risulta il più efficiente!
Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function Fuchs_perm($buf){
  $res = implode("",$buf);
  echo("$res<br />");
  $string_length = count($buf);
  for($i=0;$i<$string_length;$i++){
    $p[$i]=0;
  }
  $i=1;
  while($i < $string_length){
   if ($p[$i] < $i) {
      $j = $i % 2 * $p[$i];
      $tmp=$buf[$j];
      $buf[$j]=$buf[$i];
      $buf[$i]=$tmp;
      $res = implode("",$buf);
      echo("$res<br />");
      $p[$i]++;
      $i=1;
   } else {
      $p[$i] = 0;
      $i++;
   }
  }
}

Per testare la velocità di esecuzione ho utilizzato questa interessante classe PHP realizzata da Ioannis Cherouvim: A time measuring and performance benchmarking class, eliminando tutte le istruzioni di stampa dell’output. I risultati sono visibili nella seguente tabella e nel grafico all’inizio dell’articolo.

Benchmarks di algoritmi per le permutazioni:
Algoritmo2 lett.3 lett.4 lett.5 lett.6 lett.7 lett.8 lett.
Algoritmo non ricorsivo Fuchs0,11010,11790,14210,27781,22007,237158,1750
Algoritmo ricorsivo tradizionale0,11690,15410,31301,19787,174158,0190440,7771
Algoritmo ricorsivo O’Reilly0,19700,28980,53612,301013,8372106,2979854,8127

Se volete fare qualche test con questi 3 algoritmi potete scaricare questo pacchetto
E’ richiesto PHP versione 5.3.x o superiore!

Conclusioni:

I risultati parlano da soli e rispecchiano le mie aspettative. L’algoritmo di Fuchs, è nettamente migliore degli altri, altamente ottimizzato e non ricorsivo. Quelli ricorsivi soffrono degli svantaggi tipici di questa tecnica: ogni chiamata ricorsiva consuma memoria ed utilizza un salto ad una funzione che produce un inevitabile rallentamento.