Выбор элемента из набора, удовлетворяющего предикатом, равномерно случайно в пространстве $ O (1) $

Question

Нам дают набор объектов, скажем, целых числа, $ s $. Кроме того, нам дают предикат $ p $, например, $ p (i): leftrightarrow i geq 0 $. Мы не знаем заранее, сколько элементов $ s $ удовлетворяют предикату $ p $, но мы хотели бы попробовать или выбрать элемент в порядке случайного P (i) } $.

Наивный подход состоит в том, чтобы сканировать $ s $ и, например, записать все целые числа или индексы, для которых удерживается $ p $, а затем выбирайте один из них равномерно случайно. Недостатком является то, что в худшем случае нам нужно пространство $ | s | s | $.

Для больших наборов или, скажем, потоковой среды наивный подход недопустим. Есть ли алгоритм на месте для проблемы?

Answer 1

Следующий подход часто называют как Отбор проб водохранилища. Анкет Начните сканировать набор SET $ S $ и поддерживать индекс $ J $. Первый элемент, с которым вы сталкиваетесь, удовлетворяющий предикату, установите на него $ j $ с вероятностью 1/1 $. Обновите свой выбор для $ j $, когда вы столкнетесь с вторым таким элементом с вероятностью $ 1/2 $. Когда вы сталкиваетесь с элементом $ k $ th, удовлетворяющим предикат, установите на него $ j $ с вероятностью 1/к $.

Алгоритм работает в $ theta (n) $ времени и в постоянном пространстве. Для правильности следует показать, что каждый элемент имеет одинаковую вероятность выбора и что события, которые они отображаются, являются независимыми. Второе утверждение независимости очевидно: наши решения не основаны на том, были ли мы ранее отобранные элементы. Первое утверждение (равное вероятность) может быть доказано довольно легко при индукции.

Для получения подробной информации см. JS Vitter, случайная выборка с резервуаром, Алгоритм R. для более компактной презентации см., Например, эти слайды.