Почему push_back в векторах C ++ постоянно амортизируется?

Я изучаю C ++ и заметил, что время выполнения функции push_back для векторов постоянно «амортизируется». В документации также отмечается, что «если происходит перераспределение, само перераспределение будет линейным во всем размере».

Разве это не означает, что функция push_back - это , где - длина вектора? В конце концов, нас интересует анализ наихудшего случая, верно?$O(n)$$n$

Я думаю, что принципиально, я не понимаю, как прилагательное «амортизируется» меняет время работы.

Важное слово здесь «амортизируется». Амортизированный анализ - это метод анализа, который исследует последовательность из операций. Если вся последовательность выполняется за время , то каждая операция в последовательности выполняется за время . Идея состоит в том, что хотя некоторые операции в последовательности могут быть дорогостоящими, они не могут происходить достаточно часто, чтобы отягощать программу. Важно отметить, что это отличается от анализа среднего случая по некоторому входному распределению или рандомизированному анализу. Амортизированный анализ установил оценку наихудшего случая для производительности алгоритма независимо от входных данных. Он чаще всего используется для анализа структур данных, которые имеют постоянное состояние по всей программе.T ( n ) T ( n ) /$n$$T(n)$$T(n)/n$

Один из наиболее распространенных приведенных примеров - это анализ стека с помощью многопопулярных операций, которые выводят элементов. Наивный анализ MultiPop скажет, что в худшем случае режим MultiPop должен занять времени, так как ему, возможно, придется вытолкнуть все элементы стека. Однако, если вы посмотрите на последовательность операций, вы заметите, что количество всплывающих окон не может превышать количество нажатий. Таким образом, для любой последовательности из операций количество всплывающих окон не может превышать , и поэтому многопользовательский режим выполняется за время амортизации хотя иногда один вызов может занять больше времени.O ( n ) n O ( n ) O ( 1 $k$$O(n)$$n$$O(n)$$O(1)$

Теперь, как это относится к векторам C ++? Векторы реализованы с массивами, поэтому для увеличения размера вектора необходимо перераспределить память и скопировать весь массив. Очевидно, мы бы не хотели делать это очень часто. Таким образом, если вы выполняете операцию push_back и вектор должен выделить больше места, он увеличит размер в . Теперь это занимает больше памяти, которую вы не можете использовать полностью, но следующие несколько операций push_back выполняются за постоянное время.$m$

Теперь, если мы выполним амортизированный анализ операции push_back (которую я нашел здесь ), мы обнаружим, что она выполняется в постоянном амортизированном времени. Предположим, у вас есть предметов и ваш коэффициент умножения равен . Тогда количество перемещений примерно равно . й Перераспределение будет стоить пропорционально , о размере текущего массива. Таким образом, общее время возврата равно , поскольку это геометрический ряд. Разделите это на операций, и мы получим, что каждая операция занимаетm log m ( n ) i m i n ∑ log m ( n ) i = 1 m i ≈ n $n$$m$$\log_m(n)$$i$$m^i$$n$ н$\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$$n$ м1м$\frac{m}{m-1}$постоянная. Наконец, вы должны быть осторожны при выборе вашего фактора . Если оно слишком близко к то эта константа становится слишком большой для практических приложений, но если слишком велико, скажем, 2, то вы начинаете тратить много памяти. Идеальная скорость роста зависит от приложения, но я думаю, что некоторые реализации используют .$m$$1$$m$$1.5$

Хотя @Marc дал (я думаю, что это) отличный анализ, некоторые люди могут предпочесть рассмотреть вещи с несколько иной точки зрения.

Один из них - рассмотреть несколько иной способ перераспределения. Вместо того, чтобы сразу копировать все элементы из старого хранилища в новое хранилище, рассмотрите возможность копирования только одного элемента за раз - т.е. каждый раз, когда вы выполняете push_back, он добавляет новый элемент в новое пространство и копирует ровно один существующий элемент из старого пространства в новое пространство. Если предположить, что фактор роста равен 2, то совершенно очевидно, что когда новое пространство заполнено, мы закончили бы копирование всех элементов из старого пространства в новое пространство, и каждый push_back был точно постоянным временем. В этот момент мы отбрасываем старое пространство, выделяем новый блок памяти с вдвое большим усилением и повторяем процесс.

Совершенно ясно, что мы можем продолжать это бесконечно (или до тех пор, пока есть доступная память), и каждый push_back будет включать добавление одного нового элемента и копирование одного старого элемента.

Типичная реализация по-прежнему имеет точно такое же количество копий, но вместо того, чтобы делать копии по одной, она копирует все существующие элементы одновременно. С одной стороны, вы правы: это означает, что если вы посмотрите на отдельные вызовы push_back, некоторые из них будут значительно медленнее, чем другие. Однако, если мы посмотрим на долгосрочное среднее значение, количество копий, выполняемых за один вызов push_back, остается постоянным, независимо от размера вектора.

Хотя это не имеет отношения к вычислительной сложности, я думаю, что стоит указать, почему выгодно делать вещи, как они, вместо того, чтобы копировать один элемент на push_back, поэтому время на push_back остается постоянным. Есть как минимум три причины для рассмотрения.

Первый - это просто доступность памяти. Старая память может быть освобождена для других целей только после завершения копирования. Если вы копируете только один элемент за раз, старый блок памяти будет выделяться гораздо дольше. Фактически у вас будет один старый блок и один новый блок, выделенный практически все время. Если вы выбрали фактор роста меньше двух (который вам обычно нужен), вам понадобится еще больше памяти, выделяемой постоянно.

Во-вторых, если вы копируете только один старый элемент за раз, индексация в массиве будет немного сложнее - каждая операция индексации должна будет выяснить, находится ли элемент с данным индексом в настоящее время в старом блоке памяти или новый. Это совсем не сложно, но для элементарной операции, такой как индексация в массиве, почти любое замедление может быть значительным.

В-третьих, копируя все сразу, вы получаете гораздо больше преимуществ от кэширования. Копируя все сразу, вы можете ожидать, что источник и место назначения в большинстве случаев будут находиться в кэше, поэтому стоимость пропуска кэша амортизируется по количеству элементов, которые поместятся в строке кэша. Если вы копируете по одному элементу за раз, вы можете легко пропустить кеш для каждого копируемого элемента. Это только меняет постоянный коэффициент, но не сложность, но он все еще может быть довольно значительным - для типичной машины можно легко ожидать коэффициент от 10 до 20.

Вероятно, стоит также рассмотреть другое направление: если вы разрабатываете систему с требованиями реального времени, вполне может иметь смысл копировать только один элемент за раз, а не все сразу. Хотя общая скорость может (или не может) быть ниже, вы все равно будете иметь жесткую верхнюю границу времени, необходимого для одного выполнения push_back - при условии, что у вас есть распределитель в реальном времени (хотя, конечно, многие в реальном времени системы просто запрещают динамическое распределение памяти вообще, по крайней мере, в частях с требованиями в реальном времени).