Faux arbres : utiliser l’indentation pour une UI plus simple

 (ratfactor.com)
4 points par GN⁺ 2024-01-01 | 1 commentaires | Partager sur WhatsApp
  • Même si une UI hiérarchique semble nécessaire, la première chose à vérifier est si les données doivent réellement avoir une relation parent-enfant, ou si elles doivent seulement en avoir l’air
  • Si un vrai arbre n’est pas nécessaire, on peut représenter la structure à l’écran uniquement avec l’ordre de tri absolu de toute la liste et une valeur indent, au lieu d’un ID parent
  • L’éditeur du jeu Hiss trie des noms comme banana.eat, puis affiche en retrait ce qui suit le point (.), créant une UI qui ressemble à un namespace
  • Cette approche se rapproche davantage d’une édition façon traitement de texte, où l’utilisateur déplace des éléments vers le haut ou le bas et les indente ou désindente, ce qui réduit la charge liée à une structure de données en arbre
  • S’il faut réellement interroger ou maintenir les relations entre éléments, il faut un vrai modèle en arbre plutôt que de bricoler avec l’indentation ou des symboles dans des chaînes

Une liste qui ressemble à un arbre, sans en être un

  • Quand on veut afficher dans une application une liste dynamique comme Foo, Bar sous forme de vue en arbre, on imagine en général une structure où chaque élément pointe vers son parent
  • Dans une base de données relationnelle, on peut par exemple stocker l’ID du parent dans une colonne parent
    • le parent de Foo est null
    • le parent de Foo 1 est Foo
    • le parent de Foo 1.a est Foo 1
  • Pour récupérer ce type de données arborescentes en SQL, il peut être nécessaire d’utiliser une approche comme les CTE récursives
  • Mais dans beaucoup de listes, l’important n’est pas tant la relation réelle que l’apparence organisée pour la lecture humaine

Stocker une valeur d’indentation comme donnée

  • Si une vraie relation parent-enfant n’est pas nécessaire, on peut stocker la liste avec seulement les champs suivants
    • id
    • sort
    • indent
    • name
  • sort ne représente pas l’ordre interne des sous-éléments, mais l’ordre absolu de toute la liste
  • indent représente directement la quantité d’espace à placer devant l’élément, ce qui simplifie le rendu à l’écran
  • L’UI d’édition peut elle aussi devenir plus simple qu’une manipulation d’arbre
    • l’utilisateur peut déplacer un élément vers le haut ou le bas
    • il peut l’indenter ou le désindenter
    • si besoin, on peut ajouter des règles simples pour imposer une indentation correcte
  • Au final, l’expérience se rapproche davantage de l’édition d’une liste dans un traitement de texte que de la manipulation directe d’une structure de données issue d’un manuel d’informatique

Le faux namespace de Hiss basé sur le point (.)

  • L’éditeur de jeu d’aventure textuel Hiss affiche dans son UI des noms comme banana, banana.eat, banana.peel comme s’ils étaient hiérarchiques
  • Cela ne signifie pas que HissScript implémente réellement une fonctionnalité de namespace
  • Le fonctionnement est simple
    • les noms d’objets sont triés par ordre alphabétique
    • s’il y a un point (.) dans le nom, la partie avant le point est retirée
    • la partie restante est affichée avec une indentation
  • La logique essentielle du code d’exemple suit la même idée
    • things.keys est trié
    • si un nom contient un point, il est affiché avec indentation après suppression de la partie avant le point
    • s’il n’y a pas de point, le nom est affiché tel quel
  • Quelques lignes supplémentaires sont ensuite ajoutées pour vérifier si un élément « parent » ayant le préfixe donné existe
  • Il est possible d’ajouter des niveaux d’imbrication arbitraires, mais cela attend qu’un besoin réel apparaisse
  • Cette UI qui ressemble à un namespace est importante pour la personne qui organise le jeu, mais n’a pas de signification particulière pour l’éditeur de jeu ni pour le joueur
    • un nom contenant un point reste simplement un nom
    • la partie qui ressemble à un namespace sert seulement à maintenir l’unicité du nom

Des cas semblables à des arbres, gérés comme des listes plates

  • Dave Long propose, avec ses « vrais arbres low-tech », une manière de stocker chemins et informations dans une liste plate
  • L’idée est proche de l’exemple banana.eat
  • On peut imaginer une liste de chemins comme dans la sortie de find
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • Si l’on a besoin d’un parcours en profondeur, il suffit de trier les chemins par ordre lexicographique
  • Si l’on a besoin d’un parcours en largeur, on peut inverser les chemins selon le séparateur, ajouter des éléments vides pour aligner les profondeurs, puis trier
  • Cet exemple sert à illustrer le concept ; en pratique, il est plus naturel de découper les lignes selon le séparateur puis de les traiter sous forme de tableau
  • Les listes plates sont globalement faciles à manipuler, et lorsque c’est possible, cette approche consistant à mettre les éléments dans des plain old lists est préférable

La métaphore du scrapbook étalé au sol

  • Dans un projet personnel de scrapbook, on peut étaler au sol des photos, notes, cartes postales, tickets et autres, puis former des groupes
  • Pour un humain, les relations entre groupes peuvent sembler évidentes, mais le sol lui-même n’impose aucun mécanisme physique pour forcer ces relations
  • Le cœur de la métaphore est que les relations représentées et les relations structurelles réelles peuvent être différentes
  • De la même façon, dans une liste UI, une disposition qui semble hiérarchique pour l’humain ne signifie pas forcément une hiérarchie réelle dans le modèle de données interne

Quand un vrai arbre est nécessaire

  • Les approches fondées sur l’indentation ou sur des symboles dans les chaînes doivent être fortement adaptées au contexte et, dans un cadre de programmation général, risquent d’être considérées comme du bricolage
  • S’il faut réellement connaître les relations entre éléments, il faut utiliser une vraie structure en arbre adaptée au modèle de données, comme un ID parent ou une table de jointure parent-enfant
  • Si l’on doit classer un grand projet de recherche avec un niveau d’organisation comparable à des classeurs physiques et des dossiers, « l’approche au sol » n’est pas adaptée
  • Si, dans un projet, il faut un jour connaître réellement les relations entre éléments, imiter la structure avec l’indentation ou le nombre de symboles dans une chaîne risque de devenir une voie douloureuse pendant toute la durée de vie et la maintenance du projet

À lire aussi

1 commentaires

 
GN⁺ 2024-01-01
Avis de Hacker News

  • La première approche, celle qui ressemble à « c’est évidemment la seule façon de faire », s’appelle une liste d’adjacence (adjacency list).
    La deuxième « méthode beaucoup plus simple », je n’ai pas souvenir de l’avoir déjà vue ; elle a des inconvénients évidents, mais semble suffisante dans certains cas.
    La troisième, la « mise en espace de noms », s’appelle un chemin matérialisé (materialized path) ; il existe aussi les ensembles imbriqués (nested sets) comme autre façon de représenter un arbre : https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    À l’époque où les gens prenaient les bases de données relationnelles au sérieux, tout cela était bien connu ; on trouve par exemple des articles comme http://www.dbazine.com/oracle/or-articles/tropashko4/
    Aujourd’hui, cela ressemble à un savoir oublié.

    • L’un des moments que je détestais le plus dans un ancien boulot, c’était quand je m’épuisais à expliquer un problème et que quelqu’un reconnaissait qu’il s’agissait d’un concept existant, déjà nommé et étudié.
      Quand on est en train de comprendre soi-même les différentes facettes d’un problème, il est vraiment difficile de retrouver le nom existant de ce concept.
    • C’est vrai. Les jeunes diplômés qu’on recrute aujourd’hui veulent tout faire rentrer de force dans des documents NoSQL et réfléchissent très peu à la modélisation des données.
      Au final, toute la logique d’affichage des arbres est gérée dans le code, alors qu’avec une base relationnelle moderne et quelques CTE, beaucoup de cas d’usage pourraient être traités élégamment et gratuitement. C’est dommage.
    • Difficile de parler de savoir oublié. Il existe aussi un livre intitulé « Joe Celko's Trees and Hierarchies in SQL ».
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • Si le sujet vous intéresse, je recommande de commencer par consulter les livres de https://en.m.wikipedia.org/wiki/Joe_Celko.

  • Postgres dispose d’un type de données ltree et d’opérateurs de recherche qui fonctionnent nativement de cette manière : https://www.postgresql.org/docs/current/ltree.html
    Par exemple, on peut insérer des valeurs avec CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy');,
    puis trouver Top.Science et Top.Science.Astronomy avec SELECT path FROM test WHERE path <@ 'Top.Science';.

    • Attention aux programmeurs : l’une des particularités de ltree est que les chemins intermédiaires qui seraient des nœuds parents si on les dessinait sous forme d’arbre n’ont pas besoin d’exister réellement.
      Dans l’exemple ci-dessus, même si vous supprimez l’enregistrement Top.Science, l’enregistrement Top.Science.Astronomy n’est pas supprimé avec lui.
      Les libellés d’une valeur ltree suggèrent un arbre logique via un chemin matérialisé, mais n’imposent pas l’existence d’enregistrements correspondant à tous les nœuds parents implicites.
      Selon l’application, cela peut être exactement le comportement souhaité, ou tout l’inverse. Dans ce dernier cas, il faut prévoir un mécanisme séparé pour maintenir l’intégrité.
    • Je me demande si, pour stocker des chemins de fichiers, on peut utiliser / comme séparateur.
    • Je me demande si quelqu’un a un retour d’expérience sur les performances. On dirait qu’il y a beaucoup de traitement par expressions régulières.
    • SQL Server propose aussi une fonctionnalité très similaire[1], et d’après mon expérience elle fonctionne plutôt bien.
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • Je me demande si l’on pourrait faire la même chose avec une colonne JSON. Cela permettrait d’utiliser des types autres que des chaînes pour les nœuds.
      En revanche, je crains que les index JSON ne fonctionnent pas aussi bien que les index ltree.

  • Le problème ici, c’est que la valeur de la structure se trouve généralement dans la hiérarchie des données, pas dans un arbre destiné à l’affichage
    Il y a de fortes chances qu’on doive parcourir les données, afficher des relations, les réordonner, etc.
    Mettre des informations visuelles dans la structure de données de la base me paraît dangereux et court-termiste

    • L’auteur a pourtant déjà précisé que « les gens pensent toujours qu’il faut encoder formellement les relations parent-enfant, alors qu’en réalité ce n’est pas toujours le cas et qu’on a parfois seulement besoin d’un affichage imbriqué » ; comme réaction à ça, c’est un peu étrange
      La réponse serait « non, impossible » ?
      Ce n’est pas pour rien que YAGNI est une heuristique de conception célèbre. « Partez du principe que vous en aurez toujours besoin » n’est pas correct
    • Ironiquement, on utilise toujours un ID parent dans les données
      Il est simplement préfixé à la chaîne de données au lieu d’être stocké dans une colonne dédiée avec un type optimisé
      Ce n’est peut-être pas un nombre ni une colonne d’ID, mais cela reste un identifiant qui pointe vers une autre valeur attendue ; changer le format ne fait pas que ce ne soit plus un ID parent
    • Même avec l’encodage par ordre/indentation de l’article original, il devrait être facile de reconstruire les relations parent-enfant
      Bien sûr, il faut garantir qu’une indentation invalide, comme un enfant sans parent, ne puisse pas être enregistrée
      Donc, à mon avis, le plus simple est de stocker d’abord l’ordre/la profondeur, puis de migrer vers un modèle parent/enfant quand on implémente les fonctionnalités qui en ont besoin
      Cela dit, il vaut mieux définir « l’indentation » de façon plus abstraite, comme la profondeur dans l’arbre, et non comme le nombre d’espaces à rendre. Cela facilite la détection de données invalides, simplifie une migration ultérieure et offre une flexibilité de rendu selon les utilisateurs : / imbriqués, tabulations, 8 espaces, 4 espaces, 1 espace, etc.
    • Si l’on a une structure de données du type struct item_t { char key[255]; char display_value[255]; } et que la clé utilise un séparateur de chemin cohérent comme a/b/c, trouver les parents et les enfants est très simple
      Dans le pire des cas, il suffit de parcourir le tableau linéairement ; s’il est trié, il suffit de regarder les éléments précédents jusqu’à atteindre le parent
    • Tout à fait d’accord. La dénormalisation peut parfois être un bon choix, mais je ne vois pas ici de justification raisonnable

  • J’ai déjà créé une entreprise avec beaucoup de données en forme d’arbre. Transformer une structure arborescente en liste indentée se fait en temps O(n)
    C’était l’une de nos questions d’entretien à l’époque, et il existe des façons de stocker cela dans plusieurs bases SQL pour récupérer et rendre rapidement une partie de l’arbre sans requêtes récursives
    Une fois ces concepts compris, stocker correctement les données sous forme d’arbre présente bien plus d’avantages qu’une indentation de ce genre

    • Si vous n’avez pas besoin de ces avantages, ce n’est pas très important

  • « Une façon de récupérer des données arborescentes depuis une base de données relationnelle avec une requête SQL consiste à utiliser des CTE récursives (Common Table Expressions), ce qui est aussi amusant que le nom le laisse entendre »
    Les CTE, même récursives, n’ont rien d’effrayant et, une fois qu’on s’y habitue, je vous garantis qu’elles sont vraiment amusantes

    • Les CTE ne sont pas particulièrement amusantes. Copier-coller toute une tour de CTE dans une autre fenêtre SQL pour déboguer la partie qui m’intéresse, ce n’est pas vraiment ma définition du divertissement
    • Les CTE récursives étaient terriblement lentes pour assembler des données arborescentes depuis une représentation normalisée
      Pour assembler le chemin d’un nœud à une profondeur hiérarchique d, obtenir le résultat de la requête prenait au minimum d fois plus de temps
      L’avantage était que les opérations de modification de l’arbre étaient peu coûteuses, mais elles étaient beaucoup plus rares que les lectures
    • Les CTE, c’est très bien. Au lieu d’inscrire cette information en dur dans la table, l’auteur aurait aussi pu créer une vue avec le nom formaté via une CTE

  • La différence entre HN et Reddit illustre bien l’idée que « les gens ne veulent pas ou n’ont pas réellement besoin d’un arbre ; le plus souvent, ils ont seulement besoin de quelque chose qui ressemble à un arbre »
    Sur HN, un commentaire enfant est le nextSibling du commentaire parent, et on lui donne l’apparence d’un arbre en ajoutant 1 à la valeur d’indentation du parent
    Sur Reddit, du moins sur old.reddit.com, les commentaires enfants sont réellement imbriqués dans le commentaire parent. Je ne sais pas pour le nouveau site

    • Tu parles de la structure HTML, pas de l’affichage réel, n’est-ce pas ? À l’écran, le rendu est presque identique
    • J’ai du mal à imaginer que ce soit réellement stocké ainsi côté backend
      Toutes les opérations sur les données deviendraient un bazar complexe où il faudrait déduire la structure d’arbre puis la retraduire dans un format d’arbre implicite
    • Dans ce cas, je me demande comment fonctionne le repliage

  • L’idée centrale de l’article est simple : utiliser la structure adaptée au problème
    Mais je pense que le récit est bancal. On n’a pas forcément besoin de CTE pour récupérer un arbre depuis une base de données ; on peut récupérer une liste plate puis construire l’arbre localement. De toute façon, on risque de faire cela pour les manipulations ultérieures
    Avec la même logique, on pourrait aussi dire à quelqu’un qui utilise une base relationnelle pour stocker une liste de la mettre dans un fichier texte. Pourquoi payer le coût de la latence réseau ?
    À l’inverse, la structure proposée se comporte mal avec des arbres suffisamment grands lorsqu’il faut déplacer des branches et changer leur profondeur, car cela a un coût linéaire
    Il aurait fallu annoncer l’intention dès le départ, plutôt que de présenter trois exemples puis de les invalider en conclusion avec « si vous avez besoin d’un arbre, utilisez un arbre ». Mais si cela avait été mis au début, l’article aurait été beaucoup moins putaclic

  • J’ai eu une prise de conscience similaire à propos d’OpenGL il y a quelques années. Je n’avais pas besoin de dessiner un monde d’objets 3D hiérarchiques, mais simplement une liste triée de triangles
    Cette idée a fait tilt dans ma tête, et plusieurs optimisations sont devenues très faciles

    • Oui. Dans les jeux 3D depuis 2000, la simplicité est une grande force
      Même dans les jeux avec des hiérarchies d’entités complexes, au moment de les mettre dans la file de rendu, il faut souvent les aplatir, par exemple pour trier la transparence
      La « liste plate d’objets » est aussi l’une des bases d’ECS/DOD

  • Il existe un livre entier sur la gestion de ce genre de tâches dans les bases de données
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • On dit que tous les livres sont pour débutants, très bien

  • Une autre façon de faire de faux arbres consiste à stocker un blob JSON
    Si les données n’ont que des relations internes, cela peut être plus simple que d’essayer de garder des numéros de tri uniques et ordonnés

    • Un arbre représenté en JSON imbriqué peut même être considéré comme un arbre plus « réel » qu’un arbre virtuel obtenu en stockant des références au parent dans la base de données