2

我正在寻找最有效的方法来随机绘制n列表中的元素，给定一个概率列表，说明每个元素被选择的概率。

aList = [3,4,2,1,4,3,5,7,6,4]

MyProba = [0.1,0.1,0.2,0,0.1,0,0.2,0,0.2,0.1]

这意味着在每次抽奖时，第一个元素（即 3）被抽出的概率为 0.1。当然，

sum(MyProba) == 1 # 总是返回 True len(aList) == len(MyProba) # 总是返回 True

到目前为止，我做了以下事情：

def random_pick(some_list, proba):
    x = random.uniform(0, 1)
    cumulative_proba = 0.0
    for item, item_proba in zip(some_list, proba):
        cumulative_proba += item_proba
        if x < cumulative_proba:
            break
    return item

nb_draws = 10
list_of_drawn_elements = []
for one_draw in range(nb_draws):
    list_of_drawn_elements.append(random_pick(aList, MyProba))

它可以工作，但是对于长列表和nb_draws. 我怎样才能提高这个过程的速度？

注意：在我面临的特殊情况下，nb_draws 总是等于aList.

4

4 回答 4

1

这是我的懒惰方法...构建一个列表，其中包含所需分布的预期值数量，并用于random.choice()从列表中选择一个值。

>>> import random
>>>
>>> value_probs = dict(zip([3,4,2,1,4,3,5,7,6,4], [0.1,0.1,0.2,0,0.1,0,0.2,0,0.2,0.1]))
>>> expected_dist = sum([[i] * int(prob * 100) for i, prob in value_probs.iteritems()], [])
>>> random.choice(expected_dist)
于 2013-10-29T08:51:19.760 回答
1

一般的想法（正如其他人的回答所概述的那样）是您的方法效率低下，因为每次绘制样本时都会进行预处理（累积分布的计算），尽管在采样，然后使用预处理后的数据进行采样。

使用Walker 的别名方法可以有效地完成预处理和采样。我已经实施了一段时间；看看源代码。（对不起外部链接，但我认为在这里发布它太长了）。我的版本需要 NumPy；如果您不想使用 NumPy，还有一个无NumPy 的替代方案（我的版本基于此）。

编辑: Walker 的别名方法的解释可以在我提供的第一个链接中找到。简而言之，假设您以某种方式设法构建了一个矩形“飞镖板”，该“飞镖板”被细分为多个部分，使得每个部分对应于您的原始项目之一，并且每个部分的面积与选择相应的所需概率成正比元素。然后，您可以开始在飞镖板上随机投掷飞镖（通过生成两个随机数来指定飞镖结束位置的水平和垂直坐标）并检查飞镖击中的区域。与区域对应的项目将是您选择的项目。Walker 的别名方法只是构造飞镖板的线性时间预处理。然后可以在恒定时间内完成每个元素的绘制。最后，画n 个元素中的m个元素的预处理成本为 O( n ) ，生成样本的成本为 O( m )，总复杂度为 O( n + m )。

于 2013-10-29T08:12:08.123 回答
0

You might try to precalculate the cumulative probability range for each element and make a tree from these intervals. Then you will get a logarithmic complexity for looking up the element corresponding to the generated probability, instead of linear one that you have now.

于 2013-10-29T08:18:09.910 回答
0

你cumulative_proba每次打电话时都在计算random_pick。我建议在方法之外进行计算，使用更好的数据结构来存储，比如二叉搜索树，这样可以将时间复杂度从 O(n) 降低到 O(lgn)。

于 2013-10-29T08:29:16.037 回答