Algo "modified preorder tree traversal"

Question

Salut,

Une fois n'est pas coutume je VEUX un code tout fait !!! (<==   règlement !!)

 ma masse capillaire commence à souffrir dangereusement de mes tentatives d'implémenter une structure hiérarchique non récursive et je préfèrerai utiliser les quelques neurones qu'il me reste à d'autres tâches.

Je galère à trouver une classe PHP5 qui puisse implémenter cet algorithme.
J'entends par là une classe  documentée  qui permette de gérer facilement l'ajout, la suppression et la mise à jour des noeuds de l'arbre ( === pas de prise de tête à recalculer manuellement les right et left)

Dans l'absolu une classe capable de générer une liste ul/ol après l'application d'un filtre (du style ne pas faire apparaitre certains noeuds/ul/li tout en conservant une hiérarchie correcte ... ché pas si je suis clair là)


Merci d'avance pour vos éventuelles réponses,


Kohntark -

syndrael · Answer

Tu vas rire mais un jour on m'a posé la question et j'ai répondu de passer par DOM XML, tu peux parcourir, ajouter et supprimer sans souci. Comme un structure ul/ol etc.. peut s'apparenter à un XML.
Ca ne peut pas te convenir ??
S.

neigedhiver · Answer

Rhô l'autré, hé j'hallucine, hé...

Je sais même pas ce que c'est cet algorithme (du coup, je vais me renseigner, pas envie d'être à la traîne...)

Euh sinon, je crois que c'est mon tour de faire le mail... 'tain, comment j'suis à la bourre !!

-- 
Neige

Souvent la réponse à votre question se trouve dans la doc. Commencez par là ;)

syndrael · Answer

Pour Neige, une bonne description est présente sur: http://articles.sitepoint.com/article/hierarchical-data-database/2#
Ma réponse pour DomXml c'était hélas parce qu'à l'époque je n'avais rien trouvé en terme de Class PHP donc nous avions opté pour cette alternative.
S.

syndrael · Answer

En cherchant une page d'explication pour Neige, je suis tombé la dessus: Tapez le texte de l'url ici.
Ca peut être une piste sympa.
S.

kohntark · Answer

Merci pour vos réponses.

@Syndrael :
Ca ne peut pas te convenir ??
J'y avais pensé, mais je préfère rester sur des données en DB.
A vrai dire ce n'est pas vraiment nécessaire (la DB) pour l'utilisation que je vais en faire dans un premier temps (une cinquantaine d'enregistrements hiérarchisés tout au plus) mais j'aurai tout de même à passer des requêtes et j'ai peur que ce soit plus complexe (et moins rapide) avec XML ... menfin je connais très mal.

J'ai jeter un oeil à ton lien, malheureusement, comme beaucoup de classes que j'ai pu trouver c'est du PHP4 et surtout elle utilise d'autres composants d'un framework (j'pourrai adapter, mais bon, j'ai peur de me perdre), ... je garde sous le coude.

Je pense avoir trouvé un truc qui pourrait répondre à mes attentes :
http://bakery.cakephp.org/articles/view/modified-preorder-tree-traversal-component

Je viens de faire 2/3 tests rapides, il semblerait que ça tienne la route, malgré un pb au niveau de l'ajout de noeuds ayant le même nom (pas creusé)

@Neige :
Je sais même pas ce que c'est cet algorithme (du coup, je vais me renseigner, pas envie d'être à la traîne...) 
 Le jour où tu seras à la traine sur moi c'est que tu auras abandonné la programmation depuis 10 ans !!
J'aime bien cet algo, ça m'a l'air très efficace et très rapide, mais à mon niveau je trouve ça lourd à mettre en place avec des données très dynamiques; il est très simple de casser l'arbre et c'est une véritable galère (au point où j'en suis) à remettre d'aplomb. 

Pour le mail il n'y a aucune obligation et aucun délai 


Je vais explorer et adapter si besoin cette classe.
Concernant le filtrage que j'évoquais dans mon premier post je sèche; je ne vois pas comment il pourrait être possible d'effectuer ce filtrage à la base (cad dans la requête SQL) tout en conservant une hiérarchie correcte (et la génération ul/li), par exemple :

