Амортизированный анализ std :: vector вставка

Question

Как мы выполняем анализ вставки сзади (push_back) в std :: vector? Это амортизированное время составляет O (1) на одну вставку. В частности, в видео в канале 9 Стефана Т Лававея и в этом (17:42 и далее) он говорит, что для оптимальной производительности реализация этого метода в Microsoft увеличивает емкость вектора примерно на 1,5.

Как определяется эта константа?

Answer 1

Предполагая, что вы имеете в виду push_back, а не вставку, я считаю, что важной частью является умножение на некоторую константу (в отличие от захвата еще N элементов каждый раз), и если вы сделаете это, вы получите амортизированное постоянное время , Изменение коэффициента приводит к изменению среднего и наихудшего показателей производительности.

В частности: Если ваш постоянный коэффициент слишком велик, вы будете иметь хорошую среднюю производительность в случае, но худшую в худшем случае, особенно, когда массивы станут большими. Например, представьте себе удвоение (2x) вектора размером 10000 только потому, что вы выдвинули 10001-й элемент. РЕДАКТИРОВАТЬ: Как косвенно указал Майкл Барр, реальная стоимость здесь, вероятно, заключается в том, что вы увеличите объем памяти намного больше, чем нужно. Я хотел бы добавить к этому, что есть проблемы с кешем, которые влияют на скорость, если ваш фактор слишком велик. Достаточно сказать, что есть реальные затраты (память и вычисления), если вы становитесь намного больше, чем вам нужно.

Однако, если ваш постоянный коэффициент слишком мал, скажем, (1,1x), то у вас будет хорошая производительность в худшем случае, но плохая средняя производительность, потому что вам придется нести затраты на перераспределение слишком много раз. .

Также см. Ответ Джона Скита на аналогичный вопрос ранее. (Спасибо @Bo Persson)

Еще немного об анализе: скажем, у вас есть n предметов, которые вы отбрасываете назад, и коэффициент умножения M. Тогда количество перераспределений будет примерно равно логической базе M из n (log_M(n)). А i -ое перераспределение будет стоить пропорционально M^i (M к i -ой степени). Тогда общее время всех откатов будет M^1 + M^2 + ... M^(log_M(n)). Количество откатов равно n, и, таким образом, вы получаете эту серию (которая является геометрической серией и сокращается примерно до (nM)/(M-1) в пределе), деленную на n. Это примерно константа, M/(M-1).

При больших значениях M вы будете сильно превышать допустимые пределы и выделять гораздо больше, чем вам нужно, достаточно часто (о чем я упоминал выше). Для малых значений M (близких к 1) эта константа M/(M-1) становится большой. Этот фактор напрямую влияет на среднее время.

Answer 2

Вы можете сделать математику, чтобы попытаться понять, как это работает.

Популярным методом работы с асимптотическим анализом является метод Банкерса. То, что вы делаете, - это наценка на все ваши операции с дополнительными затратами, «экономя» их на потом, чтобы потом заплатить за дорогую операцию.

---

Давайте сделаем некоторые допущения для упрощения математики:

• Запись в массив стоит 1. (То же самое для вставки и перемещения между массивами)
• Выделение большего массива бесплатно.

А наш алгоритм выглядит так:

function insert(x){
    if n_elements >= maximum array size:
         move all elements to a new array that
         is K times larger than the current size
    add x to array
    n_elements += 1

Очевидно, «наихудший случай» происходит, когда нам нужно переместить элементы в новый массив. Давайте попробуем амортизировать это, добавив постоянную разметку d к стоимости вставки, доведя ее до (1 + d) за операцию.

Сразу после изменения размера массива (1 / K) он был заполнен, а деньги не сохранены. К тому моменту, как мы заполним массив, мы можем быть уверены, что накоплено как минимум d * (1 - 1/K) * N. Поскольку эти деньги должны быть в состоянии заплатить за все перемещаемые N элементов, мы можем выяснить соотношение между K и d:

d*(1 - 1/K)*N = N
d*(K-1)/K = 1
d = K/(K-1)

Полезный стол:

k    d     1+d(total insertion cost)
1.0  inf   inf
1.1  11.0  12.0
1.5  3.0   4.0
2.0  2.0   3.0
3.0  1.5   2.5
4.0  1.3   2.3
inf  1.0   2.0

---

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

Скорее всего, они провели несколько экспериментальных тестов, чтобы в конце концов выяснить это, хотя большую часть того, что я написал, не имеет значения.

Answer 3

Хм, анализ очень прост, когда вы знакомы с системами счисления, такими как наша обычная десятичная.

Для простоты предположим, что каждый раз, когда достигается текущая емкость, выделяется новый 10-кратный большой буфер.

Если исходный буфер имеет размер 1, то первое перераспределение копирует 1 элемент, второй (где теперь буфер имеет размер 10) копирует 10 элементов и так далее. Итак, с пятью перераспределениями, скажем, у вас есть 1 + 10 + 100 + 1000 + 10000 = 11111 выполненных копий элементов. Умножьте это на 9, и вы получите 99999; Теперь добавьте 1, и вы получите 100000 = 10 ^ 5. Иными словами, если сделать это в обратном направлении, количество копий элементов, выполненных для поддержки этих 5 перераспределений, составило (10 ^ 5-1) /9.

.

А размер буфера после 5 перераспределений, 5 умножений на 10, равен 10 ^ 5. Это примерно в 9 раз больше, чем количество операций копирования элементов. Это означает, что время, затрачиваемое на копирование, приблизительно равно линейному размеру результирующего буфера.

С основанием 2 вместо 10 вы получите (2 ^ 5-1) / 1 = 2 ^ 5-1.

И так далее для других баз (или факторов для увеличения размера буфера на).

Приветствия и hth.