je dois travailler sur un système d'arborescence qui décrit un site
contenant des rubriques et des sous-rubriques.
La table contient 3 champs: id, pid et nom
id = identifiant unique de la (sous-)rubrique
pid = identifiant du parent
nom = nom de la (sous-)rubrique.
- Une sous-rubrique peut contenir d'autres sous-rubriques (elle est
alors parent)
- Rien n'est figé, des (sous-)rubriques peuvent être ajoutées ou
retirées.
- je ne peux pas modifier la structure de la table.
Je cherche un moyen intelligent et optimisé pour faire une classe qui
me permette de travailler aisémment sur ces enregistrements, pour
avoir différents accès:
- récupérer le nombre de noeuds enfants d'une rubrique,
- depuis un noeud, retrouver tout le chemin (Niveau 0 -> Rubrique ->
Ss-rubrique -> Noeud),
- ...
Avez vous des idées? J'en ai de mon côté mais qui me semblent
lourdes (appels récursifs de la fonction)...
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Jean-Marc Molina
CrazyCat wrote:
Avez vous des idées? J'en ai de mon côté mais qui me semblent lourdes (appels récursifs de la fonction)...
Je crois qu'on ne peut pas faire plus simple qu'une fonction récursive. Cette solution n'a rien de lourd, bien au contraire. Après certains privilégient l'optimisation et optent pour des tables de hachage et autres techniques barbares :). Je te recommande la récursivité.
Je cherche un moyen intelligent et optimisé pour faire une classe qui me permette de travailler aisémment sur ces enregistrements, pour avoir différents accès: - récupérer le nombre de noeuds enfants d'une rubrique,
Pas besoin de récursivité il suffit de sélectionner les rubriques dont le pid est celui de la rubrique.
- depuis un noeud, retrouver tout le chemin (Niveau 0 -> Rubrique -> Ss-rubrique -> Noeud),
Une fonction récursive avec deux paramètres : - Niveau courant - Identifiants des rubriques retrouvées
La fonction s'arrête quand le Niveau 0 est atteint. La second paramètre contient la liste des identifiants des rubriques, dont le chemin.
CrazyCat wrote:
Avez vous des idées? J'en ai de mon côté mais qui me semblent
lourdes (appels récursifs de la fonction)...
Je crois qu'on ne peut pas faire plus simple qu'une fonction récursive.
Cette solution n'a rien de lourd, bien au contraire. Après certains
privilégient l'optimisation et optent pour des tables de hachage et autres
techniques barbares :). Je te recommande la récursivité.
Je cherche un moyen intelligent et optimisé pour faire une classe qui
me permette de travailler aisémment sur ces enregistrements, pour
avoir différents accès:
- récupérer le nombre de noeuds enfants d'une rubrique,
Pas besoin de récursivité il suffit de sélectionner les rubriques dont le
pid est celui de la rubrique.
- depuis un noeud, retrouver tout le chemin (Niveau 0 -> Rubrique ->
Ss-rubrique -> Noeud),
Une fonction récursive avec deux paramètres :
- Niveau courant
- Identifiants des rubriques retrouvées
La fonction s'arrête quand le Niveau 0 est atteint. La second paramètre
contient la liste des identifiants des rubriques, dont le chemin.
Avez vous des idées? J'en ai de mon côté mais qui me semblent lourdes (appels récursifs de la fonction)...
Je crois qu'on ne peut pas faire plus simple qu'une fonction récursive. Cette solution n'a rien de lourd, bien au contraire. Après certains privilégient l'optimisation et optent pour des tables de hachage et autres techniques barbares :). Je te recommande la récursivité.
Je cherche un moyen intelligent et optimisé pour faire une classe qui me permette de travailler aisémment sur ces enregistrements, pour avoir différents accès: - récupérer le nombre de noeuds enfants d'une rubrique,
Pas besoin de récursivité il suffit de sélectionner les rubriques dont le pid est celui de la rubrique.
- depuis un noeud, retrouver tout le chemin (Niveau 0 -> Rubrique -> Ss-rubrique -> Noeud),
Une fonction récursive avec deux paramètres : - Niveau courant - Identifiants des rubriques retrouvées
La fonction s'arrête quand le Niveau 0 est atteint. La second paramètre contient la liste des identifiants des rubriques, dont le chemin.
CrazyCat
Avez vous des idées? J'en ai de mon côté mais qui me semblent lourdes (appels récursifs de la fonction)... Je crois qu'on ne peut pas faire plus simple qu'une fonction récursive.
Cette solution n'a rien de lourd, bien au contraire. Après certains privilégient l'optimisation et optent pour des tables de hachage et autres techniques barbares :). Je te recommande la récursivité.
Ah? je pensais que ce serait gourmand en ressources :)
- récupérer le nombre de noeuds enfants d'une rubrique, Pas besoin de récursivité il suffit de sélectionner les rubriques dont le
pid est celui de la rubrique.
Si, il faut de la récursivité là aussi, car en fait ce ne sont pas les enfants mais tout ce qui est apparenté à ce noeud (enfants, petits-enfants, ....)
- depuis un noeud, retrouver tout le chemin (Niveau 0 -> Rubrique -> Ss-rubrique -> Noeud), Une fonction récursive avec deux paramètres :
- Niveau courant - Identifiants des rubriques retrouvées La fonction s'arrête quand le Niveau 0 est atteint. La second paramètre contient la liste des identifiants des rubriques, dont le chemin.
Oui, de toutes manières c'est essentiellement pour créer une chaine, donc je remonte mon arbre en faisant une concaténation, arrivé au N0 je dois avoir mon identifiant qui contient la string complète.
Merci de m'avoir confirmé que mon idée de départ n'est pas la pire :)
-- Astuces pour webmasters: http://www.crazycat.info Tchat francophone: http://www.crazy-irc.net
Avez vous des idées? J'en ai de mon côté mais qui me semblent
lourdes (appels récursifs de la fonction)...
Je crois qu'on ne peut pas faire plus simple qu'une fonction récursive.
Cette solution n'a rien de lourd, bien au contraire. Après certains
privilégient l'optimisation et optent pour des tables de hachage et autres
techniques barbares :). Je te recommande la récursivité.
Ah? je pensais que ce serait gourmand en ressources :)
- récupérer le nombre de noeuds enfants d'une rubrique,
Pas besoin de récursivité il suffit de sélectionner les rubriques dont le
pid est celui de la rubrique.
Si, il faut de la récursivité là aussi, car en fait ce ne sont pas les
enfants mais tout ce qui est apparenté à ce noeud (enfants,
petits-enfants, ....)
- depuis un noeud, retrouver tout le chemin (Niveau 0 -> Rubrique ->
Ss-rubrique -> Noeud),
Une fonction récursive avec deux paramètres :
- Niveau courant
- Identifiants des rubriques retrouvées
La fonction s'arrête quand le Niveau 0 est atteint. La second paramètre
contient la liste des identifiants des rubriques, dont le chemin.
Oui, de toutes manières c'est essentiellement pour créer une chaine,
donc je remonte mon arbre en faisant une concaténation, arrivé au N0 je
dois avoir mon identifiant qui contient la string complète.
Merci de m'avoir confirmé que mon idée de départ n'est pas la pire :)
--
Astuces pour webmasters: http://www.crazycat.info
Tchat francophone: http://www.crazy-irc.net
Avez vous des idées? J'en ai de mon côté mais qui me semblent lourdes (appels récursifs de la fonction)... Je crois qu'on ne peut pas faire plus simple qu'une fonction récursive.
Cette solution n'a rien de lourd, bien au contraire. Après certains privilégient l'optimisation et optent pour des tables de hachage et autres techniques barbares :). Je te recommande la récursivité.
Ah? je pensais que ce serait gourmand en ressources :)
- récupérer le nombre de noeuds enfants d'une rubrique, Pas besoin de récursivité il suffit de sélectionner les rubriques dont le
pid est celui de la rubrique.
Si, il faut de la récursivité là aussi, car en fait ce ne sont pas les enfants mais tout ce qui est apparenté à ce noeud (enfants, petits-enfants, ....)
- depuis un noeud, retrouver tout le chemin (Niveau 0 -> Rubrique -> Ss-rubrique -> Noeud), Une fonction récursive avec deux paramètres :
- Niveau courant - Identifiants des rubriques retrouvées La fonction s'arrête quand le Niveau 0 est atteint. La second paramètre contient la liste des identifiants des rubriques, dont le chemin.
Oui, de toutes manières c'est essentiellement pour créer une chaine, donc je remonte mon arbre en faisant une concaténation, arrivé au N0 je dois avoir mon identifiant qui contient la string complète.
Merci de m'avoir confirmé que mon idée de départ n'est pas la pire :)
-- Astuces pour webmasters: http://www.crazycat.info Tchat francophone: http://www.crazy-irc.net
motton75
Si ton tableau est stocké dans une base de données, je te déconseille vivement la procédure récursive : récupérer la hiérarchie des parents d'un enregistrement donné (pour créer la chaine "vous etes ici : groupes > fr > comp > lang > php" par exemple) est hyper couteux puisque tu vas avoir 5 requetes a envoyer a la base.
Il existe une autre façon de stocker un répertoire pour n'avoir qu'une seule requete a faire quel que soit le type de demande (avoir toute la hiérarchie sous un noeud donné, avoir tous les ancetres d'un noeud donné, etc). En contrepartie il faut faire trois requêtes pour une insertion ou une suppression, mais en général, on le fait beaucoup moins souvent.
Pour en savoir plus : http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, tu as tout à gagner aux niveaux perfos...
Si ton tableau est stocké dans une base de données, je te
déconseille vivement la procédure récursive : récupérer la
hiérarchie des parents d'un enregistrement donné (pour créer la
chaine "vous etes ici : groupes > fr > comp > lang > php" par exemple)
est hyper couteux puisque tu vas avoir 5 requetes a envoyer a la base.
Il existe une autre façon de stocker un répertoire pour n'avoir
qu'une seule requete a faire quel que soit le type de demande (avoir
toute la hiérarchie sous un noeud donné, avoir tous les ancetres d'un
noeud donné, etc). En contrepartie il faut faire trois requêtes pour
une insertion ou une suppression, mais en général, on le fait
beaucoup moins souvent.
Pour en savoir plus :
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, tu
as tout à gagner aux niveaux perfos...
Si ton tableau est stocké dans une base de données, je te déconseille vivement la procédure récursive : récupérer la hiérarchie des parents d'un enregistrement donné (pour créer la chaine "vous etes ici : groupes > fr > comp > lang > php" par exemple) est hyper couteux puisque tu vas avoir 5 requetes a envoyer a la base.
Il existe une autre façon de stocker un répertoire pour n'avoir qu'une seule requete a faire quel que soit le type de demande (avoir toute la hiérarchie sous un noeud donné, avoir tous les ancetres d'un noeud donné, etc). En contrepartie il faut faire trois requêtes pour une insertion ou une suppression, mais en général, on le fait beaucoup moins souvent.
Pour en savoir plus : http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, tu as tout à gagner aux niveaux perfos...
Jean-Marc Molina
motton75 wrote:
Si ton tableau est stocké dans une base de données, je te déconseille vivement la procédure récursive : récupérer la hiérarchie des parents d'un enregistrement donné (pour créer la chaine "vous etes ici : groupes > fr > comp > lang > php" par exemple) est hyper couteux puisque tu vas avoir 5 requetes a envoyer a la base.
Tout dépend des exigences de l'application. L'optimisation est vraiment l'une des dernières étapes à laquelle il faut passer dans certains cas. Dans d'autres on peut tout simplement s'en passer. Par exemple que représentent quelques dizaines de requêtes sur une même "page" pour une application Web utilisée par une centaine de personnes ? Quelques milliers de requêtes seulement. Pas de quoi mettre un serveur à genoux.
Par contre j'admets que dans certains cas optimiser est vraiment important mais parfois à trop vouloir optimiser on finit pas mettre plein de "bottlenecks" (bouchons) dans son application ce qui finit par lui faire plus de mal que de bien. Par exemple un serveur bien configuré avec gestion du cache vaut mieux qu'une application bidouillée. Un grand débat.
Il existe une autre façon de stocker un répertoire pour n'avoir qu'une seule requete a faire quel que soit le type de demande (avoir toute la hiérarchie sous un noeud donné, avoir tous les ancetres d'un noeud donné, etc). En contrepartie il faut faire trois requêtes pour une insertion ou une suppression, mais en général, on le fait beaucoup moins souvent.
Pour en savoir plus : http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, tu as tout à gagner aux niveaux perfos...
Sur le même sujet voir aussi le "petit papier" "Gestion d'arbres par représentation intervallaire" [1] publié sur Developpez.com.
De toutes façons le jour où il devient vraiment nécessaire de libérer des ressources sur le serveur, rien n'empêche d'optimiser la solution récursive, solution qui aura mis quelques heures à être implémentées, et encore, alors que l'optimisation c'est une autre paire de manches.
Si ton tableau est stocké dans une base de données, je te
déconseille vivement la procédure récursive : récupérer la
hiérarchie des parents d'un enregistrement donné (pour créer la
chaine "vous etes ici : groupes > fr > comp > lang > php" par exemple)
est hyper couteux puisque tu vas avoir 5 requetes a envoyer a la base.
Tout dépend des exigences de l'application. L'optimisation est vraiment
l'une des dernières étapes à laquelle il faut passer dans certains cas. Dans
d'autres on peut tout simplement s'en passer. Par exemple que représentent
quelques dizaines de requêtes sur une même "page" pour une application Web
utilisée par une centaine de personnes ? Quelques milliers de requêtes
seulement. Pas de quoi mettre un serveur à genoux.
Par contre j'admets que dans certains cas optimiser est vraiment important
mais parfois à trop vouloir optimiser on finit pas mettre plein de
"bottlenecks" (bouchons) dans son application ce qui finit par lui faire
plus de mal que de bien. Par exemple un serveur bien configuré avec gestion
du cache vaut mieux qu'une application bidouillée. Un grand débat.
Il existe une autre façon de stocker un répertoire pour n'avoir
qu'une seule requete a faire quel que soit le type de demande (avoir
toute la hiérarchie sous un noeud donné, avoir tous les ancetres d'un
noeud donné, etc). En contrepartie il faut faire trois requêtes pour
une insertion ou une suppression, mais en général, on le fait
beaucoup moins souvent.
Pour en savoir plus :
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html,
tu as tout à gagner aux niveaux perfos...
Sur le même sujet voir aussi le "petit papier" "Gestion d'arbres par
représentation intervallaire" [1] publié sur Developpez.com.
De toutes façons le jour où il devient vraiment nécessaire de libérer des
ressources sur le serveur, rien n'empêche d'optimiser la solution récursive,
solution qui aura mis quelques heures à être implémentées, et encore, alors
que l'optimisation c'est une autre paire de manches.
Si ton tableau est stocké dans une base de données, je te déconseille vivement la procédure récursive : récupérer la hiérarchie des parents d'un enregistrement donné (pour créer la chaine "vous etes ici : groupes > fr > comp > lang > php" par exemple) est hyper couteux puisque tu vas avoir 5 requetes a envoyer a la base.
Tout dépend des exigences de l'application. L'optimisation est vraiment l'une des dernières étapes à laquelle il faut passer dans certains cas. Dans d'autres on peut tout simplement s'en passer. Par exemple que représentent quelques dizaines de requêtes sur une même "page" pour une application Web utilisée par une centaine de personnes ? Quelques milliers de requêtes seulement. Pas de quoi mettre un serveur à genoux.
Par contre j'admets que dans certains cas optimiser est vraiment important mais parfois à trop vouloir optimiser on finit pas mettre plein de "bottlenecks" (bouchons) dans son application ce qui finit par lui faire plus de mal que de bien. Par exemple un serveur bien configuré avec gestion du cache vaut mieux qu'une application bidouillée. Un grand débat.
Il existe une autre façon de stocker un répertoire pour n'avoir qu'une seule requete a faire quel que soit le type de demande (avoir toute la hiérarchie sous un noeud donné, avoir tous les ancetres d'un noeud donné, etc). En contrepartie il faut faire trois requêtes pour une insertion ou une suppression, mais en général, on le fait beaucoup moins souvent.
Pour en savoir plus : http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, tu as tout à gagner aux niveaux perfos...
Sur le même sujet voir aussi le "petit papier" "Gestion d'arbres par représentation intervallaire" [1] publié sur Developpez.com.
De toutes façons le jour où il devient vraiment nécessaire de libérer des ressources sur le serveur, rien n'empêche d'optimiser la solution récursive, solution qui aura mis quelques heures à être implémentées, et encore, alors que l'optimisation c'est une autre paire de manches.
