Quelle doit être la taille d'une collection pour std :: map <k,v> pour surpasser un std :: vector <std :: pair <k,v>>?

Question

Quelle doit être la taille d'une collection pour que std :: map devance un std :: vector> trié?

J'ai un système où j'ai besoin de plusieurs milliers de conteneurs associatifs, et std::map semble avoir beaucoup de surcharge en termes de cache CPU. J'ai entendu quelque part que pour les petites collections std :: vector peut être plus rapide - mais je me demande où cette ligne est ....

EDIT: Je parle de 5 articles ou moins à la fois dans une structure donnée. Je suis le plus concerné par le temps d'exécution, pas par l'espace de stockage. Je sais que des questions comme celles-ci sont intrinsèquement spécifiques à une plate-forme, mais je cherche une «règle empirique» à utiliser.

Billy3

Answer 1

Ce n'est pas vraiment une question de taille, mais d'utilisation. Un vecteur trié fonctionne bien lorsque le modèle d'utilisation est que vous lisez les données, puis vous effectuez des recherches dans les données.

Une carte fonctionne bien lorsque le modèle d'utilisation implique un mélange plus ou moins arbitraire de modification des données (ajout ou suppression d'éléments) et de requêtes sur les données. La raison à cela est assez simple: une carte a un surcoût plus élevé sur une recherche individuelle (grâce à l'utilisation de nœuds liés au lieu d'un bloc de stockage monolithique). Une insertion ou suppression qui maintient l'ordre, cependant, a une complexité de seulement O (lg N). Une insertion ou une suppression qui maintient l'ordre dans un vecteur a une complexité de O (N) à la place.

Il existe, bien sûr, diverses structures hybrides qui peuvent également être utiles. Par exemple, même lorsque les données sont mises à jour de manière dynamique, vous commencez souvent avec un grand nombre de données et vous effectuez un nombre relativement réduit de modifications à la fois. Dans ce cas, vous pouvez charger vos données en mémoire dans un vecteur trié et conserver le (petit nombre) d'objets ajoutés dans un vecteur séparé. Puisque ce second vecteur est normalement assez petit, vous ne vous souciez pas de le trier. Quand/si cela devient trop grand, vous le trier et le fusionner avec l'ensemble de données principal.

Édition2: (en réponse à la modification en question). Si vous parlez de 5 articles ou moins, vous êtes probablement mieux ignorer tous les ci-dessus. Laissez simplement les données non triées et effectuez une recherche linéaire. Pour une collection aussi petite, il n'y a pratiquement aucune différence entre une recherche linéaire et une recherche binaire. Pour une recherche linéaire, vous prévoyez de numériser la moitié des éléments en moyenne, ce qui donne ~ 2,5 comparaisons. Pour une recherche binaire, vous parlez du journal N, qui (si mes maths travaillent cette heure du matin) correspond à ~ 2.3 - trop petite différence à prendre en compte ou à remarquer (en fait, une recherche binaire a suffisamment de temps qu'il pourrait facilement finir plus lentement).

Answer 2

Si vous dites « outspace » tu veux dire consommer plus d'espace (aka la mémoire), il est très probable que le vecteur sera toujours plus efficace (la mise en œuvre sous-jacente est un tableau de mémoire continue sans données d'Othe, où map est un arbre, donc chaque donnée implique d'utiliser plus d'espace). Cela dépend cependant de combien le vecteur réserve un espace supplémentaire pour les insertions futures.

Quand il s'agit de temps (et non d'espace), le vecteur sera aussi toujours plus efficace (faire une recherche dichotomique). Mais il sera extreamly mauvais pour ajouter de nouveaux éléments (ou les enlever).

Donc: pas de réponse simple! Recherchez les complexités, réfléchissez aux utilisations que vous allez faire. http://www.cplusplus.com/reference/stl/

Answer 3

EDIT: Voyant que vous parlez de 5 articles ou moins:

Le tri implique des articles échange. Lors de l'insertion dans std :: map, cela n'impliquera que des échanges de pointeurs. La vitesse d'échange d'un vecteur ou d'une carte dépend de la rapidité d'échange de deux éléments.

---

Je vous suggère de profiler votre application pour le comprendre.

---

Si vous voulez une règle simple et générale, alors vous êtes hors de la chance - vous devez considérer au moins les facteurs suivants:

temps

• Comment insérez-vous souvent de nouveaux éléments par rapport à la fréquence de recherche?
• Pouvez-vous insérer des lots de nouveaux articles?
• Combien coûte le tri? Les vecteurs d'éléments qui sont coûteux à échanger deviennent très coûteux à trier - les vecteurs de pointeurs prennent beaucoup moins.

mémoire

• Combien les frais généraux par répartition ne l'allocateur que vous utilisez avoir? std :: map effectuera une allocation par item.
• Quelle est la taille de vos paires clé/valeur?
• Quelle est la taille de vos pointeurs? (32/64 bits)
• Quelle est la rapidité de l'implémentation de std :: vector? (Facteurs de croissance populaires sont 1,5 et 2)

Passé une certaine taille du récipient et élément, les frais généraux d'allocation et pointeurs arbres deviendrai contrebalancés par le coût de la mémoire inutilisée à la fin du vecteur - mais de loin la façon la plus facile de savoir si et quand cela se produit est de mesurer.

Answer 4

Il doit être dans le millionième élément. Et même là ...

Je pense plus ici à l'utilisation de la mémoire et aux accès mémoire. Sous des centaines de milliers, prenez ce que vous voulez, il n'y aura pas de différence notable. Les processeurs sont très rapides ces jours-ci, et le goulot d'étranglement est la latence de la mémoire.

Mais même avec des millions d'objets, si votre carte <> a été créée en insérant des éléments dans un ordre aléatoire. Lorsque vous souhaitez parcourir votre carte (dans l'ordre trié), vous finirez par sauter de manière aléatoire dans la mémoire, bloquant le processeur pour que la mémoire soit disponible, ce qui entraîne des performances médiocres. D'un autre côté, si vos millions d'éléments sont dans un vecteur, le traverser est très rapide, en profitant des prédictions de la mémoire de la CPU.

Comme d'autres l'ont écrit, cela dépend de votre utilisation.

Editer: Je m'interrogerais davantage sur la façon d'organiser vos milliers de conteneurs associatifs que les conteneurs eux-mêmes s'ils ne contiennent que 5 éléments.

Answer 5

Le problème principal avec std::map est un problème de cache, comme vous l'avez indiqué.

Le vecteur trié est une approche bien connue: Loki::AssocVector.

Pour les très petits ensembles de données, le AssocVector doit écraser la carte malgré la copie impliquée lors de l'insertion simplement à cause de la localisation du cache. Le AssocVector surpasse également la carte pour une utilisation en lecture seule. La recherche binaire y est plus efficace (moins de pointeurs à suivre).

Pour toutes les autres utilisations, vous aurez besoin de profil ...

Il y a cependant une alternative hybride que vous pourriez envisager: en utilisant le paramètre Allocator de la carte pour limiter la zone de mémoire où les éléments sont alloués, minimisant ainsi le problème de référence de localité (la racine des échecs de cache).

Il y a aussi un changement de paradigme que vous pourriez envisager: avez-vous besoin d'éléments triés ou d'une recherche rapide?

En C++, les seuls conteneurs compatibles STL pour la recherche rapide ont été implémentés en termes de conteneurs associatifs triés depuis des années. Cependant le prochain C++ 0x comporte le unordered_map tant attendu qui pourrait surpasser toutes les solutions ci-dessus!