push_back для вектора, deque и списков

Question

Я пытаюсь оптимизировать подпрограмму C++. Основным узким местом в этой подпрограмме является push_back() вектора объектов. Вместо этого я попытался использовать deque и даже попробовал список. Но странно (и вопреки теории) реализация deque и list выполняется намного медленнее, чем векторная копия.

Фактически даже clear() работает намного медленнее для реализации deque и list, чем векторный аналог. В этом случае реализация Vector, по-видимому, является самой быстрой, тогда как реализация списка является самой медленной.

Любые указатели?

Примечание: векторный запас() мог бы ускорить реализацию, но не может быть выполнен, так как он неизвестен по размеру.

Спасибо.

Answer 1

Вы отбрасываете сами объекты или указатель на них? Указатели обычно будут намного быстрее, так как копировать всего 4-8 байт по сравнению с тем, что размер объектов.

Answer 2

Вам нужно будет предоставить дополнительную информацию о поведении рутины.

В одном месте вас беспокоит скорость push_back() в другом вас беспокоит clear(). Собираете ли вы контейнер, делаете что-то, а потом его сбрасываете?

Результаты, которые вы видите на clear() являются потому, что vector<> только должен освободить SINGL блок памяти, deque<> должен выпустить несколько, и list<> должен выпустить один для каждого элемента.

Answer 3

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

Answer 4

Ожидается, что вектор будет быстрее строить или очищать, чем deque или список; это более простая структура данных.

Что касается vector::push_back, он должен сделать две вещи:

1. проверка вектор является достаточно большим, чтобы крепят новый элемент.
2. Вставить новый товар.

Вы можете в целом ускорить процесс, исключив шаг 1 простым изменением размера вектора и используя operator[] для установки элементов.

ОБНОВЛЕНИЕ: Оригинальный плакат попросил пример. Код ниже 128 раз мега вставках и выходов

push_back   : 2.04s 
reserve & push_back : 1.73s 
resize & place  : 0.48s 

при компиляции и работать с г ++ -O3 на Debian/Ленни на старой P4 машины.

#include <iostream> 
#include <time.h> 
#include <vector> 

int main(int,char**) 
{ 
    const size_t n=(128<<20); 

    const clock_t t0=clock(); 
    { 
    std::vector<unsigned char> a; 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t1=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.reserve(n); 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t2=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.resize(n); 
    for (size_t i=0;i<n;i++) a[i]=i; 
    } 
    const clock_t t3=clock(); 

    std::cout << "push_back   : " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "reserve & push_back : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "resize & place  : " << (t3-t2)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 

    return 0; 
} 

Answer 5

Что касается push_back() будучи медленным и резерв не будучи никакой помощи, реализация STL используется в MSVC что-то работает следующим образом: Когда вы первый создать вектор она оставляет пространство для Я думаю, 10 элементов. С этого момента, когда он заполняется, он оставляет пространство в 1,5 раза больше количества элементов в векторе. Итак, что-то вроде 10, 15, 22, 33, 49, 73, 105, 157 ... Перераспределение дорого.

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

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

Answer 6

Если вы не знаете, сколько объектов вы будете добавлять, очень сложно найти оптимальное решение. Все, что вы можете сделать, это попытаться минимизировать затраты, которые, как вы знаете, происходят, что в данном случае означает, что ваш вектор постоянно изменяется.

Вы можете сделать это двумя способами;

1) Разделите свою операцию на строительство и завершение работы. Здесь вы создаете список в вектор, который, как гарантируется, будет достаточно большим и когда он будет скопирован в другой вектор.

E.g.

std::vector<Foo> hugeVec; 
hugeVec.reserve(1000); // enough for 1000 foo's 

// add stuff 

std::vector<Foo> finalVec; 
finalVec = hugeVec; 

2) В качестве альтернативы, когда ваш вектор является полным резервом вызовов, достаточным для другого набора объектов;

if (vec.capacity() == vec.size()) 
    vec.reserve(vec.size() + 16); // alloc space for 16 more objects 

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

Answer 7

Если вы хотите, чтобы вектор был быстрым, вы должны зарезервировать() достаточно места. Это имеет огромное значение, потому что каждый рост ужасно дорог. Если вы не знаете, сделайте хорошее предположение.

Answer 8

"push_back()" может быть медленным, если копия объекта работает медленно. Если конструктор по умолчанию работает быстро, и у вас есть способ использовать swap, чтобы избежать копирования, у вас может быть гораздо более быстрая программа.

void test_vector1() 
{ 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi); // copy of a large object 
    } 
} 

void test_vector2() 
{ 
    vector<int> vi0; 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi0); // copy of a small object 
     vvi.back().swap(vi); // swap is fast 
    } 
} 

Результаты:

VS2005-debug 
* test_vector1 -> 297 
* test_vector2 -> 172 

VS2005-release 
* test_vector1 -> 203 
* test_vector2 -> 94 

gcc 
* test_vector1 -> 343 
* test_vector2 -> 188 

gcc -O2 
* test_vector1 -> 250 
* test_vector2 -> 156 

Answer 9

Вы должны выбрать контейнер в соответствии с тем, что вы собираетесь с ним делать.

Релевантные действия: расширение (с push), вставка (может вообще не понадобиться), извлечение, удаление.

В cplusplus.com имеется очень хороший обзор операций по типу контейнера.

Если операция push -bound, имеет смысл, что вектор бьет все остальные. Хорошая вещь о deque заключается в том, что он выделяет фиксированные куски, поэтому будет более эффективно использовать фрагментированную память.