Atree : une implémentation d’arbre simple et efficace sans pointeurs

• Apter Trees en C++
• Un arbre représenté simplement à l’aide de seulement deux vecteurs : [valeur du nœud, index du parent)
• La plupart des arbres sont implémentés comme des arbres binaires, où chaque nœud contient sa propre valeur et des pointeurs vers ses nœuds enfants gauche/droite
• Ce type de structure de données doit être implémenté de façon récursive et peut être ralenti par le comportement du cache et des malloc() fréquents
• La notion de qui « possède » un nœud d’arbre peut devenir complexe dans un logiciel multicouche
• Les arbres Apter sont bien plus rapides, plus faciles à raisonner et plus simples à implémenter

Fonctionnement

• Implémenté avec deux tableaux de même taille
  • un vecteur (tableau) de données d
  • un vecteur p des index parents. L’index du vecteur d est utilisé comme clé (c)
  • souvent, la clé/l’index c est un entier
• Si Coco est le parent de Molly et Arca, et qu’Arca a un enfant nommé Cricket, la structure devient la suivante
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• Le nœud dont le parent est 0 et dont la clé est 0 est le nœud racine (dans les arbres Apter, la racine est obligatoire, ou bien -1 signifie « pas de parent », mais cela est ignoré ici)
• Les ordinateurs manipulent les vecteurs très rapidement. Comme cela est bien plus rapide que les opérations sur pointeurs, comparer la notation en grand O des algorithmes n’a en pratique pas vraiment de sens

Pourquoi c’est important

• Cette méthode d’implémentation est la plus élégante parmi toutes celles de structures arborescentes que l’auteur a vues
• Avec une bibliothèque adaptée d’opérations sur vecteurs, c’est facile à comprendre et les bugs sont faciles à repérer
• Sa simplicité permet de l’adapter facilement à d’autres cas d’usage
• On peut ignorer le vecteur des index parents et parcourir rapidement les valeurs, ce qui revient à une sorte de Deep Map disponible gratuitement
• C’est adapté au GPU et facile à utiliser dans des environnements embarqués
• En empêchant la taille des vecteurs de croître au-delà d’une certaine limite, il devient facile de préserver la sécurité

Origines

• L’auteur cherche à identifier la personne qui a inventé cette technique, et suppose qu’elle portait déjà un nom à l’époque orientée vecteurs des années 60 et 70
• Il en a vu pour la première fois une description complète telle qu’expliquée par Apter, mais cela est aussi largement documenté dans K3
• APL implémente les arbres de manière traditionnelle, mais utilise une technique similaire pour les graphes vectoriels
• La technique est aussi connue des utilisateurs de J, et Rosetta Code contient une explication de l’implémentation d’arbres en J
• John Earnest décrit plus en détail l’implémentation vectorielle des arbres, y compris la suppression d’éléments via une approche par « offset index »
• Une approche plus complexe consiste à suivre la profondeur de chaque élément

Autres implémentations d’arbres courantes

• Il existe par exemple l’implémentation d’arbre du noyau FreeBSD, les arbres de klib, la classe Tree de Ruby et des classes d’arbres déclaratives en Python
• Elles n’offrent pas exactement les mêmes fonctions que les arbres Apter, et certaines sont bien plus volumineuses à cause de leur généralisation

État actuel de ce code

• Il s’agit d’une tentative d’implémentation dans le but d’apprendre le C++17
• Ce n’est pas encore prêt à l’emploi, et l’auteur a encore besoin d’en apprendre davantage sur le C++

L’avis de GN⁺

• Les Apter Trees simplifient les structures arborescentes complexes existantes et permettent une gestion des données rapide et efficace
• Une implémentation d’arbre fondée sur des vecteurs peut minimiser l’overhead mémoire et améliorer les performances grâce à un accès linéaire
• Cet article offre une perspective intéressante pour explorer des approches innovantes des structures de données en ingénierie logicielle

[GN⁺]

Avis sur Hacker News

• Un utilisateur a exprimé sa surprise en voyant que son travail était lié sur Hacker News. Il a indiqué s’intéresser beaucoup aux structures de données légères basées sur des tableaux, et a mentionné en particulier une approche d’implémentation souvent utilisée pour les arbres de nœuds destinés au skinning de modèles 3D. Il explique que si le tableau est trié de sorte que les nœuds parents apparaissent avant leurs enfants, le recalcul des transformations mondiales de tous les nœuds peut se faire avec une simple boucle.
• Un autre utilisateur, en réponse à un commentaire affirmant que l’itération sur les nœuds enfants dans ce style d’arbre est en O(N), a mentionné qu’il est en réalité facile de généraliser la conception d’atree en ajoutant des pointeurs vers le « premier enfant » et le « frère suivant ». Il recommande aussi d’adapter la structure de données pour prendre en charge les opérations nécessaires.
• Un utilisateur affirme que stocker les nœuds dans un tableau et utiliser des indices comme pointeurs est essentiel pour implémenter des algorithmes sur les arbres. Il conseille notamment, lorsqu’il faut accéder aux enfants d’un nœud, d’envisager des structures distinctes pour les nœuds internes et les feuilles afin d’économiser de la mémoire.
• Un autre utilisateur remarque qu’il est un peu étrange que la représentation d’un arbre par tableau de parents suscite autant d’intérêt sur Hacker News. Selon lui, cela montre jusqu’où une bonne présentation peut porter une idée pourtant élémentaire.
• Un utilisateur souligne que ce projet ne fait finalement que remplacer les pointeurs système par ses propres pointeurs.
• Un autre utilisateur suggère d’essayer une implémentation d’arbre plus traditionnelle utilisant un pool de nœuds si l’objectif est de réduire les malloc et d’améliorer la localité des données.
• Un commentaire recommande de consulter l’explication d’Aaron Hsu utilisant APL.
• Un utilisateur propose une modification de structure consistant à regrouper tous les enfants d’un nœud ensemble. Cela permettrait de retrouver la liste complète des enfants d’un nœud par recherche binaire, tout en offrant des propriétés favorables au cache.
• Un commentaire évoque l’usage du terme « handle » ou « index-handle » pour désigner les indices dans un tableau, et note que cette manière de représenter un arbre rappelle des structures de données classiques comme les tas et les ensembles disjoints.
• Enfin, un commentaire explique que les indices de tableau peuvent eux aussi être considérés comme une forme de « pointeur », et que si les implémentations d’arbres traditionnelles nécessitent malloc, c’est à cause du besoin d’ajouter ou de supprimer des nœuds dynamiquement. Il ajoute qu’une implémentation par tableau peut convenir si la taille de l’arbre est limitée et que les suppressions sont rares.