Что быстрее, итерация вектора STL с помощью vector :: iterator или at ()? - PullRequest
Новая
       116

Что быстрее, итерация вектора STL с помощью vector :: iterator или at ()?

55 голосов
/ 22 апреля 2009

С точки зрения производительности, что будет работать быстрее? Есть ли разница? Это зависит от платформы? 

//1. Using vector<string>::iterator:
vector<string> vs = GetVector();

for(vector<string>::iterator it = vs.begin(); it != vs.end(); ++it)
{
   *it = "Am I faster?";
}

//2. Using size_t index:
for(size_t i = 0; i < vs.size(); ++i)
{
   //One option:
   vs.at(i) = "Am I faster?";
   //Another option:
   vs[i] = "Am I faster?";
}

Ответы [ 16 ]

35 голосов
/ 22 апреля 2009

Использование итератора приводит к увеличению указателя (для приращения) и для разыменования в разыменование указателя.
С индексом приращение должно быть одинаково быстрым, но поиск элемента включает добавление (указатель данных + индекс) и разыменование этого указателя, но разница должна быть незначительной.
at() также проверяет, находится ли индекс в границах, поэтому он может быть медленнее.

Результаты тестов для 500M итераций, векторный размер 10, с gcc 4.3.3 (-O3), linux 2.6.29.1 x86_64:
at(): 9158мс
operator[]: 4269мс
iterator: 3914мс

YMMV, но если использование индекса делает код более читабельным / понятным, вам следует это сделать.

26 голосов
/ 22 апреля 2009

Почему бы не написать тест и узнать?

Редактировать: Мое плохое - я думал, что рассчитывал оптимизированную версию, но это не так. На моей машине, скомпилированной с g ++ -O2, версия итератора немного медленнее , чем версия operator [], но, вероятно, не так значительно. 

#include <vector>
#include <iostream>
#include <ctime>
using namespace std;

int main() {
    const int BIG = 20000000;
    vector <int> v;
    for ( int i = 0; i < BIG; i++ ) {
        v.push_back( i );
    }

    int now = time(0);
    cout << "start" << endl;
    int n = 0;
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        n += *it;
    }

    cout << time(0) - now << endl;
    now = time(0);
    for(size_t i = 0; i < v.size(); ++i) {
        n += v[i];
    }
    cout << time(0) - now << endl;

    return n != 0;
}
15 голосов
/ 22 апреля 2009

Если вам не нужна индексация, не используйте ее. Концепция итератора для вас. Итераторы очень легко оптимизировать, а прямой доступ требует дополнительных знаний.

Индексирование предназначено для прямого доступа. Скобки и метод at делают это. at, в отличие от [], проверит индексирование вне границ, поэтому будет медленнее.

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

14 голосов
/ 22 апреля 2009

Поскольку вы смотрите на эффективность, вы должны понимать, что следующие варианты потенциально более эффективны: 

//1. Using vector<string>::iterator:

vector<string> vs = GetVector();
for(vector<string>::iterator it = vs.begin(), end = vs.end(); it != end; ++it)
{
   //...
}

//2. Using size_t index:

vector<string> vs = GetVector();
for(size_t i = 0, size = vs.size(); i != size; ++i)
{
   //...
}

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

5 голосов
/ 22 апреля 2009

Как все здесь говорят, сделайте тесты.

Сказав это, я бы сказал, что итератор работает быстрее, поскольку at () также выполняет проверку диапазона, т. Е. Выдает исключение out_of_range, если индекс выходит за пределы. Эта проверка сама по себе влечет за собой некоторые накладные расходы.

4 голосов
/ 22 апреля 2009

Я думаю, что первый вариант быстрее.

Но это зависит от реализации. Чтобы быть уверенным, вы должны профилировать свой собственный код.

Зачем профилировать свой собственный код?

Поскольку все эти факторы будут влиять на результаты:

  • Какая ОС
  • Какой компилятор
  • Какая реализация STL использовалась
  • Были ли включены оптимизации?
  • ... (другие факторы)
2 голосов
/ 14 апреля 2015

Это зависит.

Ответ гораздо более тонкий, чем показывают существующие ответы.

at всегда медленнее, чем итераторы, или operator[].
Но для operator[] против итераторов это зависит от:

  1. Как именно вы используете operator[].

  2. Наличие в вашем конкретном процессоре индексных регистров (ESI/EDI на x86).

  3. Сколько другого кода также использует тот же индекс, переданный в operator[].
    (например, индексируете ли вы через несколько массивов на шаге?)

И вот почему:

  1. Если вы делаете что-то вроде 

    std::vector<unsigned char> a, b;
for (size_t i = 0; i < n; ++i)
{
    a[13 * i] = b[37 * i];
}

    Тогда этот код, вероятно, будет намного медленнее, чем версия итератора, поскольку он выполняет умножение операцию на каждой итерации цикла!

    Аналогично, если вы делаете что-то вроде: 

    struct T { unsigned char a[37]; };
