Forum Programmation.autre Sauvegarder et ressortir un arbre, typiquement les commentaires de linuxfr

Posté par  (site web personnel, Mastodon) .
Étiquettes : aucune
5
26
avr.
2012

Bonjour,
je me demandais comment étaient gérés les commentaires dans linuxfr.

En gros je recherchais comment coder un arbre que l'on peut ressortir en une seule requête et sans avoir à faire de tri "complexe" ni avoir des id de la mort.

En cherchant sur le net des algos, j'ai rien trouvé de flagrant, du coup j'ai regardé le système de commentaires de linuxfr.

Merci le codage mvc et propre, en 2 minutes j'ai pu lire les fichiers qui m'intéressaient le plus mais je suis pas très familier de ruby et je n'ai pas été trop loin dans l'analyse du code.

pouvez-vous m'expliquer ce que fait cette fonction ?

# All the magic is here!
  def self.please_make_me_a_tree(comments)
    roots, threads = [], []
    comments.each do |comment|
      thread = self.new(comment)
      if comment.root?
        threads = []
        roots << thread
      else
        (threads.length - comment.depth).times { threads.pop }
        threads.last << thread
      end
      threads << thread
    end
    roots
  end

De plus, une chose primordiale qui va avec est de comprendre ce que contient la colonne materialized_path d'un commentaire.
https://github.com/nono/linuxfr.org/blob/master/app/models/threads.rb

