Что касается производительности, что будет работать быстрее? Есть ли разница? Это зависит от платформы?
//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?";
}
Почему бы не написать тест и не узнать?
Изменить: Мое плохое - я думал, что я выбрал оптимизированную версию, но не был. На моей машине, скомпилированной с 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;
}
Использование итератора приводит к увеличению указателя (для увеличения) и разыменованию разыменования указателя.
С индексом приращение должно быть одинаково быстрым, но поиск элемента включает добавление (указатель данных + индекс) и разыменование этого указателя, но разница должна быть предельной. at() также проверяет, находится ли индекс в границах, поэтому он может быть медленнее.
Результаты тестов для 500M итераций, размер вектора 10, с gcc 4.3.3 (-O3), linux 2.6.29.1 x86_64: at(): 9158ms operator[]: 4269ms iterator: 3914ms
YMMV, но если использование индекса делает код более удобочитаемым/понятным, вы должны это сделать.
Если вам не нужна индексация, не используйте его. Концепция итератора существует для вашего наилучшего. Итераторы очень легко оптимизируются, а прямой доступ требует дополнительных знаний.
Индексирование предназначено для прямого доступа. Скобки и метод at делают это. at будет, в отличие от [], проверять отсутствие индексации, поэтому он будет медленнее.
Кредо: не спрашивайте, что вам не нужно. Тогда компилятор не будет взимать плату за то, что вы не используете.
Поскольку вы смотрите на эффективность, вы должны понимать, что следующие варианты потенциально более эффективны:
//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 вызывается только один раз, а не каждый раз через цикл. Вероятно, компилятор все равно будет встраивать эти функции, но этот способ гарантирует.
Как говорят все остальные, делайте тесты.
Сказав это, я бы сказал, что итератор работает быстрее, так как at() также проверяет диапазон, т.е. он выдает исключение out_of_range, если индекс выходит за пределы. Эта проверка сама по себе может вызвать некоторые накладные расходы.
Я бы предположил, что первый вариант быстрее.
Но это зависит от реализации. Чтобы убедиться, что вы должны создать собственный код.
Зачем формировать собственный код?
Потому что все эти факторы будут меняться:
Первый режим будет быстрее в режиме отладки, потому что доступ к индексу создает итераторы за сценой, но в режиме выпуска, где все должно быть встроено, разница должна быть незначительной или null
Вы можете использовать этот тестовый код и сравнить результаты! Dio it!
#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;
}
Это действительно зависит от того, что вы делаете, но если вам нужно продолжать повторное объявление итератора, Итераторы становятся MARGINALLY SLOWER. В моих тестах самая быстрая возможная итерация заключалась бы в том, чтобы объявить простой * вашему массиву векторов и пройти через это.
например:
Итерация вектора и вытягивание двух функций за проход.
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);
}}
Vector заработал 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);
}}
Vector Взял 33 клика (0.033000 секунд)
Сроки с часами()
at всегда медленнее, чем итераторы или operator[].
Но для operator[] против итераторов это зависит от:
Как именно вы используете operator[].
У вашего конкретного процессора есть индексные регистры (ESI/EDI на x86).
Сколько другого кода также использует тот же самый индекс, переданный в operator[].
(например, вы индексируете через несколько массивов в стоп-стоп?)
Вот почему:
Если вы делаете что-то вроде
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 каждый раз, когда вы зацикливаете!
Если ваш процессор имеет индексные регистры, то ваш код может работать также или даже лучше с индексами, а не с помощью итераторов, если использование индекса индекса освобождает другой регистр для использования в цикле. Это не то, что вы можете сказать, просто глядя; вам придется профилировать код и/или дизассемблировать его.
Если несколько массивов могут совместно использовать один и тот же индекс, тогда код должен только увеличивать один индекс, а не увеличивать количество итераторов, что уменьшает количество записей в памяти и, как следствие, повышает производительность. Однако, если вы только итерации по одному массиву, то итератор может быть очень быстрым, так как он избегает необходимости добавлять смещение к существующему базовому указателю.
В общем, вы должны отсылать итераторы к индексам и индексам указателям до тех пор, пока вам не удастся столкнуться с узким местом, которое показывает профилирование, будет полезно переключиться, поскольку итераторы являются универсальными и уже вероятно, будет самым быстрым подходом; они не требуют, чтобы данные были случайным образом адресованы, что позволяет при необходимости заменять контейнеры. Индексы являются следующим предпочтительным инструментом, так как они по-прежнему не требуют прямого доступа к данным - они становятся недействительными реже, и вы можете, например, замените a deque на a vector без каких-либо проблем. Указатели должны быть последним средством, и они будут полезны только в том случае, если итераторы еще не вырождаются в потенциометры в режиме выпуска.
Я думаю, что единственным ответом может быть тест на вашей платформе. Как правило, единственное, что стандартизовано в STL, это тип итераторов, предлагаемых коллекцией, и сложность алгоритмов.
Я бы сказал, что между этими двумя версиями нет (не так уж много) - единственное различие, которое я мог бы подумать, - это то, что код должен перебирать всю коллекцию, когда ему приходится вычислять длину array (я не уверен, что длина сохраняется в переменной внутри вектора, тогда накладные расходы не имеют значения)
Доступ к элементам с "at" должен занять немного больше времени, чем прямой доступ к нему с помощью [], поскольку он проверяет, находитесь ли вы в границах вектора и выбрасывает исключение, если вы находитесь за пределами границ (кажется [] как правило, просто использует арифметику указателя - поэтому он должен быть быстрее)
Если вы используете VisualStudio 2005 или 2008, чтобы получить наилучшую производительность из вектора, вам нужно определить _SECURE_SCL = 0
По умолчанию используется _SECURE_SCL, что делает итерацию над помещением значительно медленнее. Тем не менее, оставьте это в отладочных сборках, это значительно облегчит отслеживание любых ошибок. Одно слово предостережения, так как макрос изменяет размер итераторов и контейнеров, вы должны быть согласованными во всех единицах компиляции, которые совместно используют контейнер stl.
Я нашел эту нить сейчас, пытаясь оптимизировать мой код OpenGL и хочу поделиться своими результатами, даже если поток старый.
Фон: У меня есть 4 вектора размером от 6 до 12. Запись происходит только один раз в начале кода, и чтение происходит для каждого из элементов в векторах каждые 0,1 миллисекунды
Ниже приведена урезанная версия используемого кода:
for(vector<T>::iterator it = someVector.begin(); it < someVector.end(); it++)
{
T a = *it;
// Various other operations
}
Частота кадров с использованием этого метода составляла около 7 кадров в секунду (fps).
Однако, когда я изменил код на следующий, частота кадров почти удвоилась до 15 кадров в секунду.
for(size_t index = 0; index < someVector.size(); ++index)
{
T a = someVector[index];
// Various other operations
}
Разница должна быть незначительной. std::vector гарантирует, что его элементы будут последовательно размещены в памяти. Поэтому большинство реализаций stl реализуют итераторы в std::vector как простой указатель. Поскольку это ум, единственная разница между этими двумя версиями должна заключаться в том, что первый увеличивает указатель, а во втором - индекс, который затем добавляется к указателю. Таким образом, моя догадка была бы второй, может быть, одной чрезвычайно быстрой (с точки зрения циклов) машинной инструкцией больше.
Попробуйте проверить код машины, который производит ваш компилятор.
В целом, однако, совет должен был бы профиль, если это действительно имеет значение. Размышление о таком вопросе преждевременно обычно не дает вам слишком многого. Как правило, ваши горячие точки кода будут в другом месте, где вы можете не подозревать об этом с первого взгляда.
Вот код, который я написал, скомпилированный в Code:: Blocks v12.11, используя компилятор mingw по умолчанию. Это создает огромный вектор, затем обращается к каждому элементу с помощью итераторов,() и индекса. Каждый цикл зацикливается один раз, вызывая последний элемент по функции и один раз, сохраняя последний элемент во временную память.
Сроки выполняются с использованием GetTickCount.
#include <iostream>
#include <windows.h>
#include <vector>
using namespace std;
int main()
{
cout << "~~ Vector access speed test ~~" << endl << endl;
cout << "~ Initialization ~" << endl;
long long t;
int a;
vector <int> test (0);
for (int i = 0; i < 100000000; i++)
{
test.push_back(i);
}
cout << "~ Initialization complete ~" << endl << endl;
cout << " iterator test: ";
t = GetTickCount();
for (vector<int>::iterator it = test.begin(); it < test.end(); it++)
{
a = *it;
}
cout << GetTickCount() - t << endl;
cout << "Optimised iterator: ";
t=GetTickCount();
vector<int>::iterator endofv = test.end();
for (vector<int>::iterator it = test.begin(); it < endofv; it++)
{
a = *it;
}
cout << GetTickCount() - t << endl;
cout << " At: ";
t=GetTickCount();
for (int i = 0; i < test.size(); i++)
{
a = test.at(i);
}
cout << GetTickCount() - t << endl;
cout << " Optimised at: ";
t = GetTickCount();
int endof = test.size();
for (int i = 0; i < endof; i++)
{
a = test.at(i);
}
cout << GetTickCount() - t << endl;
cout << " Index: ";
t=GetTickCount();
for (int i = 0; i < test.size(); i++)
{
a = test[i];
}
cout << GetTickCount() - t << endl;
cout << " Optimised Index: ";
t = GetTickCount();
int endofvec = test.size();
for (int i = 0; i < endofvec; i++)
{
a = test[i];
}
cout << GetTickCount() - t << endl;
cin.ignore();
}
Исходя из этого, я лично получил, что "оптимизированные" версии быстрее, чем "неоптимизированные". Итераторы медленнее, чем vector.at(), которая медленнее прямых индексов.
Я предлагаю вам скомпилировать и запустить код для себя.
EDIT: этот код был написан, когда у меня было меньше опыта с C/С++. Еще одним тестовым примером должно быть использование операторов приращения префикса вместо постфикса. Это должно улучшить время работы.
Только слегка касательный к исходному вопросу, но самый быстрый цикл будет
for( size_t i=size() ; i-- ; ) { ... }
который, конечно, будет отсчитываться. Это дает существенную экономию, если в вашем цикле имеется большое количество итераций, но оно содержит лишь небольшое количество очень быстрых операций.
Таким образом, с доступом оператора [] это может быть быстрее, чем многие из уже опубликованных примеров.