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

[C++] 从 0 到 2 亿随机采样(300 个)的最佳实践?

  •  
  •   zynlp · 2018-08-27 11:03:45 +08:00 via iPhone · 2949 次点击
    这是一个创建于 2041 天前的主题,其中的信息可能已经有所发展或是发生改变。
    google 了给的结果:
    1、先 shuffle 再取前 300 个
    2、stl::sample ( only c++17 )

    有没有什么其他更好的方法?
    5 条回复    2018-08-27 15:17:33 +08:00
    wutiantong
        1
    wutiantong  
       2018-08-27 11:24:58 +08:00
    从 2 亿个数里随机取一个(std::uniform_int_distribution)记为 a1
    从(2 亿-1)个数里随机取一个记为 a2,if (a2 >= a1) then (a2 += 1)
    从(2 亿-2)个数里随机取一个记为 a3,if (a3 >= max(a1, a2)) then (a3 += 2) elif (a3 >= min(a1, a2)) then (a3 += 1)
    依次类推 300 次
    geelaw
        2
    geelaw  
       2018-08-27 11:32:42 +08:00
    这个“随机采样”根本没说明白,根据心电感应做题法,你希望从 0 到 2 亿无放回抽样 300 个。

    方法 1:你做 300 次有放回抽样,如果有重复就再来一次。这样做期望 1.00224502750272 次可以得到一个有效结果。这个东西的别名叫做 birthday attack。

    方法 2:按照 #1 的方法挖洞。
    GeruzoniAnsasu
        3
    GeruzoniAnsasu  
       2018-08-27 11:36:49 +08:00
    不知道这“最佳实践”最佳在哪个方面

    是效率还是随机性还是均匀度还是什么的

    可以参考下这个,stl 默认的随机数引擎
    https://zh.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
    Nirvanada
        4
    Nirvanada  
       2018-08-27 14:22:53 +08:00   ❤️ 1
    参考下蓄水池采样
    ipwx
        5
    ipwx  
       2018-08-27 15:17:33 +08:00
    我觉得 reject sampling 对这个场景其实还行。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2921 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 14:06 · PVG 22:06 · LAX 07:06 · JFK 10:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.