Доступ к элементам std :: vector замедляется с размером вектора

Question

Доступ к элементам std :: vector замедляется с размером вектора

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

Функциональность кода следующая:
1. класс Dataset, принимает файл .txt, который содержит имена файлов. Они указывают на стандартные изображения PNG, которые необходимо загрузить. Это сделано Image<T> учебный класс. Изображения загружаются как Image<unsigned char> и толкнул обратно в std::Vector,
2. После загрузки данных было сделано. Я могу получить доступ к вектору в моем наборе данных, чтобы работать с ним. Так это выглядит примерно так:

Dataset d;
d.init("filenames_list.txt"); //Loads the images
for(int i=0; i< d.getDatavector().size(); i++){
Image<unsigned char> current = d.getDatavector()[i];
//Do work on current image here.
}

Здесь getDatavector () вернет std::Vector<Image<unsigned char> >, Изображения содержат три дюйма для ширины, высоты и количества каналов, а также общий указатель Boost, который указывает на чередующиеся данные.

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

Image<unsigned char> current = d.getDatavector()[i];

занимает около 10 мс, чтобы быть завершенным. Однако, если я хочу работать с полным набором данных из 1500 изображений, выполнение этой строки занимает около 500 мс. Я пытался сделать много разных вещей, чтобы исправить это, но я несколько ограничен общей структурой кода и памятью. Потому что, если я сделаю следующее:

const std::Vector<Image<unsigned char> > data = d.getDatavector();

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

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

До сих пор я пытался получить доступ к контенту, используя std :: vector :: iterator или используя (d.getDatavector (). Data ()) в качестве указателя. Ничто, кажется, не улучшает скорость этого.

1

c++performance stdvector stl

Решение

Другие решения

Причина в том, что вы возвращаете вектор по значению в цикле.

Сделай свой getDatavector() вернуть std::Vector<Image<unsigned short> >& или же std::Vector<Image<unsigned short> > const& не std::Vector<Image<unsigned short> >

5

Вы используете C ++ 11 или более раннюю версию C ++?

Если более ранний C ++ 11 и getDataVector возвращают вектор, возможно, его придется скопировать.
Если вы используете C ++ 11, его можно переместить в возвращаемую переменную без копирования

это может быть источником вашего замедления.

Доступ к элементу вектора является операцией с постоянным временем.

2

Как уже упоминалось, корень проблемы, кажется, в том, что getDatavector() возвращает полную копию вектора, и решением было бы вернуть ссылку (или указатель вместо).
У вас также есть похожая проблема с Image<unsigned char> current = ... где копия изображения также делается.
Одним из решений этих проблем было бы использование прямого доступа к изображению в виде:

Image<unsigned char>* getImage(int idx)
{
if (idx < _myVector.size())
{
return &_myVector[idx].Image;
}
return NULL;
}

Редактировать: версия, возвращающая ссылку

    Image<unsigned char>& getImage(int idx)
{
if (idx < _myVector.size())
{
return _myVector[idx].Image;
}
// throw exception here;
}

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

1

Источник

Accepted Answer

Что означает подпись getDataVector() выглядит как? Это

std::vector<Image<unsigned char>> getDataVector();

Если это так, функция возвращает vector по значению, и каждый раз, когда вы пишете d.getDatavector()[i] копия vector сделано, то i элемент копируется из vector а затем vector Сам разрушен.

Если вы можете изменить Dataset класс изменить функцию на

std::vector<Image<unsigned char>> const& getDataVector();

Теперь копии не будут создаваться при каждом вызове функции.

Если вы не можете изменить класс, сделайте одну копию до вход в цикл, а затем использовать локальную переменную внутри цикла.

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

5