Взвешенный случайный выбор из массива

Question

Я бы хотел случайным образом выбрать один элемент из массива, но каждый элемент имеет известную вероятность выбора.

Все шансы вместе (в массиве) суммируются в 1.

Какой алгоритм вы бы предложили как самый быстрый и наиболее подходящий для огромных вычислений?

Пример:

id => chance
array[
    0 => 0.8
    1 => 0.2
]

для этого псевдокода рассматриваемый алгоритм должен при нескольких вызовах статистически возвращать четыре элемента с идентификатором 0 для одного элемента с идентификатором 1.

Answer 1

Я собираюсь улучшить ответ https://stackoverflow.com/users/626341/masciugo.

По сути, вы создаете один большой массив, в котором количество отображаемых элементов пропорционально весу.

У него есть некоторые недостатки.

1. Вес не может быть целым числом. Представьте, что элемент 1 имеет вероятность пи, а элемент 2 имеет вероятность 1-пи. Как вы это делите? Или представьте, если таких элементов сотни.
2. Созданный массив может быть очень большим. Представьте, что если наименьший общий множитель равен 1 миллиону, то нам потребуется массив из 1 миллиона элементов в массиве, который мы хотим выбрать.

Чтобы противостоять этому, это то, что вы делаете.

Создать такой массив, но вставлять элемент случайным образом. Вероятность того, что элемент вставлен, пропорциональна весу.

Затем выберите случайный элемент из обычного.

Таким образом, если есть 3 элемента с различным весом, вы просто выбираете элемент из массива из 1-3 элементов.

Проблемы могут возникнуть, если построенный элемент пуст. То есть просто так получается, что в массиве нет элементов, потому что их игральные кости по-разному катятся.

В этом случае я предлагаю, чтобы вероятность вставки элемента была p (вставлена) = wi / wmax.

Таким образом, будет вставлен один элемент, а именно тот, который имеет наибольшую вероятность. Другие элементы будут вставлены с относительной вероятностью.

Скажем, у нас есть 2 объекта.

элемент 1 отображается в .20% времени. Элемент 2 обнаруживается в .40% времени и имеет наибольшую вероятность.

В массиве элемент 2 будет отображаться постоянно. Элемент 1 будет отображаться в половине случаев.

Таким образом, элемент 2 будет называться в 2 раза больше, чем элемент 1. Для общности все остальные элементы будут называться пропорционально их весу. Также сумма всех их вероятностей равна 1, потому что массив всегда будет содержать хотя бы 1 элемент.

Answer 2

Я полагаю, что числа больше или равные 0,8, но меньше 1,0, выбирают третий элемент.

Другими словами:

x - это случайное число от 0 до 1

если 0,0> = х <0,2: позиция 1 </p>

если 0,2> = х <0,8: позиция 2 </p>

если 0,8> = х <1,0: позиция 3 </p>