r********9
发帖数: 1116 | 1 测试一个产生随机数的函数
该随机函数可能会出现这样的结果
a1 a2 ... an a1 a2 ...
其中n可能为数十百万级别
请问如何测试出这种情况？ |
f*******t
发帖数: 7549 | 2 数十百万级别大概是几十几百M空间，能存在内存里
用个list存结果好了，如果不等于第一个值就加在后边，如果函数值与第一个相等就依
次往后比 |
p*****2
发帖数: 21240 | |
s*******1
发帖数: 3820 | 4 没看明白题目什么意思，ms提供了一个函数叫你测试？为什么随机数会在an以后重复？
【在 r********9 的大作中提到】
: 测试一个产生随机数的函数
: 该随机函数可能会出现这样的结果
: a1 a2 ... an a1 a2 ...
: 其中n可能为数十百万级别
: 请问如何测试出这种情况？
|
p*****2
发帖数: 21240 | 5 说明这个RNG有问题呀。
【在 s*******1 的大作中提到】
: 没看明白题目什么意思，ms提供了一个函数叫你测试？为什么随机数会在an以后重复？
|
e***l
发帖数: 710 | 6 所有的RNG都是伪随机，如果下一个随机数只依赖于上一个的话，一个重复的就会导致
后面的都重复，所以我猜检查到一个重复的就行了？ |
r********9
发帖数: 1116 | 7 这个恐怕不行吧， 你如何保证取到的两个段是位置对齐的？
【在 p*****2 的大作中提到】
: 一段一段的去hash。
|
W*******2
发帖数: 1460 | |
s******c
发帖数: 1920 | |
p*****2
发帖数: 21240 | 10 可以。
每次碰到a1的时候比hash，如果一样就一直比下去。不一样就继续hash。
【在 r********9 的大作中提到】
: 这个恐怕不行吧， 你如何保证取到的两个段是位置对齐的？
|
p*****2
发帖数: 21240 | 11 不行。
RNG依赖于seed。
【在 e***l 的大作中提到】
: 所有的RNG都是伪随机，如果下一个随机数只依赖于上一个的话，一个重复的就会导致
: 后面的都重复，所以我猜检查到一个重复的就行了？
|
s*******f
发帖数: 1114 | 12 static const int MAX_LEN = 10000000;//max size, if we cannot find
deplication within MAX_LEN, the random function is good.
//return where it begin duplicate
int TestRandomFun(int (*f)()){
static const int INIT_LEN = 100000;
static const int SUBARR_LEN = 10; //find 10-len substr first then
keep comparing,
static const int DUP_THRESHHOD = 1000; //if it keep equalling to
1000, we say then random function produce duplications.
vector v(INIT_LEN);
int c = 0;
while (v.size() < MAX_LEN){
for (int i = 0; i < INIT_LEN; ++i){
v.push_back((*f)());
}
vector::iterator search_start;
if (0 == c){
search_start = v.begin() + SUBARR_LEN;
}else{
search_start = v.begin() + INIT_LEN * c -
SUBARR_LEN;
}
++c;
vector::iterator it = search(search_start, v.end(),
v.begin(), v.begin() + SUBARR_LEN);
while (it != v.end()){
vector::iterator jt = v.begin() + SUBARR_LEN;
vector::iterator kt = it + SUBARR_LEN;
if (v.end() - kt < DUP_THRESHHOD){
for (int i = 0; i < DUP_THRESHHOD; ++i){
v.push_back((*f)());
}
}
int count = 0;
while (jt != it && kt != v.end()){
if (*jt != *kt){
break;
}
++jt;
++kt;
if (++count >= DUP_THRESHHOD){
return (it - v.begin());
}
}
if (jt == it){
return (it - v.begin());
}
it = search(it + 1, v.end(), v.begin(), v.begin() +
SUBARR_LEN);
}
}
return 0;
} |
