如何在 O(n) 中编写优先左洗牌算法？

Question

有像 FisherYates 这样的随机播放算法。他们采用一个数组和 return 一个具有随机顺序元素的数组。这在 O(n) 中运行。

我想做的是实现一个优先左洗牌算法。这是什么意思？

Prioritized：它不接受值数组。它需要一组值概率对。例如。 [ (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(n log n) 内完成此操作。这个想法如下。取出要打乱顺序的项目并将它们添加到二叉搜索树中，每个项目都用相关的权重进行注释。然后，对于 BST 中的每个节点，计算以该节点为根的子树中所有节点的总权重。比如根节点的权重为1（所有权重之和，因为是概率分布所以为1），根节点左边child的权重之和就是总权重在左子树中，根的右 child 中的权重之和将是右子树的总权重。

有了这个结构，您可以在 O(log n) select 时间内从树中随机选择一个元素，并根据您的权重进行分配。该算法是这样工作的。选择一个随机数 x，均匀地从 0 到树中剩余的总重量（最初为 1，但随着项目被挑选，这将减少）。然后，从树根开始。令 L 为树的左子树的权重，w 为根的权重。递归地使用此过程 select 一个节点：

如果 x < L，向左移动并从那里递归 select 一个节点。
如果 L ≤ x < L + w，return 根。
如果 L + w ≤ x，设置 x := x - L - w 并递归 select 来自右子树的节点。

这种技术有时被称为 轮盘赌 selection，以防您想了解更多信息。

一旦您从 BST select编辑了一个项目，您就可以从 BST 中删除该项目以确保您不会再次选择它。有一些技术可以确保在从树中删除节点后，您可以在时间 O(log n) 内确定树中剩余节点的权重和，以便它们正确反映剩余项的权重。搜索 augmented binary search tree 以了解有关如何执行此操作的详细信息。总的来说，这意味着您将花费 O(log n) 的工作来采样和删除单个项目，所有 n 个项目的总和给出了一个 O(n log n) 时间的算法来生成您的随机播放。

我不确定是否可以对此进行改进。还有另一种从离散分布中抽样的算法，称为 Vose 的别名方法，它提供 O(1) 时间查询，但效果不佳处理对基础分布的更改，这是您的用例所需要的。

Answer 2

我找到了 paper，其中引入了 O(1) 的 'Roulette-wheel selection via stochastic acceptance'。这使得算法复杂度为 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)]

注意：为了获得最佳性能，roulette_wheel_selection 应根据每次迭代使用 p_max 而不是 sum。我使用 sum 因为它易于计算和更新。

Answer 3

更新我的第一个回答：

我找到了 paper，其中引入了 O(1) 的 'Roulette-wheel selection via stochastic acceptance'。这使得算法复杂度为 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 4

@StefanFenn 的 'Roulette-wheel selection via stochastic acceptance' 回答从技术上回答了我的问题。

但它有一个缺点：

算法中的最大值只计算一次。更频繁地计算它会导致性能比 O(n) 更差。如果有像 [100.000.000, 1, 2, 3] 这样的优先级，如果算法选择数字 100.000.000，则该算法可能需要通过 roulette_wheel_selection 的 while 循环进行 1 次迭代，但只要选择 100.000，就需要通过 while 循环进行数百万次迭代。 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 的集合，但顺序为 prioritized/weighted。这些是指数。在最后一步中，我们根据这些索引的顺序插入值。

如何在 O(n) 中编写优先左洗牌算法？

How to write a prioritized left-shuffle algorithm in O(n)?

algorithm

complexity-theory

shuffle

fisher-yates-shuffle