[php] Recursieve boomstructuur efficienter maken

[Verwijderd]

Ik gebruik de volgende functie om een boomstructuur weer te geven:

PHP:

function makeCatRecArray($parent_id = 0, $array = array(), $level = 0)
{
       $level++;
       $ret_array = array();
       
       if(is_array($array))
       {
              foreach($array as $id => $item)
              {
                    if($item['parent'] == $parent_id)
                    {
                        $row['id'] = $id;
                        $row['text'] = printString($level*3, " ", "> ") . $item['name'];
                        $ret_array[] = $row;

                        $ret_array = array_merge($ret_array, makeCatRecArray($id, $array, $level));
                    }
              }
       }
       return $ret_array;
}

Deze functie krijgt een array mee met daarin alle rijen uit de tabel. Probleem is dat deze manier welliswaar sneller is dan voor ieder item een query uitvoeren, maar toch nog te langzaam. Op mijn eigen pc doet deze functie er gemiddeld 6 sec over om een boompje van 1250 items te genereren. Hoe kan ik dit sneller maken?

Ik heb al diverse dingen geprobeerd, zoals array_merge vervangen door `+`, maar dat is juist langzamer.

[ Voor 10% gewijzigd door Verwijderd op 03-12-2004 23:25 . Reden: typo's ]

[Eärendil]

Je zou Modified Preorder Tree Traversal kunnen proberen. Je hoeft je functie dan niet recursief aan te roepen, wat veel performance kan schelen.

[Verwijderd]

Eärendil schreef op vrijdag 03 december 2004 @ 23:49:
Je zou Modified Preorder Tree Traversal kunnen proberen. Je hoeft je functie dan niet recursief aan te roepen, wat veel performance kan schelen.

Ja ik ken deze methode, maar vind de zaken die nodig zijn om de boomstructuur te bewerken veel te omslachtig. Als het om een statische boom gaat is het ideaal.

[Verwijderd]

Ik heb nu behoorlijk wat progressie geboekt. Ik genereer nu een geneste array waarin de children per parent gegroepeerd zijn, zo dus:

PHP:

$arr[{parent}][{counter}] = array({children_data});

En laat daar deze functie op los:

PHP:

function makeCatRecArray($par, $arr, $level = 1)
{
       $ret_array = array();
       
       if(is_array($arr) && isset($arr[$par]))
       {
              for ($i = 0; $i < sizeof($arr[$par]); $i ++) 
              {
                    $id = $arr[$par][$i]['id'];
                    $name = $arr[$par][$i]['name'];
                    
                    $row['id'] = $id;
                    $row['text'] = printString($level*3, '&nbsp;', '>&nbsp;') . $name;
                    $ret_array[] = $row;

                    if(isset($arr[$id]))
                    {
                       $ret_array = array_merge($ret_array, makeCatRecArray($id, $arr, $level + 1));
                    }
              }
       }
       return $ret_array;
}

De prestaties:
1 query per child methode: 26,7 sec
array uit startpost methode: 5,9 sec
bovenstaande methode: 0,21 sec

Scheelt behoorlijk wat dus. Hoop dat andere mensen hier wat aan hebben.

[TheDane]

Ene Ironclad heeft in de Reader Comments in dit artikel ook wel een aardige methode:

I don't know where this fits into the bigger picture, but one way I solved the problem of sorting was by storing into each entry its lineage as a long text string, and then sorting by that field.

Consider these two threads:
ID Subject Lineage
001 Hello World 001
002 Goodbye Cruel World 001-002
004 Why so sad? 001-002-004
006 Skool sukz 001-002-004-006
008 Grow up 001-002-004-006-008
007 Cheer up 001-002-004-007
003 Foo was here 003
005 Kilroy was there 003-005

Although the messages were created out of strict sequence, you can safely assume that message #006 was created after #004 (unless you have some weird recordID thing going). Thus, to put all the messages into correct sorted order you just sort by the lineage.

When creating a new node you can optimise the calculation of the lineage by realising you don't need to traverse the entire ancestry - you just ask your poppa for the history.

I'm guessing this method is more suited to wider rather than deeper hierarchies, which most discussion forums are. Also, given the social dynamics of discussion forums its a good bet that the records are already close to being sorted correctly, what with replies all occuring after their parents, and replies likely to be near in time to those parents.

This approach also facilitates displaying a sub-branch at any time. For example, search for lineage starting with 001-002-004 for the entire "why so sad" thread.

Nonetheless, given the usual ratio of reading vs posting, it still probably better to simply re-sequence the lot and not sort on the fly. Note too the social dynamic of replies being near in time also lessens the impact of your update routine.

[djluc]

Verwijderd schreef op vrijdag 03 december 2004 @ 23:57:
[...]Ja ik ken deze methode, maar vind de zaken die nodig zijn om de boomstructuur te bewerken veel te omslachtig. Als het om een statische boom gaat is het ideaal.

Je kan er een functie voor maken waardoor je het alsnog heel eenvoudig kan doen. Bijvoorbeeld een functie insertInTree waar je de velden in een array meegeeft o.i.d. Eenmalig wat werk maar daarna misschien nog wel eenvoudiger dan een query opbouwen.

[Verwijderd]

djluc schreef op zaterdag 04 december 2004 @ 11:23:
[...]
Je kan er een functie voor maken waardoor je het alsnog heel eenvoudig kan doen. Bijvoorbeeld een functie insertInTree waar je de velden in een array meegeeft o.i.d. Eenmalig wat werk maar daarna misschien nog wel eenvoudiger dan een query opbouwen.

Ja da's waar, misschien begin ik er nog een keer aan, maar vond mijn laatste methode eigenlijk wel snel genoeg.

[ Voor 1% gewijzigd door Verwijderd op 04-12-2004 12:05 . Reden: typo ]

[SuperRembo]

Ik denk dat er nog wel wat snelheidswinst is te halen door zonder recursie te werken. Zeker bij een diepe boomstuctuur kan dat veel schelen.

[Creepy]

SuperRembo schreef op zaterdag 04 december 2004 @ 12:45:
Ik denk dat er nog wel wat snelheidswinst is te halen door zonder recursie te werken. Zeker bij een diepe boomstuctuur kan dat veel schelen.

En hoe had je dat bedacht zonder recursie? Let erop dat met recursie het vrij simpel is om niet afhankelijk te zijn van een maximale diepte van de boom. Ok, ook zonder recursie is dat te realiseren maar daar wordt de code meestal groter en minder duidelijk door.
Maar alleen opmerken "zonder recursie kan je ook nog wel wat snelheids winst halen" is voor mij ff te kort door de bocht

[Sjaaky]

Als je het zonder recursie wilt doen moet je zelf een lijst (niet perse een list ) bijhouden met de nodes die je nog af moet lopen. In elke iteratie pak je er een node af, die verwerk je en eventuele nieuwe nodes voeg je aan de lijst toe. Dit doe je net zolang tot je lijst leeg is.
Met recursie is dat lijstje ook aanwezig maar meer impliciet in de stack van function calls.
Ik ken geen imperatieve talen die tailrecursion optimaliseren, dus zou het zelf bijhouden van een lijst efficienter in geheugen en processortijd moeten zijn.

[Creepy]

Dat lijsteje kan je eventueel ook bijhouden m.b.v. een pointer of reference. Dus dat verwaarloosd de snelheidswinst van de niet recursieve functie.

Tuurlijk, elke keer opnieuw een functie aanroep kan langzamer zijn, maar denk je echt dat dat merkbaar scheelt met een niet recursieve functie die hiervoor 1 of 2 loops moet gebruiken en ook rekening houdend met het feit dat de niet recursieve functie vaak meer regels code bevat dan de recursieve variant?

Edlt: lees: kom eens met een niet recursieve variant en vergelijk de code en de snelheid eens met het laatste recursieve voorbeeld

[ Voor 14% gewijzigd door Creepy op 04-12-2004 14:31 ]

[Verwijderd]

Dynamisch programmeren mbv een lijst met resultaten kan hier waarschijnlijk wel een hoop snelheidswinst betekenen.
Puur alle nodes aflopen (zoals Sjaaky voorstelt) zal iteratief niet sneller zijn dan recursief.

[TheDane]

@ Creepy: in het linkje wat ik hierboven heb gepost staat een nogal simpele, maar aardige vergelijking qua performance bij recursieve en iteratieve functies, en dat scheelt idd nogal wat, vooral omdat de cost voor recursiviteit schijnbaar -in bepaalde talen- logaritmisch toeneemt.

Het uitvoeren van een regel code wordt wel even buiten beschouwing gelaten, maar 't leuke is dat er helemaal niet veel extra's nodig is bij bijvoorbeeld een flat table model.

[Creepy]

TheDane: dan pas je dus naast je functie ook nog je datamodel aan

Waar het mij meer omging is dat zomaar roepen "eeeh, haal de recursivieteit eruit, dan word het sneller" gewoon onzin is. Dit is helemaal afhankelijk van de gebruikte toepassing (en ook nog eens de gebruikte taal getuige je link ).

[Sjaaky]

Creepy schreef op zaterdag 04 december 2004 @ 14:28:kom eens met een niet recursieve variant en vergelijk de code en de snelheid eens met het laatste recursieve voorbeeld

Nou voor deze ene keer . Op platte bomen is het iets langzamer. Bij diepe bomen is hij ongeveer 2x zo snel. Als je bomen niet zo diep zijn, maakt het dus weinig uit, maar dat is logisch :-).
Het kan nog wel iets sneller voor platte bomen door de bladeren in de boom in een kleiner loopje te behandelen.

