Рандом с учетом весов за O(1) — Walker’s alias method

Есть массив A[n] с весами. Нужно выбрать случайный элемент, но не равномерным рандомом, а в соответствии с этими весами. (В общем, это дискретное распределение вероятности)

Чем примечателен метод алиаса, так это константным временем выполнения O(1)

Основная идея

(спойлер) Случайный элемент из двух с учетом весов

Итак, у нас есть функция random, которая выдает равновероятные числа в определенном диапазоне, который мы разделяем на n поддиапазонов, размер которых пропорционален весу. Получая очередной раз случайное число, мы определяем, к которому поддиапазону относится- это и будет результат.

Проблема

Проблема заключается в том, что поиск этого диапазона представляет собой проход по всему массиву и суммирование весов до тех пор пока сумма не окажется больше полученного случайного числа. А это- линейное время O(n), а не константное O(1).

Walker’s alias method

И тут, как нельзя кстати, приходит на помощь очень эффективный алгоритм, который называется алиас и суть которого заключается в том, что распределение вероятности не изменится, если мы наши n диапазонов разрежем на более мелкие поддиапазоны, и переставим их местами так, чтобы образовались диапазоны одинаковой длины с 1-2 поддиапазонами внутри. Это называется alias table, ее нужно строить один раз за линейное время и она позволяет выбирать случайный элемент за константное время: нужно два обычных рандома- один для выбора диапазона (они одинаковые, поэтому нам подходит равномерный рандом), а второй для выбора из двух поддиапазонов (см. спойлер в начале статьи).

Если звучит запутанно и нужен физический пример, то предположим что у нас есть 3 стакана разного объема с водой, маслом и ртутью. И мы можем перелить их, пусть, в 4 стакана одинакового объема, общим объемом равным тем трем стаканам. Дальше мы выбираем случайный стакан из четырех и в соответствии с долями двух жидкостей в нем, выбираем случайную жидкость.

Алгоритм по шагам

  1. Выбираем наименьшую k, чтобы 2^k > n. Создаем массив длиной 2^k — это будет alias table. Находим сумму весов, S. В каждую ячейку массива «влазит» ровно S/2^k веса.
  2. Заполняем его, перераспределяя веса:
    1. Находим наименьший нераспределенный вес и «кладем» в первую свободную ячейку, запоминая, от какого элемента это вес.
    2. Если целиком не влазит, то кладем, сколько влазит, а остальное пока храним.
    3. Если влезло целиком и осталось место, то заполняем до конца частью самого большого веса, запоминая и его элемент.
    4. Если еще есть нераспределенный вес, возвращаемся к шагу A.
  3. Выбор элемента по таблице алиаса
    1. Выбираем случайный элемент из таблицы. Ее размер выбран степенью двойки неспроста: берем первые k бит случайного числа — это и будет индекс элемента из таблицы.
    2. Если этот элемент алиас-таблицы заполнен весом единственного элемента, то его и выбираем.
    3. Если же есть два веса, то берем еще один рандом и он определяет, какой из двух элементов выбрать (см. спойлер)

Та да! 🙂

Спасибо что читаете!

ЗЫ: Реализацию на C и/или Python добавлю чуть позже.

Запись опубликована в рубрике Алгоритмы, Программирование, Разное с метками , , , . Добавьте в закладки постоянную ссылку.

2 комментария: Рандом с учетом весов за O(1) — Walker’s alias method

  1. Дмитрий говорит:

    Здравсвуйте,

    А код на C появился?

    Спасибо!

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *