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) ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Loïc Joly
amerio wrote:
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 ?
Il me semble que c'est déjà le cas automatiquement.
-- Loïc
amerio wrote:
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 ?
Il me semble que c'est déjà le cas automatiquement.
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 ?
Il me semble que c'est déjà le cas automatiquement.
-- Loïc
Jean-Marc Bourguet
"amerio" writes:
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.
Exact.
Si on insere les elements dans un ordre déjà trié, il se peut donc que l'arbre soit entièrement gauche ou droit,
Un arbre red-black est une sorte d'arbre binaire balancé.
Y a t il un moyen d'optimiser (auto-balance) l'arbre après la création du map ?
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++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
"amerio" <amerio@hotmail.com> writes:
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.
Exact.
Si on insere les elements dans un ordre déjà trié, il se peut donc
que l'arbre soit entièrement gauche ou droit,
Un arbre red-black est une sorte d'arbre binaire balancé.
Y a t il un moyen d'optimiser (auto-balance) l'arbre
après la création du map ?
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++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
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.
Exact.
Si on insere les elements dans un ordre déjà trié, il se peut donc que l'arbre soit entièrement gauche ou droit,
Un arbre red-black est une sorte d'arbre binaire balancé.
Y a t il un moyen d'optimiser (auto-balance) l'arbre après la création du map ?
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++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Benoit Dejean
Le Sat, 01 Nov 2003 10:10:24 +0000, amerio a écrit :
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) ?
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
Le Sat, 01 Nov 2003 10:10:24 +0000, amerio a écrit :
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) ?
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
Le Sat, 01 Nov 2003 10:10:24 +0000, amerio a écrit :
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) ?
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
gpg
amerio wrote:
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.
Je pense que tu veux dire AVL-tree. Dans ce cas, il resta équilibré.
amerio wrote:
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.
Je pense que tu veux dire AVL-tree. Dans ce cas, il resta équilibré.
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.
Je pense que tu veux dire AVL-tree. Dans ce cas, il resta équilibré.
