Быстрый способ push_back вектора много раз

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

В питоне питонский способ сделать это — использовать понимание списка:

my_vector = [x for x in data_vector if x > 1]

Я взломал способ сделать это в C ++, и он работает нормально. Тем не менее, я звоню это миллионы раз в течение цикла, и это медленно. Я не очень разбираюсь в распределении памяти, но я предполагаю, что моя проблема связана с распределением памяти снова и снова, используя push_back, Есть ли способ распределить мою память по-другому, чтобы ускорить этот код? (Я не знаю, насколько большой my_vector должно быть до forпетля завершена).

std::vector<float> data_vector;
// Put a bunch of floats into data_vector
std::vector<float> my_vector;

while (some_condition_is_true) {
my_vector.clear();
for (i = 0; i < data_vector.size(); i++) {
if (data_vector[i] > 1) {
my_vector.push_back(data_vector[i]);
}
}
// Use my_vector to render graphics on the GPU, but do not change the elements of my_vector
// Change the elements of data_vector, but not the size of data_vector
}

0

Решение

использование std::copy_if, и резерв data_vector.size() за my_vector изначально (так как это максимально возможное количество элементов, для которых ваш предикат может быть оценен как true):

std::vector<int> my_vec;
my_vec.reserve(data_vec.size());
std::copy_if(data_vec.begin(), data_vec.end(), std::back_inserter(my_vec),
[](const auto& el) { return el > 1; });

Обратите внимание, что вы могли бы избежать reserve Звоните сюда, если вы ожидаете, что число раз, которое ваш предикат оценивает как истинное, будет намного меньше, чем размер data_vector,

7

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

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

while (some_condition_is_true) {
my_vector.clear();
int newLength = 0;
for (i = 0; i < data_vector.size(); i++) {
if (data_vector[i] > 1) {
newLength++;
my_vector.reserve(newLength);

for (i = 0; i < data_vector.size(); i++) {
if (data_vector[i] > 1) {
my_vector.push_back(data_vector[i]);
}
}
// Do stuff with my_vector and change data_vector
}
1

Я сомневаюсь распределять my_vector проблема, особенно если while цикл выполняется много раз, как емкость my_vector должно быстро стать достаточным.

Но чтобы быть уверенным, вы можете просто зарезервировать my_vector соответствующий размеру data_vector:

my_vector.reserve(data_vector.size());

while (some_condition_is_true) {
my_vector.clear();
for (auto value : data_vector) {
if (value > 1)
my_vector.push_back(value);
}
}
1

Если вы используете Linux, вы можете зарезервировать память для my_vector предотвращать std::vector перераспределения, что является узким местом в вашем случае. Обратите внимание, что резерв не будет тратить память из-за чрезмерной загрузки, поэтому любая приблизительная верхняя оценка значения резерва будет соответствовать вашим потребностям. В вашем случае размер data_vector будет достаточно. Эта строка кода перед while Цикл должен исправить узкое место:

my_vector.reserve(data_vector.size());
1

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

Во-первых, в C ++ существует несколько типов памяти: stack, heap, data segment,

Stack для локальных переменных. Есть некоторые важные функции, связанные с ним, например, они будут автоматически освобождены, работа с ним очень быстрая, ее размер зависит от ОС и небольшой, что позволяет хранить некоторые килобайты данных в stack может вызвать переполнение памяти и так далее.

HeapДоступ к памяти можно получить по всему миру. Что касается его важных особенностей, у нас есть, его размер может быть динамически расширен, если это необходимо, и его размер больше (намного больше, чем stack), операция на нем медленнее, чем stackнеобходимо ручное освобождение памяти (в современных ОС память будет автоматически освобождена в конце программы) и так далее.

Data segment для глобальных и статических переменных. Фактически этот фрагмент памяти можно разделить на еще более мелкие части, например, BBS.

В твоем случае, vector используется. На самом деле, элементы vector хранятся во внутреннем динамическом массиве, то есть во внутреннем массиве с динамическим размером массива. В ранних версиях C ++ динамический массив можно создавать на stack память, однако, это уже не тот случай. Чтобы создать динамический массив, нужно создать его на heap, Поэтому элементы vector хранятся во внутреннем динамическом массиве на heap, Фактически, чтобы динамически увеличивать размер массива, процесс, а именно memory reallocation нужно. Тем не менее, если vector пользователь продолжает увеличивать его или ее vector, то накладные расходы reallocation Стоимость будет высокой. Чтобы справиться с этим, vector во-первых, выделил бы часть памяти, которая больше, чем текущая потребность, то есть выделяет память для потенциального использования в будущем. Следовательно, в вашем коде это не тот случай, когда memory reallocation выполняется каждый раз push_back() называется. Однако если vector Для копирования достаточно много, памяти, зарезервированной для будущего использования, будет недостаточно. Затем, memory allocation произойдет. Чтобы заняться этим, vector.reserve() может быть использовано.

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

1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector