V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
edward1987
V2EX  ›  程序员

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

  •  1
     
  •   edward1987 · 2022-08-25 15:10:41 +08:00 · 1932 次点击
    这是一个创建于 581 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求举例: 有个抽奖活动, 抽奖概率是 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
        1
    imdong  
       2022-08-25 15:16:19 +08:00 via iPhone
    数量不多,直接循环随机,数量太多,先算出他中奖的可能性与数量,然后扣掉奖品,剩下的全部填充为未中奖。
    edward1987
        2
    edward1987  
    OP
       2022-08-25 15:18:05 +08:00
    `先算出他中奖的可能性与数量`
    @imdong 关键就是这一步呀,怎么高效的算出来呢?
    TimePPT
        3
    TimePPT  
       2022-08-25 16:26:16 +08:00
    你抽 1000 次这种量级,abcd 出现的个数约等于总次数乘以概率啊。直接算出来后上下浮动个随机数,加和等于 1000 就行。
    lmshl
        4
    lmshl  
       2022-08-25 16:33:14 +08:00
    才 1000 次,说白了就是 1000 次 mul + add + mod ,暴力算也不过几微秒的事,这还要什么优化?
    就算是一百万次也不值得优化
    edward1987
        5
    edward1987  
    OP
       2022-08-25 16:33:45 +08:00
    @TimePPT 是个好想法, 不过这个浮动的随机数不知道怎么取比较合适
    Vegetable
        6
    Vegetable  
       2022-08-25 16:33:53 +08:00
    这里居然真的有人用“随机 10 次”来实现 10 连抽,过于良心引起不适。

    如果你想得到真实的结果,那其实可以算,10% * 10 能得到 1..10 这 10 种情况,每种情况出现的概率都是能算出来的。所以你只需要根据这个权重随机一次就能得到这 10 连抽应该得到几个 a 。
    Vegetable
        7
    Vegetable  
       2022-08-25 16:34:46 +08:00
    @Vegetable 哦不对,是 0..10
    UIXX
        8
    UIXX  
       2022-08-25 16:43:20 +08:00   ❤️ 3
    看来 OP 是个良心策划,铁了心践行大数定律,其实这个很简单。直接排出 100 ,300 ,400 ,200 ,然后加扰动值,这个扰动值跟批量的次数有关,批量的次数越大扰动值越小,至于是线性还是非线性,是一次方还是二次方,就跟 OP 的良心大小有关了。
    InDom
        9
    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
        10
    sillydaddy  
       2022-08-25 17:10:07 +08:00   ❤️ 1
    楼主如果想要严谨的话,应该是利用「二项式分布」: 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
        11
    icyalala  
       2022-08-25 17:16:05 +08:00
    @sillydaddy 应该是多项分布吧
    mxT52CRuqR6o5
        12
    mxT52CRuqR6o5  
       2022-08-25 17:16:29 +08:00 via Android
    取 1000 次随机数能消耗多少性能,别浪费时间优化这个没多大收益的事情了
    sillydaddy
        13
    sillydaddy  
       2022-08-25 17:31:31 +08:00
    @icyalala
    是多项分布。但是我想不到多项分布怎么去计算(多项分布的累积分布函数不知道怎么弄),所以把它拆成多个二项分布,二项分布可以利用它的累积分布函数,直接得出中奖次数。

    不过忘了说了,二项分布本身的计算很直接,但这个累积分布函数不知道有没有高效的计算方法,没有的话还不如直接循环 1000 次 random 呢。
    leimao
        14
    leimao  
       2022-08-25 22:20:40 +08:00 via iPhone
    Multinomial Distribution
    Jooooooooo
        15
    Jooooooooo  
       2022-08-25 22:21:49 +08:00
    如果你真的用普通随机会被骂的, 肯定不行.
    leimao
        17
    leimao  
       2022-08-25 22:26:45 +08:00 via iPhone
    我有一节简单讲了讲 Multinomial Distribution 怎么推导的
    https://leimao.github.io/blog/Introduction-to-Dirichlet-Distribution/
    emeab
        18
    emeab  
       2022-08-25 23:27:45 +08:00
    可以看下 Alias Method.
    emeab
        19
    emeab  
       2022-08-25 23:35:13 +08:00
    #18 构造表的时间复杂度:O(n)   后续实际抽选的时间复杂度:O(1)
    edward1987
        20
    edward1987  
    OP
       2022-08-26 10:57:58 +08:00
    @emeab 应该不行,因为我这个次数是不确定的,不是固定的 1000 次

    @leimao 多谢,看着有亿点复杂,我研究下~
    libook
        21
    libook  
       2022-08-26 11:07:40 +08:00
    中奖名额少的话,可以提前算出来第多少次中奖,然后记录下来,抽的时候只要没抽到这些次数就不中奖。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5387 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 07:06 · PVG 15:06 · LAX 00:06 · JFK 03:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.