Подтвердить что ты не робот

О развитии векторов

Проходил Книгу: С++ Primer, третье издание Стэнли Б. Липпман, Хосе Ладжое

Найдено 1 раз. ... В программе, приведенной в статье 6.3. Как создается вектор, эта программа пропускает "<" в устах!! Предлагаемая программа:

#include <vector>
#include <iostream>

int main(){
vector< int > ivec;
cout < "ivec: size: " < ivec.size()
< " capacity: "  < ivec.capacity() < endl;

for ( int ix = 0; ix < 24; ++ix ) {
ivec.push_back( ix );
cout < "ivec: size: " < ivec.size()
< " capacity: "  < ivec.capacity() < endl;
}    
}

Теперь я исправил проблему. Позже в этой статье в книге говорится следующее: "В соответствии с реализацией Rogue Wave размер и емкость ivec после его определения равны 0. При вставке первого элемента, однако, емкость ivec равна 256, а его размер равен 1."

Но, исправляя и запуская код, я получаю следующий вывод:


ivec: size: 0 capacity: 0
ivec[0]=0 ivec: size: 1 capacity: 1
ivec[1]=1 ivec: size: 2 capacity: 2
ivec[2]=2 ivec: size: 3 capacity: 4
ivec[3]=3 ivec: size: 4 capacity: 4
ivec[4]=4 ivec: size: 5 capacity: 8
ivec[5]=5 ivec: size: 6 capacity: 8
ivec[6]=6 ivec: size: 7 capacity: 8
ivec[7]=7 ivec: size: 8 capacity: 8
ivec[8]=8 ivec: size: 9 capacity: 16
ivec[9]=9 ivec: size: 10 capacity: 16
ivec[10]=10 ivec: size: 11 capacity: 16
ivec[11]=11 ivec: size: 12 capacity: 16
ivec[12]=12 ivec: size: 13 capacity: 16
ivec[13]=13 ivec: size: 14 capacity: 16
ivec[14]=14 ivec: size: 15 capacity: 16
ivec[15]=15 ivec: size: 16 capacity: 16
ivec[16]=16 ivec: size: 17 capacity: 32
ivec[17]=17 ivec: size: 18 capacity: 32
ivec[18]=18 ivec: size: 19 capacity: 32
ivec[19]=19 ivec: size: 20 capacity: 32
ivec[20]=20 ivec: size: 21 capacity: 32
ivec[21]=21 ivec: size: 22 capacity: 32
ivec[22]=22 ivec: size: 23 capacity: 32
ivec[23]=23 ivec: size: 24 capacity: 32

Следовательно, начальная емкость увеличивается с помощью формулы 2 ^ N, не так ли, где N - начальная емкость. Пожалуйста, объясните.

4b9b3361

Ответ 1

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

Каждый раз, когда возрастает векторная емкость, элементы необходимо скопировать. Если вы "амортизируете" эту стоимость за время жизни вектора, получается, что если вы увеличиваете емкость экспоненциальным фактором, вы получите амортизированную постоянную стоимость.

Возможно, это немного странно, поэтому позвольте мне объяснить вам, как это работает...

  • size: 1 capacity 1 - Никакие элементы не были скопированы, стоимость для элемента для копий равна 0.
  • size: 2 capacity 2 - Когда векторная емкость была увеличена до 2, нужно было скопировать первый элемент. Средние копии на элемент - 0,5.
  • size: 3 capacity 4 - Когда векторная емкость была увеличена до 4, необходимо было скопировать первые два элемента. Средние копии на элемент (2 + 1 + 0)/3 = 1.
  • size: 4 capacity 4 - Средние копии на элемент (2 + 1 + 0 + 0)/4 = 3/4 = 0.75.
  • size: 5 capacity 8 - Средние копии на элемент (3 + 2 + 1 + 1 + 0)/5 = 7/5 = 1.4
  • ...
  • size: 8 capacity 8 - Средние копии на элемент (3 + 2 + 1 + 1 + 0 + 0 + 0 + 0)/8 = 7/8 = 0.875
  • size: 9 capacity 16 - Средние копии на элемент (4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 0)/9 = 15/9 = 1,67
  • ...
  • размер 16 вместимости 16 - Средние копии на элемент - 15/16 = 0,938
  • размер 17 вместимость 32 - Средние копии на элемент - 31/17 = 1,82

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

