Как написать алгоритм левой перетасовки с приоритетом в O(n)?

Question

Существуют алгоритмы перемешивания, такие как FisherYates. Они берут массив и возвращают его с элементами в случайном порядке. Это выполняется за O(n).

Что я пытаюсь сделать, так это реализовать алгоритм с приоритетом тасования влево . Что это обозначает?

• С приоритетом : не принимает массив значений. Требуется массив пар значение-вероятность. Например [ (1, 60), (2, 10), (3, 10), (4, 20) ]. Значение 1 составляет 60%, значение 2 - 10%, ...
• left-shuffle : чем выше вероятность значения, тем выше его шансы оказаться далеко слева от массива.

Возьмем этот пример [ (1, 10), (2, 10), (3, 60), (4, 20) ]. Наиболее вероятный результат должен быть [ 3, 4, 1, 2 ] или же [ 3, 4, 2, 1 ].

---

Я попытался реализовать это, но не нашел решения в O(n).

O (n ^ 2) в псевдокоде на основе FisherYates:

      sum = 100  #100%
for i = 0 to n-2:
    r = random value between 0 and sum
    localsum = 0
    for j = i to n-1:
        localsum = localsum + pair[j].Probability
        if localsum >= r + 1:
            swap(i, j)
            break
    sum = sum - pair[i].Probability

Что, вероятно, могло бы немного улучшить это: сортировка элементов по убыванию по вероятности в самом начале, чтобы минимизировать количество перестановок и итераций во внутреннем цикле.

Есть ли лучшее решение (может быть, даже за O(n))?

Answer 1

Обновление моего первого ответа:

Я нашел статью, в которой вводится «Выбор колеса рулетки через стохастическое принятие» с O(1). Это делает алгоритм равным O (n) и его легко реализовать.

      from random import randint
from random import random
import time

data = [ (1, 10), (2, 10), (3, 60), (4, 20) ]

def swap(i, j, array):
    array[j], array[i] = array[i], array[j]

def roulette_wheel_selection(data, start, max_weight_limit):
    while True:
        r = random()
        r_index = randint(start, len(data) - 1)
        if r <= data[r_index][1] / max_weight_limit:
            return r_index
    

def shuffle(data, max_weight):
    data = data.copy()
    n = len(data)
    for i in range(n-1):
        r_index = roulette_wheel_selection(data, i, max_weight)
        swap(i, r_index, data)
    return data

def performance_test(iterations, data):
    start = time.time()
    max_weight = max([item[1] for item in data])
    for i in range(iterations):
        shuffle(data, max_weight)
    end = time.time()
    print(len(data), ': ',end - start)
    return end - start

performance_test(1000, data)

data2 = []
for i in range(10):
    data2 += data
performance_test(1000, data2)  

data3 = []
for i in range(100):
    data3 += data
performance_test(1000, data3) 

data4 = []
for i in range(1000):
    data4 += data
performance_test(1000, data4) 

Производительность

      4 :  0.09153580665588379
40 :  0.6010794639587402
400 :  5.142168045043945
4000 :  50.09365963935852

Итак, это линейное время в n (размер данных). В моем первом ответе я обновил константу с «обновленной суммы» до «максимального веса всех элементов данных». Но конечно, это зависит от константы max_weight. Если у кого-то есть стратегия для правильного обновления max_weight, производительность увеличится.

Answer 2

Я нашел статью, в которой вводится «Выбор колеса рулетки через стохастическое принятие» с O(1). Это делает алгоритм равным O(n) и его легко реализовать.

      from random import randint
from random import random

data = [ (1, 10), (2, 10), (3, 60), (4, 20) ]

def swap(i, j, array):
    array[j], array[i] = array[i], array[j]

def roulette_wheel_selection(data, start, sum):
    while True:
        r = random()
        r_index = randint(start, len(data) - 1)
        if r <= data[r_index][1] / sum:
            return r_index
    

def shuffle(data):
    data = data.copy()
    n = len(data)
    sum = 100.0
    for i in range(n-1):
        r_index = roulette_wheel_selection(data, i, sum)
        swap(i, r_index, data)
        sum = sum - data[i][1]
    return data

for i in range(10):
    print(shuffle(data))

Выход

      [(3, 60), (4, 20), (2, 10), (1, 10)]
