WedX - журнал о программировании и компьютерных науках

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

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

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

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

// 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).

c++ boost boost-random
20.05.2010

  • Было бы хорошо указать здесь несколько цифр: количество элементов в списке и количество элементов, которые вы потенциально можете удалить. 20.05.2010
  • Стохастическое моделирование - может варьироваться от однозначных цифр до верхней границы 1000. Я не знаю распределения внутри. 20.05.2010

Ответы:


1

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

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

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

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

20.05.2010
  • Спасибо - да, вы правы, список не поддерживает неслучайный доступ, поэтому, вероятно, это вектор. Вы правы в том, что фильтрация становится неэффективной. Также отметка недействительной выглядит как добавление члена к содержащемуся типу. Я воссоздаю генератор, когда удалю элемент. Я был зациклен на эффекте посева и последовательности rng, но я могу создать boost :: mt19937 вне цикла и повторно использовать его при создании генератора. 20.05.2010
  • Пометка как недопустимая по сути то же самое, что восстановление числа :) 20.05.2010

    • 2

    Вы можете создать свой собственный класс распределения uniform_conolated_int, который принимает контейнер в своем конструкторе, агрегирует uniform_int и воссоздает uniform_distribution каждый раз, когда контейнер меняет размер. Посмотрите описание uniform_int, которое методы, которые вам необходимо реализовать для создания вашего дистрибутива.

    20.05.2010

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

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

    20.05.2010
  • Я уверен, что ваш псевдокод действительно хорош, но я его не понимаю. Не стесняйтесь уточнить. Кроме того, мой код был не просто не очень быстрым способом получения i-го элемента, это было невозможно, поскольку список не поддерживает произвольный доступ. Я должен был использовать std::vector. 20.05.2010
    • Новые материалы
    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..
    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..
    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..
    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..
    Учебные заметки: создание моего первого пакета Node.js
    Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..
    Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!
    Примечание. Эта запись в блоге предполагает базовое знакомство с Python и концепциями анализа данных. Привет, энтузиасты данных! Добро пожаловать в мой блог, где я расскажу о невероятных..
    ИИ в аэрокосмической отрасли
    Каждый полет – это шаг вперед к великой мечте. Чтобы это происходило в их собственном темпе, необходима команда астронавтов для погони за космосом и команда технического обслуживания..
    Для любых предложений по сайту: [email protected]