У меня есть, например, эта таблица
+ ----------------- + | фрукты | вес | + ----------------- + | яблоко | 4 | | апельсин | 2 | | лимон | 1 | + ----------------- +
Мне нужно вернуть случайный фрукт. Но яблоко следует собирать в 4 раза чаще, чем лимон, и в 2 раза чаще, чем апельсин .
В более общем случае это должно быть f(weight)
часто.
Что такое хороший общий алгоритм для реализации этого поведения?
Или, может быть, на Ruby есть несколько готовых камней? :)
PS
Я реализовал текущий алгоритм в Ruby https://github.com/fl00r/pickup
algorithms
ruby
math
random
fl00r
источник
источник
Ответы:
Концептуально самым простым решением было бы создание списка, в котором каждый элемент встречается столько раз, сколько его вес, поэтому
Затем используйте любые функции, которые есть в вашем распоряжении, чтобы выбрать случайный элемент из этого списка (например, сгенерировать случайный индекс в нужном диапазоне). Это, конечно, не очень эффективно для памяти и требует целых весов.
Другой, немного более сложный подход будет выглядеть так:
Рассчитать кумулятивные суммы весов:
Где индекс ниже 4 представляет яблоко , от 4 до 6 ниже апельсин и от 6 до 7 ниже лимон .
Генерация случайного числа
n
в диапазоне0
доsum(weights)
.n
. Соответствующий фрукт - это ваш результат.Этот подход требует более сложного кода, чем первый, но требует меньше памяти и вычислений и поддерживает веса с плавающей точкой.
Для любого алгоритма шаг настройки может быть выполнен один раз для произвольного числа случайных выборов.
источник
Вот алгоритм (в C #), который может выбирать случайный взвешенный элемент из любой последовательности, повторяя его только один раз:
Это основано на следующих соображениях: давайте выберем первый элемент нашей последовательности как «текущий результат»; затем на каждой итерации либо сохраняйте ее, либо отбрасывайте и выбирайте новый элемент в качестве текущего. Мы можем вычислить вероятность того, что любой данный элемент будет выбран в конце, как произведение всех вероятностей того, что он не будет отброшен на последующих этапах, в зависимости от вероятности того, что он будет выбран в первую очередь. Если вы сделаете математику, вы увидите, что этот продукт упрощается до (вес элемента) / (сумма всех весов), что именно то, что нам нужно!
Так как этот метод выполняет итерации по входной последовательности только один раз, он работает даже с неприлично большими последовательностями, при условии, что сумма весов вписывается в
int
(или вы можете выбрать больший тип для этого счетчика)источник
Уже представленные ответы хороши, и я их немного расширю.
Как предположил Бенджамин, кумулятивные суммы обычно используются в такой проблеме:
Чтобы найти элемент в этой структуре, вы можете использовать что-то вроде фрагмента кода Nevermind. Этот кусок кода C #, который я обычно использую:
Теперь к интересной части. Насколько эффективен этот подход и какое решение наиболее эффективно? Мой кусок кода требует O (n) памяти и запускается за O (n) времени. Я не думаю, что это может быть сделано с меньшим, чем O (n) пространством, но временная сложность может быть намного ниже, O (log n) на самом деле. Хитрость заключается в том, чтобы использовать бинарный поиск вместо обычного цикла for.
Также есть история об обновлении весов. В худшем случае обновление веса для одного элемента вызывает обновление кумулятивных сумм для всех элементов, увеличивая сложность обновления до O (n) . Это тоже можно сократить до O (log n), используя двоичное индексированное дерево .
источник
Это простая реализация Python:
а также
В генетических алгоритмах эта процедура выбора называется пропорциональным выбором «Фитнес» или « Выбор колеса рулетки», поскольку:
Типичные алгоритмы имеют сложность O (N) или O (log N), но вы также можете выполнить O (1) (например, выбор колеса рулетки посредством стохастического принятия ).
источник
Эта суть делает именно то, что вы просите.
Вы можете использовать это так:
Приведенный выше код, скорее всего, (% 98) вернет 0, что является индексом для «яблока» для данного массива.
Кроме того, этот код проверяет метод, представленный выше:
Это дает вывод что-то вроде этого:
источник