[問題] 從機率不同的幾個樣本中隨機抽出一個

[shinjiyano (矢野真士)]

最近有個需求，有點像抽抽獎券

假設有5個人A B C D E

A手上有5張抽獎券
B手上有12張抽獎券
C手上有15張抽獎券
D手上有18張抽獎券
E手上有20張抽獎券
總共70張

當然抽獎券都是記自己名字的

他們將抽獎券都丟入同一個箱子

這時隨機抽出一張

A被抽中的機率就是5/70
B被抽中的機率就是12/70
C被抽中的機率就是15/70
D被抽中的機率就是18/70
E被抽中的機率就是20/70

當然真正遇到的問題可能有上萬人，每個人有幾萬張抽獎券之類的

我自己想過兩種寫法
第1種是最笨的做法
把ABCDE都丟入一個list，有幾張就丟幾個
[A,A,A,A,A,B,B,B,B,B,B,B,B,B,B,B,B,C......]
然後就用亂數隨機抽出一個就行了
但遇到上萬人這做法太沒效率了而且很佔記憶體甚至LIST可能會爆炸

第2種是用數值範圍
先把總和加起來是70的話，就抽1~70的數字
若是抽中1～5就是A
6～17就是B
18～32就是C
33～50就是D
51～70就是E
但在抽之前就得先算好每個人的範圍，感覺也蠻沒效率的


想請教高手是否有比較有效率的做法呢? 感謝!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.233.30.207
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1542374582.A.6C1.html
推 jobsdone: Fenwick tree?
推 idiont: 第二種建立前綴和 n個人只要做n次加法 要從random的結果推
→ idiont: 出是誰也可以使用二分搜加速 不會很慢吧
→ bowin: 寫一個function隨機產生uniform(0,1),然後
→ bowin: 用probability integral transform抽出你要的元素
推 hare1039: 用 std::discrete_distribution 就直接可以解了
→ hare1039: https://goo.gl/5qwWQ8 cppreference 上有範例
推 Schottky: 真士......是人狼君的作者？
→ Schottky: 幾萬個加法並不慢啊，抽獎池幾萬筆資料也不會很大
→ Schottky: 線性搜尋可以輕鬆處理的範圍，不到一秒吧
推 longlongint: 看需求 求效率的話上面回覆就夠用了
→ longlongint: 但是拿去抽轉蛋會被罵死 不如用 list 照比例配票 XD
→ longlongint: D
推 FRAXIS: 如果你是要同一個 distribution 重複抽的話
→ FRAXIS: 那用 alias method 會比較快 https://goo.gl/YLUafa
→ FRAXIS: 如果一個 distribution 只抽一次 那就 Reservoir Sampling
推 cutekid: 推 FRAXIS 大！學到好多。