std::vector<T> a;
for (size_t i = 0; i < n; ++i)
{
    a[i] = foo(i);
}

    Тогда, вероятно, также будет медленнее, чем версия итератора, потому что sizeof(T) - это , а не степень 2 , и, следовательно, вы (снова) умножаетесь на 37 каждый раз, когда вы зацикливаетесь!

  2. Если ваш ЦП имеет регистры индекса, то ваш код может работать так же или даже лучше с индексами, а не с итераторами, , если использование регистра индекса освобождает другой регистр для использования в цикле , Это , а не , что вы можете сказать, просто взглянув; вам придется профилировать код и / или разбирать его.

  3. Если несколько массивов могут совместно использовать один и тот же индекс, то код должен только увеличивать один индекс вместо увеличения нескольких итераторов, что сокращает число операций записи в память и, таким образом, обычно увеличивает производительность. Однако, если вы выполняете итерации только по одному массиву, тогда итератор вполне может быть быстрее, поскольку он устраняет необходимость добавлять смещение к существующему базовому указателю.

Как правило, следует предпочитать итераторы индексам, а индексы - указателям, до тех пор, пока профилирование не покажет, что профилирование показывает, что переключение будет выгодно, поскольку итераторы общего назначения. и уже, вероятно, будет самым быстрым подходом; они не требуют случайной адресации данных, что позволяет при необходимости менять местами контейнеры. Индексы являются следующим предпочтительным инструментом, поскольку они по-прежнему не требуют прямого доступа к данным - они становятся недействительными реже, и вы можете, например, замените deque на vector без проблем. Указатели должны быть последним средством, и они окажутся полезными только в том случае, если итераторы еще не выродились в ловушки в режиме выпуска.

2 голосов
/ 19 июля 2014

Это на самом деле зависит от того, что вы делаете, но если вам придется повторять объявление итератора, Итераторы становятся МАРЖЕННО МЕДЛЕННЫМИ. В моих тестах самая быстрая итерация состояла бы в том, чтобы объявить простой * массив ваших векторов и выполнить итерацию по нему.

например:

Итерация вектора и вытягивание двух функций за проход. 

vector<MyTpe> avector(128);
vector<MyTpe>::iterator B=avector.begin();
vector<MyTpe>::iterator E=avector.end()-1;
for(int i=0; i<1024; ++i){
 B=avector.begin();
   while(B!=E)
   {
       float t=B->GetVal(Val1,12,Val2); float h=B->GetVal(Val1,12,Val2);
    ++B;
  }}

Вектор занял 90 кликов (0,090000 секунд)

Но если вы сделали это с помощью указателей ... 

for(int i=0; i<1024; ++i){
MyTpe *P=&(avector[0]);
   for(int i=0; i<avector.size(); ++i)
   {
   float t=P->GetVal(Val1,12,Val2); float h=P->GetVal(Val1,12,Val2);
   }}

Вектор занял 18 кликов (0,018000 секунд)

Что примерно эквивалентно ... 

MyTpe Array[128];
for(int i=0; i<1024; ++i)
{
   for(int p=0; p<128; ++p){
    float t=Array[p].GetVal(Val1, 12, Val2); float h=Array[p].GetVal(Val2,12,Val2);
    }}

Массив За 15 нажатий (0,015000 секунд).

Если вы исключите вызов avector.size (), время станет таким же.

Наконец, звоним с [] 

for(int i=0; i<1024; ++i){
   for(int i=0; i<avector.size(); ++i){
   float t=avector[i].GetVal(Val1,12,Val2); float h=avector[i].GetVal(Val1,12,Val2);
   }}

Вектор занял 33 клика (0,033000 секунд)

Время с часами ()

2 голосов
/ 12 февраля 2010

Вы можете использовать этот тестовый код и сравнить результаты! Дио это! 

#include <vector> 
#include <iostream> 
#include <ctime> 
using namespace std;; 


struct AAA{
    int n;
    string str;
};
int main() { 
    const int BIG = 5000000; 
    vector <AAA> v; 
    for ( int i = 0; i < BIG; i++ ) { 
        AAA a = {i, "aaa"};
        v.push_back( a ); 
    } 

    clock_t now;
    cout << "start" << endl; 
    int n = 0; 
    now = clock(); 
    for(vector<AAA>::iterator it = v.begin(); it != v.end(); ++it) { 
        n += it->n; 
    } 
   cout << clock() - now << endl; 

    n = 0;
    now = clock(); 
    for(size_t i = 0; i < v.size(); ++i) { 
        n += v[i].n; 
    } 
    cout << clock() - now << endl; 

    getchar();
    return n != 0; 
}
2 голосов
/ 22 апреля 2009

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

Страница:
...