Вопрос по stl, amortized-analysis, stdvector, c++, algorithm – Ура & hth.

17

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

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

С какой стати люди голосуют за то, чтобы их закрыли как «не по теме» и «неконструктивно»? Голосование за закрытие как «дубликат» может быть понятно, но не причины, приведенные. Потенциальный избиратель: если вы НЕ ПОНИМАЕТЕ вопрос, пожалуйста, воздержитесь от голосования. Cheers and hth. - Alf
Вы уверены, что имеете в видувставка? Думаю только вставкав конце, или жеpush_back, амортизируется O (1); Произвольная вставка является линейной по количеству элементов, которые необходимо переместить. Kerrek SB
о, у меня были сомнения относительно этого спасибо за упоминание этого ... отредактирую это jemmanuel

Ваш Ответ

3   ответа
7

чтобы попытаться понять, как это работает.

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

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

Запись в массив стоит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

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

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

1

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

Тогда для простоты предположим, что каждый раз, когда достигается текущая емкость, выделяется новый 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.

16

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

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

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

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

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

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

@Chris A: на самом деле оптимизация (с точки зрения памяти) состоит в том, чтобы иметь разные константы для нескольких интервалов размера. Вы начинаете быстро расти и уменьшаете фактор, когда становитесь большими. Пока этот набор факторов всегда остается> 1 (даже его предел), то сложность все равно гарантирована. я люблюАдаптивные алгоритмы. Matthieu M.
да значит инерция сзади ... отредактировал вопрос .. jemmanuel
Почему удвоение выделения с вектором 10000 элементов хуже, чем выделение нового блока, который будет содержать некоторое другое количество элементов (больше 10000)? Michael Burr
Это своего рода компромисс между потреблением памяти и постоянными факторами сложности. ltjax
Итак, вы говорите, что реальная проблема с наличием слишком большого фактора в том, что у вас просто слишком много памяти? Или я упускаю суть? Вы правы, реальная стоимость - это, вероятно, копирование, которое происходит после перераспределения. Chris A.

Похожие вопросы