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

Question

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

3

我有一个美国人名单，以及他们在美国人口普查网站上对应的姓名。我想通过给定的概率从这个列表中生成随机姓名。数据在这里：美国人口普查数据我看到过像轮盘赌选择算法这样易于实现的算法，但我想知道是否有任何方法可以在O（1）中生成随机名称。对于直方图数据来说，这更容易，因为你可以创建整数到生日的哈希表，但我想对连续分布进行操作。

如果不可能，是否有任何Python模块可以接收概率分布并根据这些分布生成随机值？

- JDong

2

你考虑使用哪种概率分布？你的数据集中有很多0.000。我认为最好能找到一个小数点后超过3位的数据源。 - John La Rooy

你不能只是给每个名称分配比例宽度，然后将0到1之间的随机数映射到新范围上吗？ - Waleed Khan

2

@WaleedKhan，但是在范围内的查找是O(log n)。 - John La Rooy

2个回答

4

如今，如果您确实需要O(1)查找，完全可以枚举整个美国人口（~3.17亿）。只需选择一个不超过3.17亿的数字，然后从中获取姓名。（317000000 * 4字节 = 1.268GB）

我认为有很多O(log n)的方法。您需要O(1)的特殊原因吗？（它们将使用更少的内存）

- John La Rooy

这主要是理论性的，但我也想知道是否有比我那种本能的O(log)反应更好的解决方案。 - JDong

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Peters · Accepted Answer

有一种O(1)时间复杂度的方法。请参考这篇详细的Vose“别名”方法描述。不幸的是，它的初始化成本很高。如果想了解更简单方法的比较时间，请参考Eli Bendersky的博客文章。更多时间信息可以在Python问题跟踪器中找到。