Зразковий зразок: Вибірка з потоку

Вибірка, коли ви не знаєте n

Вибір k однорідних випадкових елементів з масиву відомого розміру n є простим – перемішайте індекси, візьміть перші k. Більш складною проблемою є потік: елементи надходять один за одним, ви не можете повернутися назад і часто не знаєте загальної кількості з них. Однак вам все ще потрібно, поки потік не зупиниться, мати набір з k елементів, де кожен бачений раніше елемент мав би точно однакову ймовірність потрапити у ваш зразок. Це гарантує зарезервована вибірка, використовуючи лише O(k) пам’яті незалежно від того, як довго триває потік.

Алгоритм R

Алгоритм R Джефрі Віттера (1985) є напрочуд простим. Заповніть резервуар обсягом k першими k елементами безпосередньо. Для кожного наступного елементу, на позиції i, згенеруйте випадкове ціле число j між 1 та i за рівномірним розподілом. Якщо j не більше ніж k, перезапишіть слот резервуара номером j; інакше відкиньте новий елемент і продовжуйте. Кожен наступний елемент розглядається як раз, з шансом k/i, що він потрапить у резерв, і якщо це станеться, він витісняє випадково існуючий слот.

const reservoir = [];
let i = 0;
for (const item of stream) {
  i++;
  if (reservoir.length < k) {
    reservoir.push(item);                 // fill the first k slots outright
  } else {
    const j = randomInt(1, i);            // uniform in [1, i]
    if (j <= k) reservoir[j - 1] = item;  // replace with probability k/i
  }
}

Чому кожен елемент в кінцевому підсумку з однаковою ймовірністю

Доказ – чистий індуктивний процес. Після обробки перших k елементів, кожен з них знаходиться у резервному банку з точністю до 1, що є очевидно рівномірним. Припустимо, що після обробки i мінус 1 елементів, кожен з них має ймовірність k поділився на (i мінус 1) бути поточним власником резервного слота. Елемент i приймається з ймовірністю k поділився на i за конструкцією. Щоб попередній елемент вижив на цьому кроці, або елемент i відхиляється, що відбувається з ймовірністю 1 мінус k поділився на i, або елемент i приймається, але не виганяє цей конкретний слот, що відбувається з ймовірністю (k поділився на i) помножено на (k мінус 1) поділився на k. Множення через все і спрощення відновлює точно k поділився на i для кожного з i елементів – отже, інваріант зберігається на кожному кроці, не лише в кінці.

Зважені та швидші варіанти

Алгоритм R витягує один випадковий номер для кожного елемента, що є марним, коли більшість елементів відхиляються у дуже довгому потоці. Алгоритми L і подібні методи пропуску вперед обчислюють за допомогою аналітичних формул, скільки елементів буде пропущено перед наступним прийомом, переходячи напряму до наступного релевантного індексу замість того, щоб кидати кубик для кожного елемента. Коли елементи несуть нерівні ваги, гарантія безвагового відбору більше не застосовується; зважене семплювання з резервуаром (Ефраїмідис та Спіракіс, A-ExpJ) призначає кожному елементу ключ, отриманий шляхом піднесення випадкового числа до степеня один поділеного на його вагу, і зберігає k елементів із найбільшими ключами, що пропорційно відбирає з урахуванням ваги, але при цьому залишається в одному потоковому проході.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Reservoir Sampling і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.