Выборка из потока (reservoir)
Равновероятная выборка k элементов из потока неизвестной длины за один проход.
1function reservoirSample<T>(stream: Iterable<T>, k: number, rng: () => number): T[] {2 const reservoir: T[] = []3 4 for (const [i, item] of stream.entries()) {5 if (i < k) {6 reservoir.push(item) // первые k — сразу в резервуар7 } else {8 const j = Math.floor(rng() * (i + 1)) // 0..i9 if (j < k) reservoir[j] = item // счастливый билет — вытесняет10 }11 }12 13 return reservoir14}Проблема
Равновероятная выборка k элементов из потока неизвестной длины за один проход.
Что вы видите
Резервуар размера k: первые k заполняют, каждый следующий с шансом k/i вытесняет случайного.
Как это работает
Элемент i попадает в выборку с вероятностью k/n для любых i и n — при этом n заранее неизвестно и хранить поток нельзя. Индукция по потоку: вероятности остаются равными.
Пошаговый разбор
- 01
Заполнение
Первые k — сразу внутрь.
- 02
Вытеснение
Случайное j из 0..i.
- 03
Равность
У каждого — k/n.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
Логи
Случайная выборка строк из гигабайт логов.
Аналитика
Unbiased-семплирование событий на лету.
Spark
Reservoir sampling в API больших данных.
Связанные алгоритмы
«Выбрать k честно из потока без памяти»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.