random - 非重复随机数

Question

我需要生成大约 9-1 亿个非重复随机数，范围从零到生成的数字量，并且我需要非常快速地生成它们。对类似问题的几个答案提出了简单地对数组进行洗牌以获得随机数，而其他人则提出了使用布隆过滤器。问题是，哪个效率更高，如果是布隆过滤器，我该如何使用它？

Answer 1

你根本不想要随机数。您想要的正是数字 0 到 N-1，以随机顺序排列。

简单地填充数组和改组应该非常快。适当的 Fisher-Yates 洗牌是 O(n)，因此在 C 甚至 Java 中，1 亿个数组应该花费不到一秒的时间，在 Python 等高级语言中稍微慢一些。

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

您永远不需要查看是否已经生成了一个数字；无论您使用哪种算法，这都会非常缓慢，尤其是在运行结束时。

如果您需要的总数略少于 N，则将数组从 0 填充到 N-1，然后尽早中止 shuffle 并获取部分结果。只有当您需要的数字数量与其范围相比非常小时，您才应该考虑生成并检查重复数据的方法。在这种情况下，鲍勃弗洛伊德的算法可能会很好。

Answer 2

作为替代方案，您可以使用适当大小的块密码。使用块密码对数字 0、1、2...进行加密，您将得到一系列不重复的随机数。确切的系列将取决于您使用的密钥。它们保证不会重复，因为块密码是可逆排列。

对于 64 位数字使用DES，对于 32 位使用Hasty Pudding（它允许大范围的块大小）或编写您自己的简单Feistel 密码。假设安全性不是一个大问题，那么自己编写是可能的。

Answer 3

为了确保它更好地创建一个算法来打乱数字，如果您使用种子，例如服务器微时间或时间戳，您可以为每毫秒有一个不同的随机字符串。

开始使用 range 函数创建数组，根据需要设置数字数量。比，你需要使用种子来使伪随机性更好。因此，您必须使用 SHUFFLE 而不是 rand，因此您将数组的范围设置为 1 到 90，设置种子，而不是使用 shuffle 对数组进行洗牌......比您以随机顺序获得所有数字（对应于种子） . 你必须改变种子才能有另一个结果。数字的顺序就是结果。如 .. 球 1 : 42 ... 球 2: 10.... 球 3: 50.... 球 1 在数组中为 0。;) 您还可以使用切片函数并创建一个 for / each 循环，增加切片因子，因此您循环

1. 切片数组 0,1 结果.. 球 1...
2. 切片数组 0.2 球 2...
3. 切片数组 0.3

这就是逻辑，我希望你理解，如果是这样..它会帮助你很多。