如何高效的生成 多次随机的结果?

[edward1987]

需求举例: 有个抽奖活动, 抽奖概率是 a:10%,b:30%,c:40%,d:20% 如果要支持批量抽,然后返回聚合结果,比如 用户可以一键批量抽 1000 次,然后返回 {a:104,b:288 ....的聚合结果

如果 1000 次要 每次都去取随机,然后统计聚合感觉太低效了, 有没有大佬有高效点的方案?

[imdong]

数量不多，直接循环随机，数量太多，先算出他中奖的可能性与数量，然后扣掉奖品，剩下的全部填充为未中奖。

[edward1987]

`先算出他中奖的可能性与数量`
@imdong 关键就是这一步呀,怎么高效的算出来呢?

[TimePPT]

你抽 1000 次这种量级，abcd 出现的个数约等于总次数乘以概率啊。直接算出来后上下浮动个随机数，加和等于 1000 就行。

[lmshl]

才 1000 次，说白了就是 1000 次 mul + add + mod ，暴力算也不过几微秒的事，这还要什么优化？
就算是一百万次也不值得优化

[edward1987]

@TimePPT 是个好想法, 不过这个浮动的随机数不知道怎么取比较合适

[Vegetable]

这里居然真的有人用“随机 10 次”来实现 10 连抽，过于良心引起不适。

如果你想得到真实的结果，那其实可以算，10% * 10 能得到 1..10 这 10 种情况，每种情况出现的概率都是能算出来的。所以你只需要根据这个权重随机一次就能得到这 10 连抽应该得到几个 a 。

[Vegetable]

@Vegetable 哦不对，是 0..10

[UIXX]

看来 OP 是个良心策划，铁了心践行大数定律，其实这个很简单。直接排出 100 ，300 ，400 ，200 ，然后加扰动值，这个扰动值跟批量的次数有关，批量的次数越大扰动值越小，至于是线性还是非线性，是一次方还是二次方，就跟 OP 的良心大小有关了。

[InDom]

把中奖概率 * 抽奖次数 = 中奖个数，然后随机给个偏差，不管需要抽多少次，你有几个奖品，就需要随机几次。

你这设置概率 100% 中奖，那就是抽一千次

c 有 40% ± rand% * 1000 次 = 104 个 1000 - 104
b 有 30% ± rand% * 1000 次 = 288 个 1000 - 104 - 288

以此类推，建议把中奖率排个序，先从这中奖率高的随机，随机完就把总次数减掉已派奖的，抽完就不抽了。

别跟我讲公平，公平你就该一次次抽奖。

[sillydaddy]

楼主如果想要严谨的话，应该是利用「二项式分布」： https://zh.m.wikipedia.org/zh/%E4%BA%8C%E9%A0%85%E5%BC%8F%E5%88%86%E5%B8%83

```
二项分布 B(n, p)，指的是单次实验成功概率是 p ，那么经过 n 次实验，成功次数的概率分布。

成功 k 次的概率是
{\displaystyle f(k,n,p)=\Pr(X=k)={n \choose k}p^{k}(1-p)^{n-k}}
```

先把 a 的中奖次数算出来：a 成功的概率 p=10%=0.1 ，实验 1000 次，成功次数小于 k 的分布，是二项分布 B(n,p)的累计分布函数，所以取一个随机值，与累积分布函数对应，得出 a 的中奖次数；
然后把 b 的中奖次数用类似的方法算出来，然后是 c ，最后 d 就不用计算了。

[icyalala]

@sillydaddy 应该是多项分布吧

[mxT52CRuqR6o5]

取 1000 次随机数能消耗多少性能，别浪费时间优化这个没多大收益的事情了

[sillydaddy]

@icyalala
是多项分布。但是我想不到多项分布怎么去计算(多项分布的累积分布函数不知道怎么弄)，所以把它拆成多个二项分布，二项分布可以利用它的累积分布函数，直接得出中奖次数。

不过忘了说了，二项分布本身的计算很直接，但这个累积分布函数不知道有没有高效的计算方法，没有的话还不如直接循环 1000 次 random 呢。

[leimao]

Multinomial Distribution

[Jooooooooo]

如果你真的用普通随机会被骂的, 肯定不行.

[leimao]

https://numpy.org/doc/stable/reference/random/generated/numpy.random.multinomial.html

[leimao]

我有一节简单讲了讲 Multinomial Distribution 怎么推导的
https://leimao.github.io/blog/Introduction-to-Dirichlet-Distribution/

[2kCS5c0b0ITXE5k2]

可以看下 Alias Method.

[2kCS5c0b0ITXE5k2]

#18 构造表的时间复杂度：O(n)   后续实际抽选的时间复杂度：O(1)

[edward1987]

@emeab 应该不行,因为我这个次数是不确定的,不是固定的 1000 次

@leimao 多谢,看着有亿点复杂,我研究下~