Comments 20
Шаг N: (для каждого N > K): с вероятностью K/N принимаем решение, выбрать ли данный пришедший элемент. Если решение положительное — перезаписываем в векторе выбранных элементов элемент с индексом N % K (% — остаток от деления) новым значением. Поскольку элемент номер N имеет равные шансы попасть в выборку со всеми предыдущими элементами, то и остаток от деления N % K будет равномерно случайным.
Я правильно понимаю, что если у нас (например) при K=3 последовательность 1,2,3,1,2,3,1,2,3,...
, то из-за размещения элементов по правилу N%K мы не имеем шанса получить в выходной выборке больше одной единицы (а также больше одной двойки и одной тройки)?
Как это согласуется с утверждением:
Алгоритм резервуарной выборки позволяет решить эту задачу за O(N) шагов и O(K) памяти. При этом не требуется знать N заранее, а условие случайности выборки ровно K элементов будет чётко соблюдено.
..? Мне кажется, выбор элементов будет частично неслучаен (коллизии элементов на расстоянии K друг от друга), что проявится в некоторых случаях (как в моём примере).
Начать нужно с того, что вообще чёрт его знает, что такое random() — в стандарте С++ есть только rand(), а значит random() — это какой-то их собственный фейсбучный велосипед и не известно, как он работает. Без этого знания было бы действительно надёжнее сгенерировать второе случайное число.
С другой стороны, пример на R в Википедии тоже обходится одним random'oм — но это принципиально другая функция, генерирующая случайное число по равномерному распределению между двумя заданными. Тут действительно, достаточно его одного и для решения брать ли число (J < K) и для использование его в качестве индекса (распределение между 1 и K будет настолько же равномерным, как и между 1 и N).
Одного случайного числа и правда достаточно (до тех пор пока N << RAND_MAX), это и без видео понятно.
Вот только правильный алгоритм выглядит так:
- Взять случайное число X от 1 до N (или от 0 до N-1)
- Если оно попадает в диапазон от 1 до K (или от 0 до K-1) — заменить выбранный элемент номер X на кандидата номер N
А у вас — вот такой алгоритм получился:
- Взять случайное число X от 1 до N (или от 0 до N-1)
- Если оно попадает в диапазон от 1 до K (или от 0 до K-1) — заменить выбранный элемент номер (N%K) на кандидата номер N
Откуда тут взялось число N%K?
На счёт N%K — я хотел упростить, но, видимо, сам себя запутал. Имелось в виду значение X%K, что для рассматриваемого случая X < K вырождается в просто Х.
Сейчас поправлю, спасибо.
он утверждает, что random() % N даёт равномерное распределение от 0 до NЭто не так, если (RAND_MAX + 1) не кратно N, т.к. числа в диапазоне [0; RAND_MAX%N + 1) будут иметь бОльшую вероятность выпадения, чем [RAND_MAX%N + 1; N).
Например, при RAND_MAX == 2 и N == 2 вероятность выпадения 0 составит 2/3, а для 1 будет 1/3.
p.s. вижу, дальше в комментариях об этом уже написали
если у нас (например) при K=3 последовательность 1,2,3,1,2,3,1,2,3
Алгоритм ничего не знает о значении элементов. Для него та единица, которая в этой последовательности первая и та, которая четвёртая — это два разных элемента, равны они или не равны — роли не играет. И всё, что он гарантирует, что и первая единица, и четвёртая имеют равные шансы попасть в результирующую выборку на любом шаге алгоритма. При этом никто не даёт никаких гарантий их туда одновременного попадания.
он гарантирует, что и первая единица, и четвёртая имеют равные шансы попасть в результирующую выборку на любом шаге алгоритма.
Но они не могут попасть в выборку одновременно.
Более наглядный пример: последовательность 1,2,3,4,5,6,7,8,9
, K=3.
Невозможно получить выборку, в которой содержатся одновременно элементы 1 и 4 (это конкретный пример, один из многих).
Т.е., в общем виде, при условии наличия в выборке элемента с номером i вероятность наличия в выборке других элементов с номером (i % K) равна 0. Такие элементы, с равными по модулю K индексами, друг друга вытесняют из выборки, но при этом они не вытесняют остальные элементы.
И Akon32 вполне обоснованно показывает, что описанный алгоритм не обеспечивает данной равномерности, т.к. на модельном множестве некоторые из подмножеств элементов (вне зависимости от их значения) мощности K имеют нулевую вероятность оказаться результатом работы алгоритма. Например (при нумерации с 0 и K = 2), вероятность одновременного попадания в результат элементов с номерами 0 и 2 равна нулю.
Цитата из ветки выше:
> Автор говорит убедительно, но есть один хитрый момент: он утверждает, что random() % N даёт равномерное распределение от 0 до N, а значит нам достаточно его одного и для решения, брать ли элемент и для определения его позиции.
Автор очень лихо оставляет незамеченным тот факт, что вид распределения абсолютно ничего не говорит о взаимной независимости случайных величин. А они у него получаются зависимыми, более того, f1(x) = f2(x).
Итак, о чём же идёт речь. Выбрать один случайный элемент из вектора — это элементарная задача:И это, разумеется, не совсем правда.
auto result = vect[rand() % vect.size()]; // С++
Не будем рассматривать тривиальный случай, когда
RAND_MAX < vect.size()
.Так вот, правдой оно будет тогда и только тогда, когда
vect.size() % RAND_MAX == 0
.Для всех остальных случаев значения из диапазона
[0 ... vect.size() % RAND_MAX)
будут возвращаться немножечко чаще.Например, в векторе у нас 2 элемента, а RAND_MAX равен 3. Тогда первый элемент вектора будет возвращатся вдвое чаще второго.
Считается ли такой вариант как K шагов и 2K дополнительной памяти?
function rnd_int_less(n) {
return Math.floor(Math.random() * n);
}
function reservoir_sampling(k, n_arr) {
let n = n_arr.length;
let k_arr = [];
let j_arr = [];
// shuffle
for (let i = 0; i < k; i++) {
const j = i + rnd_int_less(n - i);
j_arr.push(j);
const a = n_arr[i];
const b = n_arr[j];
k_arr[i] = b;
n_arr[i] = b;
n_arr[j] = a;
}
// unshuffle
for (let i = k - 1; i >= 0; i--) {
const j = j_arr[i];
const a = n_arr[i];
const b = n_arr[j];
n_arr[i] = b;
n_arr[j] = a;
}
return k_arr;
}
Алгоритм резервуарной выборки