我有一份来自美国人口普查网站的美国姓名及其各自姓名的列表。我想使用给定的概率从此列表中生成一个随机名称。数据在这里：美国人口普查数据
我见过像轮盘赌选择算法这样易于实现的算法，但我想知道是否有任何方法可以在 O(1) 中生成随机名称。对于直方图数据，这更容易，因为您可以创建一个整数哈希到生日，但我想这样做是为了实现连续分布。
如果这是不可能的，是否有任何 python 模块可以接受概率分布并根据这些分布生成随机值？
问问题
1033 次
2 回答
6
There is an O(1)-time method See this detailed description of Vose's "alias" method. Unfortunately, it suffers from high initialization cost. For comparative timings of simpler methods, see Eli Bendersky's blog post. More timings can be found in this from the Python issue tracker.
于 2013-10-21T00:07:27.130 回答
4
如今，如果您真的需要O(1)查找，枚举整个美国人口（约 3.17 亿）是可行的。只需选择一个高达 3.17 亿的数字并从那里获得名称。（317000000*4 字节 = 1.268GB）
我认为有很多O(log n)方法。您是否需要特殊原因O(1)（他们将使用更少的内存）
于 2013-10-20T23:36:55.097 回答