Блог » Полезные штуки: Random
1271762908|%e %b %Y %T|agohover
Возникла тут на работе задача генерации случайных ников для персонажей. В такой задаче не обойтись без случайной выборки из какого-нибудь списка. Для этого у меня написался довольно интересный код, которым и хочу поделиться.
Задача: есть некоторая последовательность объектов. Возможно, неизвестной длины. Надо выбрать случайный элемент этой последовательности, так чтобы вероятность выбора любого конкретного была одинакова. Вариант "со звездочкой" — для каждого элемента последовательности задан вес, надо чтобы вероятность выбора элемента была пропорциональна весу.
Обычно это решается просто: элемент номер n, где n — случайное число от 0 до N, а N — длина последовательности. Ну, типа,
return sequence[random.Next(0, sequence.Count)];
Но для этого надо знать число элементов. И иметь доступ по индексу тоже неплохо бы. А если последовательность, как в нашем условии, этого не имеет? В терминах C# — это IEnumerable. Есть способ решения и в этом случае.
Работая с IEnumerable, все что мы можем — это перебирать элементы последовательно. Подойдем к вопросу так: пусть мы, перебирая последовательность, выбрали некий элемент Х из первых n. Теперь мы берем следующий элемент, номер n+1. C какой вероятностью мы выберем именно его? Если последовательность заканчивается на нем, ответ очевиден: $1/(n+1)$. Менее очевидно, что с той же вероятностью его надо выбирать и в остальных случаях! Попробуем посчитать вероятность для случая, когда длина последовательности n+2:
- на шаге n+1 мы выберем наш элемент с вероятностью $1/(n+1)$
- на шаге n+2 мы выберем _следующий_ элемент с вероятностью $1/(n+2)$; а предыдущий останется выбран с вероятностью $\frac{n+1}{n+2}$
- в итоге, элемент с номером n+1 окажется выбранным с вероятностью $\frac{1}{n+1} \frac{n+1}{n+2} = \frac{1}{n+2}$ — что и требовалось!
Нетрудно видеть, что и для больших последовательностей все промежуточные вероятности посокращаются, и итоговый ответ будет тем что требуется. Для строгого доказательства можно без проблем выписать общую формулу.
Итого, алгоритм выбора случайного элемента простой: перебираем последовательно элементы, на каждом шаге с вероятностью 1/(число шагов) отмечаем текущий элемент как выбранный. Последний выбранный и возвращаем.
Подобную штуку так и хочется написать в виде метода расширения, чтоб потом использовать с любыми последовательностями не задумываясь1 . Так и сделаем.
public static class RandomSelectExtension { public static T Random<T>(this IEnumerable<T> enumerable, Random rng) { int totalCount = 0; // число шагов T selected = default(T); // последний выбранный элемент foreach (var data in enumerable) // перебираем элементы { int r = rng.Next(totalCount+1); // случайное число от 0 до totalCount включительно if (r >= totalCount) // с вероятностью 1/(totalCount+1) selected = data; // выбираем текущий элемент totalCount++; // и следующий шаг } return selected; } }
Генератор случайных чисел передадим в метод на всякий случай — можно было бы каждый раз создавать новый, но это во-первых неэффективно, а во-вторых, может быть, пользователь захочет управлять seed-ом.
Ну и наконец, к вопросу о задаче со звездочкой. Как быть, если веса элементов разные? Как оказалось, точно так же - только вместо номера шага надо брать вес элемента. То есть, если вес i-того элемента wi, то элемент номер n+1 выбирается с вероятностью $\frac{w_{n+1}}{\sum_{i=1}^{n}w_i}$. Доказывается это абсолютно так же, как и для случая равных весов — суммы опять сократятся. А реализуется, например, так:
public static class RandomSelectExtension { public static T Random<T>(this IEnumerable<T> enumerable, Random rng, Func<T, int> weightFunc) { int totalCount = 0; // теперь это - суммарный вес всех предыдущих элементов T selected = default(T); foreach (var data in enumerable) { int r = rng.Next(totalCount + weightFunc(data)); // weightFunc вычисляет вес текущего элемента if (r >= totalCount) selected = data; totalCount += weightFunc(data); } return selected; } }
Здесь мы передали в метод функцию, которая вычисляет вес по конкретному элементу. В конкретном приложении это будет использоваться примерно так:
return list.Random(m_Random, pd => pd.Count);
То есть, вес это поле класса, экземпляры которого лежат в списке.
Предыдущая запись: Don't make me play
Комментировать
"Надо выбрать случайный элемент этой последовательности, так чтобы вероятность выбора, так чтоб вероятность выбора"
Вот из-за таких "сложностей" я и не люблю С"что-то".
Whoops. Исправил, спасибо.
А какая тут "сложность"?
в количестве типов. Перловые 3 типа ужасно расслабляют и ускоряют мозг в совершенно других плоскостях.
Возврат скажем с перла на яву внедряют меня в маятниковое состояние wtf. Посему C"" я обхожу за довольно далеко и надолго, заодно и ноги будут целее.
ААА БЛЯЯЯ!!!! *в испуге убегает*