用Python方式选择具有不同概率的列表元素

用Python方式选择具有不同概率的列表元素

权重定义概率分布函数（pdf）。任何此类pdf的随机数均可通过将其关联的逆累积分布函数应用于0到1之间的均匀随机数来生成。

另请参见以下SO解释，或者如Wikipedia所述：

如果Y具有U [0,1]分布，则F⁻（Y）作为F分布。这用于使用逆变换采样方法的随机数生成中。

import randomimport bisectimport collectionsdef cdf(weights):    total = sum(weights)    result = []    cumsum = 0    for w in weights:        cumsum += w        result.append(cumsum / total)    return resultdef choice(population, weights):    assert len(population) == len(weights)    cdf_vals = cdf(weights)    x = random.random()    idx = bisect.bisect(cdf_vals, x)    return population[idx]weights=[0.3, 0.4, 0.3]population = 'ABC'counts = collections.defaultdict(int)for i in range(10000):    counts[choice(population, weights)] += 1print(counts)# % test.py# defaultdict(<type 'int'>, {'A': 3066, 'C': 2964, 'B': 3970})

在

choice

上述用途功能

bisect.bisect

，所以加权随机变量的选择是在完成

O(log n)

其中

n

是的长度

weights

。

---

请注意，从1.7.0版开始，NumPy具有Cythonized
np.random.choice函数。例如，这从

[0,1,2,3]

具有权重的总体中生成1000个样本

[0.1,0.2, 0.3, 0.4]

：

import numpy as npnp.random.choice(4, 1000, p=[0.1, 0.2, 0.3, 0.4])

np.random.choice

也有一个

replace

参数，可以选择是否进行替换。

---

理论上更好的算法是Alias方法。它会建立一个需要

O(n)

时间的表格，但此后可以及时绘制样本

O(1)

。因此，如果您需要绘制许多样本，则从理论上讲，别名方法可能会更快。有一个Python实现沃克别名方法在这里和这里numpy的版本。