Pourquoi le push_back dans les vecteurs C ++ est-il constamment amorti?

J'apprends le C ++ et j'ai remarqué que le temps d'exécution de la fonction push_back pour les vecteurs est constant "amorti". La documentation note en outre que "Si une réallocation se produit, la réallocation est elle-même jusqu'à linéaire dans toute la taille."

Cela ne devrait-il pas signifier que la fonction push_back est , où n est la longueur du vecteur? Après tout, nous nous intéressons à l'analyse du pire des cas, non?$O(n)$$n$

Je suppose que, fondamentalement, je ne comprends pas comment l'adjectif "amorti" modifie le temps de fonctionnement.

Le mot important ici est "amorti". L'analyse amortie est une technique d'analyse qui examine une séquence de opérations. Si la séquence entière s'exécute en temps T ( n ) , alors chaque opération de la séquence s'exécute en T ( n ) / n . L'idée est que si quelques opérations de la séquence peuvent être coûteuses, elles ne peuvent pas se produire assez souvent pour alourdir le programme. Il est important de noter que cela diffère de l'analyse de cas moyenne par rapport à une distribution d'entrée ou à une analyse aléatoire. Une analyse amortie a établi le pire des cas$n$$T(n)$$T(n)/n$lié aux performances d'un algorithme quelles que soient les entrées. Il est le plus souvent utilisé pour analyser les structures de données, qui ont un état persistant tout au long du programme.

L'un des exemples les plus courants donnés est l'analyse d'une pile avec une opération multipop qui fait apparaître éléments. Une analyse naïve du multipop dirait que dans le pire des cas, le multipop doit prendre du temps O ( n ) car il pourrait avoir à supprimer tous les éléments de la pile. Cependant, si vous regardez une séquence d'opérations, vous remarquerez que le nombre de pops ne peut pas dépasser le nombre de pushs. Ainsi, sur toute séquence de n opérations, le nombre de sauts ne peut pas dépasser O ( n ) , et donc les exécutions multipop en O ( 1 ) amortissent le temps même si parfois un seul appel peut prendre plus de temps.$k$$O(n)$$n$$O(n)$$O(1)$

Maintenant, comment cela se rapporte-t-il aux vecteurs C ++? Les vecteurs sont implémentés avec des tableaux afin d'augmenter la taille d'un vecteur, vous devez réallouer la mémoire et copier l'ensemble du tableau. De toute évidence, nous ne voudrions pas le faire très souvent. Donc, si vous effectuez une opération push_back et que le vecteur doit allouer plus d'espace, cela augmentera la taille d'un facteur . Maintenant, cela prend plus de mémoire, que vous ne pouvez pas utiliser complètement, mais les quelques opérations push_back suivantes s'exécutent toutes en temps constant.$m$

