基于概率从Python列表中选择元素

Question

我正在创建一个Python脚本，从这里列出的男性名字列表中随机挑选1000个名字：http://www.census.gov/genealogy/www/data/1990surnames/names_files.html。虽然这样做很好，但我希望根据人口普查文本文件提供的概率列来选择名称（第二列）。我已经试图在过去的几个小时里理解这个问题，但我没有取得任何真正的进展，甚至寻找其他答案也没有用。有谁能帮帮我或指点我正确的方向？提前感谢：）

- IrateIrish

---

这可能会有所帮助 - https://dev59.com/kHRC5IYBdhLWcg3wRO3k - Sukrit Kalra

Eli Bendersky在Python中关于加权随机选择的页面非常有信息量。 - DSM

@DSM 那个页面非常有帮助。谢谢！ - IrateIrish

Answer 1

一种简单的加权选择算法如下：

1. 为每个名称分配其相对概率，使所有概率之和为1。这个相对值被称为“权重”。

2. 选择一个介于0和1之间的随机数。

3. 遍历列表，在遍历时从该数字中减去每个项目的权重。

4. 当您到达0或更低时，选择当前项目。

- salezica

---

这个方法可能可行，但问题在于我要从大约1200个名称中选择1000次。那么这种方法会花费很长时间吗？ - IrateIrish

你不能比这更快了：它以线性时间运行，几乎没有最小常数因子。显然，权重只计算一次，在进行随机选择之前。 - salezica

Answer 2

数据文件的第三列是累积概率，即第二列的运行总和。

要根据累积概率分布选择随机名称，请按以下步骤操作：

1. 生成0到1之间的随机数，
2. 找到第一行其累积概率大于该随机数的行，
3. 选择该行中的名称。

import urllib2
import random
import bisect

url = 'http://www.census.gov/genealogy/www/data/1990surnames/dist.male.first'
response = urllib2.urlopen(url)
names, cumprobs = [], []
for line in response:
    name, prob, cumprob, rank = line.split()
    cumprob = float(cumprob)
    names.append(name)
    cumprobs.append(cumprob)

# normalize the cumulative probabilities to the range [0, 1]
cumprobs = [p/cumprobs[-1] for p in cumprobs]
# print(cumprobs)

# Generate 1000 names at random, using the cumulative probability distribution
N = 1000
selected = [names[bisect.bisect(cumprobs, random.random())] for i in xrange(N)]
print('\n'.join(selected))

注意，别名算法具有更好的计算复杂度，但对于选择仅1000项的情况，这可能对您的使用情况不是非常重要。

- unutbu

Answer 3

一个快速而非常“肮脏”的解决方案，适用于较小的数据集，就是将问题名称添加到数量等于加权分布的次数中。请注意，这将消耗大量内存，特别是在较大的数据集中，因此请将其视为仅适用于小型加权分布的快速实现。

import random

filename = r"location/of/file"
data = list() # accumulator

with open(filename) as in_:
    for line in in_:
        name, prob, *_ = line.split()
        for _ in range(int(float(prob)*1000)):
            data.append(name)

print(random.choice(data))

- Adam Smith