Динамично выделенные массивы или станд.:: вектор

Особенность стандартных библиотечных классов, таких как std :: vector , заключается в том, что да, наивно, это намного больше кода, чем необработанный массив. Но все это может быть тривиально встроено компилятором, а это означает, что если включена оптимизация, он становится по существу тем же кодом , как если бы вы использовали необработанный массив. Таким образом, разница в скорости заметна, но отсутствует. Все накладные расходы удаляются во время компиляции.

Но для этого необходимо включить оптимизацию компилятора.

Ради удовольствия попробуйте выполнить итерацию по простому массиву, используя указатель вместо целочисленного индекса (код должен выглядеть так же, как итерация вектора, поскольку точка итераторов STL должна выглядеть как указатель арифметика для большинства операций). Бьюсь об заклад, в этом случае скорость будет точно такой же. Это, конечно, означает, что вам следует выбрать вектор, поскольку это избавит вас от головной боли от управления массивами вручную.

Я согласен с rmeador,

  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i; // <-- quick offset calculation
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i; // <-- not fair play :) - offset = arr + i*size(int)
  }

Я предполагаю, что причина, по которой вы обнаружили, что повторение и добавление в std :: vector в 3 раза медленнее, чем простой массив, - это комбинация затрат на повторение вектора и выполнение присваивания.

Править:

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

Я не вижу, как std :: vector может быть быстрее (конечно, не в 3 раза быстрее), чем копия ванильного массива - я думаю, что к скомпилированному коду std :: vector применяется некоторая оптимизация, чего нет в версии массива.

Исходные результаты тестов:

$ ./array
array:  0.059375
vector: 0.021209

• std: : vector в 3 раза быстрее. Снова тот же тест, за исключением добавления дополнительного внешнего цикла для выполнения цикла тестового итератора 1000 раз:

  $ ./array массив: 21.7129 vector: 21.6413

• std :: vector теперь имеет такую ​​же скорость, как и array.

Edit 2

Нашел! Таким образом, проблема с вашим тестовым примером заключается в том, что в векторном случае память, содержащая данные, кажется, уже находится в кеше ЦП - либо по способу инициализации, либо из-за вызова vec.end () . Если я «прогреваю» кэш ЦП перед каждым тестом синхронизации, я получаю одинаковые числа для массива и вектора:

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

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  // get vec into CPU cache.
  for (int i = 0; vecIt != vecEnd; i++) { *(vecIt++) = i; }
  vecIt = vec.begin();
  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i;
  }
  end = clock();
  std::cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<std::endl;

  int* arr = new int[9999999];

  // get arr into CPU cache.
  for (int i = 0; i < 9999999; i++) { arr[i] = i; }
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  std::cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<std::endl;
}

Это дает мне следующий результат:

$ ./array
vector: 0.020875
array: 0.020695

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

Думаю, ответ здесь очевиден: это не имеет значения. Как сказал Джалф, код будет примерно таким же, но даже если это не так, посмотрите на числа. Опубликованный вами код создает огромный массив из 10 МИЛЛИОНОВ элементов, но итерация по всему массиву занимает всего несколько сотых секунды.

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

Чтобы доказать мою точку зрения, вот код с одним изменением: присвоение i элементу массива заменяется присвоением sqrt ( я). На моей машине, использующей -O2, время выполнения утроится с 0,02 до 0,06 секунды.

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

using namespace std;

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = sqrt(i);
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
}

Кажется, проблема в том, что вы скомпилировали свой код с отключенной оптимизацией. На моей машине OS X 10.5.7 с g ++ 4.0.1 я действительно вижу, что вектор быстрее, чем примитивные массивы, в 2,5 раза.

С помощью gcc попробуйте передать -O2 компилятору и посмотрите, есть ли улучшения.

Одна из причин, по которой ваш код может не работать точно так же, заключается в том, что в вашей версии std :: vector вы используете два значения: целое число i и std :: vector :: iterator vecIt . Чтобы быть эквивалентным, вы можете выполнить рефакторинг до

start = clock();
for (int i = 0; i < vec.size(); i++) {
  vec[i] = i;
}
end = clock();
cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

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

С вектором вы увеличиваете оба итератор (vecIT) и отдельная переменная (i) для генерации значений присваивания.

С массивом вы только увеличиваете переменную i и используете ее для двойного назначения.