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

Question

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

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

Есть указатели?

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

Спасибо.

Answer 1

* * * * * * * * * * * * * * * * * * * * * * * Вектор, который нужно быстрее построить или очистить, чем дек или список; это более простая структура данных.

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

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

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

UPDATE: Оригинальный постер попросил привести пример. Код ниже умножает на 128 мега вставок и выводит

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

при компиляции и запуске с g ++ -O3 в Debian / Lenny на старой машине 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 2

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

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

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

1007 * Е.Г. *

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 3

«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 4

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

Answer 5

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

Answer 6

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

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

На cplusplus.com очень хороший обзор операций для каждого типа контейнера.

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

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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

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