производительность — стирание векторного элемента C ++ против создания нового вектора
Я работаю с вектором элементов, которые должны быть выбраны случайным образом и эффективно удалены до тех пор, пока либо не будет выполнено условие, либо пока не будут выбраны все элементы. Однако на самом деле они не будут удалены до более поздней стадии выполнения кода, поэтому мне нужно вести список допустимых, доступных элементов. Я могу стереть элементы из этого второго вектора, или я могу воссоздать его каждый раз. Ниже приведена минимальная версия моего кода, показывающая пример того, как вектор создается каждый раз в цикле while:
Random mRandom; // Pseudo-random number generator
std::vector< Element* > mElements;
for( unsigned index = 0; index < ARBITRARY_VALUE; index++ )
mElements.push_back( new Element( ) );
std::vector< bool > removedElements;
bool condition = true;
while( condition == true ) {
std::vector< unsigned > availableIndices;
for( unsigned index = 0; index < mElements.size( ); index++ ) {
if( removedElements[ index ] == false )
availableIndices.push_back( index );
}
if( availableIndices.size( ) > 0 ) {
unsigned maximum = availableIndices.size( ) - 1;
unsigned randomIndex = mRandom.GetUniformInt( maximum ); // Zero to max
removedElements[ availableIndices[ randomIndex ] ] = true;
Element* element = mElements[ availableIndices[ randomIndex ] ];
condition = element->DoStuff( ); // May change condition and exit while
} else
break;
}
Понятно, что для удаления элемента в середине вектора требуется, чтобы базовая система перебирала оставшиеся элементы и «перемещала» их в новую, действительную позицию. Очевидно, это означает меньшее количество итераций, если стертые элементы находятся ближе к концу вектора.
Я прочитал несколько постов, касающихся затрат, связанных с удалением векторных элементов, но я не видел ничего, что напрямую касалось бы моего вопроса. Вносит ли процесс «перемещения» элементов после стирания накладные расходы, которые могли бы удешевить повторение всех элементов каждый раз, создавая новый вектор, который указывает на действительные? Как в моем примере кода выше.
Ура, Фил
Решение
Я не могу прокомментировать лучший способ решения вашей проблемы, потому что я еще не уверен, каково действительное требование функции или алгоритма (т.е. должны ли элементы сохранять порядок? Будут ли недоступные элементы снова доступны? Если они это сделают, будет ли порядок иметь значение тогда? и так далее)
Однако по поводу последнего вопроса:
Вносит ли процесс «перемещения» элементов после стирания накладные расходы, которые могли бы удешевить повторение всех элементов каждый раз, создавая новый вектор, который указывает на действительные?
Это полностью зависит от того, что вовлечено в перемещение элемента. Если это указатель, как указано выше, то вы можете переместить много элементов, прежде чем даже приблизиться к стоимости выделения памяти в новом векторе. И «много» я думаю сотни или даже тысячи.
В приведенном выше коде это выглядит так, как будто вектор доступности является избыточным. Element указатель доступен, если он находится в векторе availableIndicies,
Если я правильно понимаю намерение, я думаю, что я мог бы провести рефакторинг по следующим направлениям:
#include <vector>
#include <random>
struct Element
{
bool doStuff();
};struct ElementAvailability
{
ElementAvailability(std::vector<Element*> const& storage)
: storage_(storage)
{}
void resync()
{
// will requre an allocation at most once if storage_ does not grow
available_ = storage_;
}
std::size_t availableCount() const {
return available_.size();
}
Element* removeAvailable(std::size_t index) {
auto pe = available_[index];
available_.erase(std::begin(available_) + index);
return pe;
}
void makeUnavailable(std::size_t available_i)
{
available_.erase(std::next(std::begin(available_), available_i));
}
private:
std::vector<Element*> const& storage_;
std::vector<Element*> available_;
};
// I have used a std random engine because I don't know your library
auto eng = std::default_random_engine(std::random_device()());
void test(std::vector<Element*>const& elems)
{
auto available = ElementAvailability(elems);
bool condition = true;
auto getCount =[&condition, &available] () -> std::size_t
{
if (condition) {
available.resync();
auto count = available.availableCount();
return count;
}
else {
return 0;
}
};
while (auto count = getCount()) {
auto range = std::uniform_int_distribution<std::size_t>(0, count - 1);
auto index = range(eng);
auto candidate = available.removeAvailable(index);
condition = candidate->doStuff();
}
}
Другие решения
Представленная вами проблема случайного исключения элементов представляется мне разрешимой только в O(n^2) время и O(n) космическая сложность. Поскольку вы должны передать все элементы один раз и на каждом проходе, вы должны найти случайный индекс в последовательности все еще существующих элементов и поддерживать эту последовательность. Может быть несколько подходов с разными алгоритмическими примитивами. Ниже я представляю свое решение, которое архивирует эту цель, делая это дружественным образом к процессору / памяти.
void runRandomTasks() {
Random mRandom; // Pseudo-random number generator
std::vector<Element*> mElements;
for (unsigned index = 0; index < ARBITRARY_VALUE; ++index) {
mElements.push_back(new Element);
}
size_t current_size = mElements.size();
if (!current_size)
return;
std::vector<Element*> current_elements(current_size, nullptr);
for (unsigned index = 0; index < current_size; ++index) {
current_elements[index] = mElements[index];
}
Element** last_ptr = ¤t_elements[0] + current_size - 1;
bool condition = true;
while (condition && current_size) {
unsigned random_size = mRandom.GetUniformInt(current_size - 1) + 1; // Zero to max
Element** ptr = last_ptr;
while (true) {
random_size -= (bool)(*ptr);
if (random_size) {
--ptr;
} else {
break;
}
}
condition = (*ptr)->DoStuff(); // May change condition and exit while
*ptr = nullptr;
--current_size;
}
}
Относительно вашего вопроса о стирании векторных элементов, вы можете найти в моем решении, что есть цикл поиска случайного индекса, который эквивалентен стиранию элементов в векторе по сложности времени, но с меньшей константой, так как сдвиг элемента опущен, вместо этого значение элемента проверяется на 0 или нет. Выполнение любого выделения памяти в цикле всегда дорого, поэтому избегайте этого.