如何使用自定義概率分佈選擇隨機選擇

我有一個美國人名單及其在美國人口普查網站上的名稱列表。我想用給定的概率從這個列表中生成一個隨機名稱。數據在這裏：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

回答