Est-il un avantage de l'utilisation de la carte sur unordered_map en cas de trivial clés?

Une récente parler unordered_map en C++ me suis rendu compte que je devrais utiliser unordered_map pour la plupart des cas où j'ai utilisé map avant, en raison de l'efficacité de la recherche ( amorti O(1) vs O(log n) ). La plupart du temps j'utilise une carte, j'utilise soit int ou std::string comme le type de la clé; c'est pourquoi je n'ai pas de problèmes avec la définition de la fonction de hachage. Plus j'y pensais, plus je me rends compte que je ne peux pas trouver une raison de l'utilisation d'un std::map sur une std::unordered_map dans le cas de clés avec les types simples-j'ai pris un coup d'oeil au niveau des interfaces, et n'a pas trouvé de différences significatives qui aurait un impact sur mon code.

D'où la question: est-il vraiment de raison d'utiliser std::map sur std::unordered map dans le cas de types simples comme les int et std::string?

Je me demande à partir d'un strict point de vue programmation, je sais qu'il n'est pas pleinement considéré comme la norme, et que cela peut poser des problèmes avec le portage.

Aussi, j'attends que l'une des bonnes réponses peut être "il est plus efficace pour les petits ensembles de données" en raison d'une moindre frais généraux (est-ce vrai?) - donc j'aimerais restreindre la question au cas où le montant des touches est non-trivial (>1 024).

Edit: euh, j'ai oublié l'évidence (merci GMan!) -- oui, les cartes sont commandés, bien sûr, je sais qu', et je suis à la recherche pour d'autres raisons.

J'aime poser cette question dans les entretiens: "Quand est-tri rapide mieux que la bulle de tri?" La réponse à la question donne un aperçu de l'application pratique de la théorie de la complexité et non de la simple noir et blanc des déclarations telles que O(1) est meilleure que O(n) ou O(k) est équivalent à O(logn) etc....
Je pense que tu voulais dire "quand est-bulle-sort mieux que le tri rapide" 😛
Serait un pointeur intelligent être une banale clé?
Voici l'un des cas dans lesquels la carte est avantageuse: stackoverflow.com/questions/51964419/...

InformationsquelleAutor Kornel Kisielewicz | 2010-02-04

c++dictionary performance unordered-map

379

N'oubliez pas que map garde ses éléments commandés. Si vous ne pouvez pas abandonner, évidemment, vous ne pouvez pas utiliser unordered_map.

