在 Python 中从多重集（计数器）中有效采样

Question

令人讨厌的是，以下方法不起作用：

from collections import Counter
import random

c = Counter([1,1,1,1,0,0])
random.choice(c) # I expect this to return 1 with probability 2/3, 
                 # and 0 with probability 1/3.
                 # It actually returns 4 or 2, with probability 1/2

在 Python（任何版本）中从多重集采样的惯用方法是什么？

编辑是的，我确实需要使用多重集。我的实际数据要大得多，仅将其存储在列表中是不切实际的。

编辑 2我需要以合理的效率执行此操作，因为我的代码将重复执行此操作。Counter 对象中将存储大量数据，任何涉及将所有这些数据复制到新数据结构的操作都不是可行的解决方案。

Answer 1

从文档：

一个常见的任务是使用加权概率进行 random.choice() 。

如果权重是小的整数比，一个简单的技术是构建一个具有重复的样本总体：

>>> weighted_choices = [('Red', 3), ('Blue', 2), ('Yellow', 1), ('Green', 4)]
>>> population = [val for val, cnt in weighted_choices for i in range(cnt)]
>>> random.choice(population)
'Green'

更通用的方法是使用 itertools.accumulate() 将权重排列在累积分布中，然后使用 bisect.bisect() 定位随机值：

>>> choices, weights = zip(*weighted_choices)
>>> cumdist = list(itertools.accumulate(weights))
>>> x = random.random() * cumdist[-1]
>>> choices[bisect.bisect(cumdist, x)]
'Blue'

对于您的应用程序，您可能希望使用 Counter 来构建选择列表和累积概率列表，然后使用第二种技术进行采样。

Answer 2

你可以使用内置的random.choicespython >= 3.6来做到这一点

from collections import Counter
import random

c = Counter([1,1,1,1,0,0])
random.choices(list(c.keys()), weights=list(c.values()), k=1)

注意：在 python >= 3.7 中保证 dict 键的排序，因此示例代码将在 python >= 3.7 中运行。但在 python 3.6 中可以使用类似的解决方案。