非重复随机数 [英] non-repeating random numbers

问题描述

我需要生成大约9到1亿个非重复的随机数，范围从零到生成的数量不等，而且我需要非常快地生成它们.提出了一些类似问题的答案，只是简单地对数组进行改组以获得随机数，而提出的其他问题则使用布隆过滤器.问题是，哪一个效率更高?如果是布隆过滤器，该如何使用?

I need to generate around 9-100 million non-repeating random numbers, ranging from zero to the amount of numbers generated, and I need them to be generated very quickly. Several answers to similar questions proposed simply shuffling an array in order to get the random numbers, and others proposed using a bloom filter. The question is, which one is more efficient, and in case of it being the bloom filter, how do I use it?

推荐答案

您根本不需要随机数.您需要精确地将数字0到N-1随机排列.

You don't want random numbers at all. You want exactly the numbers 0 to N-1, in random order.

简单地填充数组并改组应该很快.正确的Fisher-Yates洗牌是O(n)，因此使用C甚至Java在一亿的数组中应该花不到一秒的时间，而在像Python这样的高级语言中，速度稍慢一些.

Simply filling the array and shuffling should be very quick. A proper Fisher-Yates shuffle is O(n), so an array of 100 million should take well under a second in C or even Java, slightly slower in a higher-level language like Python.

您只需要生成N-1个随机数即可进行随机播放(如果使用拒绝采样来获得完美的均匀性，则可能高达1.3N)，因此速度很大程度上取决于RNG的速度.

You only have to generate N-1 random numbers to do the shuffle (maybe up to 1.3N if you use rejection sampling to get perfect uniformity), so the speed will depend largely on how fast your RNG is.

您将无需查看是否已生成数字；无论您使用哪种算法，这都将是致命的，特别是在运行快结束时.

You'll never need to look up whether a number has already be generated; that will deadly be slow no matter which algorithm you use, especially toward the end of the run.

如果您需要的总数少于N个，请将数组从0填充到N-1，然后尽早中止改组并获得部分结果.仅当所需数量与其范围相比很小时，才应考虑生成并检查重复项的方法.在那种情况下，鲍勃·弗洛伊德(Bob Floyd)的算法可能会很好.

If you need slightly fewer than N total numbers, fill the array from 0 to N-1, then just abort the shuffle early and take the partial result. Only if the amount of numbers you need is very small compared to their range should you consider the generate-and-check-for-dups approach. In that case Bob Floyd's algorithm might be good.

这篇关于非重复随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！