Y a-t-il un avantage à utiliser map plutôt que unordered_map dans le cas de clés triviales ?

Question

Un récent discours sur unordered_map en C++ m'a fait réaliser que je devrais utiliser unordered_map pour la plupart des cas où j'ai utilisé map auparavant, en raison de l'efficacité de la recherche ( amortis O(1) vs. O(log n) ). La plupart du temps, j'utilise une carte, soit int o std::string comme type de clé ; par conséquent, je n'ai aucun problème avec la définition de la fonction de hachage. Plus j'y pensais, plus je me rendais compte que je ne voyais aucune raison d'utiliser un type de clé std::map sur un std::unordered_map dans le cas des clés avec des types simples -- J'ai jeté un coup d'oeil aux interfaces, et je n'ai pas trouvé de différences significatives qui auraient un impact sur mon code.

D'où la question : y a-t-il une réelle raison d'utiliser std::map en std::unordered_map dans le cas de types simples comme int y std::string ?

Je pose la question d'un point de vue strictement programmatique - je sais que ce n'est pas entièrement considéré comme un standard et que cela peut poser des problèmes de portage.

Aussi, je m'attends à ce que l'une des réponses correctes soit "c'est plus efficace pour les petits ensembles de données" en raison d'une charge moins importante (est-ce vrai ?) -- c'est pourquoi j'aimerais restreindre la question aux cas où le nombre de clés est non trivial (>1 024).

Edit : duh, j'ai oublié l'évidence (merci GMan !) -- oui, les cartes sont commandées bien sûr -- je le sais, et je cherche d'autres raisons.

Answer 1

N'oubliez pas que map garde ses éléments ordonnés. Si vous ne pouvez pas renoncer à cela, il est évident que vous ne pouvez pas utiliser unordered_map .

Il faut aussi garder à l'esprit que unordered_map utilise généralement plus de mémoire. map n'a que quelques pointeurs pour le ménage, et de la mémoire pour chaque objet. Au contraire, unordered_map a un grand tableau (qui peut devenir assez grand dans certaines implémentations), puis de la mémoire supplémentaire pour chaque objet. Si vous avez besoin d'être attentif à la mémoire, map devrait s'avérer meilleur, car il n'y a pas de grand tableau.

Donc, si vous avez besoin d'une recherche pure, je dirais que unordered_map est la voie à suivre. Mais il y a toujours des compromis à faire, et si vous ne pouvez pas vous les permettre, alors vous ne pouvez pas l'utiliser.

Par expérience personnelle, j'ai constaté une énorme amélioration des performances (mesurées, bien sûr) en utilisant unordered_map au lieu de map dans une table de consultation de l'entité principale.

En revanche, j'ai constaté qu'il était beaucoup plus lent pour insérer et retirer des éléments de manière répétée. C'est très bien pour une collection d'éléments relativement statique, mais si vous faites des tonnes d'insertions et de suppressions, le hachage + le bucketing semblent s'accumuler. (Remarque, ceci a été fait sur de nombreuses itérations).

Answer 2

Si vous voulez comparer la vitesse de votre std::map y std::unordered_map vous pouvez utiliser l'application Google sparsehash qui a un programme time_hash_map pour les chronométrer. Par exemple, avec gcc 4.4.2 sur un système Linux x86_64

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)

Answer 3

Je reprendrais à peu près le même point que GMan : tout dépend du type d'utilisation, std::map peut être (et est souvent) plus rapide que std::tr1::unordered_map (en utilisant l'implémentation incluse dans VS 2008 SP1).

Il y a quelques facteurs de complication à garder à l'esprit. Par exemple, en std::map En effet, vous comparez des clés, ce qui signifie que vous ne regardez jamais assez le début d'une clé pour distinguer les sous-branches droite et gauche de l'arbre. D'après mon expérience, la seule fois où vous regardez une clé entière est si vous utilisez quelque chose comme int que vous pouvez comparer en une seule instruction. Avec un type de clé plus typique comme std::string, vous ne comparez souvent que quelques caractères.

