Python:随机绘制列表中的几个对象

Question

我正在寻找最有效的方法来在列表中随机绘制 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 # always returns True len(aList) == len(MyProba) # always returns 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 的长度。

Answer 1

一般的想法(正如其他人的答案所概述的那样)是您的方法效率低下，因为每次抽取样本时都会进行预处理(累积分布的计算)，尽管这样做就足够了在采样之前进行一次，然后使用预处理后的数据进行采样。

可以使用 Walker's alias method 高效地完成预处理和采样.我已经实现了一段时间；看看 source code . (对于外部链接很抱歉，但我认为在这里发布它太长了)。我的版本需要 NumPy；如果你不想使用 NumPy，有一个 NumPy-free alternative以及(我的版本基于此)。

编辑:Walker别名方法的解释可以在我提供的第一个链接中找到。简而言之，想象一下你设法构建了一个矩形的“飞镖板”，它被分割为多个部分，每个部分对应一个你的原始项目，每个部分的面积与选择相应项目的期望概率成正比元素。然后你可以开始在飞镖板上随机 throw 飞镖(通过生成两个随机数来指定飞镖结束位置的水平和垂直坐标)并检查飞镖击中了哪些区域。与区域对应的项目将是您选择的项目。 Walker 的别名方法只是构建飞镖板的线性时间预处理。然后可以在恒定时间内绘制每个元素。最后，从 n 中提取 m 个元素的预处理成本为 O(n)，而 O(m) 用于生成样本，产生的总复杂度为 O(n + m)。