Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

4:16p

Равновероятный выбор случайного элемента из растущего множества Суть задачи: есть поток данных, с помощью некоторого алгоритма определяется принадлежность некоторой части данных потока к целевому множеству. Заранее кол-во вхождений, которые будут принадлежать целевому множеству не известно, но в процессе просмотра это кол-во подсчитывается. Ситуация осложняется тем, что поток большой, до нескольких сотен мегабайт и повторно его воспроизвести нельзя, так же как и сохранить данные соответствующие каждому из целевых элементов. В каждый момент времени известно: данные из потока соответствующие последнему найденному элементу и кол-во уже найденных. Можно ли на этой основе осуществить равновероятный выбор из всего растущего множества? Если можно, то как?

Аналогия: поиск текста на странице и равновероятный выбор одного из найденных вхождений, с описанными выше ограничениями на подсчёт и хранение вхождений.