从一个非常大的范围复制随机值
我想要一个函数，它将从一组n个整数中产生k个伪随机值，从0到n-1，而不重复任何以前的结果。 k小于或等于n。 由于n大小和我需要重新洗牌的频率， O（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-state 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的下一个二次幂定义一个函数，并在此构造中使用：
long nextvalue(void) {
static long s = 0;
long x = s++;
do { x = f(x); } while (x >= n);
}
但是，这仍然有同样的问题（不太可能给出一个公平的洗牌的近似值）。
有没有更好的方法来处理这种情况？ 或者也许我只需要一个f()的很好的函数，这个函数具有很高的参数化性，并且易于设计访问n离散状态。
我想到的一件事是一个类似散列的操作，我设法通过仔细设计的映射使第一个j结果完全随机，然后j和k之间的任何结果都可以简单地外推到该模式上（尽管以可预测的方式） 。 然后可以选择j的值来寻找公平混洗和可容忍内存占用之间的折中。
首先，打折使用O（n）内存的任何东西似乎都是不合理的，然后讨论一个涉及底层数组的解决方案。 你有一个数组。 随机播放它。 如果这不起作用或速度不够快，请回过头来提问。
您只需执行一次完整的洗牌。 之后，从索引n抽取该元素，并在其之前随机定位一个元素，并增加n ，模数元素数。 例如，对于这样一个大数据集，我会使用类似这样的东西。
素数是散列的一个选项，但可能与您的想法不同。 使用两个梅森素数（ 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))
例如，对于大于大约两个八位字节的所有输入，这应该产生一些相当好的分布，对于零字节前缀来说，小的麻烦例外。 你可能想要以不同的方式对待它们。
所以...我最终做的是深入挖掘已有的方法，试图确认他们接近公平混洗的能力。
我使用一个简单的计数器，它本身保证只访问一次范围内的值，然后用一个n位块密码对其进行“加密”。 相反，我将范围调至2的幂，并应用一些1：1函数; 那么如果结果超出范围，我重复置换直到结果在范围内。
这可以保证最终完成，因为在幂的2范围内只有有限数量的超范围值，并且它们不能进入总是超范围的循环，因为这意味着某些在循环中映射来自两个不同的先前状态（一个来自范围内的集合，另一个来自超出范围的集合），这将使得该功能不是双射的。
所以我需要做的就是设计一个可调参数函数，我可以调整到任意数量的位。 像这个：
uint64_t mix(uint64_t x, uint64_t k) {
const int s0 = BITS * 4 / 5;
const int s1 = BITS / 5 + (k & 1);
const int s2 = BITS * 2 / 5;
k |= 1;
x *= k;
x ^= (x & BITMASK) >> s0;
x ^= (x << s1) & BITMASK;
x ^= (x & BITMASK) >> s2;
x += 0x9e3779b97f4a7c15;
return x & BITMASK;
}
我知道它是双射的，因为我碰巧有它的反函数：
uint64_t unmix(uint64_t x, uint64_t k) {
const int s0 = BITS * 4 / 5;
const int s1 = BITS / 5 + (k & 1);
const int s2 = BITS * 2 / 5;
k |= 1;
uint64_t kp = k * k;
while ((kp & BITMASK) > 1) {
k *= kp;
kp *= kp;
}
x -= 0x9e3779b97f4a7c15;
x ^= ((x & BITMASK) >> s2) ^ ((x & BITMASK) >> s2 * 2);
x ^= (x << s1) ^ (x << s1 * 2) ^ (x << s1 * 3) ^ (x << s1 * 4) ^ (x << s1 * 5);
x ^= (x & BITMASK) >> s0;
x *= k;
return x & BITMASK;
}
这使我可以像这样定义一个简单的参数化PRNG：
uint64_t key[ROUNDS];
uint64_t seed = 0;
uint64_t rand_no_rep(void) {
uint64_t x = seed++;
do {
for (int i = 0; i < ROUNDS; i++) x = mix(x, key[i]);
} while (x >= RANGE);
return x;
}
将seed和key初始化为随机值，你很好。
使用反函数让我确定强制rand_no_rep()产生给定输出的seed必须是什么; 使测试更容易。
到目前为止，我已经检查了常数a的情况，其后是常数b 。 对于ROUNDS==1对在正好50％的键上发生碰撞（并且每对碰撞与a和b不同的一对;它们并不全部收敛于0,1或其他）。 也就是说，对于各种k ，特定a -followed逐b情况下出现一个以上的k （这必须发生的至少一个）。 后面的值在这种情况下不会发生冲突，因此不同的键不会在不同的位置进入同一循环。 每个k都有一个独特的循环。
50％的碰撞来自于25％的不匹配，当它们被添加到列表中时（算上它自己，并计算它遇到的那个人）。 这可能听起来不好，但实际上比生日悖论逻辑暗示的要低。 随机选择，不能独特的新条目的百分比看起来在36％到37％之间收敛。 就随机性而言，“比随机更好”显然比随机更差，但这就是为什么他们被称为伪随机数的原因。
将其扩展到ROUNDS==2 ，我们要确保第二轮不会取消或仅仅重复第一轮的效果。
这很重要，因为这意味着多轮会浪费时间和记忆，并且该功能不可能在很大程度上被批准。 如果mix()包含所有的线性运算（比如说，乘法和加法，mod RANGE ），它可能会发生轻微的变化。 在这种情况下，所有的参数都可以相乘/相加在一起产生一个单一的参数，这个参数可以产生相同的效果。 这是令人失望的，因为它会将可达到的排列数量减少到只有一个参数的大小，并且如果该集合小到那么那么将需要更多的工作来确保它是好的，有代表性的集合。
因此，我们希望从两轮中看到的是一组无法在一轮中实现的结果。 证明这一点的方法之一是寻找原来的b -follows- a例的附加参数c ，我们希望看到每一个可能的c以下a和b 。
我们知道，从一个全面的测试，在50％的病例只有一个c可以遵循a和b ，因为只有一个k那地方b后a 。 我们也知道，25％的a和b对无法达到（即进入碰撞的一半而不是新的独特值所留下的差距），最后的25％出现在两个不同的k 。
我得到的结果是，给定两个键的自由选择，可以在给定的a和b之后找到大约五个八的c值。 大约四分之一的a / b对是无法到达的（由于潜在的中间映射进出重复或不可到达的情况，现在这是一个不太可预测的结果），四分之一的a ， b和c出现在两个序列中（之后分歧）。
我认为从一轮到两轮之间的差异可以推断出很多，但是我可能会错，我需要仔细检查。 进一步的测试变得更困难; 或者至少比较慢，除非我更仔细地考虑我将如何去做。
我还没有证明它可以产生的一系列排列中，它们都具有相同的可能性; 但这通常不能保证任何其他PRNG。
PRNG的速度相当慢，但它可以轻松适应SIMD。
链接地址: http://www.djcxy.com/p/37277.html