Maintenant, si nous faisons l'analyse amortie de l'opération push_back (que j'ai trouvée ici ), nous constaterons qu'elle s'exécute en temps amorti constant. Supposons que vous ayez éléments et que votre facteur de multiplication soit m . Le nombre de délocalisations est alors approximativement log m ( n ) . La i ème réallocation coûtera proportionnellement à m i , environ la taille du tableau courant. Ainsi, le temps total pour n repoussage est ∑ log m ( n ) i = 1 m i ≈ n $n$$m$$\log_m(n)$$i$$m^i$$n$ , car c'est une série géométrique. Divisez ceci parnopérations et nous obtenons que chaque opération prenne$\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$$n$ , une constante. Enfin, vous devez faire attention au choix de votre facteurm. S'il est trop proche de1,cette constante devient trop grande pour des applications pratiques, mais simest trop grand, disons 2, alors vous commencez à gaspiller beaucoup de mémoire. Le taux de croissance idéal varie selon l'application, mais je pense que certaines implémentations utilisent1.5.$\frac{m}{m-1}$$m$$1$$m$$1.5$

Bien que @Marc ait donné (ce que je pense) une excellente analyse, certaines personnes pourraient préférer considérer les choses sous un angle légèrement différent.

L'une consiste à envisager une façon légèrement différente de procéder à une réaffectation. Au lieu de copier immédiatement tous les éléments de l'ancien stockage vers le nouveau stockage, pensez à ne copier qu'un seul élément à la fois - c'est-à-dire que chaque fois que vous effectuez un push_back, il ajoute le nouvel élément au nouvel espace et copie exactement un existant élément de l'ancien espace vers le nouvel espace. En supposant un facteur de croissance de 2, il est assez évident que lorsque le nouvel espace est plein, nous aurions fini de copier tous les éléments de l'ancien espace vers le nouvel espace, et chaque push_back a été un temps exactement constant. À ce stade, nous supprimions l'ancien espace, allouions un nouveau bloc de mémoire avec un gain deux fois plus important et répétions le processus.

Assez clairement, nous pouvons continuer cela indéfiniment (ou tant qu'il y a de la mémoire, de toute façon) et chaque push_back impliquerait l'ajout d'un nouvel élément et la copie d'un ancien élément.

Une implémentation typique a toujours exactement le même nombre de copies - mais au lieu de faire les copies une par une, elle copie tous les éléments existants à la fois. D'une part, vous avez raison: cela signifie que si vous examinez les invocations individuelles de push_back, certaines d'entre elles seront considérablement plus lentes que d'autres. Cependant, si nous regardons une moyenne à long terme, la quantité de copie effectuée par invocation de push_back reste constante, quelle que soit la taille du vecteur.

Bien que cela ne soit pas pertinent pour la complexité de calcul, je pense qu'il vaut la peine de souligner pourquoi il est avantageux de faire les choses comme elles le font, au lieu de copier un élément par push_back, de sorte que le temps par push_back reste constant. Il y a au moins trois raisons à considérer.

Le premier est simplement la disponibilité de la mémoire. L'ancienne mémoire ne peut être libérée pour d'autres utilisations qu'après la copie. Si vous ne copiez qu'un seul élément à la fois, l'ancien bloc de mémoire resterait alloué beaucoup plus longtemps. En fait, vous auriez un ancien bloc et un nouveau bloc alloués essentiellement tout le temps. Si vous décidiez d'un facteur de croissance inférieur à deux (ce que vous voulez généralement), vous auriez besoin de plus de mémoire allouée tout le temps.

Deuxièmement, si vous ne copiez qu'un seul ancien élément à la fois, l'indexation dans le tableau serait un peu plus délicate - chaque opération d'indexation devrait déterminer si l'élément à l'index donné se trouve actuellement dans l'ancien bloc de mémoire ou nouveau. Ce n'est pas terriblement complexe, mais pour une opération élémentaire comme l'indexation dans un tableau, presque tout ralentissement pourrait être significatif.

Troisièmement, en copiant tout à la fois, vous profitez beaucoup mieux de la mise en cache. En copiant tout à la fois, vous pouvez vous attendre à ce que la source et la destination soient dans le cache dans la plupart des cas, de sorte que le coût d'un échec de cache est amorti sur le nombre d'éléments qui tiendront dans une ligne de cache. Si vous copiez un élément à la fois, vous pourriez facilement manquer un cache pour chaque élément que vous copiez. Cela ne change que le facteur constant, pas la complexité, mais il peut quand même être assez important - pour une machine typique, vous pouvez facilement vous attendre à un facteur de 10 à 20.

Cela vaut probablement aussi la peine de considérer l'autre direction pendant un moment: si vous concevez un système avec des exigences en temps réel, il pourrait être judicieux de copier un seul élément à la fois au lieu de tous en même temps. Bien que la vitesse globale puisse être (ou ne pas être) inférieure, vous aurez toujours une limite supérieure stricte sur le temps pris pour une seule exécution de push_back - en supposant que vous disposiez d'un allocateur en temps réel (bien sûr, de nombreux en temps réel les systèmes interdisent tout simplement l'allocation dynamique de la mémoire, au moins dans les parties avec des exigences en temps réel).