machin
-machin1
--machin10
---machin101
---machin101
----machin1010
----machin1011
---machin102
--machin11
-machin2
-...

Comment afficher l'arbre sans le machin101 et ses 2 enfants 
J'avoue ne pas y avoir réfléchi plus que ça, mais un décalage des right / left dans la méthode d'affichage risque de poser problème.
Le mieux reste surement de retirer l'arbre complet et de filtrer ensuite ... toute idée reste la bienvenue 

Bonne soirée à vous,


Kohntark -

kohntark · Answer

le lien de la class :
http://phpro.org/tutorials/Managing-Hierarchical-Data-with-PHP-and-MySQL.html



Kohntark -

neigedhiver · Answer

Plop,

Bon je me suis toujours pas renseigné... Mais ton histoire d'afficher l'arbre sans machin101 et ses enfants, la solution pourrait ressembler à un FilterIterator. Mais comme j'ai pas encore pris le temps de lire les liens qu'on m'a proposés... (depuis 3 jours, je suis sur The Shield, je devrais terminer la saison 3 ce soir, pis je passe à la saison 4, parce que faut pas trainer quoi).

Si je peux apporter quoi que ce soit d'inutile, faites le moi savoir, ce sera avec plaisir. ^^

-- 
Neige

Souvent la réponse à votre question se trouve dans la doc. Commencez par là ;)

kohntark · Answer

Kesako "The Shield" ?? une connerie américaine ??  (sorry pour mon inculture télévisuelle, mais TV rime avec placard/poubelle chez moi ^^ <== sisi ça existe )

Le "pb" de filterIterator est qu'il demandera de retirer l'arbre complet de la base. Ce n'est vraiment pas un problème pour le peu de données que j'ai a traiter à l'instant T, mais j'aurai peut être besoin plus tard d'appliquer cet algo sur un nombre plus conséquent d'enregistrements (plusieurs milliers). Dans ce cas les performances risquent d'en prendre un coup, et passer par des méthodes du crû "getSubChild" auront le même effet (multiplication des requêtes)

Je réfléchis tout haut et je dis sans doute des conneries.
Pour tenter d'être plus clair :
Ce qui m'inquiète un peu c'est de pouvoir obtenir une partie de l'arbre :
virer un/plusieurs noeud, un/plusieurs sous noeud, un/plusieurs sous sous noeuds, etc ... tout en conservant la justesse de la profondeur.

Bon, je vais tester un peu avant de dire n'importe quoi, et je n'aurai vraisemblablement pas besoin de tout ça ^^

Merci pour ta dispo Neige, j'apprécie, et je ne manquerai pas d'en profiter, surtout concernant la SPL qui a souvent tendance à me prendre la tête ( super bien documentée)



Kohntark -

syndrael · Answer

Je pense avoir trouvé un truc qui pourrait répondre à mes attentes : 
Eh monsieur !! C'est le lien que j'avais mis !! Je demande le droit d'auteur.. de la trouvaille de 07h35 !! 
Mais dans l'ensemble tu as pu arriver à ce que tu cherchais ??
S.

neigedhiver · Answer

Plop,

Sans avoir rien lu, je comprends mieux le problème grâce à cette phrase : "Le "pb" de filterIterator est qu'il demandera de retirer l'arbre complet de la base."

Quand je disais que la solution ressemblerait à FilterIterator, je ne disais pas que FilterIterator ETAIT la solution. Je ne faisais qu'une analogie (je sais, c'était pas forcément évident à deviner).
Une solution serait d'avoir comme clé primaire (PK) une clé générée "manuellement" et dont l'intégrité n'est pas garantie par le SGBR, mais par le script. Ca laisse un peu plus la place à l'erreur, mais en faisant gaffe, c'est pas la fin du monde.
La PK devrait alors refléter, de par sa valeur, la hiérarchie de l'élément. Il serait alors possible de filtrer avec une simple clause where.
Est-ce que ce que je dis est pertinent, ou bien est-ce que je suis à des années-lumières de la problématique ? Désolé, je ne fais que répondre entre 2 épisodes... (oui, The Shield est une série américaine, désolé pour ma faiblesse ; à ma décharge, je regarde aussi de bons films de temps en temps lol)

