c++ - 随机生成 n 个唯一数

Question

如果我想生成 0 到 999 的 1000 个唯一的数字，我该怎么办？
我的第一次尝试是创建一个数组 {0, 1, 2, ..., 999} 并使用它std::random_shuffle来打乱它们。但是，由于我必须在一个长循环中生成数字，比如说 O(10^7)，这种方法会占用运行时间。
有没有更好的方法来解决这个问题？

Answer 1

如果您存储 1000 个数字的数组，并std::random_shuffle在每次需要时在循环中调用，这实际上是您能够以您需要的方式生成 1000 个随机唯一数字的最快方式。您不需要每次都重新创建数组。

你的循环是否有 O(10^7) 次迭代并不重要，因为如果你要按照你所说的那样使用这 1000 个整数，那么它已经需要 O(n) 操作来遍历每个这些数字在您使用时。std::random_shuffle时间复杂度也是 O(n) 所以它不会让你慢得多。

Answer 2

1. 将您的号码容器保存到另一个容器 C2。

2. 生成元素的索引以在 C1 中选择随机元素。每次生成索引时，将其从容器 C1 中删除。这样，下次您将获得唯一编号。

3. 一旦 C1 变空，用 C2 重新填充 C1 并转到步骤 2。

Answer 3

您要求实现shuffle（这是对您要求的准确描述），这将比标准库中的实现更好。这是一个很长的镜头。

但我会试试的。我会说：准备一个包含 10^7 个这样排列的文件，然后从中读取。确保以某种方式预取，否则它肯定会更慢。如果您在不同的线程中预取，它实际上可能会更快。但这只是一个疯狂的猜测。

当我想到它时，如果您可以运行多线程，则可以使用简单的生产者-消费者解决方案。一个线程放置排列，另一个线程只是读取它们。