[php] recursieve functie werkend, efficient?

[Verwijderd]

PHP:

function showCustomers( $searchparent, $level ){
    global $eas;
    $thisparent = "";
    
    $query_customers = "select * from contact where ouder_ID= ". $searchparent ." order by naam";
    $eas->selectQuery( $query_customers );
    $result_customers = $eas->result;
    if( $eas->numRows() != 0 ){
        
        //run through results
        for( $i=0 ; $i < count($result_customers) ; $i++ ){
            $output = "";
            
            //there are children found, descending one level
            if( $thisparent != $searchparent ){
                //$searchparent contains the ouder_ID we're searching for this call
                //found a valid child, so descend one level
                //$thisparent = $searchparent descend only one time this for loop
                $thisparent = $searchparent;
                $level++;
            }
            
            //align it a little
            for( $j=0 ; $j < $level ; $j++ ){
                $output .= "&nbsp;&nbsp;&nbsp;&nbsp;";
            }
            
            $output .= $result_customers[$i]["naam"] ."<br>";
            print( $output );
            
            //recursion
            showCustomers( $result_customers[$i]["ID"], $level );   
        }
    }
}

Ik heb een recursieve functie geschreven om een "boom" achtige structuur te tekenen. Hij werkt prima zo, maar ik vraag me af of wat ik bedacht heb ook de logischte & efficientste manier is om dit probleem te tackelen!

dus... wat vinden jullie van deze opzet?

[ Voor 40% gewijzigd door Verwijderd op 06-11-2003 10:17 ]

[Verwijderd]

Het eerste wat me opvalt is dat je bij elke aanroep van je functie een SELECT-query uitvoert. Ik weet niet hoe groot die boom is, maar als je een flinke boom hebt, kan dat wellicht een onnodig grote belasting voor je databaseserver worden...

[Verwijderd]

sir5 -> het zijn een record of 50 ongeveer, dus dat valt wel mee.
maar wel een goed punt! ik had hier verder eigenlijk niet bij stilgestaan!

[Verwijderd]

Verwijderd schreef op 06 november 2003 @ 10:04:

PHP:

