C ++ Vector at / [] скорость оператора

Question

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

curr = myvec.at( i );
doThis( curr );
doThat( curr );
doStuffWith( curr );

Но я должен сделать:

doThis( myvec.at( i ) );
doThat( myvec.at( i ) );
doStuffWith( myvec.at( i ) );

(как ответили на мой другой вопрос)

• Тогда я собираюсь сделать очень много звонков на myvec.at(). Насколько это быстро по сравнению с первым примером использования переменной для хранения результата?

• Есть ли другой вариант для меня? Можно ли как-нибудь использовать указатели?

Когда все станет серьезно, будут тысячи звонков на myvec.at() в секунду. Так что каждый маленький любитель производительности важен.

Answer 1

Вы можете использовать ссылку:

int &curr = myvec.at(i);
// do stuff with curr

Функция-член at выполняет проверку границ, чтобы убедиться, что аргумент находится в пределах размера vector. Профилирование - это единственный способ точно определить, насколько он медленнее, чем operator[]. Использование ссылки здесь позволяет выполнить поиск один раз, а затем использовать результат в других местах. И вы можете сделать это ссылкой на const, если хотите защитить себя от случайного изменения значения.

Answer 2

Из моих собственных тестов с похожим кодом (скомпилированным в gcc и Linux), operator[] может быть заметно быстрее, чем at, не из-за проверки границ, а из-за накладных расходов на обработку исключений. Замена at (которая вызывает исключение за пределами) моей собственной проверкой границ, которая вызвала утверждение за пределами оценки, дала ощутимое улучшение.

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

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

Однако, как сказал Крис Бекке, нет никакой замены для профилирования.

Answer 3

Причина, по которой первая не работает, заключается в том, что вы не устанавливаете указатель или итератор на адрес i-й переменной. Вместо этого вы устанавливаете curr равным значению i-й переменной, а затем модифицируете curr. Я предполагаю, что doThis и doThat являются ссылками.

Сделайте это:

MyObject& curr = myvec.at( i );

Answer 4

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

Никто не может ответить на этот вопрос, кроме вас самих: создайте тестовый комплект, нарисуйте несколько алгоритмов и посмотрите, что вы получите.

пс. если производительность действительно является проблемой, я получил увеличение скорости в 10 раз из png-декодера, удалив векторы и заменив их необработанными массивами. Опять же, это было для Visual Studio 6. Я не утверждаю, что замена необработанного массива даст вам улучшение в 10 раз, но это что-то, что нужно попробовать.

Answer 5

Оператор [] может быть быстрее, чем at, поскольку не требуется выполнять проверку границ.

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

MyClass & curr = myvec.at(i);

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

Answer 6

Параметры, которые я вижу, примерно в обратном порядке предпочтения :

1. Храните указатели в вашем контейнере вместо реальных объектов. В любом случае это может быть целесообразно, если объекты достаточно сложны, и копирование их вокруг проблематично.
2. Используйте оператор индексирования [] вместо at().
3. Просто позвоните at() один раз и сохраните его в качестве ссылки (см. Ответ Кристо выше).
4. Забудьте об этом, пока у вас не возникнет проблема с чрезмерным временем выполнения. Если это произойдет, сначала профилируйте свой код, чтобы убедиться, что узкое место здесь, и только потом беспокойтесь о выполнении одного из вышеперечисленных для ускорения все наверх.

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

Answer 7

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

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

Answer 8

Векторы наиболее подходят для скорости доступа. Доступ к случайному элементу в векторе имеет сложность O (1) по сравнению с O (n) для общих связанных списков и O (log n) для деревьев ссылок.

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

Answer 9

Сложность at() постоянна, т. Е. На практике это означает, что она должна быть спроектирована так, чтобы не иметь какого-либо существенного снижения производительности.

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

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