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

Question

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

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

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

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

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 
} 

Answer 1

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

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 звоните сюда, если вы ожидаете, что количество раз, которое ваш предикат оценивает как true, будет намного меньше размера data_vector.

Answer 2

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

Answer 3

Я сомневаюсь, что 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); 
    } 
} 

Answer 4

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

my_vector.reserve(data_vector.size()); 

Answer 5

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

Во-первых, на 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().

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