Et sinon, pourriez-vous m'indiquer un endroit qui contiendrait de la doc sur la sauvegarde d'arbre ? Je suppose qu'il y a pléthore de réflexions sur le sujet.

  • # Sauvegarde d'arbre

    Posté par  (site web personnel) . Évalué à 2.

    http://stackoverflow.com/questions/51783/how-to-serialize-a-graph-structure

    Un arbre, c'est un graph sans cycles et sans partage, c'est super simple…
    Et je suis sûr que ruby possible une lib pour sérialiser/lire des objets en mémoire…

  • # The simplest(?) way to do tree-based queries in SQL

    Posté par  (site web personnel) . Évalué à 4.

    Ça date de 2010, mais je l'avais marqué dans mon agrégateur pour ne pas le perdre: http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html

  • # 3 façons

    Posté par  (site web personnel) . Évalué à 8.

    Pour enregistrer des arbres dans une base de données, il existe 3 grandes façons de faire.

    La première consiste à avoir un champ parent_id sur chaque élément. C'est celle que l'on rencontre le plus souvent et pourtant, c'est probablement celle qui est la moins intéressante et la moins performante.

    La seconde technique est celle utilisée par LinuxFr.org. On la retrouve généralement sous le nom de materialized path. Ça consiste à avoir sur chaque enregistrement un champ path avec la liste des identifiants des parents. Par exemple, si le commentaire 12 a pour parent le commentaire 7, et que le commentaire 7 a pour parent le commentaire 3, alors le commentaire 12 aura pour path 3.7.12 (en fait, pour LinuxFr.org, on remplit les ids sur une taille fixe plutôt que d'utiliser un séparateur, donc ce serait plutôt 00000003000000700000012).

    Enfin, la troisième manière est ce que l'on appelle les nested sets. Ça consiste à parcourir un arbre et à donner des numéros à chaque élément. On part de la racine et on fait le tour. Quand on passe à gauche, on remplit le champ lft (left est un mot-clé réservé) et quand on repasse à droite, on remplit le champ rgt (right) :

                            (1) Commentaire n°1 (10)
                           /               \
              (2) Commentaire n°3 (7)   (8) Commentaire n°5 (9)
                 /           \
(3) Commentaire n°7 (4)  (5) Commentaire n°9 (6)

ID | lft | rgt |
 1 |   1 |  10 |
 3 |   2 |   7 |
 5 |   8 |   9 |
 7 |   3 |   4 |
 9 |   5 |   6 |

    Il devient aussi alors très facile de retrouver tous les commentaires d'un même fil de discussions. Il suffit de prendre tous ceux qui ont un lft plus grand que celui du commentaire parent et un rgt plus petit que celui du commentaire parent.

    • [^] # Re: 3 façons

      Posté par  (site web personnel) . Évalué à 1.

      A noter que l'utilisation d'une méthode ou d'une autre peut dépendre aussi du SGBD utilisé.

      Par exemple dans Oracle il y a des moyens de manipuler des arborescences avec la première méthode avec les clauses START WITH et CONNECT BY : http://www.adp-gmbh.ch/ora/sql/connect_by.html .

      Dans la norme SQL 1999 il y a les Common Table Expressions qui semble permettent de faire de même mais je ne connais pas. Ca a l'air supporté par SQLServer http://sqlpro.developpez.com/cours/sqlserver/cte-recursives/ et PostgreSQL http://wiki.postgresql.org/wiki/CTEReadme

      Par contre pour MySQL, rien de tout cela semble-t-il.

      Pour le "Nested Sets" modèle c'est sympa pour la consultation mais pour l'insertion ou la suppression ça peut devenir lourd. Quand je parcours rapidement http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ j'ai un peu peur :)

      L'association LinuxFr ne saurait être tenue responsable des propos légalement repréhensibles ou faisant allusion à l'évêque de Rome, au chef de l'Église catholique romaine ou au chef temporel de l'État du Vatican et se trouvant dans ce commentaire

      • [^] # Re: 3 façons

        Posté par  . Évalué à 1.

        je connaissais les "Nested Nets"

        la méthode des "Closure Tables" indiquée dans le lien donné par Amand Tihon semble avoir pour avantage de ne nécessiter qu'1 requête pour ajouter/supprimer une relation père/fils

        pour le reste des avantages/inconvénients, je ne suis pas assez calé pour juger

        je ne serai pas étonné qu'une méthode soit plus adapté pour les SGBD (voire un SGBD particulier) et qu'une autre méthode soit plus facile/performante lorsqu'on l'emploi dans une boucle d'un langage autre que SQL (genre php/python/ruby…)

        Envoyé depuis mon Archlinux

    • [^] # Re: 3 façons

      Posté par  . Évalué à 2.

      on remplit les ids sur une taille fixe plutôt que d'utiliser un séparateur, donc ce serait plutôt 00000003000000700000012

      This bunch of zeros should be enough to any use troll.

      Pas utiliser de séparateur, c'est pour une question de performances ?

      • [^] # Re: 3 façons

        Posté par  (site web personnel) . Évalué à 3.

        This bunch of zeros should be enough to any use troll.

        Avant d'être à court de chiffres, on aura un autre problème : la clé primaire a aussi une limite (232, si je me souviens bien).

        Pas utiliser de séparateur, c'est pour une question de performances ?

        Oui, ça permet de récupérer tous les commentaires sur un contenu déjà triés par MySQL (ORDER BY path). Il ne reste plus qu'à utiliser le code cité initialement pour reconstruire l'arbre.

        Avec un séparateur, si tu as un commentaire dont le path est 12.99, il arrivera après celui avec 12.100 comme path alors qu'il lui est pourtant antérieur.

        • [^] # Re: 3 façons

          Posté par  (site web personnel) . Évalué à 1.

          Il n'y a pas moyen d'avoir un tri numérique, comme avec la commande sort -n plutôt que simplement sort ?

          Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/

          • [^] # Re: 3 façons

            Posté par  (site web personnel) . Évalué à 2.

            En bidouillant un peu, on peut y arriver pour le premier niveau mais, à ma connaissance, ce n'est pas possible pour ce qui se trouve après le premier séparateur.

            • [^] # Re: 3 façons

              Posté par  (site web personnel) . Évalué à 1.

              Je viens de tester, à part si on convertit tous les nombres en chaînes avec plein de zéro bouche-trou devant, sort ne marche pas. Donc on retombe sur la situation des chaînes pleines de zéro.

              Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/

        • [^] # Re: 3 façons

          Posté par  . Évalué à 2.

          Merci pour cette explication.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.