如何使用自定义概率分布选择随机选择

我有一个美国人名单及其在美国人口普查网站上的名称列表。我想用给定的概率从这个列表中生成一个随机名称。数据在这里：US Census data 如何使用自定义概率分布选择随机选择

我见过像roulette wheel selection算法这样的算法很容易实现，但我想知道是否有任何方法在O（1）中生成随机名。对于histogram data这很容易，因为你可以创建一个整数到生日的散列，但我想这样做的持续分布。

如果这是不可能的，是否有任何python模块接受概率分布并基于这些分布生成随机值？

2013-10-20 JDong

你想用什么样的概率分布？数据集中的许多条目都是0.000。我认为如果你能找到一个有3位小数的数据来源会更好。 –

难道你不能只分配每个名称的比例宽度，然后将从0到1的随机数映射到新的范围？ –

@WaleedKhan，但范围内的查找是O（log n） –

有一个O(1)时间方法请参阅this detailed description of Vose's "alias" method。不幸的是，它的初始化成本很高。有关更简单方法的比较时间，请参阅Eli Bendersky's blog post。更多的时间可以在in this from the Python issue tracker找到。

2013-10-21 00:07:27

别名方法阅读很有意思。我认为表代可能会使一个很好的代码高尔夫 –

我认为别名方法是最接近我正在寻找。问题跟踪器也是一个有趣的链接。尽管如此，我仍然需要找到更好的数据来源。 – JDong

@JDong，请注意，问题跟踪器项目附有文件，其中包含所有Serhiy Storchaka报告时间方法的Python实现。祝你好运！ :-) –

如果您确实需要查找O(1)查找，现在可以列举整个美国人口（约3.17亿）。只需要挑选一个高达3.17亿的数字并从那里获取名称。（317000000 * 4字节= 1.268GB）

我认为有很多O(log n)方式。是否有特殊原因需要O(1)（他们会使用更少的内存）

2013-10-20 23:36:55

这主要是理论上的，但我也想知道是否有比我的膝盖混战O（对数）反应更好的解决方案。 – JDong

回答