Если вы увеличили емкость на 1.5 * N вместо 2 * N, вы получите очень похожий эффект, за исключением того, что верхняя граница копий на элемент будет выше (я думаю, что это будет 3).

Я подозреваю, что реализация выбрала бы 1,5 более двух, чтобы сохранить немного места, но также потому, что 1.5 ближе к золотому коэффициенту . У меня есть интуиция (которая в настоящее время не подкрепляется никакими жесткими данными), что темпы роста в соответствии с золотым соотношением (из-за его связи с последовательностью фибоначчи) окажутся наиболее эффективными темпами роста для реальных нагрузок с точки зрения минимизации использования дополнительного пространства и времени.

Ответ 2

Чтобы иметь возможность предоставлять амортизированные константные временные вставки в конце std::vector, реализация должна увеличивать размер вектора (когда это необходимо) на коэффициент K>1 (*), так что при попытке добавить к вектору размера N, который заполнен, вектор становится K*N.

В разных реализациях используются разные константы K, которые предоставляют разные преимущества, в частности большинство реализаций идут либо для K = 2, либо K = 1.5. Более высокий K сделает его быстрее, поскольку он потребует меньшего роста, но в то же время он будет иметь большее влияние на память. Например, в gcc K = 2, тогда как в VS (Dinkumware) K = 1.5.

(*) Если бы вектор рос на постоянную величину, то сложность push_back стала бы линейной, а не амортизированной постоянной. Например, если вектор рос на 10 элементов при необходимости, стоимость роста (копия всего элемента на новый адрес памяти) была бы O( N / 10 ) (каждые 10 элементов, переместить все) или O( N ).

Ответ 3

Емкость vector полностью зависит от реализации, никто не может сказать, как она растет.

Ответ 4

Используете ли вы реализацию "Rogue Wave"?

Как растет производительность, до реализации. Используйте 2 ^ N.

Ответ 5

Да, емкость удваивается каждый раз, когда она превышена. Это зависит от реализации.

Ответ 6

Просто чтобы добавить математическое доказательство сложности времени для vector::push_back, скажем, размер вектора равен n, здесь нас интересует количество копий, которое произошло до сих пор, скажем, y, обратите внимание, что копия происходит каждый раз, когда вы увеличиваете вектор.

Расти с коэффициентом K

  y = K^1 + K^2 + K^3 ... K^log(K, n)
K*y =     + K^2 + K^3 ... K^log(K, n) + K*K^log(K, n)

K*y-y = K*K^log(K, n) - K
y = K(n-1)/(K-1) = (K/(K-1))(n-1)

T(n) = y/n = (K/(K-1)) * (n-1)/n < K/(K-1) = O(1)

K/(K-1) является константой, и видим наиболее распространенные случаи:

  • K = 2, T (n) = 2/(2-1) = 2
  • K = 1,5, T (n) = 1,5/(1,5-1) = 3

и фактически есть причина выбора K как 1,5 или 2 в различных реализациях, см. график ниже: T(n) changes by K

Мы можем видеть, как T(n) достигает минимума, когда K составляет около 2, использование большого K не дает больших преимуществ за счет выделения большего количества памяти.

Расти на постоянное количество C

y = C + 2*C + 3*C + 4*C +  ... (n/C) * C
  = C(1+2+3+...+n/C), say m = n/C
  = C*(m*(m-1)/2)
  = n(m-1)/2

T(n) = y/n = (n(m-1)/2)/n = (m-1)/2 = n/2C - 1/2 = O(n)

Как мы могли видеть это лайнер