按权重选择随机项

Question

我有大约10000个项目的列表。现在的情况是，每个项目都有一个相关的权重（优先级或重要性）。目前最小的权重是-100（负数和零的值可以去掉），而最高的权重是1500。这个权重是由人们的直觉决定的（也就是他们觉得这个项目对社区有多重要）。因为确定哪个项目最重要并不容易，所以我想引入一些随机因素，这样权重较低的项目被选中的机会就会少一些，并且它们的权重在未来会进行调整（这是一种常识和随机性的结合）。

你知道怎么写一个叫getItem的函数吗？

def getItem(dict):
  # this function should return random item from 
  # the dictionary of item-weight pairs (or list of tuples)
  # Normally I would return only random item from the dictionary,
  # but now I'd like to have this: The item with weight 1500 should
  # have much more chance to be returned than the item with weight 10.
  # What's my idea is to sum up the weights of all items and then compute
  # some ratios. But maybe you have better idea.
  return randomItem

谢谢

Answer 1

你需要先随机抽取一个数字，这个数字的范围是从0到所有权重的总和（权重都是正数）。然后，你可以通过使用bisect这个工具，从一个列表中找到对应的项目。你可以在这里查看bisect的详细信息：http://docs.python.org/library/bisect.html（这是bisect的标准模块）。

import random 
import bisect
weight = {'a':0.3,'b':3.2,'c':2.4}
items = weight.keys()
mysum = 0
breakpoints = [] 
for i in items:
    mysum += weight[i]
    breakpoints.append(mysum)

def getitem(breakpoints,items):
    score = random.random() * breakpoints[-1]
    i = bisect.bisect(breakpoints, score)
    return items[i] 

print getitem(breakpoints,items)

Answer 2

Python 3.6 版本引入了一个新功能，叫做 random.choices()。

def get_item(items, items_weights):
    return random.choices(items, weights=items_weights)[0]

Answer 3

看看这个，我觉得这正是你需要的，它对不同的方法做了一些很好的比较。你可以在这里找到关于Python中的加权随机生成的内容。

这里建议的最简单的方法是：

import random

def weighted_choice(weights):
    totals = []
    running_total = 0

    for w in weights:
        running_total += w
        totals.append(running_total)

    rnd = random.random() * running_total
    for i, total in enumerate(totals):
        if rnd < total:
            return i

你可以在上面的链接中找到更多细节和可能的改进，以及一些不同的方法。