Как мы проводим анализ вставки на обратной стороне (push_back) в std::vector? Это амортизированное время равно O (1) за вставку. В частности, в видеоролике в этом (17: 42 и далее) он говорит, что для оптимальной производительности реализация этого метода в Microsoft увеличивает пропускную способность вектора примерно на 1,5.
Как определяется эта константа?
Предполагая, что вы имеете в виду push_back, а не вставку, я считаю, что важная часть - это умножение на некоторую константу (в отличие от захвата N дополнительных элементов каждый раз), и пока вы это делаете, вы получите амортизированное постоянное время, Изменение фактора изменяет средний случай и наихудший результат.
А именно: Если ваш постоянный коэффициент слишком велик, вы получите хорошую среднюю производительность, но плохую худшую производительность, особенно когда массивы становятся большими. Например, представьте себе удвоение (2x) вектора размера 10000 только потому, что вы нажимаете 10001-й элемент. EDIT: Как заметил Майкл Бэрр, реальная стоимость здесь, вероятно, заключается в том, что вы увеличите свою память намного больше, чем вам нужно. Я бы добавил к этому, что есть проблемы с кешем, которые влияют на скорость, если ваш фактор слишком велик. Достаточно сказать, что есть реальные затраты (память и вычисления), если вы растете намного больше, чем вам нужно.
Однако, если ваш постоянный коэффициент слишком мал, скажем (1.1x), то у вас будет хорошая производительность в худшем случае, но плохая средняя производительность, потому что вам придется нести расходы на перераспределение слишком много раз.
Также см. Jon Skeet ответ на аналогичный вопрос ранее. (Спасибо @Bo Persson)
Немного больше об анализе: скажем, у вас есть теги n, которые вы отбрасываете назад, и коэффициент умножения M. Тогда число перераспределений будет примерно равняться log M n (log_M(n)). А перераспределение i th будет стоить пропорционально M^i (M до i th мощности). Тогда общее время всех откатов будет M^1 + M^2 + ... M^(log_M(n)). Количество pushbacks n, и таким образом вы получаете эту серию (которая представляет собой геометрическую серию и ограничивается примерно до (nM)/(M-1) в пределе), деленная на n. Это примерно константа, M/(M-1).
При больших значениях M вы будете слишком много перегружать и выделять гораздо больше, чем вам достаточно часто (о чем я упоминал выше). При малых значениях M (близких к 1) эта постоянная M/(M-1) становится большой. Этот фактор напрямую влияет на среднее время.
Вы можете сделать математику, чтобы попытаться понять, как это работает.
Популярным методом работы с асимптотическим анализом является метод банкиров. То, что вы делаете, - это разметка всех ваших операций за дополнительную плату, "сохранение", чтобы впоследствии заплатить за дорогостоящую операцию.
Давайте сделаем некоторые предположения дампа, чтобы упростить математику:
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
Таким образом, вы можете получить приблизительную математическую идею о том, как компромисс между временем/памятью работает для этой проблемы. Конечно, есть некоторые предостережения: я не стал сжимать массив, когда он получает меньше элементов, это относится только к худшему случаю, когда ни один элемент не удаляется, а затраты времени на выделение дополнительной памяти не учитываются.
Они, скорее всего, провели кучу экспериментальных тестов, чтобы понять это в конце, делая большую часть того, что я написал, но не имеет значения.
Uhm, анализ действительно прост, когда вы знакомы с числовыми системами, такими как наш обычный десятичный.
Для простоты предположим, что каждый раз, когда достигается текущая емкость, выделяется новый 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.