optimiser un std::map
Le
amerio
Bonjour,
Je m'interroge sur la possibilité d'optimiser les accés d'un std::map.
Dans certaines implémentations, std::map est implémenté comme un arbre binaire RedBlack.
Si on insere les elements dans un ordre déjà trié, il se peut donc que l'arbre soit
entièrement gauche ou droit, donc qu'une recherche dans le map soit techniquement
équivalente à un parcours linéaire d'une list, soit une efficaité en O(N) plutot qu'en
O(LogN).
Y a t il un moyen d'optimiser (auto-balance) l'arbre après la création du map ?
Ou bien doit on prévoir d'ajouter les élements dans un désordre calculé (sic) ?
Ou bien me trompe je completement et la compléxité de la recherche par map::find est elle
garanti d'etre toujours au plus en O(LogN) ?
Je m'interroge sur la possibilité d'optimiser les accés d'un std::map.
Dans certaines implémentations, std::map est implémenté comme un arbre binaire RedBlack.
Si on insere les elements dans un ordre déjà trié, il se peut donc que l'arbre soit
entièrement gauche ou droit, donc qu'une recherche dans le map soit techniquement
équivalente à un parcours linéaire d'une list, soit une efficaité en O(N) plutot qu'en
O(LogN).
Y a t il un moyen d'optimiser (auto-balance) l'arbre après la création du map ?
Ou bien doit on prévoir d'ajouter les élements dans un désordre calculé (sic) ?
Ou bien me trompe je completement et la compléxité de la recherche par map::find est elle
garanti d'etre toujours au plus en O(LogN) ?
Poser une question
Il me semble que c'est déjà le cas automatiquement.
--
Loïc
Exact.
Un arbre red-black est une sorte d'arbre binaire balancé.
C'est ce que fait l'algo d'insertion dans un arbre red-black (plus
précisément la feuille la plus lointaine de la racine est au maximum à
deux fois la distance de la feuille la plus courte).
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++...index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
le principe même du RB-tree c'est qu'il reste quasi-équilibré malgré
les insertions/suppressions
[To the tune of Paint It Black, with my utmost apologies to the Rolling Stones]
I see a brand new node
I want to paint it black.
We need a balanced tree,
we've got to paint it black.
I want to find my key in log n time -- thats all,
Rotating sub-trees 'round sure can be a ball.
I see a brand new node
I want to paint it black.
Can't have a lot of red nodes,
We must paint them black.
Unfortunately, coding them can be a bitch.
If we had half a brain to splay trees we would switch.
I see a brand new node
I want to paint it black.
No time for AVL trees
we must paint it BLACK.
And if they're still confusing, you should have no fear.
Because outside this class, of them you'll never hear.
I wanna paint 'em BLACK. Paint nodes black. Again and again
Je pense que tu veux dire AVL-tree. Dans ce cas, il resta équilibré.