Quelle structure de données optimale en temps et en espace ?

Bonjour à tous,

Je suis actuellement en train de réaliser une structure d'arbre amenée à devenir très rapidement immense en mémoire, et que j'ai besoin d'optimiser autant que possible.

Basiquement, l'arbre est un ensemble de nœuds dont chacun pointe sur tous ses fils (les nœuds suivants dans l'arbre).

Et je suis en train de me questionner sur la manière optimale de stocker cette liste de fils (qui sont des objets de type Noeud).

En effet, un arbre peut avoir des millions voire des milliards de nœuds en fonction des données analysées, et il est donc très important que le traitement en temps et en mémoire soit optimal.

Pour ce qui est du traitement en temps, les branches issues de chaque nœuds sont peu nombreuses et à chaque fois qu'on les traite on a besoin de les itérer de toute manière jusqu'à trouver la donnée que l'on cherche. De plus, on ne retire (pour l'instant) jamais un nœud lors de la construction de l'arbre, on ne fait qu'ajouter de nouvelles branches.

Pour ce qui est du traitement en espace, la seule chose dont on ait besoin est cet itérateur sur la liste de fils.

Ma question est donc très simple : Quelle est la liste la moins lourde en espace et pour laquelle l'ajout se fasse en temps constant et la lecture par itération en C++ svp ?

Merci d'avance :)

Salut,

ça semble un peu farfelu comme demande dit comme ça (millions, milliards, ..), mais ce que tu cherches est une liste simplement chaînée.
Dans la std il y a la queue, mais elle utilise une deque par défaut qui ne correspond pas, je te conseillerais donc de créer une simple classe pour servir de Container à une queue, voire d'utiliser ta classe ainsi créée directement.

Si tu te poses la question, c'est que tu as déjà codé avec une solution raisonnable, telle que std::list, et que tu constates que les performances sont insuffisantes.

Ma première suggestion, c'est de te pousser à regarder du côté de boost.intrusive.
Les listes intrusives sont les plus efficaces en manipulation de mémoire, et sont effectivement en temps constant à l'ajout.
Par contre, l'accès par index est lent, mais tu ne sembles pas en avoir besoin

As-tu tout de même regardé si une simple map avec une classe de chemin comme clé ne suffirait pas?
Par exemple, une std::list<string> avec un comparateur qui compare les éléments un par un.

Et pour faire mieux, il y a un gain énorme à utiliser des entiers comme identifiants (plutot que des strings), quitte à avoir une map<identifiant, string> à coté pour traduire.


Edit:
Pour reprendre l'idée de Bousk, il y a la possibilité de définir la collection sous-jacente d'une queue: std::queue< Node, std::list<Node> >.

D'accord merci beaucoup pour vos réponses, je vais voir ce que je peux faire.

Si on veut optimiser en temps comme en espace, une liste est à bannir... Un std::vector sera beaucoup mieux dans les deux cas ! Une liste a un overhead mémoire par noeud, et fragmente la mémoire, là où un vector n'a qu'un overhead par conteneur, et que les données sont contigües, ce qui permet une bonne utilisation du cache.

Maintenant, on peut peut-être trouver mieux encore : Tu dis :

Citation:

---

les branches issues de chaque nœuds sont peu nombreuses

---

Est-ce que ce nombre est borné avec une borne très petite ? Si oui, il vaudra mieux utiliser un std::array ayant pour taille cette borne. Tu évites alors des allocations mémoire et ta strucutre de données est encore plus contigüe.
Si non, ça peut être une bonne idée quand même, mais il va falloir ruser, par exemple en utilisant un array quand il y a peu d'éléments, et en basculant vers un vector quand il y en a plus. Le tout packagé une bonne fois pour toutes pour éviter les fausses manips. Je te conseille de regarder par exemple http://llvm.org/docs/ProgrammersManu...-smallvector-h (l'article autour est intéressant lui aussi).

Bien entendu, entre les différentes stratégies que je te propose, comme il n'y a pas de différences en terme de complexité algorithmique, uniquement en terme de détails d'implémentation, je te conseille d'essayer avec les 3 (l'interface doit être assez semblable pour que basculer de l'un à l'autre soit hyper simple), et de mesurer ce qui est le mieux sur les données que tu manipules.