векторный резерв С++

У меня есть очень большой многомерный вектор, который постоянно меняется в размере. Есть ли смысл использовать функцию vector.reserve(), когда я знаю только приблизительные размеры.

Итак, в основном у меня есть вектор

A[256*256][x][y]

где x изменяется от 0 до 50 для каждой итерации программы, а затем снова возвращается к 0. Значения y могут каждый раз отличаться, а это значит, что для каждого из [256*256][y] элементов вектор y может быть разного размера, но все же меньше 256;

Итак, чтобы прояснить мою проблему, это то, что у меня есть:

vector<vector<vector<int>>> A;
for(int i =0;i<256*256;i++){
  A.push_back(vector<vector<int>>());
  A[i].push_back(vector<int>());
  A[i][0].push_back(SOME_VALUE);
}

Добавьте элементы в вектор...

A.clear();

И после этого я делаю то же самое снова сверху.

Когда и как я должен резервировать место для векторов. Если я правильно понял, я бы сэкономил много времени, если бы использовал резерв, так как я все время меняю размеры?

Каковы будут отрицательные/положительные стороны резервирования максимального размера, который может иметь мой вектор, который в некоторых случаях будет [256*256][50][256].

КСТАТИ. Я знаю о разных шаблонах Matrix и Boost, но решил использовать векторы на этом...

EDIT: мне также было интересно, как использовать резервную функцию в многомерных массивах. Если я зарезервирую вектор только в двух измерениях, скопирует ли он все это, если я превыслю его возможности в третьем измерении?


c++ vector
person Community    schedule 17.02.2010    source источник
comment
256*256*50*256*4 == 3,5 ГБ. Это действительно так?   -  person Will    schedule 17.02.2010
comment
Я боюсь, что это! Но это максимальный размер... Вероятно, в среднем будет что-то вроде 256*256*50*100; Технически максимальное значение никогда не будет достигнуто...   -  person    schedule 17.02.2010

Ответы (4)


arrow_upward
4
arrow_downward

Чтобы помочь в обсуждении, вы можете рассмотреть следующие определения типов:

typedef std::vector<int> int_t;   // internal vector
typedef std::vector<int_t> mid_t; // intermediate
typedef std::vector<mid_t> ext_t; // external

Стоимость роста (увеличение емкости вектора) int_t повлияет только на содержимое этого конкретного вектора и не повлияет ни на какой другой элемент. Стоимость роста mid_t требует копирования всех сохраненных элементов в этом векторе, то есть потребуется весь вектор int_t, что гораздо дороже. Стоимость увеличения ext_t огромна: потребуется скопировать все элементы, уже сохраненные в контейнере.

Теперь, чтобы повысить производительность, было бы гораздо важнее получить правильный размер ext_t (в вашем вопросе кажется фиксированным 256 * 256). Затем скорректируйте промежуточный размер mid_t, чтобы дорогие перераспределения были редкими.

Объем памяти, о котором вы говорите, огромен, поэтому вы можете рассмотреть менее стандартные способы решения вашей проблемы. Первое, что приходит на ум, это добавление дополнительного уровня косвенности. Если вместо того, чтобы хранить фактические векторы, вы держите интеллектуальные указатели на векторы, вы можете уменьшить стоимость выращивания векторов mid_t и ext_t (если размер ext_t фиксирован, просто используйте вектор mid_t). Теперь это будет означать, что код, использующий вашу структуру данных, будет более сложным (или лучше добавить оболочку, которая заботится о косвенных обращениях). Каждый вектор int_t будет размещен в памяти один раз и никогда не будет перемещаться ни при mid_t, ни при ext_t перераспределениях. Стоимость перераспределения mid_t пропорциональна количеству выделенных int_t векторов, а не фактическому количеству вставленных целых чисел.

using std::tr1::shared_ptr; // or boost::shared_ptr
typedef std::vector<int> int_t;
typedef std::vector< shared_ptr<int_t> > mid_t;
typedef std::vector< shared_ptr<mid_t> > ext_t;

Еще одна вещь, которую вы должны принять во внимание, это то, что std::vector::clear() не освобождает выделенное внутреннее пространство в векторе, а только уничтожает содержащиеся в нем объекты и устанавливает размер равным 0. То есть вызов clear() никогда не освободит память. Шаблон для фактического освобождения выделенной памяти в векторе:

typedef std::vector<...> myvector_type;
myvector_type myvector;
...
myvector.swap( myvector_type() ); // swap with a default constructed vector
person David Rodríguez - dribeas    schedule 17.02.2010
comment
@ Дэвид, ты уверен, что правильно понял биты internal_t и intermediate_t в первом фрагменте? - person Manuel; 26.02.2010

arrow_upward
2
arrow_downward

Всякий раз, когда вы вставляете вектор в другой вектор, установите размер в конструкторе вложенных векторов:

 A.push_back(vector<vector<int>>( somesize ));
person Community    schedule 17.02.2010
comment
›› в шаблонах не всегда корректно обрабатывается. Вставьте пробел, чтобы сделать его переносимым. Просто нытье. - person Roman Shapovalov; 17.02.2010

arrow_upward
0
arrow_downward

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

См. как делать-я -работа-с-динамическими-многомерными-массивами-в-c для примера

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

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

person Will    schedule 17.02.2010
comment
Не делай этого. векторы обрабатывают перераспределение для вас. использование realloc() в программе на C++ почти наверняка будет неправильным. - person ; 17.02.2010
comment
В этом конкретном примере вектор векторов векторов POD, как может malloc/realloc/free быть неуместным? - person Will; 17.02.2010
comment
По крайней мере, поскольку у меня есть разные размеры в третьем измерении, я могу легко получить доступ к размеру, если использую векторы... - person ; 17.02.2010

arrow_upward
0
arrow_downward

Если вы знаете размер вектора во время построения, передайте размер c'tor и назначьте его, используя operator[] вместо push_back. Если вы не совсем уверены в окончательном размере, сделайте предположение (может быть, добавьте немного больше) и используйте reserve, чтобы вектор зарезервировал достаточно памяти заранее.

Каковы будут отрицательные/положительные стороны резервирования максимального размера моего вектора, который в некоторых случаях будет [256*256][50][256].

Отрицательная сторона: потенциальная трата памяти. Положительная сторона: меньше процессорного времени, меньше фрагментация кучи. Это компромисс между памятью и процессором, оптимальный выбор зависит от вашего приложения. Если вы не ограничены в памяти (на большинстве потребительских компьютеров оперативной памяти более чем достаточно), рассмотрите возможность резервирования заранее.

Чтобы решить, сколько памяти резервировать, смотрите на среднее потребление памяти, а не на пиковое (резервирование 256*256*50*256 не очень хорошая идея, если такие размеры не нужны регулярно)

person Alexander Gessler    schedule 17.02.2010