7
votes

Insertion rapide des valeurs dans une carte avec un entier croissant comme clé?

Efficacité de la carte Carte :: Insertion (position Itératrice, Const Value & K) peut être considérablement améliorée en fournissant la valeur appropriée en position de paramètre.

Si j'utilise des nombres entiers comme clé, et chaque insertion est effectuée avec un nombre plus grand que toutes les touches précédemment insérées, puis-je accélérer l'opération :: Insérer lorsque vous donnez le :: end () itérateur de la carte ?

quelque chose comme: xxx

où myMap est de type carte et next_number est un grand nombre d'integults d'incrémentation.

EDIT:

La réponse à cette question peut différer selon que les données stockées dans le Carte est dense ou non (voir la discussion ci-dessous). Donc, posons la question des deux manières: une fois que c'est dense une fois que ce n'est pas le cas. Toujours curieux. Peut-être mesurer va y répondre.


                        
                        
                            
                                                                    c++
                                                                    map
                                                            
                        
                                                    
                            
                            
                                12 commentaires
                                
                                                                            Exactement. Dans le cas où la clé est  uint64_t  et toujours en augmentation, est-ce le "meilleur indice" à donner  :: end ()  comme indice?

                                        
                                                                            Je parierais que  insert  nécessite un itérateur déérique (quel  fin ()  n'est pas), mais je ne suis pas absolument certain à ce sujet.

                                        
                                                                            @ EQ-: Non, la position Itératrice doit simplement être un itérateur valide, pas une seule éventuelle. Et, puisque l'idée est que c'est une position que votre nouvel élément précède le plus probablement, ce serait un peu inutile si cela ne permettait pas la fin ().
                                        
                                                                            Si vous êtes préoccupé par les performances d'insertion, pourquoi ne pas utiliser  Unommked_map <>  au lieu de  mappe <> ?

                                        
                                                                            La norme ne mandait aucune différence que ce soit. Il s'agit donc d'une question de micro-optimisation que vous ne pouvez résoudre que des tests réels. Dans un test rapide, j'ai trouvé que l'insertion d'une tonne d'éléments dans l'ordre a pris presque exactement le même temps de chaque sens, et plus de temps a été consacré à l'affectation de nouveaux morceaux de mémoire que n'importe où ailleurs, mais votre plate-forme peut être différente.
                                        
                                                                            @Abarnert Je pense que C ++ 11 a effectivement changé de quel côté de "indice" la valeur insérée a été signalée pour être applicable (c'est-à-dire un indice Pre-C ++ 11 devait précéder la nouvelle valeur).
                                        
                                                                            @Abarnet Je fais beaucoup d'insertions et de suppressions. En moyenne, seulement deux poignées restent stockées dans le conteneur.
                                        
                                                                            @ EQ- vient de vérifier les spécifications. L'indice n'a pas besoin d'être déréférencieux (en C ++ 03 ou C ++ 11), mais vous avez raison sur la modification de la commande entre C ++ 03 et C ++ 11.
                                        
                                                                            @Chrisjohnson Je suis corrigé. Bon à effacer celui-là.
                                        
                                                                            @Chrisjohnson: En fait, on dirait que vous avez raison de changer de commande, mais vous l'avez en arrière. En C ++ 11, la complexité est "logarithmique en général, mais une constante amortise si t est insérée juste avant P", et "T est insérée aussi près que possible de la position avant la fin de P". ), tandis qu'en C ++ 03, il est "constant amorti si t est inséré à droite après p", et "P est un indice pointant sur l'endroit où l'insert devrait commencer à chercher", il devrait donc être ". Et c'est apparemment pourquoi ils ont fait le changement, alors finirait () aurait un sens. Mais toujours, +1 pour soulever la question.
                                        
                                                                            @Frank: Alors? Expliquer votre cas d'utilisation à utiliser ne nous permet pas de deviner combien l'optimisation vous aidera. Le seul moyen de trouver cela est de mesurer réellement.
                                        
                                                                            Si vous allez insérer afin que les données vont toujours à la fin, pourquoi pas simplement utiliser un  std :: vecteur  avec  std :: inférieur  /  std: : Upper_bound  pour effectuer votre recherche? Avec la plupart des processeurs modernes, vous pouvez énormément de compter sur cet être un peu plus rapide que  std :: map . Si vos clés sont des entiers consécutifs (non seulement augmentant), vous pouvez vous indexer dans O (1) au lieu d'une recherche binaire (log n).



                                    
                    4 Réponses :
                    
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Toute suggestion est simplement une suggestion, quelque chose à essayer de mesurer. Nous ne pouvons pas vraiment vous dire le moyen le plus performant de faire l'insertion, vous devriez mesurer votre propre cas d'utilisation spécifique et voir le meilleur. 

 Si votre carte est compacte et dense (presque tous les articles de 0 - Touche MAX sont occupés par des données réelles) et la touche maximale est suffisamment basse pour être un index de tableau raisonnable que vous pouvez basculer pour utiliser un  std :: Vector   et insère toujours sur la fin. Depuis sa croissance, vous devrez occasionnellement réaffecter le vecteur (typiquement c'est quand le vecteur double). Cela peut être coûteux, mais généralement l'insertion sera très bon marché. Vous n'avez pas à gérer le rééquilibrage potentiel d'un arbre binaire et de vecteur est extrêmement cache convivial à d'autres fins. 

 Si l'espace clé de votre carte n'est pas compact / dense et que la touche Max est si grande que ce n'est pas un indice concevable en mémoire, puis l'insertion avec un indice va être votre meilleur choix. 

 Si la commande n'a pas d'importance, vous pouvez essayer  std :: Unorded_map  . Ceci est une mise en œuvre de la table de hachage. Donc, le coût d'insertion va se rapporter à la qualité et à la vitesse du hachage. Il devrait être trivial et rapide de prendre votre clé de 64 bits et de la transformer en hachage de taille_t (taille_t peut même être 64 bits). 

 Mais ne devez pas me faire passer mon mot, mesurez-le et voyez-le pour vous-même ...                                 


                                                                    
                                    
                                    
                                        6 commentaires
                                        
                                                                                            
                                                    Habituellement, je dirais la même chose moi-même, mais dans ce cas, le paramètre d'indice a été ajouté à l'interface standard pour une raison.                                                
                                                
                                                                                            
                                                    Mes données sont l'inverse de ce que vous appelez "dense". J'ai 2 millions d'insertions (en 20 secondes) et le nombre moyen d'éléments dans le conteneur (carte) est d'environ 20. Mais la clé (comme je l'ai dit) augmente toujours. Que dis-tu? Carte, avec allusion à la fin? Ou est-ce que dans mon cas un rééquilibrage de l'arbre trop souvent?                                                
                                                
                                                                                            
                                                    @FRANK J'essayerais un ONUORDED_MAP si la commande n'a pas d'importance. Je dirai également que les conteneurs STL sont des objectifs assez généraux. Dans mon expérience, il y a occasionnellement des moments où la performance est si importante que sa peine d'écrire une structure de données élevée pour votre objectif très spécifique. Bien sûr, vous pouvez facilement vous tirer dessus dans le pied. Comme toujours mesurer et considérer vos options avec soin.                                                
                                                
                                                                                            
                                                    @Dougt. Ok, je vais essayer un usered_map un try. Une question:  mappe  et  Unorded_map  Utilisez en interne l'opérateur  neuf  pour allouer la mémoire pour le nouvel élément. Cela peut-il être optimisé beaucoup en utilisant un allocateur de piscine de taille constante?                                                

                                                
                                                                                            
                                                    Eh bien, l'habituel  "ne pense pas, mesurez!"  -Asswer devient encore plus de déchets lorsque la norme dit  "Si vous l'insérez là-bas, c'est constant (même si amorti), sinon logarithmique ". Mais d'accord, le reste de la réponse est assez bon -1 / + 1.                                                

                                                
                                                                                            
                                                    @Christianrau: En fait, à moins que vous n'ayez d'énorme n, il n'y a pas beaucoup de différence entre constante et logarithmique. Et considérant que n ici (la taille de la carte au moment de chaque insertion) est "quelques poignées" ou "environ 20", c'est très certainement un cas pour "Ne pense pas, mesurer".                                                
                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    4
 votes
                                
                            
                            
                                
                                     Pour répondre directement à la question posée, les spécifications C ++ disent que: 


 en C ++ 03, insertion dans une carte avec  a.insert (p, t)  doit être une complexité constante amortie (plutôt que logarithmique) si  t  est inséré Droite  après   p . 
 en C ++ 11, insertion dans une carte avec  A.insert (p, t)  doit être une complexité constante amortie si  t  est inséré à droite  avant   p . 


 et dans aucun cas,  p  doit être déériqueférencieux. Par conséquent, dans votre cas,  a.end ()  est probablement le meilleur indice de C ++ 11, mais pas en C ++ 03.                                 


                                                                    
                                    
                                    
                                        4 commentaires
                                        
                                                                                            
                                                    C'est une situation tordue. Est-ce que je reçois le pire possible si je mets l'indice qu'une seule position à la droite du meilleur indice?                                                
                                                
                                                                                            
                                                    @FRANK: Vous pouvez toujours décrémenter de manière conditionnelle en fonction de la valeur du  __ CplusPlus  macro.                                                

                                                
                                                                                            
                                                    J'espère qu'une implémentation pratique est bonne avec l'indice avant ou après. Sinon, c'est un changement drastique.                                                
                                                
                                                                                            
                                                    @MarkRansom: le texte ci-dessus ne vous dit pas que. Mais l'autre texte dans les normes ("Itérateur P est un indice de pointage sur l'endroit où l'insertion devrait commencer à rechercher" et "T est inséré aussi près que possible de la position juste avant P"), ou un peu pensé à la façon dont il Doit être mis en œuvre, implique qu'il est probablement toujours amorti constant, juste avec une constante plus élevée. (Fondamentalement, vous devez faire deux extratures et se compare par insertion au lieu d'un.)                                                
                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    2
 votes
                                
                            
                            
                                
                                     Je suggérerais deux choses: 


 Préférez  std :: Unordered_map  Dans ce cas, l'insertion toujours à une extrémité est un scénario pire cas pour les arbres noirs rouges 
 Utilisez un allocator personnalisé si  Nouveau  s'avère être une préoccupation, de ce que vous parlez d'une stratégie d'allocation de piscine pourrait être utilisé 


 Notez que C ++ 11 permet d'utiliser des allocateurs d'état d'être utilisés, il devrait donc être suffisamment facile de fournir un allocator qui convient à un  std intégré :: vecteur   à l'intérieur et l'utiliser comme une pile.                                 


                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     J'ai fait des mesures depuis que je suis tombé sur cette question récemment. 
 J'ai une grande carte, avec de nombreuses données, les données sont rarement insérées, 99% du temps est juste accessible et modifié en place en utilisant des références.
Toutefois, ces données doivent éventuellement être sauvegardées sur le disque et le rechargement.
Des solutions telles que "utiliser une carte non ordonnée", semblent un moyen rapide de faire de la tâche rapide, la carte commandée était la bonne façon pour moi, car les données sont commandées. Seule problème était en cours de chargement à partir de fichier.  
 Je voulais savoir quel est le coût réel de cette opération et sur la manière de la rapider, j'ai donc mesuré:   xxx  
 résultats:   xxx  
   
    
  Résumé:   

  oui il y a un gain, un gain énorme, sans aucun inconvénient réel. Extrêmement meilleur qu'une carte sans ordonnée lorsque les données sont commandées, extrêmement utiles pour le cas d'économie d'une carte et de la recréer.  
  Délai d'insertion si l'indice est correct est le même quel que soit le nombre d'éléments. Il n'est donc pas nécessaire de se reproduire dans une carte sans commande de hachage pour avoir du temps constant.  
  Le pire des cas que vous pourriez perdre une partie si votre indice est la pire indice possible. Je ne vois plus aucun point pour faire des insertions sans indice, spécialement si vous avez des connaissances sur l'endroit où les données seront insérées. Et la plupart du temps que vous faites.  
                                 


                                                                    
                                    
                                    
                                        0 commentaires

Articles qui pourrait vous intéresser : Catalina C ++: L'utilisation d'en-têtes <cmath> génère une erreur: aucun membre nommé 'signbit' dans l'espace de noms global installation du compilateur c ++ 11 (+) sans autorisation d'administrateur Application de console C ++ VS2019 - Le débogueur n'acceptera pas les arguments de commande Meilleur moyen en C ++ de garder une grosse structure atomique?