On connaît la fonction count() en PHP, qui permet de connaître le nombre d’éléments d’un tableau. Mais si je veux savoir à quelle profondeur je risque d’être conduit en parcourant récursivement mon tableau, comment faire ?
J’en profite pour vous faire découvrir le deuxième argument de la fonction count(), qui mis à la valeur COUNT_RECURSIVE prendra en compte les éléments internes du tableau.
Je reprends l’exemple de la doc PHP pour éclairer mon propos.
$food = array(
'fruits' => array(
'orange', 'banana', 'apple' => array('verte', 'jaune', 'rouge')
),
'veggie' => array(
'carrot', 'collard', 'pea'
)
);
// count récursif
echo count($food, COUNT_RECURSIVE); // affiche 11 et non 8
Parmi les fonctions de tableau, il n’en existe aucune qui permet de juste obtenir la profondeur d’un tableau.
La raison, à mon avis, est qu’un tableau peut-être multi-dimensionnel de manière inégale, comme dans mon exemple ci-dessus.
Dans mes flux RSS, des réponses à vos questions- How Do GOOD Developers Ask Questions? | mikebernat.com Web-Development, Design, Usability (author unknown)
- Simple Techniques to Lock Down your Website - Nettuts+ (author unknown)
- Dangereux métier que formateur ! - 60 questions, le blog (author unknown)
- Formateur et enseignant, un même métier ? (author unknown)
- Chicks Rule! Gender balance on social networking sites via... (author unknown)
- Traduire complètement l’admin generator de Symfony « blogafab.com (author unknown)
- Running numerous symfony versions using MAMP on Mac OS X | 2cool4school ! (author unknown)
- Hey look! Symfony 1.3 alpha1! Kris Wallsmith
- Formaldehyde: PHP debug info for the client side Dion Almaer
- FireSymfony-- Symfony Debugging with FireBug noreply@blogger.com (Soon Hui)
@Formation
17 mai 2008 at 15:40
La manière la plus efficace pour connaitre la profondeur de ce genre de structure (qui n’est finalement qu’un arbre avec une arité non fixé) est de parcourir l’ensemble des noeuds à l’aide d’un parcours eulériens ou bien d’utiliser une petite méthode récursive. Ce genre de parcours passe une et une seule fois par tous les noeuds.
Donc, pour conclure, il n’est pas possible de connaitre la profondeur d’un arbre sans le parcourir. Notons toutefois que la complexité d’une telle recherche est O(n) où n est le nombre de noeuds ce qui reste acceptable.
Pour plus d’info à ce sujet, on peut toujours consulter “Data Structure and Algorithms in Java” aux pages 273-276.
2 juillet 2008 at 15:12
Le résultat de :
echo count($food, COUNT_RECURSIVE);
affiche 11 et non 8 !
Antoine, je suis intéressé par le parcours eulériens.
Peux-tu m’en dire plus ?
Qu’est-ce que c’est ?
Comment l’appliquer ?
Un algo peut être ?
D’avance merci =)
2 juillet 2008 at 15:44
Très bonne remarque, cela affiche 11 (honte à moi, j’avais oublié de compter les index)
19 mars 2009 at 8:55
Comme l’a dit Antoine, il sera nécessaire de parcourir le tableau. Mais oui, il est possible de connaitre la profondeur d’un tableau.
L’idée vient d’une utilisation récursive de la fonction is_array(). Ainsi pour chaque entrée, on teste la contenance et si oui, on rentre dedans et check encore son propre contenu puis on remonte, et check les autres index, etc.
Attention, en terme de consommation CPU, il faut peser la nécessité du parcours d’un tableau (plus il sera grand, plus cela consommera)