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)
Сообщения
Вычислительная сложность на добавление - константная. Но при увеличении размера делается copy. Если коэффициент 1.618, то копировать будет чаще, чем добавлять. А значит даже в случае int-ов оверхед будет в разы больше, чем при простом добавлении без ресайза. А если там сложные объекты и конструкторы копирования, то готовься к десятикратным и сколько угодно кратным оверхедам...
ОтветитьУдалитьИ вообще, пихать что-то в вектор не зарезервив его сначала - это моветон :)
P.S.:
OpenID не работает - ни стэндалон блог ни ЖЖ не дает использовать.
1.618
ОтветитьУдалитьOleg: По поводу OpenID - может у blogspot'а что-то барахлит.
ОтветитьУдалитьGunner Kade: Интересно почему авторы выбрали такое отношение?
ОтветитьУдалить"Интересно почему авторы выбрали такое отношение?"
ОтветитьУдалитьhttp://alenacpp.blogspot.com/2005/06/vector_30.html
capacity нужно делить на предыдущую capacity. А то получается что буфер увеличился с 32 до 64 а у Вас коэффициент 1.939394. В libstdc+++ увеличивается вдвое:
ОтветитьУдалитьconst size_type __len = size() + std::max(size(), __n);
NSL: очень интересная причина выбора константы - пытаться выделять память так, чтобы максимально плотно заполнить освободившуюся память (минимизировать фрагментацию).
ОтветитьУдалитьАлександр: по поводу сложности алгоритма - сперва подумал, что сложность O(k), потом учел затраты на копирование при выделении нового буфера - снова O(k). Вообще говоря, нужно еще учитывать сложность алгоритма выделения и освобождения памяти (я считал, что сложность этих алгоритмов не выше, чем O(n)).
Gunner Kade: Да, было бы интересно взглянуть на эту константу в разных реализациях STL.
ОтветитьУдалитьДобавил собственный вариант решения по вычислительной сложности.
ОтветитьУдалить>Получаем в этоге: O(k*log2(k)).
ОтветитьУдалитьПолучается, вроде, O(k + log2(k)), что на самом деле остаётся O(k). Вы же не при каждом добавлении элемента делаете O(log2(k)) операций. Или я что-то не так понял?
Василий: все так, но надо еще не забыть про затраты на копирование старого буфера в новый при каждом 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)
Gunner Kade: А почему 2^1 + 2^2 + 2^3 + ... + 2^[log2(k)] преобразуется в 2*(2^[log2(k)]-1)/(2-1)? Ведь это же просто 2^(log2(k)+1)-1, нет?
ОтветитьУдалитьАлександр: было бы 2^(log2(k)+1)-1, если бы сумма начиналась с 2^0, но в данном случае по формуле суммы геометрической прогрессии получаем:
ОтветитьУдалитьS = [первый член суммы]*([знаменатель прогрессии]^[кол-во членов в сумме]-1)/([знаменатель прогрессии] - 1) = 2*(2^[log2(k)]-1)/(2-1)