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

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

Функциональность кода следующая: 1. Класс набора данных принимает файл .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()) в качестве указателя. Ничто, кажется, не улучшает его скорость.


c++ performance stdvector stl
person Pandoro    schedule 14.11.2012    source источник
comment
1) Где вы запускаете/останавливаете таймер? 2) Вы хотите включить время выделения памяти или нет? 3) Вы запускаете это в IDE или вне IDE (командная строка)?   -  person    schedule 15.11.2012
comment
getDatavector возвращает ссылку? Или значение?   -  person Benjamin Lindley    schedule 15.11.2012
comment
действительно, это кажется странным, тип данных Image довольно мал, и единственная большая часть переносится интеллектуальным указателем.   -  person didierc    schedule 15.11.2012
comment
почему у вас unsigned short в одном случае, а unsigned char в другом? может быть, из-за этой разницы происходит какое-то преобразование между форматами изображений? Или это простая опечатка?   -  person didierc    schedule 15.11.2012
comment
Время измерялось исключительно вокруг d.getDataVector()[i]; Проблема действительно заключалась в том, что я возвращал объект, а не ссылку. И я исправил опечатку, где было написано unsigned short, спасибо за это!   -  person Pandoro    schedule 15.11.2012

Ответы (4)


arrow_upward
5
arrow_downward

Как выглядит подпись 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 должен быть непрерывным, и поэтому доступ к элементу ith так же прост, как добавление i к указателю пометка начального адреса массива данных и разыменование результата.

person Praetorian    schedule 14.11.2012
comment
Спасибо всем за очень полезные комментарии! На самом деле это исправило мою проблему. Я предпочитаю принять этот ответ, так как он наиболее сложный. Это фактически сократило время загрузки с 15 минут до примерно 10 секунд! Особенно дополнительный d.getDataVector().size() в заголовке цикла добавлял дополнительное время. Передача ссылки на const вместо копирования объекта была идеальным решением, и мне не нужно было ничего менять, кроме добавления const&, что не нарушало общий конвейер :) - person Pandoro; 15.11.2012

arrow_upward
5
arrow_downward

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

Заставьте getDatavector() возвращать std::Vector<Image<unsigned short> >& или std::Vector<Image<unsigned short> > const&, а не std::Vector<Image<unsigned short> >

person Öö Tiib    schedule 14.11.2012

arrow_upward
2
arrow_downward

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

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

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

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

person Marshall Clow    schedule 14.11.2012
comment
+1. Я сразу предполагаю, что вопрос в том, что он заметно медленнее, а не в доступе к элементу. - person ; 15.11.2012
comment
Но если вы переместите vector, класс Dataset не останется с действительной копией. Это, наверное, нежелательно. - person Praetorian; 15.11.2012

arrow_upward
1
arrow_downward

Как уже упоминалось, корень проблемы, по-видимому, в том, что 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;
    }

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

person Michael Shmalko    schedule 14.11.2012