Алгоритми та структури даних · Senior · Запитання 17 з 75
Як вибрати рівномірно випадкову вибірку з k елементів із потоку невідомої довжини?
- 1Брати кожен k-й елемент у міру надходження
- ✓Правильна відповідь: Reservoir sampling: лишати елемент i з імовірністю k/i
- 3Зберегти весь потік, перемішати й узяти k
Пояснення
Після будь-якої кількості елементів кожен перебуває в «резервуарі» з однаковою ймовірністю k/n, за O(k) пам'яті й один прохід. Кожен k-й елемент - не рівномірна вибірка, і вона залежить від довжини потоку.