Reconstruire un arbre depuis une table de données - Page 1

Hum...
Je cherche la façon la plus efficace de reconstruire un arbre depuis une table de données dans laquelle j'ai un identifiant de noeud, et le numéro du parent (s'il existe) - et j'ai évidemment d'autres informations spécifiques à chaque noeud.
J'étais parti par faire ça avec des requêtes SQL récursives (mes données sont dans une base de données), mais la multiplication des requêtes (mon arbre est assez profond et j'ai des quantités de données de l'ordre du million d'enregistrements) rend la chose extrêmement lente.
J'ai vu qu'il existait la structure WITH ... RECURSIVE en SQL, mais je ne suis pas certain que ça me permette de faire ce que je veux.
Du coup, pour l'instant, j'ai décidé de travailler avec des dumps partiels (pour ne pas prendre trop de mémoire d'un coup, même si ça ne semble pas être problématique de charger mon million de lignes d'un coup) et de faire un traitement par script pour reconstruire mon arbre.

Le souci, c'est que j'en arrive à multiplier les parcours de mon tableau pour reconstruire l'arbre, du coup je n'ai pas l'impression d'être parti dans un système optimal. Donc si quelqu'un connaît un algo générique (ou a déjà utilisé WITH... RECURSIVE et me dit que c'est LA solution).

Bon, j'ai fait un peu de récursivité, ça a l'air de fonctionner plutôt bien.

Encore une victoire de canardsouane!

Par contre, ça prend 10 minutes à traiter pour 50000 lignes, du coup c'est ingérable Je vais devoir trouver une autre modalité d'enregistrement de mes données :/
À mon avis, ça va se terminer par des sérialisations à la sauvage !

Vu de loin, et sans porter d'attention plus que ça aux performances, j'aurais chargé les données de la base, et bouclé dessus en retirant de la liste les éléments qui sont insérés dans l'arbre tant que la liste n'est pas vide, sachant qu'évidemment lors des premiers tours de boucle plein d'éléments devront être sautés parce que leurs parents ne seront pas référencés.

monArbre= vide
maListeIssueDeSQL
tant que maListeIssueDeSQL n'est pas vide
   element= maliste.removeFirstElement();
   node= monArbre.find(element.parent)
   if node trouvé
      node.addChild(element)
   else 
      maListeIssueDeSQL.pushback(element)
   end
fin tant que

Moi je dit, plante les graines dans le sol et attend

L'arbre viendra à qui sait l'attendre !

./5 éventuellement tu peux ajouter une vérification au cas où il y a au moins un élément orphelin dans ta liste, ça évitera une boucle infinie

Pen² > Ouais c'est exactement ce que je fais, en fait. Ca fonctionne très bien sur un petit nombre d'éléments, mais là c'est too much.
Du coup, je pense faire un peu le bourrin, et enregistrer tout en BDD (ce sont des logs assez complexes) uniquement pour consultation en cas de problème (puisque ça ajoute une entrée à quasi chaque événement), par contre pour une consultation classique si le processus est allé jusqu'au bout sans planter, je vais simplement sérialiser mon objet principal (qui contient toutes mes données) à la fin du traitement, et stocker cette donnée dans un fichier.

Nil (./8) :
Ouais c'est exactement ce que je fais, en fait

Nil (./2) :
j'ai fait un peu de récursivité

Pourtant ma boucle n'est pas récursive du tout ?

Pourquoi ne pas recuperer toutes les donnes dans un tableau et generer l'arbre dans le code l'utilisant plutot que faire 150^9000 requetes?

table = "SELECT * FROM TABLE;"

et puis

doit(table, entry)
{
l = table[entry].left;
r = table[entry].right;
if (l) doit(table, l)
if (r) doit(table, r)
faire_quelquechose_avec_le_noeud_en_cours()
}


et paf pasteque

En fait, je fais le "monArbre.find" de façon récursive tout au long de mon processus (je ne peux pas faire le .find sans retraverser complètement l'arbre depuis le début, ce qui n'est pas du tout optimal).

Voilà ce que j'ai, de mon côté :

monArbre = vide
quiEstMonPere = vide
maListeIssueDeSQL

pour chaque élément de ma liste
	quiEstMonPere[idFiston] = idPapa
	maListeParID[idFiston] = mon élément en cours
	monArbre = construireArbre(quiEstMonPere, idAncetre, maListeParId)

---

fonction construireArbre(quiEstMonPere, idAncetre, maListeParId)
	monArbrePartiel = vide
	pour chaque élément de quiEstMonPere (idPapa, idFiston)
		quiEstMonPere[idFiston].supprime
		si idPapa = idAncetre
			monArbrePartiel[idPapa][donnees] = maListeParId(idPapa)
			monArbrePartiel[idPapa][enfants] = construireArbre(quiEstMonPere, idPapa, maListeParId)
	retourner monArbrePartiel

Godzil (./10) :

doit(table, entry)
{
l = table[entry].left;
r = table[entry].right;
if (l) doit(table, l)
if (r) doit(table, r)
faire_quelquechose_avec_le_noeud_en_cours()
}

Je fais effectivement une requête unique (vu les résultats pourris que j'ai avec des requêtes pour retrouver les enfants de chaque parent). Et c'est pas un arbre binaire, du coup je ne peux pas savoir pour chaque parent qui est mon enfant puisqu'il peut en avoir plusieurs (sinon, effectivement, ça aurait été beaucoup plus simple !)

Ben c'est pas super complique:

doit(table, entry)
{
current = table[entry]
foreach(child_id, child_count(current))
{
doit(table, current.childs[child_id])
}
faire_quelquechose_avec_le_noeud_en_cours()
}

Et pasteque!

(oui, c'est ma fonction construireArbre sauf qu'elle met 12 minutes pour 50000 entrées et que j'en ai près d'un million à traiter )

Pourquoi pas comme ça (pseudo-code, un peu entre le Java et le C++, à toi d'adapter)?

class Node {
  int id;
  int parentId;
  … // autres données
  Node * parent;
  Vector<Node *> children;
  // constructeur
  Node(id, parentId, …) {
    this->id = id;
    this->parentId = parentId;
    …; // autres données
    this->parent = null;
    this->children = Vector<Node *>(); // vecteur vide
  }
};
HashTable<int, Node *> nodes;
ResultSet results = db.query("SELECT * FROM MYTABLE;");
for (Result result : results) {
  Node *node = new Node(result.id, …);
  nodes.put(result.id, node);
}
for (Node *node : nodes.values()) {
  node->parent = nodes.get(node->parentId);
  node->parent->children.append(node);
}

Ça marche même si ta clé primaire n'est pas un entier tant qu'elle est hachable.

Nil (./11) :
En fait, je fais le "monArbre.find" de façon récursive tout au long de mon processus

Ah mais c'est ça le problème, la complexité est mauvaise, il faut mettre ça dans une map quelconque qui te trouve ton résultat rapidement. J'avais hésité à l'écrire explicitement, désolé ^^

Ok, je vais essayer d'approfondir, du coup (Cela dit, il me faut moins de 3 secondes pour récupérer les données déjà sous la bonne forme avec une dé/sérialisation ^^)