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

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

4 голосов
/ 20 мая 2010

См. связанный вопрос о более общем использовании библиотеки 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).

Ответы [ 3 ]

2 голосов
/ 20 мая 2010

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

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

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

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

1 голос
/ 20 мая 2010

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

0 голосов
/ 20 мая 2010

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

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--

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

...