c++ - 从非常大的范围返回非重复的随机值

Question

我想要一个函数，它可以从一组 n 个整数(0 到 n-1)中产生 k 个伪随机值，而不重复任何先前的结果。 k 小于或等于 n。 O(n) 内存是 Not Acceptable 因为 n 的大小很大以及我需要重新洗牌的频率。

这些是我到目前为止考虑过的方法:

数组: 通常，如果我想要无重复的随机值，我会打乱一个数组，但那是 O(n) 内存。 n 可能太大而无法工作。

long nextvalue(void) {
  static long array[4000000000];
  static int s = 0;
  if (s == 0) {
    for (int i = 0; i < 4000000000; i++) array[i] = i;
    shuffle(array, 4000000000);
  }
  return array[s++];
}

n 态 PRNG: 有多种随机数生成器可以设计为具有 n 的周期。并访问n那个时期的独特状态。最简单的例子是:

long nextvalue(void) {
static long s = 0;
static const long i = 1009; // assumed co-prime to n
  s = (s + i) % n;
  return s;
}

问题在于，为给定的 n 动态设计一个好的 PRNG 并不一定容易。 ，并且如果 PRNG 没有很多可变参数(更难设计)，它不太可能近似于公平洗牌。但也许有一个我不知道的好东西。

m 位散列: 如果集合的大小是 2 的幂，则可以设计出完美的哈希函数 f()它执行从范围内的任何值到范围内的某个其他值的 1:1 映射，其中每个输入都会产生唯一的输出。使用这个函数我可以简单地维护一个静态计数器 s ，并将生成器实现为:

long nextvalue(void) {
  static long s = 0;
  return f(s++);
}

这并不理想，因为结果的顺序由 f() 决定，而不是随机值，因此它会遇到与上述所有相同的问题。

NPOT 哈希: 原则上我可以使用与上面相同的设计原则来定义 f() 的版本。它可以在与所需范围兼容的任意基础上工作，甚至可以在复合基础上工作；但这可能很困难，而且我很可能会弄错。相反，可以为大于或等于 n 的下一个 2 的幂定义一个函数。 , 并在这个结构中使用:

long nextvalue(void) {
  static long s = 0;
  long x = s++;
  do { x = f(x); } while (x >= n);
}

但是这仍然有同样的问题(不太可能给出公平洗牌的良好近似值)。

有没有更好的方法来处理这种情况？或者，也许我只需要一个很好的函数 f()高度可参数化且易于设计以准确访问 n离散状态。

我正在考虑的一件事是类似散列的操作，我设法在其中获得第一个 j通过精心设计的映射，结果完全随机，然后是 j 之间的任何结果和 k将简单地推断该模式(尽管以可预测的方式)。值j然后可以选择在公平洗牌和可容忍的内存占用之间找到折衷。

Answer 1

首先，打折任何使用 O(n) 内存然后讨论引用底层数组的解决方案似乎是不合理的。你有一个数组。洗牌。如果这不起作用或速度不够快，请向我们提出相关问题。

你只需要执行一次完整的洗牌。之后，从索引 n 中抽取，将该元素与随机位于它之前的元素交换并增加 n，模元素计数。例如，对于如此大的数据集，我会使用 something like this .

质数是哈希的一个选项，但可能与您的想法不同。使用两个 Mersenne 素数(low 和 high，也许是 0xefff 和 0xefffffff)你应该能够想出一种更通用的哈希算法。

size_t hash(unsigned char *value, size_t value_size, size_t low, size_t high) {
    size_t x = 0;
    while (value_size--) {
        x += *value++;
        x *= low;
    }
    return x % high;
}
#define hash(value, value_size, low, high) (hash((void *) value, value_size, low, high))

例如，对于大于大约两个八位字节的所有输入，这应该会产生相当分布的东西，零字节前缀的小麻烦异常(exception)。您可能希望以不同的方式对待它们。