2

有像 FisherYates 这样的洗牌算法。他们接受一个数组并以随机顺序返回一个元素。这在 O(n) 中运行。

我正在尝试做的是实现一个优先的 left-shuffle algorithm。这意味着什么？

  • 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) 中没有找到任何解决方案。

基于 FisherYates 的伪代码中的 O(n^2)：

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) 中）？

4

4 回答 4

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 konstant。如果有人有以适当方式更新 max_weight 的策略，性能将会提高。

于 2021-06-01T19:28:27.667 回答
0

我找到了一篇论文，其中介绍了 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)]

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

于 2021-05-22T19:53:44.300 回答
0

有一种方法可以使用增强的二叉搜索树在 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) 时间的算法来生成您的 shuffle。

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

于 2021-05-22T16:05:28.087 回答
-1

@StefanFenn 的“通过随机接受选择轮盘赌”的答案在技术上回答了我的问题。

但它有一个缺点：

算法中的最大值只计算一次。更频繁地计算它会导致性能比 O(n) 更差。如果有类似的优先级[100.000.000, 1, 2, 3]，算法可能需要通过 while 循环进行 1 次迭代，roulette_wheel_selection如果它选择了数字 100.000.000，但是一旦选择了 100.000.000，就会通过 while 循环进行数百万次迭代。

因此，我想向您展示一个非常短的 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 的集合，但按优先级/加权随机顺序排列。这些是指数。在最后一步中，我们根据这些索引的顺序插入值。

于 2021-12-23T08:33:46.450 回答