快速生成10亿个不重复的18位随机数的算法
求一种快速生成随机数的算法，问题如下：从0~9、a-z中随机抽取18个字符组成一个18位随机数，一共需要生成10亿个这样的随机数，然后把这些随机数写入文件，算法需要尽量快速，本算法需解决的两个最大的问题就是：1、10亿数据量的规模对算法速度和文件存储方式的要求。2、生成不重复数据的算法。需要严格的可证明的不重复算法，不能用概率论的方式
[解决办法]
不知道这个随机的要求是什么,是要完全的随机,还是可以是一个建立在某种算法上的随机序列?
如果是后者的话,需要找一个大于10亿的与10^18互质的一个数M(可以随机产生一个这样的数),然后再随机一个起始项S,
S % 10^18为第一个数,S+M % 10^18为第二个数......S + (10^9 - 1) * M % 10^18 为第10亿个数
[解决办法]
p(x)=x^89+x^6+x^5+x^3+1.
[解决办法]
一个实现,效率不是很好,楼主自己优化一下吧.
- C/C++ code
#include <cstdlib> #include <iostream> #include <windows.h> using namespace std;char map2char[]={'1','2','3','4','5','6','7','8','b','c','d','e','f','g','h','i', 'j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y'};void getbit( unsigned e, char *s, int offset ){ int i=17; while( i>=0 ){ s[18*offset+i]=((e>>i)&1); --i; } }int main(int argc, char *argv[]) { srand(GetTickCount()); char bit[90], S[90]; for( int i=0; i<sizeof(bit); ++i ) bit[i]=0, S[i]=0; unsigned x, T; for( int k=0; k<5; ++k ){ do x=rand(); while( x==0 ); getbit( x, S, k); getbit( x, bit, k ); } unsigned head=89; unsigned j=0, time=GetTickCount(), Max=1000000; do{ ++j; T=(bit[head]&1)^(bit[(head-83)%90]&1)^(bit[(head-84)%90]&1)^(bit[(head-86)%90]&1)^(bit[(head-89)%90]&1); bit[head]=T; head=(head+1)%90; for( int index=0; index<18; ++index ){ int num=0; for( int j=0; j<5; ++j ) num+=(bit[(head+5*index+j)%90]==0)? 0 : (1<<j); cout<<map2char[num]; } cout<<endl; }while( j<Max ); cout<<"time: "<<GetTickCount()-time<<" ms!\n"; system("PAUSE"); return EXIT_SUCCESS; }
[解决办法]
卖点卡之类的需要类似的算法
不过10亿的量真是吓人啊，似乎也就是中移动了
你去找一个比较强的加密算法
用它来加密1到10亿，这个是肯定不会重复的，重复的话就无法解密了
把加密的结果转化为0-9,a-z的串，随便找种一一对应的映射就行了
转化之后的串不够18位，后面的你随便用一种随机算法补齐就可以了
[解决办法]
10亿个18位，文件大概要2个G。而且10亿个不重复。确实困难。
我只是用简单的随机函数产生18位，等等产生25万个的时候文件大小就有近5M了。10亿太难了。也没检查是否重复。10亿不好做。
如果随机产生 10亿/pow(36, 18),重复的概率极小，如果检查是否重复，代价太大了吧。可能有好的算法，我不懂。
这是产生的一些样例：
- C/C++ code
5zy4hsuiykhtpfpn7q30roe94yxwqnbibix4zj7ubf2lxkl7tsnwaxl7blpm4be60a4e44e9exyeuxlk9n0a0wywzso32jtaquxh9bvuou92tuhhws6xtlloa6hozz3mzsqylgya3n7xdbxf5hp2tcey2yx80b6zmnchk3j92evke4o9ofc41ihju2o8jzkpojn9itpahkzr8tvkarwsctder1xfv3azw0uuow2h5q1do6ygqnat2zfs4r2683o2aqbtpicctuq3dbt0shzk8qfd509xr7y1qpgyxx48tuhhw9s057epp8doa9b374j1ddupdbl4qd8azu61w7qntj91c8wtt0pauad4cq11r2dqkncf98iqtlaxae8ev5ubephmqcuq0zpqz1u5pez4kh6khvevzxvg7ktx709h9zwye2wgz8leeajhjkwndmwevo