-- 
Neige

Souvent la réponse à votre question se trouve dans la doc. Commencez par là ;)

kohntark · Answer

Eh monsieur !! C'est le lien que j'avais mis !! Je demande le droit d'auteur.. de la trouvaille de 07h35 !!
Mais dans l'ensemble tu as pu arriver à ce que tu cherchais ??
S. 

Yep, je sais Syndrael, je me suis rendu compte de l'erreur juste après avoir posté et j'ai corrigé dans mon post de 18:08:42
En fait je (re re) regardais ton lien et comme un c.. j'ai recopié par mégarde l'url tu m'avais proposée au lieu de ma trouvaille de 5h15 (preums !! ).
Tu devrais jeter un oeil au lien, je pense que ça pourrait t'intéresser.
... et je suis preneur de tes avis avertis 

Bonne soirée à toi,

Kohntark -

neigedhiver · Answer

Plop,

Bon, j'ai fini la saison 3, alors je me replonge un peu dans le PHP, ça fait pas de mal... Je suis donc en train de lire l'article sur sitepoint. Comme j'aime pas lire à partir du milieu, j'ai commencé à la page 1 (qui traite de l'ago récursif). La question que je me pose est : l'auteur est-il compétent ?
Ouais, je suis un peu direct, mais sincèrement : il a pas trouvé mieux pour itérer que de faire une requête par noeud ?
J'ai déjà illustré sur ce forum comment parcourir les éléments d'une table contenant des données hiérarchisées et ce avec une seule requête et en partant du niveau et de l'élément parent qu'on souhaite. Et c'est pourtant pas quelque chose de bien compliqué...
Bon je continue la lecture... :/

-- 
Neige

Souvent la réponse à votre question se trouve dans la doc. Commencez par là ;)

neigedhiver · Answer

Je viens de lire la page 2, celle qui concerne bien ton problème.
Ma principale question est : en dehors du fait que la structure de la table n'est pas cohérente ni conforme à un modèle valide, qu'apporte cette manière de stocker ? Je vois un autre inconvénient : le besoin de regénérer les valeurs des colonnes lft et rgt chaque fois qu'on insère ou supprime un élément.

Après ça, peut-être que je pourrais comprendre ce que tu cherches exactement à faire :)

-- 
Neige

Souvent la réponse à votre question se trouve dans la doc. Commencez par là ;)

syndrael · Answer

Pour Neige:
Les algo de hiérarchies sont un peu un des problèmes récurrents en informatique, du fait de la multitude de façons d'agir. Ce qui différencie chacun sont les perfs, la maniabilité et les effets sur les éléments soi-disant non impactés. Le problème est analogue pour les tris, les chaines, les piles.. Enfin tout ce qui permet de gérer des données en nombre.
Tout dépend de ton besoin, mais si tu as les bonnes classes la maniabilité des infos en création ou en modification doit être aisé. Et c'est justement ce que cherchait Kohntark.
Y'en a qui s'éclatent sur le dernier Assasin Creed ou PES, moi c'est de l'algorithmique.. LOL !!

kohntark · Answer

Après ça, peut-être que je pourrais comprendre ce que tu cherches exactement à faire :) 

Je cherche à :
   - ne pas rester sur l'échec d'il y a quelques mois lorsque, suite à un post sur ce forum, j'avais tenter de capté un minimum le truc
   - trouver un algo simple de hiérarchisation des données en SGDB
   - faire fondre quelques neurones afin de tenter de m'endormir moins con le soir (c'est pas gagné mais tant qu'il m'en reste ça vaut le coup d'essayer ^^)

Je pense que Syndrael résume bien la chose et si tu peux me renseigner sur un algo "magique" qui serait efficace en terme de perfs, de manipulation / maj, etc ... je suis preneur.
Je suis assez nul dans le domaine et le but de la manoeuvre est de l'être moins.

Le mptt me semble performant en terme d'affichage pour des données peu dynamiques. Les ajouts / suppressions (...) sont bien plus complexes et consommeraient pas mal de ressources si ils devaient être mis à jour fréquemment (update d'une grosse partie de l'arbre)

