Комментарии 13
Есть другой способ объяснения, и мне он кажется более интуитивным. Ясно, что равномерно перемешав все карты и взяв первые k мы получим все карты равновероятно. Этот метод работал бы, но требует сохранить все n карт в памяти.
Теперь посмотрим на код, и попробуем его исправить, чтобы не держать в памяти все карты:
for (int i = 0; i < n; ++i) {
int j = rand() % (i+1);
swap(a[i], a[j]);
}Этот код перетасовывает массив равновероятно за O(N) операций. Делает он это индуктивно: после каждой итерации первые i+1 элементов равномерно перемешаны. После этого мы случайно выбираем любую позицию от 0 до i для i-ого элемента. Ведь в равномерно перетасованом массиве этот элемент может быть на любом из этих мест равновероятно. Теперь можно просто свапнуть i-ый элемент на это место. Все остальные элементы, включая тот, с которым мы свапнули, будут равномерно перемешаны, потому что они уже были равномерно перемешаны до этого.
Теперь, если нам надо взять только k первых элементов в конце, то вместо swap() будем просто записывать новый элемент в одно из k мест. Потому что в первые k мест мы можем только свапнуть какой-то новый элемент. Нам же нужно только началомассива, вот мы и будем игнорировать все, что дальше.
for (int i = 0; i < k; ++i) samples[i] = a[i];
for (int i = k; i < n; ++i) {
int j = rand() % (i+1);
if (j < k) samples[j] = a[i];
}Это можно переписать онлайн:
void Process(int x) {
if (count < k) {
samples.push_back(x);
} else {
int j = rand() % count;
if (j < k) {
samples[j] = x;
}
}
++count;
}Фактически, условие rand() % count < k - это вероятность взять текущий элемент и она равна k/n. Вот откуда она берется.
Есть эквивалентный, но не требующий никакой арифметики алгоритм. Только ДСЧ и сравнения.
Каждый раз когда нам показывают карту, мы генерируем случайное число. Для первой карты просто забираем её и запоминаем это число. Для каждой следующей карты сравниваем числа у старой и новой карты. Оставляем ту, у которой число больше (или меньше, это неважно).
Это то же самое, что назначить каждой карте число, отсортировать их по возрастанию чисел (random shuffle), и взять первую. Несложно обобщается на выбор n карт: сравниваем новую карту с "минимальной" из уже выбраных и если у новой число больше - подменяем.
Так мы ведь не знаем количество карт, как нам тогда назначать числа?
Случайные из интервала [0,1). Math.random() или что там в вашем языке доступно, количество не влияет (товарищ выше очень понятно объяснил: каждой карте назначили случайное число и выбрали ту, что с самым большим).
А зачем вам знать количество карт? Карты не надо нумеровать "1,2,3,4...". Если после воображаемой сортировки ряд будет "7,40,12345,999999,10000000", алгоритм сработает точно так же.
Поэтому можно взять любой ДСЧ, генерирующий числа от 0 до N и его использовать. Для большинства практических применений 2^64 вполне хватит с запасом.
Скажите, а как вы сделали такие замечательный графики и видео? спасибо.
В оригинале оно ещё и интерактивное в браузере. Там уже F12 поможет.
Чёт мне кажется идея "а давайте мы отбросим часть логов" уже сама по себе шизоидная. Достаточно просто в небольшом кэше сравнить тип поступающего события и увеличивать счётчик таких событий (в задаче ведь озвучено что они одинаковые), без всей этой возьни с алгоритмами. Если же события разные, то отбрасывая часть мы априори часть информации потеряем, хоть идеально случайная она, хоть нет.
Но, конечно, всегда забавно почитать как кто-то выдумывает чудесное хитрожопое решение просто ради всей этой мыслительной гимнастики. Жаль мне за такое не платят.
Я благодарю вас за статью
Могли бы вы объяснить чем такой алгоритм лучше и практичнее в вашем случае, чем простое бросание кубика при показе очередной карты? Мы бросаем кубик, в общем случае классический случайный генератор от 0 до единицы, если выпавшее число больше 0.9, мы забираем карту. Я вижу, что тут мы можем настраивать вероятность выбора следующей карты. Возможно вам нужна какая то другая метрика которую я не понял. Что это за метрика?
Так. Кажется, я понял.
Вам нужно выбрать 1 элемент из потока неопределённой длины. Хранить весь поток вы не можете. Или можете, но зачем, если есть экономный и простой способ? Как описан в нашей статье.
Алгоритм позволяет держать в памяти 1 элемент и при этом гарантировать, что случайность выборки любого элемента будет 1 к N , где N это длина массива.
Бросание кубика или случайного генератора как я предлагал в комментарии выше - приведёт к выборке случайного элемента скорее всего где-то в начале массива. Выпадение будет смещено.
Бросание кубика или случайного генератора как я предлагал в комментарии выше - приведёт к выборке случайного элемента скорее всего где-то в начале массива.
Это смотря как реализовывать. Если вы берете элемент пока есть пустое место, то, да - смещение в начало. Если всегда берете элемент с заданной вероятностью и вытесняете что уже набрано, если взяли слишком много, то смещение будет в конец массива.
Резервуарное сэмплирование и собачки