Autre chose à garder à l'esprit est que unordered_map généralement utilise plus de mémoire. map a juste quelques maison de maintien de pointeurs, et de la mémoire pour chaque objet. A l'inverse, unordered_map a un grand tableau (que l'on peut obtenir assez grandes dans certaines implémentations), puis de la mémoire supplémentaire pour chaque objet. Si vous avez besoin d'être en mémoire consciente, map doit prouver mieux, parce qu'il manque le grand tableau.

Donc, si vous avez besoin de la pure recherche de la récupération, je dirais unordered_map est le chemin à parcourir. Mais il y a toujours des compromis, et si vous ne pouvez pas se le permettre, alors vous ne pouvez pas l'utiliser.

Juste à partir de l'expérience personnelle, j'ai trouvé une énorme amélioration dans les performances (mesurées, bien sûr) lors de l'utilisation de unordered_map au lieu de map au sein d'une grande entité (look-up table.

D'autre part, j'ai trouvé que c'était beaucoup plus lente, à plusieurs reprises, l'insertion et la suppression d'éléments. Il est idéal pour un relativement statique de la collection d'éléments, mais si vous êtes en train de faire des tonnes d'insertions et de suppressions de hachage + écopage semble ajouter jusqu'à. (À noter que cela a été pendant de nombreuses itérations.)
- +1: oui, j'ai oublié l'évidence commandé bien :), et la mémoire de la pointe est quelque chose que je n'étais pas au courant de -- merci
- Une chose de plus sur les grandes(r) bloc de mémoire de la propriété de unordered_map vs. carte (ou vecteur vs liste) , le processus par défaut tas (en parlant de Windows ici) est sérialisé. L'allocation de (petits) blocs en grandes quantités dans une application multithread est très cher.
- RA: Vous pouvez un peu de contrôle qu'avec votre propre allocateur de type combiné avec n'importe quel conteneur, si vous pensez que c'est important pour un programme donné.
- Si vous connaissez la taille de la unordered_map et de la réserve qu'au début - avez-vous encore de payer une pénalité de nombreuses insertions? Dire que vous êtes seulement l'insertion d'une fois lorsque vous avez créé la table de recherche - et plus tard seulement lire.
- Aussi loin que je peux dire, il devrait y avoir aucune pénalité en termes de performances. La raison de la performance prend un coup est dû au fait que si le tableau devient trop importante, il va faire une resucée de tous les éléments. Si vous appelez de la réserve, il est possible que ressasser les éléments existants, mais si vous l'appelez au début, il n'y a pas de pénalité, à moins d'après ce cplusplus.com/reference/unordered_map/unordered_map/reserve
- pour(auto c' = map.begin(); it!=carte.end(); ++it) cout<<it->premier<<endl; permet d'imprimer les clés dans l'ordre
- Je suis tout à fait sûr que la mémoire-sage, il est à l'opposé. En supposant que la valeur par défaut 1.0 facteur de charge pour un non ordonnée contenant: vous avez un pointeur par élément pour le seau et d'un pointeur par élément pour le prochain élément dans le seau, donc vous vous retrouvez avec deux pointeurs ainsi que les données pour chaque élément. Pour un ordre de conteneurs, d'autre part, un type RB-arbre de mise en œuvre: trois pointeurs (gauche/droite/parent), plus un bit de couleur qui, en raison de l'alignement prend une suite de mots. C'est quatre pointeurs ainsi que les données pour chaque élément.
- Il est possible d'intégrer la couleur de bit dans l'un des pointeurs. C'est ce qui se fait réellement dans le noyau linux: ils intégrer la couleur de bit dans le parent de pointeur. Je voudrais la STL mise en œuvre pour faire de même 🙂
- Le noyau Linux n'est pas utiliser std::map. Et typique std::map impementations ne pas le faire (je ne l'avais jamais vu celui qui le fait). Il y a une raison à cela: c'métiers de la mémoire pour l'exécution, et vous ne pouvez pas le faire de façon générique si vous ne connaissez pas l'alignement des garanties et de l' (modélisé) type de pointeur (rappelez-vous que les contenants de travailler avec des allocateurs?). Maintenant, même si vous avez pressé que la couleur a un peu quelque part d'autre, ou utilisé un auto-équilibrage arbre binaire qui n'en a pas besoin (comme le bouc émissaire des arbres), vous demeurez toujours avec 2 pointeurs vs 3 pointeurs en faveur de unordered_map.
- C'était juste une remarque au sujet de la possibilité de compresser le bit de couleur. Je vais prendre votre mot sur la façon dont std::map est mis en œuvre
InformationsquelleAutor GManNickG

116

Si vous voulez comparer la vitesse de votre std::map et std::unordered_map implémentations, vous pouvez utiliser Google sparsehash projet qui a un time_hash_map programme à temps eux. 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)

Il ressemble à puces de la carte bat la carte de la plupart des opérations.De l'événement à l'insertion...
sparsehash n'existe plus. il a été supprimé ou démonté.
J'ai édité la question à se référer à un waybackmachine lien.

InformationsquelleAutor Blair Zajac

79

J'avais echo à peu près le même point de GMan fait: selon le type d'utilisation, std::map peut être (et est souvent) plus rapide que std::tr1::unordered_map (à l'aide de la mise en œuvre inclus dans VS 2008 SP1).

Il y a quelques facteurs à garder à l'esprit. Par exemple, dans std::map, vous êtes en comparant les clés, ce qui signifie que vous ne regardez jamais à assez de début d'une clé de la distinction entre droite et gauche sous-branches de l'arbre. Dans mon expérience, presque la seule fois que vous regardez l'intégralité de la clé est de savoir si vous êtes en utilisant quelque chose comme int que vous pouvez comparer en une seule instruction. Avec un plus typique clé de type std::string, vous compare souvent à seulement quelques caractères ou plus.

Un décent fonction de hachage, par contraste, regarde toujours l' ensemble clé. OIE, même si la table de recherche est la constante de la complexité, de la valeur de hachage lui-même a peu près linéaire de la complexité (bien que sur la longueur de la clé, pas le nombre d'éléments). Avec de longues chaînes de caractères comme des clés, un std::map peut terminer une recherche avant un unordered_map serait même commencer sa recherche.