Je vais continuer à creuser un peu dans ce sens, et sans doute reviendrai je à une structure un peu plus conformiste ...

As tu jeté un oeil à la classe citée dans un précédent message ?
Qu'en penses tu ?

Cordialement,


Kohntark -

neigedhiver · Answer

Plop,

Mon frère, qui fait semblant d'être DBA, m'a parlé de la clause CONNECT BY sur Oracle (et sur PostgreSQL avec un patch).
Sur MySQL, qui est de plus en plus pourri à mes yeux (mon frangin m'aide bien à avoir une opinion décroissante de ce SGBDR, seulement c'est le seul que je sois capable d'administrer un petit peu) il faut regarder du côté de WITH RECURSIVE.
Ces clauses / options servent justement à gérer ce genre de données sans se casser la tête sur des algos compliqués. En d'autres termes, la première page de l'article sur sitepoint présente la seule manière valable d'organiser ses données dans une base. Et il existe des manières de gérer la hiérarchie au sein même des SGBDR, de sorte qu'il ne soit pas nécessaire de faire des fonctions compliquées qui vont mettre à jour des champs avec des valeurs calculées et compliquées ou faire 150 requêtes pour avoir juste un arbre...

J'ai pas encore eu le temps de regarder de près comment ça se passe sur MySQL, je viens seulement de finir la saison 4 de The Shield, et j'en ai encore 3 à voir... Mais je vais faire l'effort, hein, faut juste que je trouve un moment entre deux épisodes o j'ai un peu la motiv' ^^

-- 
Neige

Souvent la réponse à votre question se trouve dans la doc. Commencez par là ;)

kohntark · Answer

t'as raison Neige, il n'y a pas que le dev dans la vie, et je vais moi même lever (un peu) le pied bientôt (pas pour des conneries amerloc  mais pour "m'envoyer en l'air" au sens figuré et propre du terme)

Je connais assez peu Oracle, mais suffisamment pour penser qu'il reste un SGBD plus puissant que MySQL ... sauf qu'il faut pondérer (en comparaison à Mysql) :
  - c'est un gouffre à ressources
  - sans un véritable DBA il est difficile d'en tirer pleinement partie

Pour des projets de 'moyenne' envergure il n'est pas du tout adapté, et mySQL se révèle bien plus flexible et rapide (d'après le peu d'expérience que j'ai et les quelques comparatifs sérieux que j'ai pu lire)

Pour la petite histoire j'ai au boulot plusieurs bécanes qui utilisent Oracle (11g)... pour quelques milliers de données et une dizaine de requêtes ultra basiques SELECT, INSERT, contraintes et vues ... => obligé de blinder la machine (XP pro) avec 4Go (et encore c'est limite), un proc assez récent, etc ...
 est ce le bon choix dans un contexte industriel ? => clair que non, et c'est la même chose en ce qui concerne 85% des sites WEB.

Tout ça pour dire que j'aime beaucoup mySQL, qui réponds bien mieux que bon nombre d'autres à la plupart des problématiques, sans en ajouter des superflues (Oracle, SQL server, ...)

Merci pour tes infos, je regarderai attentivement dès que j'en aurai l'occasion, et si tu as plus d'infos je plusois ^^

Bon film :)

Kohntark -

neigedhiver · Answer

Je voulais pas lancer un troll Oracle vs MySQL... Mon frère ne travaille que sur Oracle et un peu sur Postgres (davantage libre que MySQL et plus proche des standards SQL), donc il m'a parlé de ce qu'il connait.
Mais juste comme ça, installer Oracle sur Windows, je trouve ça un peu dégueu... C'est quand même mieux sur Redhat, d'autant que Redhat appartient à Oracle (de même que MySQL me direz-vous, certes).

Bref. J'ai fait une rapide recherche, je n'ai rien trouvé concernant une option WITH RECURSIVE sur MySQL... Donc euh bon, voilà.

Pour ce qui est du choix du SGBDR, Oracle est vraiment énorme et très cher (150 000€ par processeur environ, un truc dans le genre et non, je n'exagère pas), gourmand en ressources, peut-être, mais quand un DBA me parle des différences entre ORacle et MySQL... je comprends assez vite. C'est pour ça que PostgreSQL est une alternative à ne pas négliger, dans le sens où c'est un SGBDR libre (davantage que MySQL : la licence Sun de MySQL oblige à publier les sources de toute application utilisant MySQL, non, je n'exagère pas, et certains modules de MySQL sont propriétaires)

Mais bon, c'est pas forcément le bon endroit pour avoir ce genre de discussion ^^ et même sur un forum sérieux, de toute façon, c'est difficile d'échapper aux trolls et aux arguments stériles.

Tout ça pour dire que j'ai pas de solution pour le moment lol

-- 
Neige

Souvent la réponse à votre question se trouve dans la doc. Commencez par là ;)

syndrael · Answer

Allez hop.. on va réagir à tout ça.. LOL !!
@kohntark:
l n'y a pas que le dev dans la vie
Quoi ?? On m'aurait menti ?? LOL.. Non je déconne, mais c'est vrai que beaucoup de sujet de la 'vraie' vie m'amène à coller une appli pour améliorer la chose. Actuellement, une appli pour commander..des patisseries faites maison par ma chère et tendre. 
Un album photo de mon bébé ? PHP + JQuery..
Je ramène tout à mon ptit Eclipse et compagnie..
@Neige:
davantage libre que MySQL et plus proche des standards SQL
Oui mais le client s'en fout des standards, tant que ça lui permet d'avoir un produit vite et proche du gratuit.
Pour en revenir au sujet, l'implémentation dans mon super lien de 7h et des brouettes me semble pas trop déconnant. 
Après si j'étais dans la situation de Kohntark, moi je serai d'avis de l'implémenter pour obtenir cette fonctionnalité rapide et voir ses perfs. Si ça tient la route c'est que c'est bon, si ça tient pas la route c'est que le client n'a pas correctement exprimé ses besoins.. LOL !!
Un peu expéditif mais assez persuasif quand tu enchaines sur le budget pour améliorer tout ça.. 
A pluuus !!
S.

kohntark · Answer

Mais bon, c'est pas forcément le bon endroit pour avoir ce genre de discussion ^^ et même sur un forum sérieux, de toute façon, c'est difficile d'échapper aux trolls et aux arguments stériles. 
J'ai du mal à te suivre sur ce coup  je ne vois pas en quoi cela constituerait un troll, et encore moins sur le fait que ça ne soit pas le bon endroit.
Ca change un peu des "j ve savoir kommen metre un lien", non ?

Mais juste comme ça, installer Oracle sur Windows, je trouve ça un peu dégueu.
Sans doute, mais je n'apprendrai à personne que dans le monde industriel on préfère payer à prix d'or des licences windows, oracle, and co ... je n'ai jamais vraiment compris pourquoi d'ailleurs.

la licence Sun de MySQL oblige à publier les sources de toute application utilisant MySQL
Ben je vois plutôt ça comme étant un argument contraire à "davantage [libre] que MySQL"
Je n'ai jamais travaillé avec PostgreSQL, ... va falloir que je m'y mette un jour ou l'autre vu le bien que l'on en dit.


Actuellement, une appli pour commander..des patisseries faites maison par ma chère et tendre. 
Cool ça ... t'as pas un algo UAEOTF (understand and enforce orders to females) des fois ? 

l'implémentation dans mon super lien de 7h et des brouettes me semble pas trop déconnant. 
Même si je le garde sous le coude je préfère tout de même mon super lien de 5h et des brouettes (poster le soir à 18h08) ^^
http://phpro.org/tutorials/Managing-Hierarchical-Data-with-PHP-and-MySQL.html

Je n'ai une fois de plus pas eu trop de temps pour retravailler le sujet, mais cette classe semble donner satisfaction.
Je suis en train de la modifier de mon mieux afin qu'elle puisse, entre autres, générer des listes.



Bonne soirée,


Kohntark -

Algo "modified preorder tree traversal"

23 réponses

Votre réponse

Discussions similaires