[PHP 5.3] Transformer algorithme récursif en itératif

[Bakura]

Bonjour,

Désolé si ce topic a plutôt sa place dans le forum Algorithmique, mais étant donné qu'il utilise certaines notations de Zend et du PHP j'ai préféré le mettre ici, surtout que ce n'est sûrement pas bien difficile, mais je bloque.

Voilà, je dispose d'un forum avec de très nombreuses catégories, sous catégories, sous-sous catégories et ainsi de suite.

J'ai réussi à écrire l'algorithme pour établir ma hiérarchie à base de tableaux, toutefois je n'ai réussi qu'à faire une fonction récursive (plus simple à visualiser), j'aimerais savoir si vous pourriez m'aider (si c'est possible évidemment) à la transformer en fonction itérative, ce qui est sûrement plus performant (j'ai potentiellement énormément de catégories). J'ai pensé aux closures mais je ne les maîtrise pas.

Voici la fonction :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
protected function _createCategoryHierarchy($parentId = null)
{
    $hierarchy = array();
 
    $categoryPaginator = $this->categoryMapper->getByParentId($parentId);
    $categories = $categoryPaginator->getItems(0, -1);
 
    if (!empty($categories))
    {
        foreach($categories as $category)
	    $hierarchy[] = array('category' => $category, 'subCategories' => $this->_createCategoryHierarchy($category->id));
    }
 
    return $hierarchy;
}

Le getItems se contente de renvoyer tous les éléments, vous pouvez ignorer le paginateur .

Par exemple, avec une catégorie mère et deux catégories filles, j'obtiens ceci :

Code :

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
array(1) {
  [0] => array(2) {
    ["category"] => object(Application_Model_ForumCategory)#79 (1) {
      ["_properties":protected] => array(4) {
        ["id"] => string(1) "5"
        ["parentId"] => NULL
        ["name"] => string(5) "Cat 1"
        ["description"] => string(7) "Cattt 1"
      }
    }
    ["subCategories"] => array(2) {
      [0] => array(2) {
        ["category"] => object(Application_Model_ForumCategory)#82 (1) {
          ["_properties":protected] => array(4) {
            ["id"] => string(1) "6"
            ["parentId"] => string(1) "5"
            ["name"] => string(5) "Cat 2"
            ["description"] => string(7) "Cattt 2"
          }
        }
        ["subCategories"] => array(0) {
        }
      }
      [1] => array(2) {
        ["category"] => object(Application_Model_ForumCategory)#83 (1) {
          ["_properties":protected] => array(4) {
            ["id"] => string(1) "7"
            ["parentId"] => string(1) "5"
            ["name"] => string(5) "Cat 3"
            ["description"] => string(7) "Cattt 3"
          }
        }
        ["subCategories"] => array(0) {
        }
      }
    }
  }
}

Merci de votre aide .

[nosferapti]

Envoyé par Bakura

j'ai potentiellement énormément de catégories

est ce que tu peux essayer ton code en conditions réelles pour mesurer les performances ?
je demande ça parce que ce mois, j'ai fait un code qui avait l'air de de consommer beaucoup de ressources mais après avoir testé avec les données finales, le traitement que j'aurais pu optimiser mettait moins d'un vingtième du temps de génération de la page. donc je suis passé à la suite et j'ai mis cette optimisation dans la liste "à faire plus tard"

en faisant des tests tu pourras voir si c'est la construction qui prend le plus de temps ou alors les requêtes dans la base de données par exemple ?
toujours dans la même application, j'ai voulu optimiser un bout de code pour sélectionner seulement les éléments de l'arborescence et au final, j'ai gardé le bout de code qui cherche tout le contenu de la table même si la moitié n'est pas utilisé

d'ailleurs ça me fait penser à une astuce que j'utilise dans toutes mes arborescences c'est ça :
http://sqlpro.developpez.com/cours/arborescence/

[Bakura]

Merci pour ce lien très intéressant ...

D'autre part en relisant mon code, je me suis aperçu que, puisque au final je récupère toutes les catégories, je peux faire un fetchAll (donc une seule requete), plutôt que énormément de requêtes SQL comme actuellement.

Merci