根据概率从Python列表中选择元素

Question

我正在写一个Python脚本，想从这里的男性名字列表中随机挑选1000个名字：http://www.census.gov/genealogy/www/data/1990surnames/names_files.html

这个功能目前运行得很好，但我希望能根据人口普查文本文件中提供的概率列（第二列）来选择名字。

我这几小时一直在思考这个问题，但到现在为止还没有什么实质性的进展，甚至查找了其他的答案。

有没有人能帮我一下，或者给我指个方向？提前谢谢大家 :)

Answer 1

一个快速而且非常简单的办法，适合小数据集，就是把你想要的名字重复添加多次，次数根据它的权重来决定。需要注意的是，这样做会占用很多内存，特别是在处理大数据集的时候，所以这个方法只适合小的权重分布。

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))

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个项目，这个效率可能对你来说并不重要。

Answer 3

一个简单的加权选择算法是：

1. 给每个名字分配一个相对概率，使得所有概率的总和为1。这个相对值叫做“权重”。

2. 随机选择一个0到1之间的数字。

3. 遍历列表，每经过一个项目，就从你的数字中减去这个项目的权重。

4. 当你的数字减到0或更低时，选择当前这个项目。