[(3, 60), (1, 10), (4, 20), (2, 10)]
[(3, 60), (1, 10), (4, 20), (2, 10)]
[(3, 60), (4, 20), (1, 10), (2, 10)]
[(3, 60), (4, 20), (2, 10), (1, 10)]
[(3, 60), (4, 20), (2, 10), (1, 10)]
[(3, 60), (4, 20), (2, 10), (1, 10)]
[(4, 20), (3, 60), (1, 10), (2, 10)]
[(3, 60), (2, 10), (4, 20), (1, 10)]
[(4, 20), (3, 60), (2, 10), (1, 10)]

Answer 3

Есть способ сделать это за время O(n log n), используя расширенные бинарные деревья поиска. Идея следующая. Возьмите элементы, которые вы хотите перемешать, и добавьте их в бинарное дерево поиска, каждое из которых помечено соответствующими весами. Затем для каждого узла в BST вычислите общий вес всех узлов в поддереве, основанном на этом узле. Например, вес корневого узла будет 1 (сумма всех весов, который равен 1, потому что это распределение вероятностей), сумма веса левого дочернего элемента корня будет общим весом в левом поддереве. , а сумма весов в правом потомке корня будет общим весом правого поддерева.

Имея такую ​​структуру, вы можете за время O(log n) выбрать случайный элемент из дерева, распределенный в соответствии с вашими весами. Алгоритм работает так. Равномерно выберите случайное число x в диапазоне от 0 до общего веса, оставшегося в дереве (первоначально 1, но по мере выбора предметов это будет уменьшаться). Затем начните с корня дерева. Пусть L - вес левого поддерева дерева, а w - вес корня. Рекурсивно используйте эту процедуру для выбора узла:

• Если x <L, переместитесь влево и рекурсивно выберите узел оттуда.
• Если L ≤ x <L + w, вернуть корень.
• Если L + w ≤ x, установите x:= x - L - w и рекурсивно выберите узел из правого поддерева.

Этот прием иногда называют выбором колеса рулетки , если вы хотите узнать о нем больше.

После того, как вы выбрали элемент из BST, вы можете удалить этот элемент из BST, чтобы не выбирать его снова. Существуют методы, которые гарантируют, что после удаления узла из дерева вы можете исправить суммы весов оставшихся узлов в дереве за время O(log n), чтобы они правильно отражали веса оставшихся элементов. Выполните поиск по расширенному двоичному дереву поиска, чтобы узнать, как это сделать. В целом это означает, что вы потратите O(log n) работы на выборку и удаление одного элемента, что в сумме по всем n элементам дает алгоритм времени O(n log n) для генерации вашего перемешивания.

Я не уверен, можно ли это улучшить. Существует еще один алгоритм выборки из дискретного дистрибутива, называемый методом псевдонима Vose, который дает запросы за время O(1), но он плохо обрабатывает изменения в базовом дистрибутиве, что вам нужно для вашего варианта использования.

Answer 4

Ответ @StefanFenn «Выбор колеса рулетки через стохастическое принятие» технически отвечает на мой вопрос.

Но у него есть недостаток:

Максимум в алгоритме вычисляется только один раз. Его вычисление чаще всего приводит к производительности хуже, чем O(n). Если есть такие приоритеты, как [100.000.000, 1, 2, 3], алгоритму, вероятно, потребуется 1 итерация цикла while roulette_wheel_selectionесли он выбирает число 100.000.000, но миллионы итераций через цикл while, как только будет выбрано 100.000.000.

Итак, я хочу показать вам очень короткое решение O(n*log(n)) которое я нашел, которое не зависит от того, насколько велики сами приоритеты (код C#):

      var n = elements.Count;
Enumerable.Range(0, n)
          .OrderByDescending(k => Math.Pow(_rng.NextDouble(), 1.0 / elements[k].Priority))
          .Select(i => elements[i].Value);

Описание: На основе коллекции с приоритетами из n элементов создаем новую коллекцию со значениями 0, 1, ... n-1. Для каждого из них мы называем Math.Powметод для вычисления ключа и упорядочения значений по этому ключу (поскольку нам нужны значения с более высоким приоритетом слева, а не справа). Теперь у нас есть коллекция с 0, 1, ... n-1, но в приоритетном/взвешенном случайном порядке. Это индексы. На последнем шаге мы получаем вставку значений в зависимости от порядка этих индексов.