选择带权重的随机项。

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

谢谢你

- xralf

---

嗨，我最近回答了一个类似这样的问题：https://dev59.com/eF_Va4cB1Zd3GeqPXt2O#9073313 - Sam Felix

Answer 1

看看这个链接，我认为它能提供你所需的内容，并对不同方法进行了良好的比较：在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

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

- Bogdan

---

在SO上的答案应该是自包含的，因此请考虑将链接文章的精华融入您的答案中。 - Sven Marnach

需要对 weights 进行排序吗？ - Acebee

Answer 2

Python 3.6 引入了 random.choices()

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

- m.elahi

---

这段代码完美地实现了OP所需的功能，只使用了一行标准Python库代码。谢谢！ - Huw Walters

Answer 3

您需要提取一个在0和权重总和之间的随机数（根据定义为正）。然后，通过使用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)

- jimifiki

Answer 4

如果权重不为负数，那么这个问题就比较容易解决。但是如果你必须使用负数权重，你需要将权重偏移至最小可能的权重值。在你的情况下，offsetted_weight = itemweight + 100

伪代码如下：

Calculate the sum of all the weights.
Do a random from 0 to the sum of the weights
Set i to 0
While the random number > 0
    Subtract the weight of the item at index i  from random
    If the random number is < 0 return item[i]
    Add 1 to i

- Dervall

---

负重量是在每个项目的重量都为1时出现的，但没有必要有负重量，我可以去掉负数。 - xralf

Answer 5

如果您正在数据库中存储数据，可以使用SQL：

SELECT * FROM table ORDER BY weight*random() DESC LIMIT 1

- groovekiller

---

很整洁，但这是SQL，而问题标记为Python。不管怎样，我喜欢这个想法。 - KL-7

@copperttim 实际上我很喜欢它，因为我使用 sql，你的解决方案乍一看看起来相当不错和可用。 - xralf

根据您的描述，我认为您正在使用 SQL。希望它能按您的需求工作。 - groovekiller

我取消了我的踩，但是你的答案似乎有和我的一样的缺陷（正如@SvenMarnach所指出的）。 - Tim Pietzcker

我也看到了，但是有缺陷的答案对于学习来说还是不错的。删除它们有点可惜。在此之前加上“警告”就足够了。 - xralf