*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 31 марта 2010 г.

Добавление элементов в std::vector

На собеседованиях по С++ задают много вопросов про контейнеры STL. И самый безобидный из них, как думал, std::vector. Но вот и по нему попался интересный вопрос.

Представим, что стратегия управления внутренним буфером контейнера std::vector (в реальности, она иная) такова: изначально размер буфера равен нулю, и он будет увеличивается вдвое каждый раз, когда в нем уже нет места под следующий элемент.

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

Как я полагаю, в среднем ожидается, что отвечать стоит практически сразу.

На всякий случай: мой ответ будет завтра.

А сейчас мини эксперимент с реальным std::vector (компилятор, и сообразно STL — Sun C++ 5.9 SunOS_sparc) для выяснения реальной стратегии роста буфера в векторе:

#include <vector>
#include <iostream>
#include <iomanip>
#include <cstdlib>

int main() {
  int last = -1;
  std::vector<int> a;
  std::cout << std::setw(12) << "Capacity" << " " 
            << std::setw(12) << "Size"
            << std::setw(12) << "Ratio" << std::endl
            << std::setw(12) << std::setfill('-') << "-" << " " 
            << std::setw(12) << "-" << " "
            << std::setw(12) << "-" << std::endl;

  std::cout << std::setfill(' ') << std::fixed;
  while (1) {
    if (a.capacity() != last) {
      last = a.capacity();
      std::cout << std::setw(12) << a.capacity() << " "
                << std::setw(12) << a.size() << " "
                << std::setw(12) << std::setprecision(6)
                << (float)a.capacity() / a.size() << std::endl;
    }
    a.push_back(std::rand());
  }
  return 0;
}

А вот и результат:

    Capacity         Size       Ratio
------------ ------------ ------------
           0            0          NaN
          32            1    32.000000
          64           33     1.939394
         103           65     1.584615
         166          104     1.596154
         268          167     1.604790
         433          269     1.609665
         700          434     1.612903
        1132          701     1.614836
        1831         1133     1.616064
        2962         1832     1.616812
        4792         2963     1.617280
        7753         4793     1.617567
       12544         7754     1.617746
       20296        12545     1.617856
       32838        20297     1.617875
       53131        32839     1.617924
       85965        53132     1.617952
      139091        85966     1.617977
      225049       139092     1.617987
      364129       225050     1.617992
      589160       364130     1.617994
      953260       589161     1.617996
     1542374       953261     1.617998
     2495561      1542375     1.617999
     4037817      2495562     1.617999
     6533187      4037818     1.617999
    10570696      6533188     1.618000
    17103386     10570697     1.618000
    27673278     17103387     1.618000
    44775363     27673279     1.618000
    72446537     44775364     1.618000
   117218496     72446538     1.618000
   189659526    117218497     1.618000
   306869113    189659527     1.618000

Выходит, что для моей STL - это какой-то магический коэффициент 1.618.

Update: В комментариях подсказали хорошую ссылку на тему стратегии управления размером вектора.

Update 2: Лично мой ответ на тему вычислительной сложности последовательного добавления элементов в вектор, если вектор будет удваивать размер буфера при переполнении.

Так как мы добавляем k элементов, то это как минимум O(k). А так как по условию вектор удваивает буфер каждый раз, когда нет места, то произойдет log2(k) раз (так как по условию элементы поступают последовательно).

Получаем в этоге: O(k*log2(k)).

Update 3: В комментариях меня поправили: O(k + log2(k)) или просто O(k)

13 комментариев:

  1. Вычислительная сложность на добавление - константная. Но при увеличении размера делается copy. Если коэффициент 1.618, то копировать будет чаще, чем добавлять. А значит даже в случае int-ов оверхед будет в разы больше, чем при простом добавлении без ресайза. А если там сложные объекты и конструкторы копирования, то готовься к десятикратным и сколько угодно кратным оверхедам...
    И вообще, пихать что-то в вектор не зарезервив его сначала - это моветон :)

    P.S.:
    OpenID не работает - ни стэндалон блог ни ЖЖ не дает использовать.

    ОтветитьУдалить
  2. Oleg: По поводу OpenID - может у blogspot'а что-то барахлит.

    ОтветитьУдалить
  3. Gunner Kade: Интересно почему авторы выбрали такое отношение?

    ОтветитьУдалить
  4. "Интересно почему авторы выбрали такое отношение?"
    http://alenacpp.blogspot.com/2005/06/vector_30.html

    ОтветитьУдалить
  5. capacity нужно делить на предыдущую capacity. А то получается что буфер увеличился с 32 до 64 а у Вас коэффициент 1.939394. В libstdc+++ увеличивается вдвое:
    const size_type __len = size() + std::max(size(), __n);

    ОтветитьУдалить
  6. NSL: очень интересная причина выбора константы - пытаться выделять память так, чтобы максимально плотно заполнить освободившуюся память (минимизировать фрагментацию).
    Александр: по поводу сложности алгоритма - сперва подумал, что сложность O(k), потом учел затраты на копирование при выделении нового буфера - снова O(k). Вообще говоря, нужно еще учитывать сложность алгоритма выделения и освобождения памяти (я считал, что сложность этих алгоритмов не выше, чем O(n)).

    ОтветитьУдалить
  7. Gunner Kade: Да, было бы интересно взглянуть на эту константу в разных реализациях STL.

    ОтветитьУдалить
  8. Добавил собственный вариант решения по вычислительной сложности.

    ОтветитьУдалить
  9. >Получаем в этоге: O(k*log2(k)).

    Получается, вроде, O(k + log2(k)), что на самом деле остаётся O(k). Вы же не при каждом добавлении элемента делаете O(log2(k)) операций. Или я что-то не так понял?

    ОтветитьУдалить
  10. Василий: все так, но надо еще не забыть про затраты на копирование старого буфера в новый при каждом resize'е вектора.
    Если посчитать кол-во операций копирования получим:
    2^0 + 2^1 + 2^2 + 2^3 + ... + 2^[log2(k)] = (2^([log2(k)]+1) - 1)/(2-1) = [примерно равно] = 2*k.
    Вкупе с [log2(k)] операциями освобождения и выделения памяти сложности O(1) (допустим) и с k добавлениями элементов в вектор (push_back) получаем
    O(2*k + [log2(k)] + k) = O(k)

    ОтветитьУдалить
  11. Gunner Kade: А почему 2^1 + 2^2 + 2^3 + ... + 2^[log2(k)] преобразуется в 2*(2^[log2(k)]-1)/(2-1)? Ведь это же просто 2^(log2(k)+1)-1, нет?

    ОтветитьУдалить
  12. Александр: было бы 2^(log2(k)+1)-1, если бы сумма начиналась с 2^0, но в данном случае по формуле суммы геометрической прогрессии получаем:
    S = [первый член суммы]*([знаменатель прогрессии]^[кол-во членов в сумме]-1)/([знаменатель прогрессии] - 1) = 2*(2^[log2(k)]-1)/(2-1)

    ОтветитьУдалить