Bonjour,

Je travaille actuellement sur les arbres utilisés dans le calcul scientifique pour calculer des interactions à longue distance entre des particules. Ce qu'on appelle quadtree et octree.

Je cherche à tester différentes alternatives dans l'algorithme de calcul des forces, ce qui implique que je ne peux pas utiliser une bibliothèque déjà écrite (ou alors il faudrait que je modifie le code de cette lib, chose que je veux éviter).

Mon problème consiste à choisir une option au niveau de la gestion de la mémoire. C'est presque de l'algorithmique mais je cherche une solution C++ pour l'instant.

Je construis mon arbre à partir des positions des objets que je veux placer dedans. Si plusieurs objets sont situés sur un même noeud, je divise l'espace géré par ce noeud en 8 parties et je place les objets récursivement dans l'arbre jusqu'au moment où il n'y a plus qu'un objet par feuille.
Durant la partie de calcul des forces, je dois parcourir l'arbre mais ceci se fait toujours en partant depuis la racine. i.e. pas de parcours transversal.

J'ai imaginé deux manières de stocker mes noeuds en mémoire:

La première consiste juste à utiliser "new" et ainsi à laisser l'ordinateur placer mes noeuds "aléatoirement" dans la mémoire sans réelle organisation. Avec cette méthode, on est obligé de parcourir l'arbre depuis la racine vers les feuilles. Il n'y a pas de mémoire perdue mais on ne peut pas accéder aux feuilles directement.

La deuxième consiste à créer un tableau de nœuds puis à remplir ce tableau de manière logique si nécessaire. C'est-à-dire, placer d'abord la racine, puis ses 8 fils, puis les 64 petit-fils, etc... Avec cette méthode, on a un moyen d'accéder directement à n'importe quel noeud en O(1) . Le parcourt en descendant est toujours possible mais par contre on a besoin d'allouer de la mémoire "inutile" pour le tableau puisqu'à moins de redimensionner correctement le tableau à chaque insertion d'élément (ce qui serait désastreux niveau performances) on est obligé d'allouer un tableau plus grand que nécessaire.

Entre ces deux options, mon coeur balance et je n'ai pas le temps d'implémenter les deux et de développer une batterie de tests afin de choisir la meilleure option.
Quelqu'un aurait-il un retour d'expérience à ce sujet ?

Ou alors, y aurait'il une troisième alternative à laquelle je n'ai pas pensé ?

Merci d'avance !