PHP:

function makeCatItArray($par, $arr, $level=1)
{
    $stack = array();
    $stack[] = array($par, 0, $level);
    $ret_array = array();
    $top = 0;
   
    if(is_array($arr) && isset($arr[$par])) {
        while ($top >= 0){
            $s = &$stack[$top];
            $par = $s[0];
            $i = $s[1];
            $level = $s[2];
            if($i >= sizeof($arr[$par])) {
                $top--;
            } else {
                $id = $arr[$par][$i]['id'];
                $name = $arr[$par][$i]['name'];
    
                $row['id'] = $id;
                $row['text'] = str_repeat(" ",$level*3). "> " . $name;
                $ret_array[] = $row;
                if (isset($arr[$id][0])){
                    $top++;
                    $stack[$top] = array($id, 0, $level+1);
                }
    
                $s[1]++;
            }
        }
    }
    return $ret_array;
}

edit: en zo is het wel altijd sneller. (zoek de verschillen)

PHP:

function makeCatItArray($par, $arr, $level=1)
{
    $stack = array();
    $stack[] = array($par, 0, $level);
    $ret_array = array();
    $top = 0;
   
    if(is_array($arr) && isset($arr[$par])) {
        while ($top >= 0){
            $s = &$stack[$top];
            $par = $s[0];
            $i = $s[1];
            $level = $s[2];
            $size = sizeof($arr[$par]);
            while($i < $size) {
                $id = $arr[$par][$i]['id'];
                $name = $arr[$par][$i]['name'];
    
                $row['id'] = $id;
                $row['text'] = str_repeat("&nbsp;",3*$level). ">&nbsp;" . $name;
                $ret_array[] = $row;
                $s[1]++;
                if (isset($arr[$id][0])){
                    $top++;
                    $stack[$top] = array($id, 0, $level+1);
                    break;
                }
                $i++;
            }
            if ($i >= $size){ 
                $top--;
            }
        }
    }
    return $ret_array;
}