function showCustomers( $searchparent, $level ){
    ...
        for( $i=0 ; $i < count($result_customers) ; $i++ ){
          ...
}

Puur om performantie redenen gezien, is die count daar niet erg slim. Aangezien je resultset van je MySQL query niet verandert ($result_customers) zal dus ook je count niet veranderen, en kan je die best in een var zetten voor de loop. Spaart je weer x functie aanroepen uit.

En jah een query per keer is wat veel, als 10 mensen die pagina opvragen zijn dat al gauw 500 queries alleen voor die functie

[ACM]

Ik zou me pas bezighouden met optimalisaties als blijkt dat je het nodig hebt

Als het een page is die minder dan 1000x per dag aangeroepen wordt, dan zou ik me er echt niet druk om maken.
't Enige waar ik me dan om druk zou maken is of ie correct en prettig werkt

Btw, dat forloopje om je spaties toe te voegen -> str_repeat is wat duidelijker/handiger.

Ook snap ik die if met je $level++ niet helemaal, je verhoogt bij elk gevonden child je level (wat je imho niet wil) en wijst die nieuwe child aan de $thisparent toe, terwijl je daar vervolgens weinig mee doet.

Volgens mij kan dat wel wat nuttiger, zoiets bijv:

PHP:

<?
function showCustomers( $searchparent, $level=0, $naam="Start" ){
    global $eas;
    $thisparent = "";

    $output = str_repeat("    ", $level);
    $output .= $naam ."<br>";
    print( $output );
    
    $query_customers = "select * from contact where ouder_ID= ". $searchparent ." order by naam";
    $eas->selectQuery( $query_customers );
    $result_customers = $eas->result;
    if( $eas->numRows() != 0 ){
        
        //run through results
        for( $i=0 ; $i < count($result_customers) ; $i++ ){
             //recursion
            showCustomers( $result_customers[$i]["ID"], $level +1, $result_customers[$i]["naam"] );
        }
    }
}
?> 

[Janoz]

In dit geval worden er 51 queries uitgevoerd bij 50 namen. IMHO erg inefficient. Het zou sowieso al een flink stuk schelen waneer je bij je query ook het aantal kinderen opvroeg (mbv een join). Op die manier kun je voordat je de querie loslaat kijken of je de recursie in moet. Zeker als je veel items in weinig 'groepen' hebt staan wordt het aantal queries enorm verminderd.

Er zijn nog veel ingewikkelere optimalisaties te bedenken (In principe is het ook mogenlijk in 1 query), maar een recursieve structuur is erg lastig te implementeren in een relationele database.

[crisp]

Mijn ervaring is toch dat een iteratieve oplossing vaak vele malen sneller is, minder geheugen gebruikt, en het risico op callstack-overflows uitsluit (iets dat bij PHP - zeker onder windows - al vrij snel gebeurd).

[Robtimus]

Verwijderd schreef op 06 november 2003 @ 11:51:
Puur om performantie redenen gezien, is die count daar niet erg slim. Aangezien je resultset van je MySQL query niet verandert ($result_customers) zal dus ook je count niet veranderen, en kan je die best in een var zetten voor de loop. Spaart je weer x functie aanroepen uit.

Dit klopt absoluut.

ECHTER, ik heb eens gekeken in Java wat het verschil in tijd is.
Over 10.000 iteraties is het telkens aanroepen van de grote van een List vrijwel even snel als het slechts 1x uitroepen en dan de variabele gebruiken in de bound. Sterker nog (en dat vind ik wel vreemd), bij veel van de experimenten komt het elke keer aanroepen zelfs iets beter uit de bus (1031ms tegenover 1042ms en 1212ms tegenover 1242ms de laatste 2 keren). Niet altijd echter.

Ik weet niet hoe dit in PHP is, maar ik vond dat ik het even moest melden.

[Verwijderd]

Ook snap ik die if met je $level++ niet helemaal, je verhoogt bij elk gevonden child je level (wat je imho niet wil) en wijst die nieuwe child aan de $thisparent toe, terwijl je daar vervolgens weinig mee doet.

PHP:

//there are children found, descending one level 
            if( $thisparent != $searchparent ){ 
                //$searchparent contains the ouder_ID we're searching for this call 
                //found a valid child, so descend one level 
                //$thisparent = $searchparent descend only one time this for loop 
                $thisparent = $searchparent; 
                $level++; 
            }

nu verhoogt hij juist niet bij elk gevonden child de level
als er bij de parent meerdere childs zijn, dus die op dezelfde level horen, voert hij maar 1x de $level++ uit.

Puur om performantie redenen gezien, is die count daar niet erg slim. Aangezien je resultset van je MySQL query niet verandert ($result_customers) zal dus ook je count niet veranderen, en kan je die best in een var zetten voor de loop. Spaart je weer x functie aanroepen uit.

aangepast

PHP:

$output = str_repeat("    ", $level);

thnx ACM die staat er ook in

[ Voor 21% gewijzigd door Verwijderd op 06-11-2003 12:40 ]

[FlowinG]

Ik ben hier zelf ook mee bezig en het heeft me aardig wat tijd gekost om iets uit te vinden. In tegenstelling tot waar jij mee begonnen bent, ben ik er vanaf het begin al mee bezig geweest dat ik maximaal 1 of 2 queries wou uitvoeren. Ik zit nu een systeem te bedenken dat ik alles in een array zet en die array gewoon doorloop, en alles dan op volgorde zet.

Als ik hiermee verder gekomen ben, laat ik het wel horen.

[Verwijderd]

ben ik er vanaf het begin al mee bezig geweest dat ik maximaal 1 of 2 queries wou uitvoeren.

ja ik wist al dat het weinig gebruikt gaat worden en laat staan door meer dan 2 personen tegelijkertijd, dus ik hoef me daar geen zorgen over te maken.
maar ik ga het denk ik nog wel aanpassen, just 4 the fun of it!

ik dacht aan 1 grote array die doorlopen (recursief) en de gevonden items overcopieren naar een 2e array waardoor alles op zijn plek terecht komt....

ik zal het hier ook posten als het er van gekomen is

[FlowinG]

Verwijderd schreef op 06 november 2003 @ 14:11:
[...]
ik dacht aan 1 grote array die doorlopen (recursief) en de gevonden items overcopieren naar een 2e array waardoor alles op zijn plek terecht komt....

ik zal het hier ook posten als het er van gekomen is

Ja ik heb hier al paar mijn gedachte over laten gaan. Ik heb dus een tabel met categorieen. Ik wil nu simpel een select box (multiple) maken waarmee je kan aangeven in welke categorie je werkt. Ook is het makelijk om zo een menu structuur uit te printen in meerdere submenu's.

Er zal vast wel ergens een voorbeeld van zijn maar ook voor mij is het de fun

[Soultaker]

Verwijderd schreef op 06 november 2003 @ 11:51:
Puur om performantie redenen gezien, is die count daar niet erg slim. Aangezien je resultset van je MySQL query niet verandert ($result_customers) zal dus ook je count niet veranderen, en kan je die best in een var zetten voor de loop. Spaart je weer x functie aanroepen uit.

Dat is niet alleen nuttig voor de performance, maar ook conceptueel is het beter om hier een foreach-statement te gebruiken. Je wilt namelijk helemaal geen variabele $i gebruiken; je doet er namelijk niets mee (behalve je array indexeren). Met een foreach-statement kunt je veel nauwkeuriger uitdrukken wat je precies wil: voor elk element van je array de lus een keer uitvoeren. Als je voor deze conceptueel superieure methode kiest, krijg je de eventuele verbeterde performance kado!

IceManX schreef op 06 november 2003 @ 12:27:
ECHTER, ik heb eens gekeken in Java wat het verschil in tijd is. Over 10.000 iteraties is het telkens aanroepen van de grote van een List vrijwel even snel als het slechts 1x uitroepen en dan de variabele gebruiken in de bound. Sterker nog (en dat vind ik wel vreemd), bij veel van de experimenten komt het elke keer aanroepen zelfs iets beter uit de bus (1031ms tegenover 1042ms en 1212ms tegenover 1242ms de laatste 2 keren). Niet altijd echter.

Ik denk dat het ook in PHP niets kost, aangezien in de meeste interpreted talen de grootte van een lijststructuur gewoon opgeslagen wordt in het geheugen. In andere talen, zoals functionele programmeertalen en traditionele talen waar gebruik wordt gemaakt van datastructuren als linked lists of boomstructuren, wordt bij het uitvoeren van een count functie ook echt geteld en dat is kostbaar. In PHP en JavaScript zal (in ieder geval in een gangbare implementatie) gewoon de grootte al bekend zijn. Het opvragen van de grootte is dan ongeveer net zo ingewikkeld als het opvragen van de inhoud van een aparte variabele.

[ Voor 12% gewijzigd door Soultaker op 06-11-2003 16:06 ]

[Soultaker]

Verwijderd schreef op 06 november 2003 @ 14:11:
ik dacht aan 1 grote array die doorlopen (recursief) en de gevonden items overcopieren naar een 2e array waardoor alles op zijn plek terecht komt....

Je kunt alle resultaten wel direct op de juiste plaats invoegen, maar je hebt altijd het probleem dat je ofwel meerdere queries moet doen, ofwel een tijdelijke array moet opbouwen (wat voor <1000 nodes in je boom geen probleem zou moeten zijn). Als je beide problemen wilt oplossen (dus een SQL query wilt maken die alle resultaten in de goede volgorde oplevert) dan moet je een andere representatie van de boomstructuur in je database gebruiken. Als er belasting voor is kan ik daar wel over uitweiden maar voor dit specifieke probleem lijkt het me overbodig.

[djluc]

Bedoel je dit toevallig Soultaker?: http://www.webgoeroe.net/item/277

Netjes uit je favorieten een site kopiëren, bestaat de site niet meer

[ Voor 37% gewijzigd door djluc op 06-11-2003 16:19 ]

[Verwijderd]

PHP:

$customerArray = array();
$sortedCustomerArray = array();
function showCustomers(){
    global $eas, $customerArray;
    $query_customers = "select * from contact order by naam";
    $eas->selectQuery( $query_customers );
    if( $eas->numRows() > 0 ){
        $customerArray = $eas->result;
        sortarray( 0, 0 );
    }
}

function sortarray( $search, $level ){
    global $eas, $customerArray, $sortedCustomerArray;
    $thisparent="";
    
    $index = count( $customerArray );
    
    for( $i=0 ; $i < $index ; $i++ ){
        if( $customerArray[$i]["ouder_ID"] == $search ){
            
            if( $thisparent != $search ){
                $level++;
                $thisparent = $search;
            }
            
            $sortedIndex = sizeof( $sortedCustomerArray );
            $sortedCustomerArray[$sortedIndex]["id"] = $customerArray[$i]["ID"];
            $sortedCustomerArray[$sortedIndex]["naam"] = $customerArray[$i]["naam"];
            $sortedCustomerArray[$sortedIndex]["ouder_ID"] = $customerArray[$i]["ouder_ID"];    
            $sortedCustomerArray[$sortedIndex]["level"] = $level;
            
            sortarray( $customerArray[$i]["ID"], $level );
        }   
    }
}

aanroep:

PHP:

showCustomers(); 
$index = array_keys( $sortedCustomerArray );
foreach( $index as $i ){
    $output  = "";
    $output .= str_repeat("    ", $sortedCustomerArray[$i]["level"] );
    $output .= $sortedCustomerArray[$i]["naam"] ."<br>";    
    
    print( $output );
}

Dit is database technisch een stuk efficienter lijkt me
Is het mogelijk om de "al gelezen" items uit de array te rippen? scheelt ook weer in de loop dan

[Genoil]

crisp schreef op 06 november 2003 @ 12:26:
Mijn ervaring is toch dat een iteratieve oplossing vaak vele malen sneller is, minder geheugen gebruikt, en het risico op callstack-overflows uitsluit (iets dat bij PHP - zeker onder windows - al vrij snel gebeurd).

is dat hetzelfde als "Modified Preorder Tree Traversal"?

http://www.sitepoint.com/article/1105/2

[FlowinG]

Verwijderd schreef op 06 november 2003 @ 16:19:

(..)
Is het mogelijk om de "al gelezen" items uit de array te rippen? scheelt ook weer in de loop dan

je bedoelt om ze te deleten?
ik gebruik vaak unset($array[$key])

[Soultaker]

Genoil schreef op 06 november 2003 @ 16:23:
is dat hetzelfde als "Modified Preorder Tree Traversal"?
http://www.sitepoint.com/article/1105/2

Nee, dat is een andere manier om je gegevens op te slaan (waardoor je ze ook anders kunt benaderen), waar ik het al over had en die djluc ook al probeer te aan te halen (als WebGoeroe nog zou bestaan ).

Bij de indeling die IceFlame gebruikt moet je, zoals gezegd, ofwel meerdere queries doen, ofwel tijdelijk geheugen gebruiken. Crisp stelt dat je dat geheugen beter op de heap dan op de stack kunt alloceren, want in het algemeen wel waar is. Als het aantal items beperkt is, maakt het niet zoveel uit (en dan geniet wat mij betreft de meest simpele/duidelijke oplossing de voorkeur).

edit:
Ik vind de voorbeeldcode op de website die je aanhaalt niet zo sterk; die zou 'niet-recursief' zijn, maar dat is ook alleen maar omdat ze de stack van PHP hebben vervangen door een eigen stack in heap-space.

[ Voor 14% gewijzigd door Soultaker op 06-11-2003 16:32 ]

[Verwijderd]

heap dan op de stack kunt alloceren

HA betrap ik jou daar even op dure woorden
iemand ondertiteling?

[Soultaker]

Verwijderd schreef op 06 november 2003 @ 16:33:
HA betrap ik jou daar even op dure woorden
iemand ondertiteling?

Hmm, het is een beetje een basisprincipe. Ik kan het wel even kort toelichten.

Een stack is een stuk geheugen dat je alleen aan de achterkant kunt uitbreiden en inkrimpen. Meestal werk je alleen op een deel ervan aan het eind. Je kunt het letterlijk als 'stapel' (=='stack') zien: als je een stapel boeken hebt, dan kun je aleen boeken aan de bovenkant erop leggen en eraf pakken. Een heap wordt daarintegen in principe gebruikt om min-of-meer willekeurig stukken geheugen uit te pakken. Je kunt het zien als een boekenplank: je kunt boeken op elke willekeurige plek invoegen en wegpakken. Vrijwel elke moderne applicatie heeft beschikking over geheugen in deze twee vormen.

In PHP hoef je niet zelf je geheugen te alloceren dus je merkt er weinig van, maar op het moment dat je een statements als "$a = array(1, 2, 3)" uitvoert, dan wordt er een stuk geheugen op de heap gereserveerd (er wordt dus ruimte op de boekenplank gezocht die groot genoeg is) en daar wordt de array met z'n inhoud in opgeslagen.

PHP kent geen eigen stack-allocatie voor variabelen, dus daar zal ik niet op ingaan, maar gebruikt wel de stack voor recursieve function calls. Voor elk 'nivo' in je recursie alloceer je een stukje extra geheugen (een stack frame). (In de analogie: elke keer dat je een functie aanroept komt er boek op de stapel; elke keer dat je een return-statement uitvoert wordt er weer een boek vanaf gehaald). Nu hebben allerlei interpreted talen zoals (blijkbaar) ook PHP de rare eigenschap dat de grootte van de stack (de maximale hoogte van de stapel) vast staat terwijl de grootte van de heap uit te breiden is (als het geheugen op is, vraagt PHP aan het besturingssysteem om meer geheugen; een extra boekenplank). In het algemeen is je stack iets van een megabyte groot, wat dus doorgaans veel minder is dan de heap, die vaak zonder problemen honderden megabytes tot aan (in theorie) een paar gigabyte groot kan worden. Als je veel gegevens kwijt moet, zet je ze dus liever in de boekenkast dan bovenop de stapel boeken die al snel het plafond bereikt.

Nu vind ik het in PHP eigenlijk een beetje vreemd dat je je daar druk om moet maken, want ik zou absoluut niet weten waarom je de stack niet dynamisch uit zou kunnen breiden als 'ie vol is. Waarschijnlijk is dit overgenomen uit het gedrag van 'native' applicaties die helemaal nooit checken of de stack misschien wel vol is (want dat is te kostbaar) en waarbij het dus gebruikelijk is om een statische stack te hebben. Een beetje dom om deze beperking over te nemen, want PHP checkt juist wel altijd de beschikbare stack space (sterker nog, de PHP stack wordt zelf op de heap gealloceert!) en er is dus geen reden waarom de stack niet uit te breiden is.

Geen idee of een PHP-programmeur dit sterk systeemprogrammatie-getinte betoog nog een beetje kan volgen, maar het komt er dus op neer dat je met een recursieve functie niet al te 'diep' wilt gaan; enkele tientallen nivo's is geen probleem, maar miljoenen nivo's diep is echt teveel. Verzin dan liever een iteratieve methode (met een while-lus of iets dergelijks dus) waarbij je een array gebruikt als nep-stack.

[ Voor 17% gewijzigd door Soultaker op 06-11-2003 17:02 ]

[Verwijderd]

Geen idee of een PHP-programmeur dit sterk systeemprogrammatie-getinte betoog nog een beetje kan volgen

yep, duidelijk verhaal! ik ben weer helemaal bij
Heb dit allemaal ook gehad op school een paar jaar terug, alleen zakt die kennis langzaam weg

[Orphix]

Naast de hierboven genoemde oplossingen zou je ook in je query bij de SELECT clause enkel de velden kunnen aangeven die je ook daadwerkelijk gebruikt. In dit geval dus naam en ID. Dat dit efficienter en duidelijker is behoeft weinig uitleg denk ik.

[Soultaker]

Orphix schreef op 06 november 2003 @ 22:15:
Naast de hierboven genoemde oplossingen zou je ook in je query bij de SELECT clause enkel de velden kunnen aangeven die je ook daadwerkelijk gebruikt. In dit geval dus naam en ID. Dat dit efficienter en duidelijker is behoeft weinig uitleg denk ik.

Efficiënter alleen als er (significant) meer kolommen in die tabel zitten dan gebruikt worden bij het uitprinten.

[Verwijderd]

Naast de hierboven genoemde oplossingen zou je ook in je query bij de SELECT clause enkel de velden kunnen aangeven die je ook daadwerkelijk gebruikt. In dit geval dus naam en ID.

in de tabel staan 3 velden die alle drie gebruikt worden.
dit zijn ID, naam en de parent.
vandaar de select *

[Verwijderd]

waar ik eigenlijk wel nieuwsgierig naar ben is de daadwerkelijke performance verschillen van de beide codes.

de array functie lijkt mij ook best een wat cpu tijd opeisen, meerdere functies ed?!
het eigenlijk niet zo heel veel kaas van performance optimalisatie, de sites die ik tot nu toe ontwikkeld heb zijn allemaal relatief klein.
Maximaal 10 simultane gebruikers e.d. , maar ik ben eigenlijk wel zeer benieuwd!

[Soultaker]

Maak twee pagina's en gebruik ab om te benchmarken!

[Verwijderd]

kan je ab ook gebruiken op een windows installatie?
(daar ben ik nu op aan het bouwen namelijk en de "live" server heb ik geen rechten op)