Deuxième, bien qu'il existe plusieurs méthodes de redimensionnement des tables de hachage, la plupart d'entre eux sont assez lent-au point que, à moins que les recherches sont 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 relatif à votre question précédente, vous pouvez également utiliser une table des arbres. Cela a des avantages et des inconvénients. D'une part, elle limite le pire des cas à celle d'un arbre. Il permet aussi rapide d'insertion et de suppression, parce que (au moins, quand je l'ai fait, j'ai utilisé une taille fixe de la table. L'élimination de tous redimensionnement d'un tableau vous permet de garder votre table de hachage beaucoup plus simple et généralement plus rapide.

Un autre point: les exigences pour le hachage et des arbres, les cartes sont différentes. Le hachage nécessite à l'évidence une fonction de hachage, et une comparaison d'égalité, où commandé des cartes nécessitent moins de comparaison. Bien sûr, les hybrides, je l'ai mentionné nécessite à la fois. Bien sûr, pour le cas de l'utilisation d'une chaîne de caractères comme la clé, ce n'est pas vraiment un problème, mais certains types de touches de fonction de commande de mieux que de hachage (ou vice versa).
- Hachage de redimensionnement peut être freiner par dynamic hashing techniques, qui consistent à avoir une période de transition où chaque fois que vous insérez un élément, vous aussi resucée k d'autres éléments. Bien sûr, cela signifie que, pendant la transition, vous avez à la recherche de 2 tables différentes...
- "Avec de longues chaînes de caractères comme des clés, un std::map terminer une recherche avant un unordered_map serait même de commencer sa recherche." -- si la clé n'est pas présente dans la collection. Si il est présent, alors bien sûr toute la longueur doit être comparées afin de confirmer le match. Mais, de même unordered_map besoin de confirmer un hash match avec une comparaison complète, donc tout dépend de ce que les parties du processus de recherche, vous êtes contrastées.
- habituellement, vous pouvez remplacer la fonction de hachage basée sur la connaissance des données. par exemple, si votre long des chaînes varie plus au cours des 20 octets que dans les 100 premiers, juste de hachage les 20 dernières.
InformationsquelleAutor Jerry Coffin
54

