boucle récursive pour arboresceprob nce - PHP - Programmation
Marsh Posté le 08-10-2005 à 00:00:28
l'histoire des secteurs j'ai pas trop compris mais disons qu'il est fixe pour l'exemple
un resultat possible serait
secteur rubrique parent
0 1 0
0 9 0
0 2 1
0 3 1
0 4 1
0 5 2
0 6 2
0 7 3
tu veux un affichage du genre
rub1
rub2
rub5
rub6
rub3
rub7
rub4
rub9
donc en une requete c pa possible
faut faire un parcours en profondeur recursif (ou iteratif avec un pile mais plus chiant a faire)
pour facilité l'algo l'ideal c de faire une liste d'adjacence avec les sous rubriques pour chaque rubrique
genre
1 : 2 ~ 3 ~ 4
2 : 5 ~ 6
3 : 7
4 : ø
5 : ø
6 : ø
7 : ø
8 : ø
9 : ø
l'algo en gros
ajouter_recursif(rubrique,profondeur)
{
ajouter dans la liste deroulante rubrique (identer en fct de profondeur)
tant que rubrique a des sous rubrique
ajouter_recursif(sousrubrique,prodondeur+1)
supprimer la sousrubrique traité dans la liste d'adjacence de rubrique
}
t'appelle ajouter_recursif(rubrique,0) pour toute les rubrique de parents 0
et ca devrait etre bon
Marsh Posté le 08-10-2005 à 00:35:03
merci de ta réponse .. j'avoue que çà me parait pas évident ..
le fonction ajouter_recursif(rubrique) serait une autre requete ?
> une variable pour sauvegarder la profondeur
comment tu fais çà ?
si tu peux m'éclairer ..
Marsh Posté le 08-10-2005 à 00:37:53
j'ai actualisé qd tu repondais... dsl
il faut d'abord cree la liste d'adjacence
avec la reponse du ton mysql_query
ensuite appeller la fonction php ajouter_recursif(rub,0)
pour la liste d'adjacence en fait c un tableau php
dont les indices sont les rubriques et la valeur par exemple une enumeration separé par des virgules des sous rub
par exemple
$tab[1]="2,3,4;"
$tab[2]="5,6";
apres tu explode $tab[i] par exemple pour avoir un tableau des sous rub de rub i
pour profondeur l'algo que je t'ai donné s'en oqp qd on appelle recursivement ajouter_recursif la profondeur est augmenté de 1
qd je dis ajouter la rubrique dans la liste deroulante, tu peux te servir immediatement de la variable profondeur qui correspond au nombre d'indentation à faire
Marsh Posté le 08-10-2005 à 00:38:30
si tu fais pas d'etudes d'infos c va pas etre evident en effet deja que moi ca me soulerait de le faire, lol
relis tout car g fait des corrections
Marsh Posté le 08-10-2005 à 01:48:38
j'ai un système similaire, qui prend une liste (obtenue d'un stockage à la SQL) pour la convertir en une structure multidimensionnelle (à la xml : nodes et children) ...
ouais, au départ, j'étais parti sur un truc récursif (rubrique, parent) que j'ai finalement laché pour qlque chose de linéaire bcp plus simple et énormément plus facile à maintenir (ordre, profondeur) avec des requêtes SQL ...
conclusion : avec la méthode 2 (en linéaire) je ne fais qu'une seule itération de ma liste originale, alors qu'avec la méthode récursive tu dois soit maintenir un index d'ordre en plus de "rubrique" et "parent" soit faire une pré-itération pour générer ce que Vlad' appelle la liste d'adjacence ...
mais bon, j'te raconte pas les paquets de café utilisé dans cet algo ...
Marsh Posté le 08-10-2005 à 03:03:12
le parcours en profondeur (recursif ou iteratif avec une pile) est optimale pour ce type d'operation
niveau sql cout minimum (juste recupérer les données sans les trier meme pas besoin de order)
la liste d'adjacence est en 0(n) autant d'operation que de ligne
y'a y a juste la prog qui demande un petit effort
que tu stockes dans une liste d'adjacence, une matrice ou une structure multidimensionnelle, il faudra bien faire une iteration pour respecter l'arborescence et c la toute la difference.
j'ai reflechi un peu et la seul autre methode pour s'en sortir serait de recuperer les données triés par parent et de calculer la position de chaque rubrique et sa profondeur pour les n lignes et reiterer celle déja ajouter pour les mettre a jour
genre: (par rapport à mon exemple post ci-dessus)
rub 1 : position 1 profondeur 0
rub 9 : position 2 profondeur 0
rub2 : position 2 (car c un fils de rub1 donc il doit etre en dessous) profondeur 2 (profondeur du pere + 1)
donc je dois mettre a jour s'il y en a les rub de profondeur 0 autre que le parent de rub2 (rub1) donc rub 9
rub 9 : position 3 profondeur 0
rub3 : position 3 (fils de rub1) profondeur 1
donc je met a jour rub 9
rub9 : position 4 profondeur 0
etc
d'une c n'est pas du tout linéaire (c n'est pas parce que c'est iteratif que c linéaire)
linéaire ca serait genre n lignes a traiter n itérations (ou appel recursif) mais je crois qu'on utilise rarement ce terme
la c du 1+2+3+4+...+n=n(n+1)/2 soit en O(n²) la ou le parcours en profondeur fait du O(n)
bref c tres tres couteux!
mais plus facile a mettre en oeuvre pour un autodidacte (l'algo de parcours en profondeur on ne le pond pas tout seul meme si qd on y regarde de plus pres ca parait logique )
Marsh Posté le 08-10-2005 à 10:55:41
vlad' a écrit : d'une c n'est pas du tout linéaire (c n'est pas parce que c'est iteratif que c linéaire) |
ok autant pour moi le terme 'linéaire' 'est inaproprié. Je l'ai utilisé pour différencier l'itération simple de la récursivité. Je voulais mettre l'accent sur la différence entre
1. méthode recursive : une boucle récursive + stockage de la rub. + stockage de l'id du parent + une itération ou un stockage supp. pour la liste d'adjacence + stockage d'un index
2. méthode itérative simple : une itération + stockage d'un index + stockage de la profondeur
Et comment gères-tu l'ordre d'arrivée des parents, de deux enfants d'un même parent, comment savoir qui est avant qui ?
Notes donc que la solution récursive n'est pas correctement maintenable sans un index d'ordre ...
tu es obligé de maintenir un index d'ordre dans la méthode récursive.
la maintenance SQL, comment fais-tu pour déplacer une branche entière sous une autre branche, ou à la racine ?
1. méthode récursive : tu dois mettre à jour la rub + les parents + ton index d'ordre
2. méthode itérative simple : mise à jour de l'index d'ordre + profondeur
- donc toi, tu ne trouves pas "tres tres couteux" de gérer parent-rub-ordre, de réitérer ou de stocker une liste d'adjacence, puis finalement de balancer le tout dans une boucle récursive ?
vlad' a écrit : j'ai reflechi un peu et la seul autre methode pour s'en sortir serait de recuperer les données triés par parent et de calculer la position de chaque rubrique et sa profondeur pour les n lignes et reiterer celle déja ajouter pour les mettre a jour |
bah non ...
si tu as juste l'ordre et la profondeur, tu n'as pas besoin de plus ... pour faire _une seule_ itération.
vlad' a écrit : mais plus facile a mettre en oeuvre pour un autodidacte (l'algo de parcours en profondeur on ne le pond pas tout seul meme si qd on y regarde de plus pres ca parait logique ) |
excuses moi, mais je te dirais bien de parler pour toi ...
ce qui parait le plus logique n'est pas forcément le plus simple - mais ce qui est le plus simple parait le plus logique, non ?
Marsh Posté le 08-10-2005 à 11:01:46
Pour mon forum, j'ai opté pour une organisation qui permet d'aficher les discution par ordre chronologique ou pas arborescence.
pour faire ça, j'ai dans ma base :
Ca m'évite de faire des requettes de maniére récursive. Par contre, c'est vrai qu'au début, j'y ai passé du temps avant d'arriver à avoir toutes les données comme il faut.
Au boulot, l'ancien webmaster a opté pour une arborescence dont les positions de messages sont notés par des suites de lettres par exemple "bc" veut dire troisiéme réponse au second message de niveau 1. Ca permet d'avoir en une seule donnée le niveau d'imbrication et la position d'affichage ('il suffit de trié sur cette colone) et ca évite de devoir modifier cette information quand on insére un nouveau message, mais par contre, ca prend vite plus de place dans la base de donnéek, la base de donnée mettra plus de temps à trier les donénes, ca nécessite un petit traitement pour savoir à quel niveau d'imbrication correspond chaque message et ca limite le nombre de réponse possible à un message donnée. Donc des avantages et des inconvénients.
Comme tu vois, il y a plusieurs solutions possible pour éviter la récusrsivité, mais si rien n'a été prévus pour disposer directement de l'odre d'affichage, il faudra la calculer de maniére récursive.
Marsh Posté le 08-10-2005 à 11:07:26
shakpana a écrit : la maintenance SQL, comment fais-tu pour déplacer une branche entière sous une autre branche, ou à la racine ? |
Faux :
C'est quasiment le seul cas où l'organisation récursive est plus efficace que le stockage de l'ordre d'affichage.
Marsh Posté le 08-10-2005 à 11:15:58
et l'ordre alors ?
parce qu'avec les "children" tu organises comment ?
Marsh Posté le 08-10-2005 à 11:54:09
omega2 a écrit : il sffit de changer la colone "fils de" de la tête de la branche qu'on veut déplacer. |
j'ajouterais :
moi aussi et pour le plaisir, je vais crier : "Faux" !
parce que tu aurais une manière de faire tout ce qu'il a été exposé, avec juste un champs "fils de", whaou, je suis impressionné ...
Marsh Posté le 08-10-2005 à 15:08:01
je rappel que jhac veut afficher l'arborescence de son site dans une liste deroulante.
il n'a pas parler d'ordonnance pour les rubriques de meme niveaux
S'il le veut il suffit d'ajouter une colonne pour ordonner les rubriques d'un meme niveau comme ci-dessous)
un resultat (order by parent,ordre) possible serait donc
rubrique parent ordre | position
9 0 1 | 1
1 0 2 | 2
4 1 1 | 3
2 1 2 | 4
3 1 3 | 7
6 2 1 | 5
5 2 2 | 6
7 3 1 | 8
ce qui devrait donner
rub9
rub1
rub4
rub2
rub6
rub5
rub3
rub7
liste d'adjacence (n itérations)
0: 9 ~ 1
1 : 4 ~ 2 ~ 3
2 : 6 ~ 5
3 : 7
4 : ø
5 : ø
6 : ø
7 : ø
8 : ø
9 : ø
bref rien de compliqué ni couteux
l'algo de parcours reste le meme vu qu'il ajoutera les rubriques en respectant l'ordre de la liste d'adjacence
on va tout de meme calculer c que ferai l'algo
que je rappel et modifie en consequence
arbo_recur(rub,p,l)
/*
rub : n° de la rubrique
p : profondeur de rub
l : liste d'adjacence (tableau)
*/
debut
si (rubrique != 0) alors
ajouter dans la liste déroulante p indentations + rub
tant que l[rub] non vide
arbo_recur(tete de l[rub],p+1,l)
supprimer la donné en tete de l[rub]
fintantque
}
executons l'algo...
on appelle arbo_recur(0,0,l)
rub=0, on ajoute rien dans la liste deroulante
l[0] est non vide
on appelle arbo_recur(9,1,l)
rub=9, on ajoute 9 dans la liste deroulante 9
l[9] est vide, on sort
on supprime 9 de l[0]
l[0] est non vide
on appelle arbo_rescur(1,1,l)
rub=1, on ajoute 1 dans la liste deroulante 1
l[1] est non vide
on appelle arbo_recur(4,2,l)
rub=4, on ajoute 4 dans la liste deroulante 4
l[4] est vide, on sort
on supprime 4 de l[1]
l[1] est non vide
on appelle arbo_recur(2,2,l)
rub=2, on ajoute 2 2
l[2] est non vide
on appelle arbo recur(6,3,l)
rub=6, on ajoute 6
l[6] est vide on sort
on supprime 6 de l[2]
l[2] est non vide
on appelle arbo_recur(5,3,l)
rub=5, on ajoute 5
l[5] est vide on sort
on supprime 5 de l[2]
l[2] est vide on sort
on supprime 2 de l[1]
l[1] est non vide
on appelle arbo_recur(3,2,l)
rub=3, on ajoute 3
l[3] est non vide
on appelle arborecur(7,3,l)
rub=7, on ajoute 7
l[7] est vide, on sort
on supprime 7 de l[3]
l[3] est vide, on sort
on supprime 3 de l[1]
l[1] est vide, on sort
on supprime 1 de l[0]
l[0] est vide on sort
terminé
n+1 appelle donc O(n) optimal
Pour en revenir a vos reponses
shakpana
Citation : donc toi, tu ne trouves pas "tres tres couteux" de gérer parent-rub-ordre, de réitérer ou de stocker une liste d'adjacence, puis finalement de balancer le tout dans une boucle récursive ? |
parent rub ordre c le minimum pour faire ce que l'ont veut
stocker dans une liste d'adjacence est optimale, n itérations et les données sont directement prete a être utiliser
questionner la base à coup de mysql_fetch_array est plus couteux dans ce contexte car l'algo utilisé derriere est en O(n²).
=> la structure de liste d'adjacence permet d'economiser ensuite sur le nombre d'iterations (meilleur algo utilisé par la suite)
fonction recursive : optimal, n+1 appelle
Citation : bah non ... |
// pour l'algo sans parcours
qd tu affecte un ordre et une profondeur à une rubrique ils ne sont que provisoires.
exemple
tu veux
rub9
rub2
rub1
le tableau mysql retourne
rub ordre profondeur
9 1 0
1 2 0
2 1 1
rub1 va etre placé avant rub2
rub9
rub1
rub2
il faut mettre a jour l'ordre des rubriques comprise entre rub2 et son pere
bref relis mon exemple parce que la t'es completement largué
Marsh Posté le 08-10-2005 à 15:37:20
vlad' a écrit : je rappel que jhac veut afficher l'arborescence de son site dans une liste deroulante. |
Je trouve ça un peu présomptueux comme raisonnement ...
- acceuil, rub1, rub2, contact, crédits
risque de se retrouver
- acceuil, crédits, contact, rub2, rub1
si l'on ne créé pas tout le bon ordre et comment ferait-on si voulait mettre rub2 avant rub1 ?
vlad' a écrit : Dans le cas contraire il suffit d'ajouter une colonne pour ordonner les rubriques d'un meme niveau comme ci-dessous) |
donc tu te retrouve à gérer en plus un index d'ordre, merci.
vlad' a écrit : bref rien de compliqué ni couteux |
ben si, car tu gères les relation parents/enfants PLUS l'ordre
Or il est possible de gérer seulement l'ordre et la pronfondeur ... sans ce soucier du nom du parent ou des enfants
vlad' a écrit : parent rub ordre c le minimum pour faire ce que l'ont veut |
je ne sais où tu as vu plusieurs mysql_fetch_array ?
il est possible de faire une lecture SQL + une itération simple et de se retrouver avec une structure multidimensionelle sans aucune liste d'adjacence ni aucune pre-itération.
Pour l'écriture Ajout ou Modif, il faut connaitre le point cible d'insertion|réaffection (son ordre) et son niveau, puis une requête SQL pour décaler l'ordre et une deuxième requête pour l'insertion/modification de la source
lecture : une requête SQL, une itération
écriture : lecture + une itération pour correction de la profondeur s'il y a lieu + une requête SQL UPDATE order = order (+|-) 1 + une requête SQL INSERT|UPDATE
mais bon ...
Marsh Posté le 08-10-2005 à 16:24:34
Citation : donc tu te retrouve à gérer en plus un index d'ordre, merci. |
tu arrives a ordonner les rubriques de meme niveau sans en avoir l'information, tu es tres fort
le probleme c'est que tu ne differencies pas la phase de construction et la phase d'utilisation
pour la construction on a besoin de l'ordre et du parent de chaque rubrique (ou l'ordre est l'ordonnance des rubriques de meme niveau)
cette construction implique l'affectation de la position finale de chaque rubrique et leur profondeur
de cette facon la lecture est optimal : order by position et c'est fini
la liste d'adjacence est construite avec une unique itération de la table comme toi et ta structure multidimensionnelle
ensuite l'algo de parcours (construction) effectue le travail en n+1 appel recursifs, le tient est moins performant car il n'ajoute pas en respectant immediatement l'arborescence, il doit mettre a jour.
Prenons le cas ou tu dois inserer une nouvelle rubrique entre une rubrique et une de ses sous rubriques ca serait vraiment terrible pour ton algo;
l'algo en profondeur le ferait toujours en n+1 appels au pire la ou le tient mettra sans cesse les positions a jour
En esperant avoir été clair, j'abandonne si tu ne toujours comprends pas
Marsh Posté le 08-10-2005 à 17:21:39
> il faut mettre a jour l'ordre des rubriques comprise entre rub2 et son pere
> bref relis mon exemple parce que la t'es completement largué
ouais, tu sais quoi, c'est moi qu'arrête là.
je te répête une truc 15 fois, et tu ne veux même pas l'envisager, tu restes campé sur tes positions, c'est un peu fatiguant, quant à celui qui ne comprend pas à priori c'est toi, mais une bonne relecture du thread t'éclaireras un peu. J'ai un système itératif/récursif qui fonctionnait à merveille, que j'ai remplacé par un système beaucoup plus simple et plus rapide seulement itératif.
donc en gros tout ce que tu me racontes j'y suis déjà passé, et je sais déjà que çà marche, ok ?
à bon entendeur ...
je te laisse ça puis après ...
Code :
|
quant tu l'auras sous cette forme en une seule itération, tu m'en reparles ...
edit : et que tu pourras le maintenir en 2 requête SQL avec un UPDATE order et un INSERT|UPDATE
Code :
|
Marsh Posté le 08-10-2005 à 17:51:54
J'ai pas lu tout le bazar en entier mais si jamais ça peut aider, j'avais écrit une petite fonction pour représenter une arbo par ici :
http://forum.hardware.fr/hardwaref [...] 4510-1.htm
Marsh Posté le 08-10-2005 à 18:03:58
c'est un peu ce genre là, sauf que c'est l'inverse
on part d'un structutre linéraire pour la mettre en multidim - enfin moi c'est ce que fait / ce dont j'ai besoin ...
Marsh Posté le 08-10-2005 à 18:58:57
Mouais, ça m'a l'air un poil lourd pour maintenir de gros arbre ton système shakpana non ? Parce que bon, tu ajoutes un élément au début (order = 0) tu modifies TOUT le bazard ?
(et l'order de B1 devrait pas valoir 4 dans ton exemple ?)
Enfin, ça prouve bien qu'il y a autant de manière de gêrer ça que de personne qui s'y colle
Marsh Posté le 08-10-2005 à 19:06:26
> naceroth
oui bien vu, m'étais planté dans mes copié/collés ... mais cette valuer valeur n'as pas d'importance, tant que tout est ordonné, c'est un champ de la table pour la requete SQL, ici, pour l'exemple
> élément au début (order = 0) tu modifies TOUT le bazard
oui, ça donne une requête genre UPDATE table SET order = order + 1 WHERE order > 0
ce qu'il n'y a pas plus terrible, vu que dans mon schema je risque de jamais arriver à plus de, allez disons 30,40,50 entrées et que l'ajout est fait de manière _très_ sporadique
> Enfin, ça prouve bien qu'il y a autant de manière de gêrer ça que de personne qui s'y colle
bah oui ... bien dit ...
Marsh Posté le 08-10-2005 à 19:11:27
naceroth a écrit : Mouais, ça m'a l'air un poil lourd |
mais pourquoi donc ? je reprend
à la lecture 1 requête, 1 itération, point barre ...
après je peux pas faire moins, enfin sinon je suis preneur
Marsh Posté le 08-10-2005 à 20:39:16
ce n'est pas parce que c mysql qui fait les opérations qu'il ne faut pas les compter...
je n'ai pas dit que ce n'etait pas correcte ce que tu as fait loin de là juste moins performant
enfin bref t'es le meilleur
Marsh Posté le 08-10-2005 à 20:51:44
vlad' a écrit : enfin bref t'es le meilleur |
ok, le prends pas comme ça, c'est franchement pas mon propos ...
mais je vois pas en quoi c'est moins performant ... au contraire d'ailleurs ...
car la requête dont tu parles (celle que je n'aurais pas compter, mais dont je parle depuis longtemps, celle d'UPDATE order ), tu dois la faire aussi ... dont je cherche toujours ce que je ferais de plus qu'avec la méthode recursive, à part supprimer le récursivité et la table d'adjacence ... y'a strictement rien de plus, donc 1 - 1 + 0 = 0
Marsh Posté le 09-10-2005 à 02:09:26
shakpana a écrit : mais pourquoi donc ? je reprend |
Oui, dans le sens lecture en effet, tout système multi-requête est bon à jeter aux ordures on est d'accord. Par contre, perdre à l'écriture ce que tu gagnes à la lecture, là, je suis moins convaincu. Je prends que l'exemple de ma boite où on a des arbres "simples" dont la seule racine contient dans les 20 branches et pour lesquels on a parfois 7 ou 8 niveaux, mémoriser l'ordre (comme la profondeur d'ailleurs, j'ai même pas réfléchi à comment tu déplaces une branche entière ou, encore plus chiant, une partielle) me semble lourd pour le serveur sql
Marsh Posté le 09-10-2005 à 13:07:26
En pratique, on lit généralement plus souvent qu'on écrit, donc perdre en écriture, c'est moins génant qu'en lecture.
Et pour une arborescence de site, on lit beaucoup plus souvent le menu qu'on ne le modifie.
Pour le déplacement d'une branche ou d'une sous-branche, c'est vrai que ca peut sembler lourd, mais en général, on peut s'en sortir en 3 ou 4 requettes si on a bien prévus le truc :
Marsh Posté le 09-10-2005 à 15:52:49
omega2 a écrit : En pratique, on lit généralement plus souvent qu'on écrit, donc perdre en écriture, c'est moins génant qu'en lecture. |
En pratique, sur des gros trucs, tu utilises des caches, tu ne t'amuses pas à lire et recréer la structure à chaque accès aux pages...
Citation :
|
Que tu utilises 1, 2 ou X requête(s) ne rend pas moins lourd le fait que tu modifies toute la base ou presque (dans le pire des cas) pour ajouter un et un seul élément, et ce quelque soit la position de l'élément.
Prennons un cas basique (je reprend l'exemple de shakpana pour illustrer), tu ajoutes un élément Level 2 Order 3 (à la fin de la première branche donc), aller modifier dans la foulée des éléments qui n'appartiennent même pas à la même branche me semble très moyen
Marsh Posté le 09-10-2005 à 16:22:05
Soit l'arborescence
Accueil
Php
Types
Entier
Chaine de caractère
Fonctions
Javascript
Intro
Java / Javascript
J'ai décidé de coder l'algo dont je parlais
Je precise que je suis loin de maitriser le php et qu'il y a certainement moyen d'optimiser pas mal d'instructions (concaténation, initialisation du tableau etc) [je code essentiellement en java]
Code :
|
Code :
|
EXEMPLE D'UTILISATION
----------------------------------------------------------
Arborescence avant insertion
02: Accueil
01: Php
04: Types
05: Entier
06: Chaine de caractère
03: Fonctions
07: Javascript
08: Intro
09: Java / Javascript
J'insere simultanement les rubriques suivantes (synthaxe: id,nom,id_parent,ordre)
10,isset(),3,1
11,trim(),3,1
12,chop(),3,2
13,Fonction,7,3
CELA DONNE
Bilan de construction
------------------------------
Opérations: 7 maj de positions
Appel récursif: 15
------------------------------
Arborescence apres insertions et construction
------------------
02: Accueil
01: Php
04: Types
05: Entier
06: Chaine de caractère
03: Fonctions
11: trim()
12: chop()
10: isset()
07: Javascript
08: Intro
09: Java / Javascript
13: Fonction
Marsh Posté le 10-10-2005 à 15:08:28
naceroth a écrit : En pratique, sur des gros trucs, tu utilises des caches, tu ne t'amuses pas à lire et recréer la structure à chaque accès aux pages... |
oui d'ailleurs, je pense à inclure un cache XML, un de ces quatres ...
naceroth a écrit : Que tu utilises 1, 2 ou X requête(s) ne rend pas moins lourd le fait que tu modifies toute la base ou presque (dans le pire des cas) pour ajouter un et un seul élément, et ce quelque soit la position de l'élément. (...) |
je suis, bien sûr, de ton avis en ce cas, sur une arbo de 200 items, çe devient lourd comme comportement ...
mais en ce cas, je m'interroge grave sur ton système de gestion, comment est géré l'ordre ?
- ordonancement par branche // nan pas valable car retrouves les mêmes limitations pour une branche de 200 items
- par items de même niveau par branche // ya un truc là, mais pas sans données annexes ou sans recursivité, ce qui était en fait mon système original au lieu d'avoir un liste ordonnée, j'avais une liste nivellée (genre : level 0, 1, 2, 3) que où je raccrochait chaque enfant en fonction de sa branche/niveau/parent i.e. à la méthode de Vlad' mais qui avait cette même limitation : l'ordre absolut
- ma, après j'vois pas bien comment gérer autrement cet(te saletée d')orde...
Marsh Posté le 10-10-2005 à 17:51:28
up, modification du script, post ci-dessus
shakpana ton algo est performant pour l'ajout d'un unique element, mais des lors ou qd tu veux ajouter plusieurs elements l'algo de parcours est bien meilleur.
je cite
Citation : shakpana a dit : la requête dont tu parles (celle que je n'aurais pas compter, mais dont je parle depuis longtemps, celle d'UPDATE order ), tu dois la faire aussi ... |
l'algo en profondeur update au pire (si on ajoute m elements en tete) n+m positions où n=nombre de rubriques dans la base
on peut tres bien construire une arborescence complete de n elements ca fera n+1 appels recursifs et n affectation de positions.
ton algo update au pire (si tu ajoutes m elements en tete) (n+1)+(n+2)+....+(n+m) positions
Pour etre plus clair [update set position = position +1 where position > 0] m fois.
Bref environ n*m mise a jours de positions
tu vois le hic
pour résumer:
si on veut ajouter plusieurs rubriques : insertion utilisant l'algo de parcours.
si on veut ponctuellement ajouter une rubrique à l'arborescence: ton algo.
Marsh Posté le 11-10-2005 à 11:47:27
vlad' a écrit : ton algo update au pire (si tu ajoutes m elements en tete) (n+1)+(n+2)+....+(n+m) positions |
ok, j'ai bien compris ton idée
mais ta parcours_arbo()
tu fais un foreach() qui mène à un sql(UPDATE) pour maintenir ton champ position, donc
x étant le nombre d'éléments en dessous du point d'insertion,
toi tu fais m+x sql(UPDATE) qui touchent m+x éléments
moi je fait 2 sql(UPDATE) qui touchent en fait m+m+x éléments - cf plus bas pour mon process
attention ! à ce point je ne dis pas mieux ou moins bien ...
car en si on remonte 200 el. de 300 places
je touche 700 el. contre toi qui en touches 500 el.
mais je ne puis dire honnêtemment si
500 sql_queries pour 500 éléments
est mieux que
2 sql_queries pour 500 + 200 éléments
même si j'ai une grande tendance à penser que 500 appels à une fonction pour 500 opérations SQL c'est plus long que 700 opérations en 2 appels*
*EDIT: toutes ces 2 queries n'affecte qu'un seul champ : "order"
à ce point, je pense qu'un bench va s'imposer, car au final les deux méthodes proposent les mêmes fonctionnalités ...
pour décrire ma mise à jour, je la fait ainsi
1. requête de décalage des éléments suivant le point d'insert.
2. requête de décalage des éléments à déplacer
donc en gros, c'est du décalage d'offset ..
au lieu de faire "m*n requêtes", donc pour ça j'ai besoin de connaitre
1. ordre du noeud précédent le point d'insert
2. ordre du 1er el. à déplacer
3. ordre du dernier el. à déplacer (dernier enfant du 1er el. à déplacer)
que j'obtiens par le formulaire de mise à jour
et il n'y a pas de différence entre la maj et l'ajout (sauf les multiples sql(INSERT))
donc au final, et comme je le disais dans mon post précédent, et pointé par naceroth, ce qui nous bloque (enfin ce qui bloque ces deux méthodes) c'est la gestion de cet ordre absolut ... mais là je vois pas du tout comment s'en passer ...
en tout cas merci de ces échanges, c'est bien cool
Marsh Posté le 11-10-2005 à 12:41:54
tu parles de m insertions d'elements qui repectent tous une propriété essentiellle : elle sont toutes devant toutes les autres (en tete) ca te permet de deplacer de m place les x elements du dessous. Je t'ai tendu une perche, c'etait pas le bonne exemple en fait.
Disons que tu veux ajouter m elements qui n'ont vraisemblablement rien en commun, tu ne peux donc pas rusé (point d'insertion differents pour chaque element). il faudra que tu ajoutes les m elements un à un en decalant a chaque fois correctement. soit bien cette fois ci m requetes [update set pos =pos + 1 where pos > element dans m]
Marsh Posté le 11-10-2005 à 14:10:25
oui, précisement, je parlais du _déplacement_ d'un branche, vers un autre emplacement ...
donc un UPDATE et non un INSERT
> Disons que tu veux ajouter m elements qui n'ont vraisemblablement rien en commun
oui en ce cas je te suis, tu as raison
pour chaque INSERT qui ne constitue pas une branche, je devrais faire mon process complet
mais je vois pas la différence fondamentale, car tu as aussi un champ "position" ordre absolut à maintenir pour chaque INSERT - comme ouam, je m'explique :
c'est un cas que j'envisage pas dans mon process, chaque INSERT est soit une entrée unique, soit un arbre, mais si je devais l'envisager, j'aurais autant de sql_query que neccessaire ce qui revient à faire pour une insertion de 100 el. à l'offset 100 et 100 el. à l'offset 200 sur une struct de 300 => d'abord 2 UPDATE table SET order = order + 100 + taille_de_l_insert_suivant_en_ordre_inverse WHERE order > point_d_insert_en_cours AND order < ordre_du_dernier_insert - 1 en commençant par le dernier et les 200 INSERT complets
donc le minimum requis sans itération, sans récursion, en 202 requêtes ...
tout ça via une fonction spécifique genre add_multi()
hélas hé-oui, cette fois je touche autant de records que toi, avec beaucoup moins* de requêtes !?!
donc je touche tous les éléments en dessous du premier point d'insert., et tu est obligé le faire aussi car tu dois réécrire ta 'position' ...
* bah oui, là tu en fera 200 + 200
donc j'ai bien eu ta perche sur ce coup là ...
Marsh Posté le 11-10-2005 à 17:11:54
moi je parle d'inserer par exemple 100 elements a des offset differents et non pas au meme. donc avec ton algo 100 fois [update set pos=pos +1 where pos > x] pour a chaque fois decaler de 1 tous les trucs en dessous.
dans cette situation l'algo de parcours fera ca en ((n-position du parent le plus haut)+200) requetes update set position where id=x.
Pour etre plus clair et en arrondissant : ca ne revient vraiment pas au meme de faire n requetes qui mettent à jour une unique position et n requetes qui mettent à jour m positons !
MISE EN SITUATION
------------------------------
ARBORESCENCE DE DEPART
-----------------------------
02: Accueil
01: Php
04: Types
05: Entier
06: Chaine de caractère
03: Fonctions
07: Javascript
08: Intro
09: Java / Javascript
INSERTION DES ELEMENTS SUIVANTS
10,Fonctions,7,2
11,Blabla,8,1
12,Differences,9,1
12,Maths,10,1
13,random(),12,1
14,round(),12,1
15,Dates,10,2
16,getDate(),15,1
17,getDay(),15,2
RESULTAT
----------------------------------
Bilan de construction
Opérations: 10 maj de positions
Appel récursif: 18
Arborescence
02: Accueil
01: Php
04: Types
05: Entier
06: Chaine de caractère
03: Fonctions
07: Javascript
08: Intro
11: Blabla
10: Fonctions
15: Dates
16: getDate()
17: getDay()
09: Java / Javascript
12: Differences
14: round()
13: random()
-----------------------------------------------
mais revenons a ton cas particulier (plusieurs ajouts au meme endroit).
on est d'accord que pour ton exemple tu fais 2 requetes, la on je fais m requetes.
mais il n'y a pas de difference au niveau du nombre de mise a jour de positions
ce n'est parce que c une requete que ca coute 1
qd tu fais un update set pos= pos + y where pos > x, c en fait un boucle de 'update set pos = pos + y' pour les lignes respectant le where donc autant que moi.
j'ai bien compris ton argument : une requete qui modifie tout en meme temps est mieux que n requetes qui modifie un seul element c sur!
c pour cela que je dis que dans le cas d'un ajout unique (et aussi je n'y avait pas pensé, de plusieurs ajouts sur un meme point d'insertion ton algo est meilleur. mais des qu'il s'agit d'ajouter des elements a des parents differents c fini.
j'ajoute que pour reserrer l'ecart de performance entre ton algo et le mien,dans ce cas precis (ajouts sur meme point d'insertion) on peut mettre a jour les positions a la fin du parcours.
on stocke l'id et sa position dans un tableau et a la fin on met a jour en quelques requetes toutes les positions!
cad par exemple faire 20updates par query. mysql_query(update.....;update.....;......;update...;);
on ferait donc par exemple pour 300updates 15requetes ce qui est tres raisonnable.
bref l'ajout sur un meme point d'insertion reste un cas particulier, dans la pratique on veut pouvoir ajouter les elements comme ca nous chante.
donc l'algo de parcours est vraisemblablement l'ideal car polyvalent, il assure une mise a jour coutant au pire n+m mise a jour de positions pour m insertions (ou m est non borné!).
tu sais moi j'invente rien, c mon cours d'algorithmie des arbres, le parcours en profondeur est l'algo le meilleur pour travailler sur les arborescences. tu auras beau retourner le truc dans tous les sens, des lors que les ajouts ne touchent pas le meme parent tu ne pourras pas faire mieux
je dirai que c fut une sacrée etude!
j'ai revisé mes connaissance en algoritmie avec tout ce travail :p
Marsh Posté le 12-10-2005 à 00:51:21
vlad' a écrit : moi je parle d'inserer par exemple 100 elements a des offset differents et non pas au meme. donc avec ton algo 100 fois [update set pos=pos +1 where pos > x] pour a chaque fois decaler de 1 tous les trucs en dessous. |
ok, je reconnais avoir un peu tordu ton argument ... en ne prenant que 2 points d'insert ...
encore une fois mon système utilisait d'abord la méthode récursive, et en me prenant bien la tête, j'ai pondu cette soluce qui m'a permis de réduire drastiquement le nb de lignes de code, et de donc de gagner quelques cycles processeurs non-négligeable ... sans toucher aux fonctionnalités finales
mais effectivement et clairement, ce n'est pas une solution orthodoxe au sens théorique ...
vlad' a écrit : tu sais moi j'invente rien, c mon cours d'algorithmie des arbres, le parcours en profondeur est l'algo le meilleur pour travailler sur les arborescences. tu auras beau retourner le truc dans tous les sens, des lors que les ajouts ne touchent pas le meme parent tu ne pourras pas faire mieux |
oui, mais comme je te l'ai dis ce n'est pas mon propos de dire qu'elle est meilleur, loin de là, je soutenais juste que cette méthode est aussi valable et qu'elle n'en est pas moins performante, toute choses étant égales par ailleurs (j'aime bien cette phrase vide de sens) elle a ses défauts, mais comme la récursive a les siens ... en tout cas en relation avec des requêtes sql derrière ...
Et pour l'anecdote, moi pas de cours d'algorithmie, me suis formé sur le tas, sans aucun mérite et avec beaucoup de café
vlad' a écrit : je dirai que c fut une sacrée etude! |
bah oui a qui le dis-tu, et je ne desespère pas une fois avoir terminé qlqs projets en cours de faire 2 ptites classes reprenant mon code en cours et un mélange de mon ancien système + tes modifs si neccessaire pour en faire qlq chose d'utile, et pis un peu de benchmark qd même ...
et pour voir si j'arrive à m'affranchir de cet `order` ... advienne que pourra
Marsh Posté le 12-10-2005 à 01:15:05
Citation : Et pour l'anecdote, moi pas de cours d'algorithmie, me suis formé sur le tas, sans aucun mérite et avec beaucoup de café |
tu m'etonnes, moi je cumul l'apprentissage scolaire et personnel.
Citation : j'ai pondu cette soluce |
franchement ct pas bete du tout et sans mes cours j'aurais surment fait comme ca.
Citation : réduire drastiquement le nb de lignes de code, et de donc de gagner quelques cycles processeurs non-négligeable |
là tu te leurres mais arretons en là pour les chamailleries
Citation : mon code en cours et un mélange de mon ancien système + tes modifs si neccessaire pour en faire qlq chose d'utile |
Clair, je suis sur qu'en melangeant le parcours en profondeur recursif, la modelisation en classe, ta structure xml et un feuille xsl ca le ferait bien
Marsh Posté le 12-10-2005 à 10:14:46
<shakpana> j'ai pondu cette soluce
<Vlad'> franchement ct pas bete du tout et sans mes cours j'aurais surment fait comme ca.
mais enfin ?!? je te répètes que ma 1ère méthode était celle que tu as présenté tout le long du thread ...
spa possible, ça ! donc j'ai déjà fait la méthode récursive, là même que la tienne !
<shakpana> réduire drastiquement le nb de lignes de code, et de donc de gagner quelques cycles processeurs non-négligeable
<Vlad'> là tu te leurres mais arretons en là pour les chamailleries
mon temps de génération de page est tombé de quelques pourcent pas négligeable ...
donc j'ai _vu_ le bénéfice, et ne me leurre pas sur ce point précis ...
- fait le test de 1000 sql_query sur 1 record contre 1000x1 sql_query sur 1 record, parce que même si tu dis l'avoir compris, je suis pas sûr que tu réalises l'importance de cette nuance, un appel à une fonction est couteux
- la génération de l'arbre* est fait en 5 lignes répéter par n items
- *de plus tu ne gères pas cet arbre : le tableau multidimmensionel; alors c'est le but que je recherche; tu te contentes d'afficher direct la liste avec l'indentation, alors que j'ai besoin de sortir un tableau à n niveaux
mais ok restons en là ... sinon on est repartit pour un tour
<shakpana> mon code en cours et un mélange de mon ancien système + tes modifs si neccessaire pour en faire qlq chose d'utile
<Vlad'> Clair, je suis sur qu'en melangeant le parcours en profondeur recursif, la modelisation en classe, ta structure xml et un feuille xsl ca le ferait bien
vi, c'est déjà fait, ma classe actuelle output soit via DOM, soit via à_la_mano, et recursion-free
reste un système de cache XML, et pour XSL à voir ...
mais je sortirais l'essentiel pour en faire deux classes de base lecture/écriture/sortie d'un tableau multidimm./sortie d'une zone de liste HTML <ul><li>/sortie DOM dont une recursive, et l'autre non
to be continued ...
Marsh Posté le 12-10-2005 à 16:40:36
shakpana a écrit : |
En simplifiant un max (parce que la recréation de l'arbre passe en partie par des fonctions créées spécialement pour, le tout dans une dll), on se fiche complètement de l'ordre absolu dans la db.
Bon, faut remettre ça dans le contexte : un gros arbre qui une fois normalement rempli va subir moins d'insert/delete que de déplacements d'éléments/branches. On s'est donc demander comment optimiser les déplacements et il est assez clair que gérer un ordre absolu est très moyen pour les raisons évoquées plus haut. On a à la place choisi un ordre relatif, certes un poil plus lourd en terme de code à la lecture (difficile à estimer, vu que tout n'est pas du php pur), mais nettement plus souple en mise à jour : si on déplace l'élément X, on doit modifier l'élément qui précède l'ancienne position de X et l'élément qui précède la nouvelle position de X ainsi que X lui même.
Pour reprendre partiellement la mise en situation de Vlad' et en tenant compte de l'optimisation de base des insertions, si on devait ajouter en une seule fois les éléments 10, 15, 16 et 17 (la branche Fonctions de Javascript), on aurait 4 inserts et 1 update (pour l'ajout de Fonctions), sauf erreur de ma part.
Marsh Posté le 12-10-2005 à 18:17:12
naceroth a écrit : En simplifiant un max (parce que la recréation de l'arbre passe en partie par des fonctions créées spécialement pour, le tout dans une dll), on se fiche complètement de l'ordre absolu dans la db. |
ah ok, je vois mieux maintenant, merci de ta réponse.
j'avais exploré l'interdépendance un moment, mais apparament pas assez ...
> (...) on aurait 4 inserts et 1 update (...)
et on ne toucherait que 5 éléments ... et 2 pour un déplacement de la même branche ...
vi vi vi, ben je vais retourner à mes crayons ...
et je vais poser ça par écrit, pour en sortir ce que j'ai dit, mes ptites classes de gestion ...
naceroth, merci
Marsh Posté le 12-10-2005 à 18:43:02
naceroth j'ai pas vu trop de quoi tu parlais mais il me semble que ca rejoint un autre idée a laquelle j'ai pensé.
gérer l'ajout, la modification, la suppression et le deplacement avec un graphe.
c'est à dire un objet Rubrique du genre
Rubrique
-----------------
int etiquette;
string nom;
Rubrique suivants; //rubriques de meme niveau
Rubrique enfants; //sous rubriques
-----------------
ajouter_enfant()
ajouter_suivant()
exporter_xml()
importer_mysql()
edit : les cycles sont utiles que si on veut ordonné les rubriques de meme niveaul
pour
Accueil
Php
Types
Fonctions
Javascript
Types
Fonctions
On sauvegarderait uniquement chaque rubrique avec leurs etiquette, nom et parent dans la bd
une methode importerait les données pour creer le graphe.
pour terminer une methode creerait le xml
Marsh Posté le 07-10-2005 à 23:06:06
bonjour,
j'essaye de faire un menu déroulant issu d'une requete sur une bd pour afficher l'arborescence du site.
dans la base chaque rubrique à un ID "secteur" "id_rubrique" et"id_parent"
une rub à la racine a donc id secteur =0 id parent =0 et id rubrique=1(par ex)
une sous rub de celle ci aura id secteur =0 id_parent=1 et id_rubrique=2 (vous aviez compris !)
et je voudrais afficher dans le menu déroulant que l'arborescence soit respectée avec un décallage horizontal pour le titre des rub selon le niveau ou elles se situent ... je pense en plus que cela doit-êtr epossible de faire une seule requete en boucle pour que selon qu'elle trouve des descendant elle continue..
j'ai fait un truc qui marche mais qui n'est surement optimisé et qui ne permet pas d'avoir l'ordre .. j'essaye selon l'ORDER BY .. mais j'y arrive pas
çà donne :
<option value="0,,racine" selected>rubriques :</option>
<?php $res = mysql_query("SELECT id_rub,id_secteur,id_parent,rub_titre FROM $tbl_rubs ORDER BY id_parent ASC" ) ;
while( $ligne = mysql_fetch_object($res) )
{
echo "<option value=\"$ligne->id_secteur,$ligne->id_rub,$ligne->id_parent\">- ".stripslashes($ligne->rub_titre)."" ;
}
echo "</select> ";
?>
une idée pour m'aider ?
merci
antoine