use*_*469 2 random shuffle bloom-filter non-repetitive
我需要生成大约9到1亿个非重复随机数,范围从零到生成的数字量,我需要它们很快生成.对类似问题的几个答案提出简单地改组数组以获得随机数,而其他提议使用布隆过滤器.问题是,哪一个更有效,如果它是布隆过滤器,我该如何使用它？
您根本不需要随机数.你想要随机顺序的数字0到N-1.
简单地填充阵列和洗牌应该非常快.一个适当的Fisher-Yates shuffle是O(n),所以一个1亿的数组应该在C或甚至Java的一秒内很好,在像Python这样的高级语言中稍微慢一些.
您只需要生成N-1个随机数来进行随机播放(如果使用拒绝采样来获得完美的均匀性,则可能高达1.3N),因此速度在很大程度上取决于您的RNG的速度.
你永远不需要查询是否已经生成了一个数字; 无论你使用哪种算法,特别是在运行结束时,这都会很慢.
如果您需要略少于N个总数,请将数组从0填充到N-1,然后提前中止洗牌并获取部分结果.只有当您需要的数字量与其范围相比非常小时,您才应考虑生成并检查重复方法.在那种情况下,Bob Floyd的算法可能会很好.