@Tweakert:
Ik snap niet hoe je dit kan verbeteren met dynamisch programmeren. En puur alle items aflopen, tja dat doe ik, uiteraard, dat is de bedoeling.

[ Voor 50% gewijzigd door Sjaaky op 04-12-2004 18:35 ]

[SuperRembo]

Kijk, 't was niet zo dom wat ik zei
Ik had het misschien wat voorzichtiger kunnen formuleren: Ik denk dat er misschien nog wel wat snelheidswinst is te halen door zonder recursie te werken.

[Soultaker]

Dat is echt onzin. Je moet gewoon de meest heldere oplossing gebruiken, samen met de meest geschikte datastructuren.

De uiteindelijke oplossing van Lusch is zo snel, omdat 'ie een hashtable (associative array in PHP) gebruikt om items op te zoeken, in plaats van elke keer die hele lijst door te zoeken. Dat is slim; je gebruikt dan namelijk een geschiktere datastructuur om daarmee de complexiteit van je algoritme te reduceren. Dat is een zinnige optimalisatie.

Omschrijven van recursief naar iteratief levert misschien een constante factor aan snelheidswinst op, maar het verschil is verwaarloosbaar als de inhoud van de functie de berekening domineert. Recursieve function calls elimineren is in principe alleen nuttig als je daarmee het gebruik van een stack kunt voorkomen (en dan wordt je algoritme dus wezenlijk anders). Hier is daar geen sprake van. Je wisselt dan de function call stack van PHP af voor een eigen mechanisme met een stack en een function body (binnen de while lus) en het lijkt me sterk dat die efficienter is.

[ Voor 6% gewijzigd door Soultaker op 04-12-2004 19:49 ]

[pjotrk]

Sinds ik eenmaal gewend ben geraakt aan celko-trees, waarnaar Eärendil al verwees zou ik niet zo snel meer gaan voor een 'standaard' tree structuur, tenzij je erg vaak inserts in de tree verwacht, de omslachtige inserts en deletes zijn even wat minder, daar staat wel tegenover dat je de tree bijna altijd met één query in de gewenste vorm kan ophalen en dus performance winst. Maar ik heb de functie toch nog net iets sneller gekregen (voornamelijk door het meegeven van de arrays als reference).

(vergelijking tussen de celko-tree en de 'standaard' tree is natuurlijk niet helemaal eerlijk zo, de celko-tree komt uit de database en de 'standaard' tree wordt opgebouwd met een functie, maarja... )

PHP:

<?php

include 'config.php';
include 'timer.class.php';

// functie om standaard tree op te bouwen
function makeCatRecArray( $par, &$arr, &$ret_array, $level = 1 )
{
   foreach ( $arr[$par] as $node )
   {
      $row['id'] = $node['id'];
      $row['text'] = str_repeat('&nbsp;', 3 * $level ) . '>&nbsp;' . $node['name'];
      $ret_array[] = $row;

      if( isset( $arr[ $node['id'] ] ) )
      {
         makeCatRecArray( $node['id'], &$arr, &$ret_array, $level + 1 );
      }
   }
}

// celko-pagetree class
class pagetree
{
   enz...

   // functie om celko-tree op te bouwen
   function get_tree()
   {
      $sql = "SELECT t1.id, concat( repeat('&nbsp;', count(*)) , '>&nbsp;', t1.name) as name
              FROM tree AS t1
                 LEFT JOIN tree AS t2 ON ( t2.lft < t1.lft AND t2.rgt > t1.rgt)
              GROUP BY t1.id
              ORDER BY t1.lft";
      $resId = mysql_query($sql, $this->dbconn);

      // skip de rootNode
      mysql_data_seek($resId, 1);

      // gooi de nodes in een array
      while($tree[] = mysql_fetch_assoc($resId));

      return $tree;
   }

   enz...
}

// functie om random trees te genereren
function buildRandomTree($nodes, &$pagetree)
{
   $tree = array();
   //$pagetree->reinit(); // gooi celko tree leeg en insert root node

   for ($i = 2; $i <= $nodes+1; $i++)
   {
      $par = rand(1, $i-1);
      $name = 'node' . $i;
      //$pagetree->addLastChild($par, $name); // voeg nieuwe node toe aan de celko tree 
      $tree[$par][] = array('id'=>$i, 'name'=>$name);
   }

   return $tree;
}

$timer = new timer();

// Celko tree
$timer->start();
$test2 = $pagetree->get_tree();
$timer->stop();
$timer->show();
// Resultaat: 0.009666 seconden

// standaard tree
$timer->start();
$test2 = array();
$testTree = buildRandomTree(1250, &$pagetree);
makeCatRecArray(1, &$testTree, &$test2);
$timer->stop();
$timer->show();
// Resultaat:  0.025301 seconden
?>

[Verwijderd]

Die pass-by-reference versie is inderdaad sneller, maar daar moet wel bijgezegd worden dat het niet netjes geprogrammeerd is. Maar dan is de vraag, is dat belangrijker dan snelheid?