J'ai été intrigué par la réponse de @Jerry Cercueil, ce qui suggère que la commande de la carte serait présentent des hausses de performances sur de longues cordes, après une période d'expérimentation (qui peut être téléchargé à partir de pastebin), j'ai trouvé que cela ne semble vrai pour les collections de chaînes aléatoires, lorsque la carte est initialisée avec un triées dictionnaire (qui contiennent des mots avec des quantités considérables de préfixe de chevauchement), cette règle se décompose, probablement en raison de l'augmentation de la profondeur de l'arbre nécessaire pour récupérer la valeur. Les résultats sont présentés ci-dessous, le 1er numéro de la colonne est l'heure d'insertion, la 2e est 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
```
InformationsquelleAutor Gearoid Murphy
31

Je voudrais juste souligner que... il y a de nombreux types de unordered_maps.

Chercher le Article De Wikipedia sur le hachage de la carte. En fonction de la mise en œuvre a été utilisé, les caractéristiques en terme de recherche, d'insertion et de suppression peuvent varier de façon très significative.

Et c'est ce qui m'inquiète le plus avec l'ajout de unordered_map de la STL: ils devront choisir une mise en oeuvre particulière que je doute qu'ils vont aller en bas de la Policy de la route, et nous allons donc être coincé avec une mise en œuvre pour la moyenne de l'utiliser et rien pour les autres cas...

Par exemple, certains de hachage, les cartes ont linéaire ressasser, où, au lieu de ressasser tout le hachage de la carte à la fois, une partie est réchauffé à chaque insertion, ce qui permet d'amortir le coût.

Un autre exemple: certains de hachage des cartes utiliser une simple liste de nœuds pour un seau, d'autres l'utilisation d'une carte, d'autres n'utilisez pas de nœuds, mais trouver le plus proche de logement et, enfin, certains utilisent une liste de nœuds, mais de la réorganiser, de sorte que le dernier élément est accessible à l'avant (comme une mise en cache des chose).

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

Ne m'obtenez pas le mal, je voudrais utiliser la std::unordered_map et je peut, dans l'avenir, mais il est difficile de "faire confiance" à la portabilité d'un tel conteneur lorsque vous pensez à toutes les façons de la mettre en œuvre et les différentes prestations qui résultent de cette.
- +1: point valide, la vie était plus facile quand j'ai été en utilisant ma propre mise en œuvre, au moins je savais que où il a sucé :>
InformationsquelleAutor Matthieu M.
20

Différences importantes qui n'ont pas vraiment été suffisamment évoqué ici:
- map garde des itérateurs pour tous les éléments stables, en C++17 vous pouvez même déplacer des éléments d'une map à l'autre sans pour autant invalider les itérateurs pour eux (et si elles sont appliquées correctement, sans aucune affectation éventuelle).
- map les horaires pour de simples opérations sont généralement plus cohérent puisqu'ils n'ont jamais besoin d'importantes allocations.
- unordered_map à l'aide de std::hash implémenté dans la bibliothèque libstdc++ est vulnérable à DoS si nourris avec douteuses en entrée (il utilise MurmurHash2 avec une constante de semences non pas que les semis qui serait vraiment utile, voir https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/).
- En cours de commande permettant d'effectuer efficacement des recherches, par exemple itérer sur tous les éléments clés ≥ 42.
InformationsquelleAutor user1531083
14

Tables de hachage ont plus constantes que carte commune implémentations, qui deviennent significatifs pour les petits contenants. La taille maximum est de 10, 100, ou peut-être même 1000 ou plus? Les constantes sont toujours les mêmes, mais en O(log n) est proche de O(k). (Rappelez-vous logarithmique de la complexité est encore vraiment bon.)

Ce qui fait une bonne fonction de hachage dépend de vos données caractéristiques; donc, si je n'ai pas de plan sur la recherche à un personnalisé fonction de hachage (mais peut certainement changer d'avis plus tard, et facilement depuis que je typedef sacrément proche de tout) et même si les valeurs par défaut sont choisis pour effectuer décemment pendant de nombreuses sources de données, je trouve la nature ordonnée de la carte à être assez d'une aide au départ que j'ai encore défaut à la carte plutôt que d'une table de hachage dans ce cas.

Plus de cette façon, vous n'avez pas à même de penser à l'écriture d'une fonction de hachage pour d'autres (généralement de type défini par l'utilisateur) les types, et il suffit d'écrire op< (que vous voulez de toute façon).
- connaissez-vous le montant approximatif des éléments qui unordered_map records carte? Je vais probablement écrire un test pour le bien, de toute façon... (+1)
- Il ne prend pas beaucoup; mes tests ont avec près de 10 000 éléments. Si nous voulons un vraiment précis graphique, on pourrait y voir une mise en œuvre de map et l'un des unordered_map, avec certaines plate-forme et de certains taille du cache, et de faire une analyse complexe. 😛
- Dépend des détails de mise en œuvre, au moment de la compilation des paramètres de réglage (facile à prendre en charge si vous êtes en train de rédiger votre propre mise en œuvre), et même la machine utilisée pour les tests. Tout comme pour les autres récipients, le comité définit les exigences générales.
InformationsquelleAutor
11

Raisons ont été données dans d'autres réponses; ici est une autre.

std::map (arbre binaire équilibré) opérations sont amortis O(log n) et le pire cas O(log n).
std::unordered_map (table de hachage) opérations sont amorti O(1) et au pire des cas O(n).

Comment cela se joue dans la pratique, c'est que la table de hachage "hoquet" à chaque fois dans un certain temps avec un O(n) opérations, qui peuvent ou peuvent ne pas être quelque chose que votre application peut tolérer. Si il ne peut pas le supporter, vous préférez std::map sur std::unordered_map.

InformationsquelleAutor Don Hatch
10

J'ai fait un test récemment, ce qui a fait 50000 fusion&tri. Cela signifie que si la chaîne touches sont les mêmes, de fusionner la chaîne d'octets. Et le résultat final doit être triée. Donc, cela inclut un look pour chaque insertion.

Pour la map mise en œuvre, il faut 200 ms pour terminer le travail. Pour le unordered_map + map, il prend 70 ms pour unordered_map d'insertion et de 80 ms pour map d'insertion. Si l'hybride de la mise en œuvre est de 50 ms plus rapide.

Nous devrions réfléchir à deux fois avant d'utiliser le map. Si vous avez seulement besoin de données pour être triés dans le résultat final de votre programme de, une solution hybride peut-être mieux.

InformationsquelleAutor wendong
8

Résumé

En supposant que la commande n'est pas important:
- Si vous allez construire une grande table une fois et faire beaucoup de requêtes, utilisez std::unordered_map
- Si vous allez construire une petite table (peut-être moins de 100 éléments) et faire beaucoup de requêtes, utilisez std::map. C'est parce que les lectures sont O(log n).
- Si vous allez changer de table beaucoup, alors peut être std::map est la bonne option.
- Si vous êtes dans le doute, il suffit d'utiliser std::unordered_map.
Contexte Historique

Dans la plupart des langues, non triées de la carte (aka le hachage en fonction des dictionnaires) sont de la map par défaut cependant, en C++, vous obtenez commandé la carte comme carte par défaut. Comment est-ce arrivé? Certaines personnes, à tort, supposons que C++ comité a pris cette décision dans leur unique sagesse, mais la vérité est, malheureusement, plus laid que ça.

Il est largement cru que le C++ est retrouvé avec ordonné la carte en tant que par défaut, car il n'y a pas trop de paramètres sur la façon dont ils peuvent être mis en œuvre. D'autre part, le hachage en fonction des implémentations a des tonnes de choses à raconter. Donc, pour éviter les blocages dans la normalisation ils viens le long de commandés carte. Autour de 2005, de nombreuses langues avaient déjà de bonnes implémentations de hachage en fonction de la mise en œuvre et il était donc plus facile pour le comité d'accepter de nouveaux std::unordered_map. Dans un monde parfait, std::map aurait été non ordonnée et nous aurions std::ordered_map comme type distinct.

Performance

Ci-dessous deux graphiques parlent d'eux-mêmes (source):
- Les données intéressantes; comment de nombreuses plates-formes avez-vous inclure dans vos tests?
- pourquoi devrais-je utiliser std::map à une petite table lorsque vous faites beaucoup de requêtes depuis std::unordered_map effectue toujours mieux que std::map selon les 2 images que vous avez posté ici?
- Le graphique montre les performances de 0,13 M ou plus d'éléments. Si vous avez des petits (peut-être <100) éléments en O(log n) pourraient devenir plus petit que non triées de la carte.
InformationsquelleAutor Shital Shah
0

Petit plus à l'ensemble de la ci-dessus:

Mieux utiliser map, quand vous en avez besoin pour obtenir des éléments en gamme, comme ils sont triés et vous pouvez simplement effectuer une itération sur eux à partir d'une frontière à l'autre.

InformationsquelleAutor Denis Sablukov
-1

À partir de: http://www.cplusplus.com/reference/map/map/

"En interne, les éléments de la carte sont toujours triés par sa clé à la suite d'un spécifique faible stricte de la commande critère indiqué par la comparaison de l'objet (type de Comparer).

carte conteneurs sont généralement plus lents que unordered_map conteneurs pour accéder aux éléments individuels par leur clé, mais elles permettent de direct itération sur des sous-ensembles en fonction de leur ordre."

InformationsquelleAutor Kunal Bansal

Vous devez vous connecter pour publier un commentaire.

Différences importantes qui n'ont pas vraiment été suffisamment évoqué ici: