Auteur Sujet: Le Meilleur Moyen De Mémoriser Une Arborescence  (Lu 2139 fois)

0 Membres et 1 Invité sur ce sujet

Hors ligne Yannick

  • Habitué
  • **
  • Messages: 204
Le Meilleur Moyen De Mémoriser Une Arborescence
« le: 13 novembre 2003 à 14:41:00 »
Bonjour,

Je recherche le meilleur moyen (performance/taille occupée) pour mémoriser dans une table une structure arborescente.

Voilà un exemple :

[Groupe 1]
  [Groupe 1-1]
    donnée 1
    donnée 2
    ...
  [Groupe 1-2]
  [Groupe 1-3]
[Groupe 2]
  [Groupe 2-1]
    [Groupe 2-1-1]
    [Groupe 2-1-2]
...

La fenêtre de gauche de l'explorateur de fichiers de Windows, par exemple, répond à une structure similaire (où les Groupes ci-dessus sont en fait des répertoires et les Données des fichiers.

J'ai besoin, donc, d'exploiter ce type d'arborescence en PHP. J'ai nécessité également à mémoriser une arborescence en un unique champ MySQL. L'arborescence ne doit pas être limitée.

Voici ci-dessous les différentes réflexions que j'ai eues :

1) XML

Des données hiérarchisées comme ci-dessus font tout de suite penser à XML. Je pourrais donc mémoriser cette arborscence dans un format XML, et l'enregistrer dans un champ de ma table MySQL.

Inconvénient : la multitude des balises XML vont prendre presque autant de place (en terme de quantité d'informations, donc d'octets) que les données elles-mêmes. Et puis, quelles sont les performances de PHP nécessaires pour parser de telles données ?

2) ARRAY()

On peut imaginer écrire les données dans des tableaux de tableaux. Cette fois, plus de place perdu, et peut-être un gain de temps pour PHP lors de l'estraction des données.

Ainsi, l'arborescence ci-dessus pourrait s'écrire ainsi :

array('Groupe 1' => array( 'Groupe 1-1' => array('données 1', 'données 2'), 'Groupe 1-2' => array(), 'Groupe 1-3' => array() ), 'Groupe 2' => array( 'Groupe 2-1' => array(  'Groupe 2-1-1' => array(),  'Groupe 2-1-2' => array() )

C'est nettement moins lisible, mais une fois l'algorithme PHP créé, cela se gère tout seul.

Ma question : quelle est votre avis sur la chose ? Laquelle des deux solutions utiliser ? Existe t-il une autre solution ?

Merci par avance.
 

Hors ligne Dash

  • Débutant
  • *
  • Messages: 61
    • http://www.phpnet.org/forum/index.php?showuser=454
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #1 le: 13 novembre 2003 à 14:56:57 »
Si tu veux quelque chose d'exportable, et donc privilegier l'interoperabilite du code, tu peux utiliser un fichier XML.

Si tu veux quelque chose uniquement pour un usage interne, et donc privilegier la vitesse du code, utilise plutot un tableau en php. Pour aller encore plus vite que mySQL? tu peux utiliser un fichier cache, genere periodiquement, a chaque fois que tu dois faire un nouveau scan du repertoire.
<?php
$arborescence= array('Groupe 1' => array( 'Groupe 1-1' => ....
?>

il ne restera plusqu'a faire un simple include de ce fichier pour recupere l'arborescence. Aucun parsing, aucun pre/post traitement a faire lors de la lecture. C'est la methode que j'utilise personnellement.  

Hors ligne Yannick

  • Habitué
  • **
  • Messages: 204
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #2 le: 13 novembre 2003 à 15:09:10 »
Je suis obligé d'utiliser MySQL, car il peut (rêvons un peu) y avoir 10 arborescences à mémoriser par utilisateur, avec 10 000 utilisateurs !  ;)

Dans tout les cas, je dois pouvoir afficher les données d'une manière lisible et visuelle. Donc même lors de l'emploi d'un tableau, je dois le parser pour générer un affichage compréhensible à l'écran.

Le but est donc d'enregistrer l'arborescence dans MySQL et la resortir et la parser le plus rapidement possible, en préservant autant que possible les ressources.

J'aimerai idéalement enregistrer les données au format xml directement dans le champ de ma table. Mais, comme je l'ai dis plus haut, je trouve que cela génère un gâchis en place occupée.

Tu recommandes donc le tableau. Au fait, existe t-il une limite en taille d'un tableau ? Sur certains langages (comme le Lingo de Director jusqu'à la version 6), une variable ne pouvait faire plus de 32Ko.  

Hors ligne Patanock

  • Connaisseur
  • ***
  • Messages: 277
    • http://www.potoland.com
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #3 le: 13 novembre 2003 à 16:05:37 »
Tu peux stocker ca dans une table ayant pour champs ID, ID_PERE, ID_UTILISATEUR (si c'est pour gérer des menus perso) et NOM par exemple.

Lorsque tu veux reconstruire ton arborescence, plusieurs solutions :

- une requete de base qui te sort tous les niveaux 1 (ID_PERE null) et ensuite, une methode RECURSIVE qui pour chaque Pere, va te chercher les fils en base...
Inconvénients : Beaucoup de requêtes
Avantages : Facile à mettre en place, récursivité donc facilité de modification et code propre

- une seule requête qui te sort toutes les feuilles de ton arbre ordonné par exemple par ID_PERE et NOM, puis un traitement Php qui te construit un tableau de fils par ID_PERE, que tu peux par exemple rattaché à son pere par une Hashtable qui a comme clé l'ID_PERE
Au final, de nouveau une méthode récursive, mais sans requête cette fois, qui parcours un tableau de pere et qui pour chaque élément va prendre dans la hashtable ses fils, en commencant avec le tableau de niveau 1.
Inconvénients : bah euh yen a pas vraiment, j'pense pas que le traitement php soit bien long. Juste un peu plus dur à coder.
Avantages : 1 seule requete, récursivité etc...

Voilà :)

Si vous cherchez une communauté et un tchat sympa, venez visiter le site qui déchire !!


Hors ligne Anubis

  • Habitué
  • **
  • Messages: 161
    • http://
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #4 le: 13 novembre 2003 à 19:11:45 »
Tu dis que XML est trop lourd, c'est possible, mais seulement si tes données sont vraiment très petites. Pour ce qui est de la vitesse, DOM XML ets très rapide, et te permettra d'avoir tout de suite un arbre.

Tu dis que les tableaux sont plus rapides, ça je n'en suis pas sûr du tout, surtout que l'arbre XML est créé à base de tableaux (en PHP4, objet et tableau sont pareils) et plus simple à parser. Enfin les tableaux, c'est vraiment pas la solution, c'est la plus simple à première vue, mais pas la meilleure.

Je te conseille de carrément refaire une strcuture de données à toi.
Tu fais un tableau double entrée, contenant d'un côté le contenu, et de l'autre l'indice du parent de ce contenu.

Ça se dump très facilement (puisque c'est une structure de donnée constante, tu peux même dumper dans un fichier binaire) et tu auras de très bonnes performances (cette structure est utilisée par pas mal de systèmes de fichiers).

Par contre, il faudra adapter ton traitement à cette nouvelle forme de données, mais ça ne devrait pas poser trop de problèmes.
virtual void Life[span style=\'color:purple\']() = 0;[/span]

Genezys, humeurs d'un codeur
ChuWiki, le wiki simple et facile
Le lynx et autre félins (j'ai seulement fait les designs ^^)

Hors ligne Yannick

  • Habitué
  • **
  • Messages: 204
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #5 le: 14 novembre 2003 à 08:33:48 »
Ma structure arborescente va continuellement se modifier (exactement, pour reprendre l'analogie, comme des répertoires et fichiers dans l'explorateur de Windows : tu en créé de nouveaux, en supprime, en déplace... continuellement).

Les infos à stockées sont relativement courtes, effectivement.

Exemple si xml :

<principal>
  <groupe_1>
    test
  </groupe_1>
  <groupe_2>
     <sous_groupe 1>
        essai
     </sous_groupe 1>
  </groupe_2>
</principal>

On voit bien ici que les balises prennent pas mal de place. 'test' et 'essai' sont très courts dans mon exemple, mais réellement, cela devrait être des chaînes de 50 caractères maxi.

Mais c'est vrai que, à moins d'avoir des milliers et des milliers d'enregistrements, peut-être n'est-ce pas si gênant que ca ?

Peux-tu m'en dire un peu plus sur ta solution énoncée en fin de message ?

Merci.
 

Hors ligne Yannick

  • Habitué
  • **
  • Messages: 204
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #6 le: 14 novembre 2003 à 11:24:28 »
Voilà que je trouvais ta solution, Anubis, séduisante avec DOM XML, mais malheur, je m'apperçois, dans la doc PHP, que les fonctions sont expérimentales, et peuvent changer à tout moment...

Je ne peux envisager d'utiliser cette approche, car il me faut une solution fiable et s'appuyant sur des bases solides de PHP.

Hors ligne Patanock

  • Connaisseur
  • ***
  • Messages: 277
    • http://www.potoland.com
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #7 le: 14 novembre 2003 à 23:55:01 »
Bah utilise la recursivité, franchement ma 2eme solution je l'applique en java/jsp pour des sites professionnels et ca roule nikel.

Si vous cherchez une communauté et un tchat sympa, venez visiter le site qui déchire !!


Hors ligne Anubis

  • Habitué
  • **
  • Messages: 161
    • http://
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #8 le: 15 novembre 2003 à 18:19:38 »
Je te parlais d'un stockage en binaire d'une structure de données contantes, je m'explique...

Tu as un tableau contenant la structure de ton arbre, en enregistrant le parent :

[0 => null] [1 => 0] [2 => 0] [3 => 0] [4 => 1] [5 =>1] [6 => 4] [7 => 6]
À partir ce ça, tu peux refaire l'arborescence :
0
|- 1
|  |- 4
|  |  |- 6
|  |     |- 7
|  |
|  |- 5
|
|- 2
|- 3

Ensuite, tu as un tableau contenant les données (tu peux fusionner les deux, si tes données ne sont pas trop grosses) :

[0 => plop] [1 => onk] [2 => trez]  [3 => grumpf] [4 => windows] [5 => linux] [6 => php] [7 => lib]
Ce qui te permet de retrouver l'arborescence complète :
plop
|- onk
|  |- windows
|  |  |- php
|  |     |- lib
|  |
|  |- linux
|
|- trez
|- grumpf

Bon après, ces deux tableaux sont des tableaux facilement enregistrables en PHP, et tu gagneras forcément en taille si tu te fais ton propre format (sans passer par les sérialisations PHP).

Si tu veux connaitre l'analogie avec les systèmes de fichiers, le premier tableau s'appelle la table d'allocation des fichiers (ou table d'inodes sous Linux), et le second tableau s'appelle la table des blocs de données, et contient les données de ton disque dur :-).
« Modifié: 15 novembre 2003 à 18:19:54 par Anubis »
virtual void Life[span style=\'color:purple\']() = 0;[/span]

Genezys, humeurs d'un codeur
ChuWiki, le wiki simple et facile
Le lynx et autre félins (j'ai seulement fait les designs ^^)

Hors ligne york

  • Débutant
  • *
  • Messages: 20
Le Meilleur Moyen De Mémoriser Une Arborescence
« Réponse #9 le: 15 novembre 2003 à 18:39:35 »
Merci bien.

Merci à tous, vous avez apporté de l'eau à mon moulin.

A moi d'jouer !