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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 821 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

第 1 条附言 · 2022-08-25 18:35:53 +08:00

哈哈哈哈主要还是求知欲想了解下方案,目前比较理想的方案应该是楼里的同学说的: 取期望值+浮动

最后还是选择了直接随机 1000 次,因为大部分情况下随机次数都比较少

聚合

抽奖

随机

21 条回复 • 2022-08-26 11:07:40 +08:00

imdong

2022-08-25 15:16:19 +08:00 via iPhone

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

edward1987

2022-08-25 15:18:05 +08:00

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

TimePPT

2022-08-25 16:26:16 +08:00

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

lmshl

2022-08-25 16:33:14 +08:00

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

edward1987

2022-08-25 16:33:45 +08:00

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

Vegetable

2022-08-25 16:33:53 +08:00

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

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

Vegetable

2022-08-25 16:34:46 +08:00

@Vegetable 哦不对，是 0..10

UIXX

2022-08-25 16:43:20 +08:00

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

InDom

2022-08-25 16:43:43 +08:00

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

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

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

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

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

sillydaddy

2022-08-25 17:10:07 +08:00

楼主如果想要严谨的话，应该是利用「二项式分布」： 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

2022-08-25 17:16:05 +08:00

@sillydaddy 应该是多项分布吧

mxT52CRuqR6o5

2022-08-25 17:16:29 +08:00 via Android

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

sillydaddy

2022-08-25 17:31:31 +08:00

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

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