如果您的加权选项列表是相对静态的，并且您希望频繁采样，则可以执行一个O(N)预处理步骤，然后使用相关答案中的函数在O(1)中进行选择。

# run only when `choices` changes.
preprocessed_data = prep(weight for _,weight in choices)

# O(1) selection
value = choices[sample(preprocessed_data)][0]

使用numpy

def choice(items, weights):
    return items[np.argmin((np.cumsum(weights) / sum(weights)) < np.random.rand())]

步骤1:生成您感兴趣的CDF F

步骤2:生成u.r.v. u

步骤3:求z=F^{-1}(u)

这种建模在概率论或随机过程课程中有描述。这是适用的，因为您有简单的CDF。

一种方法是随机化所有权重的总和，然后使用这些值作为每个变量的极限点。以下是作为生成器的粗略实现。

def rand_weighted(weights):
    """
    Generator which uses the weights to generate a
    weighted random values
    """
    sum_weights = sum(weights.values())
    cum_weights = {}
    current_weight = 0
    for key, value in sorted(weights.iteritems()):
        current_weight += value
        cum_weights[key] = current_weight
    while True:
        sel = int(random.uniform(0, 1) * sum_weights)
        for key, value in sorted(cum_weights.iteritems()):
            if sel < value:
                break
        yield key

假设你有

items = [11, 23, 43, 91] 
probability = [0.2, 0.3, 0.4, 0.1]

你有一个函数，它生成一个介于[0,1)之间的随机数(我们可以在这里使用random.random())。 现在求概率的前缀和

prefix_probability=[0.2,0.5,0.9,1]

现在，我们只需取一个0-1之间的随机数，然后使用二分搜索来查找该数字在prefix_probability中的位置。这个索引就是你的答案

代码是这样的

return items[bisect.bisect(prefix_probability,random.random())]

在Udacity免费课程AI for Robotics中，Sebastien Thurn对此进行了演讲。基本上，他用mod运算符%做了一个权重索引的圆形数组，将变量beta设为0，随机选择一个索引， for循环遍历N，其中N是指标的数量，在for循环中，首先按公式增加beta:

Beta = Beta +来自{0…2 * Weight_max}

然后在for循环中嵌套一个while循环per:

while w[index] < beta:
    beta = beta - w[index]
    index = index + 1

select p[index]

然后到下一个索引，根据概率(或课程中介绍的情况下的归一化概率)重新采样。

在Udacity上找到第8课，机器人人工智能的第21期视频，他正在讲粒子滤波器。