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;
} |