UK 
EnglishТипова
Polski🪣 Резервуарна вибірка — чесна вибірка з потоку
Оберіть k рівномірних зразків із потоку невідомої довжини за один прохід: елемент i замінює комірку резервуара з імовірністю k/i. Гістограма підтверджує, що кожен елемент однаково ймовірний.
Про цю симуляцію
Ця симуляція виконує алгоритм R — класичний однопрохідний метод резервуарної вибірки для обрання k рівномірних випадкових елементів із потоку довжиною N без знання N наперед. Елемент i (з індексацією від 1) потрапляє прямо в резервуар, якщо i ≤ k; інакше витягується випадкове ціле j в 1..i, і елемент замінює комірку резервуара j лише якщо j ≤ k. Гістограма внизу накопичує результати тисяч незалежних прогонів, щоб емпірично підтвердити, що кожен елемент опиняється у фінальному резервуарі з точно однаковою ймовірністю k/N.
🔬 Що показано
Один потоковий прохід через N елементів (5–60), що заповнює резервуар із k комірок (1–12), із підсвіченим поточним елементом і живим повідомленням, чи заповнив він порожню комірку, замінив наявну, чи був відкинутий. Нижче зростаюча гістограма будує емпіричну частоту включення кожного елемента за багатьма завершеними прогонами відносно теоретичної цільової лінії k/N.
🎮 Як користуватись
Задайте довжину потоку N і розмір резервуара k повзунками, потім натисніть Play, щоб анімувати алгоритм R елемент за елементом, або Step, щоб просуватися по одному елементу. Використайте «Run 5000×», щоб безшумно виконати 5000 повних прогонів і побачити, як стовпчики гістограми вирівнюються до пунктирної цільової лінії k/N. Reset очищає всю накопичену статистику.
💡 Чи знали ви?
Алгоритм R популяризував Дональд Кнут у своїй праці «Мистецтво програмування» — і він досі є стандартною технікою для рівномірної вибірки з потоків даних, надто великих для пам'яті, наприклад вибірки рядків логу з живого сервера без збереження всього логу. Його коректність випливає з красиво простого імовірнісного аргументу: множення шансу вибору елемента на власному кроці (k/i) на шанс пережити кожну наступну спробу витіснення телескопічно згортається точно до k/N.
Часті запитання
Як алгоритм R вирішує, зберегти чи відкинути кожен елемент?
Для перших k елементів (i ≤ k) елемент напевно потрапляє прямо в комірку резервуара i−1. Для кожного наступного елемента i код витягує рівномірно випадкове ціле j між 1 і i включно; якщо j ≤ k, елемент замінює те, що було в комірці j−1, інакше він повністю відкидається. Це означає, що елемент i зберігається з імовірністю рівно k/i і, якщо збережений, витісняє рівномірно випадкову наявну комірку.
Чому це просте правило дає кожному елементу однакову загальну ймовірність k/N?
Елемент i доживає до фінального резервуара, лише якщо його обрано на власному кроці (ймовірність k/i), а потім він ніколи не витісняється на жодному наступному кроці m > i, де ймовірність не бути витісненим щоразу дорівнює 1 − 1/m. Множення k/i на добуток (1 − 1/m) для m від i+1 до N телескопічно згортається точно до (k/i)·(i/N) = k/N — однаково для кожного елемента незалежно від того, коли він пройшов потоком, що й покликана продемонструвати гістограма симуляції.
Що насправді робить кнопка «Run 5000×» інакше, ніж Play?
Play і Step анімують один прохід потоком із візуальним підсвічуванням поточного елемента та комірки резервуара, корисним для стеження за механікою алгоритму R. «Run 5000×» натомість викликає безшумну, неанімовану версію того самого алгоритму 5000 разів у щільному циклі, підраховуючи, який елемент опинився в резервуарі після кожного повного прогону, тож гістограма накопичує достатньо вибірок, щоб емпірична частота включення видимо збіглася до теоретичної лінії k/N.
Що насправді представляють «Max dev.» і стовпчики гістограми?
Кожен стовпчик гістограми показує для одного конкретного індексу елемента частку завершених прогонів, у яких цей елемент опинився десь у фінальному резервуарі — буквально counts[i], поділене на загальну кількість прогонів. Max dev. — найбільша абсолютна різниця між спостережуваною частотою включення будь-якого елемента й теоретичним цільовим значенням k/N; зі зростанням кількості прогонів це максимальне відхилення має зменшуватися до нуля.
Чому резервуарна вибірка корисна, коли неможливо зберегти весь потік?
Уся суть алгоритму R полягає в тому, що йому потрібно тримати в пам'яті лише k елементів (сам резервуар) плюс лічильник поточного елемента, незалежно від того, якою виявиться довжина потоку N — йому не потрібно знати N заздалегідь і він ніколи не зберігає раніше побачені відкинуті елементи. Це робить його стандартним вибором для рівномірної вибірки з джерел даних на кшталт серверних логів, мережевого трафіку чи будь-якого набору даних, надто великого, щоб завантажити в пам'ять одразу.