
Обучающие данные | 103
А это значит, что вам заранее неизвестна вероятность, по которой должен быть
выбран твит. Но вы хотите убедиться, что:
! каждый твит выбирается с одинаковой вероятностью;
! вы можете остановить алгоритм в любое время, и твиты будут выбраны с верной
вероятностью.
Одно из решений для этих проблем — резервуарное семплирование. Его алгоритм
предусматривает как бы резервуар, который может быть массивом, и состоит из
трех шагов:
1. Первые k элементов помещаются в резервуар.
2. Для каждого поступающего n-го элемента генерируется случайный номер i,
причем 1 ≤ i ≤ n.
3. Если 1 ≤ i ≤ k, элемент ...