Une fonction de hachage décente, par contre, regarde toujours le tout le site clé. Autrement dit, même si la consultation de la table est d'une complexité constante, le hachage lui-même a une complexité à peu près linéaire (mais sur la longueur de la clé, pas sur le nombre d'éléments). Avec de longues chaînes de caractères comme clés, une std::map pourrait terminer une recherche avant un unordered_map serait même commencer sa recherche.

Deuxièmement, bien qu'il existe plusieurs méthodes pour redimensionner les tables de hachage, la plupart d'entre elles sont assez lentes -- au point que, à moins que les recherches ne soient considérablement plus fréquentes que les insertions et les suppressions, std::map sera souvent plus rapide que std::unordered_map .

Bien sûr, comme je l'ai mentionné dans le commentaire sur votre question précédente, vous pouvez également utiliser une table des arbres. Cela présente à la fois des avantages et des inconvénients. D'une part, cela limite le pire cas à celui d'un arbre. D'autre part, cela permet des insertions et des suppressions rapides, car (du moins quand je l'ai fait) j'ai utilisé une table de taille fixe. Élimination de todo Le redimensionnement de la table vous permet de garder votre table de hachage beaucoup plus simple et généralement plus rapide.

Un autre point : les exigences pour les cartes à base de hachage et les cartes à base d'arbres sont différentes. Le hachage nécessite évidemment une fonction de hachage et une comparaison d'égalité, alors que les cartes ordonnées nécessitent une comparaison de type "moins que". Bien sûr, l'hybride que j'ai mentionné nécessite les deux. Bien sûr, dans le cas courant de l'utilisation d'une chaîne de caractères comme clé, ce n'est pas vraiment un problème, mais certains types de clés conviennent mieux à l'ordonnancement qu'au hachage (ou vice versa).

Answer 4

J'ai été intrigué par la réponse de @Jerry Coffin, qui a suggéré que la carte ordonnée présenterait une augmentation des performances sur les longues chaînes de caractères, après quelques expérimentations (qui peuvent être téléchargées à partir de pastebin ), j'ai constaté que cela ne semble être vrai que pour des collections de chaînes aléatoires, lorsque la carte est initialisée avec un dictionnaire trié (qui contient des mots avec des quantités considérables de chevauchement de préfixe), cette règle s'effondre, probablement en raison de la profondeur accrue de l'arbre nécessaire pour récupérer la valeur. Les résultats sont présentés ci-dessous, la première colonne de chiffres correspond au temps d'insertion, la deuxième au temps de récupération.

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298

Answer 5

Je voudrais juste souligner que... il y a plusieurs sortes de unordered_map s.

Cherchez le Article de Wikipedia sur la carte de hachage. Selon l'implémentation utilisée, les caractéristiques en termes de recherche, d'insertion et de suppression peuvent varier de manière significative.

Et c'est ce qui m'inquiète le plus avec l'ajout de unordered_map à la STL : ils devront choisir une implémentation particulière, car je doute qu'ils suivent la voie de la Policy et nous serons donc coincés avec une implémentation pour l'utilisation moyenne et rien pour les autres cas...

Par exemple, certaines cartes de hachage sont dotées d'une fonction de hachage linéaire. Au lieu de hacher toute la carte de hachage en une seule fois, une partie est hachée à chaque insertion, ce qui permet d'amortir le coût.

Autre exemple : certaines cartes de hachage utilisent une simple liste de nœuds pour un seau, d'autres utilisent une carte, d'autres n'utilisent pas de nœuds mais trouvent l'emplacement le plus proche et enfin, certaines utilisent une liste de nœuds mais la réorganisent de façon à ce que le dernier élément accédé soit au début (comme un truc de cache).

Pour le moment, j'ai donc tendance à préférer le std::map ou peut-être un loki::AssocVector (pour les ensembles de données congelées).

Ne vous méprenez pas, j'aimerais bien utiliser la std::unordered_map et je le ferai peut-être à l'avenir, mais il est difficile de "faire confiance" à la portabilité d'un tel conteneur quand on pense à toutes les façons de le mettre en œuvre et aux diverses performances qui en résultent.