Использование boost::random для выбора из списка std::, где удаляются элементы

Question

Посмотрите этот связанный вопрос о более общем использовании библиотеки Boost Random.

Мои вопросы включают в себя выбор случайного элемента из std::listвыполнение некоторой операции, которая может потенциально включать удаление элемента из списка, а затем выбор другого случайного элемента, пока не будет выполнено некоторое условие.

Код повышения и цикл выглядят примерно так:

// create and insert elements into list
std::list<MyClass> myList;
//[...]

// select uniformly from list indices
boost::uniform_int<> indices( 0, myList.size()-1 );    
boost::variate_generator< boost::mt19937, boost::uniform_int<> > 
  selectIndex(boost::mt19937(), indices);

for( int i = 0; i <= maxOperations; ++i ) {
    int index = selectIndex();
    MyClass & mc = myList.begin() + index;

    // do operations with mc, potentially removing it from myList
    //[...]
}

Моя проблема заключается в том, что как только операции, выполняемые над элементом, приводят к удалению элемента, variate_generator может потенциально выбрать неверный индекс в списке. Я не думаю, что имеет смысл полностью воссоздавать variate_generator каждый раз, особенно если я заполняю его временем (0).

Answer 1

Я предполагаю что MyClass & mc = myList.begin() + index; это просто псевдокод, так как начало возвращает итератор, и я не думаю, что поддержка списка итераторов (без случайного доступа) operator+,

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

• Воссоздайте генератор при удалении предмета.
• Выполните фильтрацию по сгенерированному индексу и, если он>= текущий размер списка, повторите попытку, пока не получите действительный индекс. Обратите внимание, что если вы удалите много индексов, это может стать довольно неэффективным.
• Оставьте узел в списке, но пометьте его как недопустимый, поэтому, если вы попытаетесь работать с этим индексом, он безопасно не будет работать. Это просто другая версия второго варианта.

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

Answer 2

Вы могли бы создать свой собственный класс распределения iform_contained_int, который принимает контейнер в своем конструкторе, агрегирует universal_int и воссоздает равномерный_распределение каждый раз, когда контейнер изменяет размер. Посмотрите на описание iform_int, какие методы вам нужно реализовать для создания своего дистрибутива.

Answer 3

Я думаю, вам нужно больше беспокоиться о производительности. Особенно это:

std::list<MyClass> myList;
myList.begin() + index;

не очень быстрый способ получения indexэлемент

Я бы преобразовал это во что-то вроде этого (которое должно работать со случайной подпоследовательностью списка):

X_i ~ U(0, 1) for all i
left <- max_ops
N <- list size
for each element
  if X_i < left/N
    process element
    left--
  N--

при условии, что вам не нужна случайная перестановка элементов.