给40亿个不重复的unsigned int的整数.doc

1. 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中A. 申请512M的内存 一个bit位代表一个unsigned int值 读入40亿个数，设置相应的bit位 读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在B. 1.unsigned int 32位有40亿个的，这是事实 2.确实是用位图做的，512M内存-C. 使用位图法判断整形数组是否存在重复 判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。 位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。-D. 我的解法，看看还能不能优化了。 #include #include #define BITPERINT 32 /每个int型字节数 #define BITPERCHAR 8 /每个char型字节数 #define N 4000000000 /40亿个数 #define SIZE N/BITPERINT #define MASK 0x80 /1000000 掩码 /犹豫40亿个数会超出栈空间，所以在堆上分配动态数组。 typedef struct BitList unsigned char *base; int intLength; BitList,*P_BitList; /初始化线性顺序表，总位数为intSize*BITPERCHAR int InitBitList(BitList &BL ,int intSize) BL.base = (unsigned char*)malloc(sizeof(int)*intSize); if(BL.base = NULL) printf(n Out of memomry !n); exit(0); /内存初始化为 0 for(int i = 0;i intSize; i+) BL.basei=0; BL.intLength = intSize; return 1; /销毁位图线性表 void DestroyBitList(BitList &BL) BL.intLength = 0; /for(int i = 0 ;i intBitIndex); return 1; /清除标志位，将堆中内存的第intIndex位设置为0(关) int ClrList(BitList &BL,int intIndex) int intListIndex = intIndex/BITPERCHAR; int intBitIndex = intIndex%BITPERCHAR; BL.baseintListIndex = BL.baseintListIndex(MASKintBitIndex); return 1; /获取堆中内存的第intIndex位的值（0或1） int GetList(BitList &BL,int intIndex) int intListIndex = intIndex/BITPERCHAR; int intBitIndex = intIndex%BITPERCHAR; return ( BL.baseintListIndex&(MASKintBitIndex) )(7-intBitIndex); int main() BitList bl; InitBitList(bl,SIZE); for(int i =0;i 5 = bx5&(1 5&(1 (y&0x0000001f)） y在那40亿个数据中; else y不在那40亿个数据中; 这个问题在编程珠玑里有很好的描述，大家可以参考下面的思路，探讨一下： 又因为232为40亿多，所以给定一个数可能在，也可能不在其中； 这里我们把40亿个数中的每一个用32位的二进制来表示 假设这40亿个数开始放在一个文件中 然后将这40亿个数分成两类: 1.最高位为0 2.最高位为1 并将这两类分别写入到两个文件中，其中一个文件中数的个数 =20亿（这相当于折半了）； 与要查找的数的最高位比较并接着进入相应的文件再查找 再然后把这个文件为又分成两类: 1.次最高位为0 2.次最高位为1 并将这两类分别写入到两个文件中，其中一个文件中数的个数 =10亿（这相当于折半了）； 与要查找的数的次最高位比较并接着进入相应的文件再查找 . 以此类推，就可以找到了,而且时间复杂度为O(logn) 不过有个问题是怎样读取数据？ 高手再指点指点2. 求一种快速生成随机数的算法，问题如下：从09、a-z中随机抽取18个字符组成一个18位随机数，一共需要生成10亿个这样的随机数，然后把这些随机数写入文件，算法需要尽量快速，本算法需解决的两个最大的问题就是：1、10亿数据量的规模对算法速度和文件存储方式的要求。2、生成不重复数据的算法。需要严格的可证明的不重复算法，不能用概率论的方式/知道这个随机的要求是什么,是要完全的随机,还是可以是一个建立在某种算法上的随机序列? 如果是后者的话,需要找一个大于10亿的与1018互质的一个数M(可以随机产生一个这样的数),然后再随机一个起始项S, S % 1018为第一个数,S+M % 1018为第二个数.S + (109 - 1) * M % 1018 为第10亿个数/我觉得还是用18和by比较快一些,毕竟是32个字符,用二进制比较好表示,速度也更有保证. 可以利用本原多项式来生成. 考虑模2的89阶本原多项式即可. p(x)=x89+x6+x5+x3+1.#include #include #include 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 ) s18*offset+i=(ei)&1); -i; int main(int argc, char *argv) srand(GetTickCount(); char bit90, S90; for( int i=0; isizeof(bit); +i ) biti=0, Si=0; unsigned x, T; for( int k=0; k5; +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=(bithead&1)(bit(head-83)%90&1)(bit(head-84)%90&1)(bit(head-86)%90&1)(bit(head-89)%90&1); bithead=T; head=(head+1)%90; for( int index=0; index18; +index ) int num=0; for( int j=0; j5; +j ) num+=(bit(head+5*index+j)%90=0)? 0 : (1j); coutmap2charnum; coutendl; while( jMax ); couttime: GetTickCount()-time ms!n; system(PAUSE); return EXIT_SUCCESS; /卖点卡之类的需要类似的算法 不过10亿的量真是吓人啊，似乎也就是中移动了 你去找一个比较强的加密算法 用它来加密1到10亿，这个是肯定不会重复的，重复的话就无法解密了 把加密的结果转化为0-9,a-z的串，随便找种一一对应的映射就行了 转化之后的串不够18位，后面的你随便用一种随机算法补齐就可以了如果你的应用跟钱相关一定要小心些 加密的密钥一定不要泄露，加密算法要用强加密算法，免得有人分析得出了你的密钥解出了你的前N位 目前常用的分组加密算法明文密文都是8字节的 8字节的密文转化为0-9,a-z的串 256*8=37*x x=12.28 就是说你用13位就可以完全表示8字节密文，后面还有5位可以自由发挥 算法的安全性还是有保障的/1) 生成一个数组a，大小为10亿，以110亿填充 2）random shuffle一下a 3)对数组中的每个数字，计算其md5码，存在b 4)对b中的每个数字，取前18位即可/用一个简单的方法： 1.开一个十亿的空间，把1-10亿个数据放在里面去。 2.以当前时间为基数，开个随机计时器，随机调换这空间里的数据位置 3.重复第二步骤上亿次。 4.依次读出空间里的数据。 此方法保证不重复，也能完全随机，不过效率和占用资源都比较大/推荐一种办法: 36个字符提取32个作为有序数,另外4个随机补足,打乱字符排列顺序,使用累加器做64位数的累加,总共可以产生18446744073709551615个完全不同的值,把每一个值转换为32进制(作为有序数的32个字符表示),64bit=5bit * 12 + 4bit,也就是可以产生一个的不重复串13位,然后再用剩余的个字符,随机顺序,外加32个字符当中产生一个随机字符进行补足,就凑足了18位,由于总共有一千八百多亿个亿的值,所以可以通过随机数来决定是否需要.并且还可以人为分段.从整体来讲,使用有序数来保证是最为快速和有效的./不理解题目，就不可能给出正确答案。我来重新阐述一下题目： 1.这些18位字符串要包含09,az,一共36个字符。有些同学给的结果是纯数字，不符合要求。 2.题目要求产生18位的字符串。这样的18位字符串空间有3618个元素。 3.所谓的“随机”，应该理解为，在这3618个18位字符串构成的空间中，随机选取其中10亿个元素构成子集， 这个子集中不能重复有重复元素。 4.有很多笨办法可以找出这样的子集，但题目似乎想要的是一种算法，这样就可以通过运行算法得到结果，而 不必存储10亿个元素。或者在相同输入下，重复运行算法可以得到同样的子集。/设计思路： 09，az总共可以排列出3618个结果，即10314424798490535546171949056个结果。 要求取其中1000000000个结果，且随机不重复。 将总结果集看做一张表，每个结果对应一个序号，在这个结果集中取对应序号的值。 方案1: 定义一个起始值X，取从X开始的值，然后下一个取值直接用系统当前时间为间隔，以此类推。 方案2： 定义一个起始值X，取从X开始的值，下一个取110314424798490535546之间的一个随机数做间隔，以此类推。 方案3： 定义一个起始值X，取从X开始的值，下一个取110314424798490535546之间的一个随机数做间隔，设置变量Y，Y值等于（10314424798490535546 - 上次间隔随机数 + 本次随机间隔数），以此类推。 方案1速度快，不过分布平均。 方案2速度适中，且在一个已知的值基础上，就能确定增长110314424798490535546内，一定存在下一个值。 方案3就是慢了点。/char CONST_BASE_CHARS = l,2,3,4,5,6,7,8,9, a,b,c,d,e,f,g,h,j, k,m,n,p,q,r,s,t,u, v,w,x,y,z; char CONST_OTHER_CHARS = 0,1,i,o; char Data21; LARGE_INTEGER u64_pfmc_start,u64_pfmc_end; QueryPerformanceCounter(&u64_pfmc_start); Data18 = r; Data19 = n; Data20 = 0; HANDLE hFile = CreateFile(c:Data.dat,GENERIC_WRITE,0,NULL,CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL /*| FILE_FLAG_OVERLAPPED */,NULL); if (hFile = INVALID_HANDLE_VALUE) MessageBox(GetActiveWindow(),创建文件失败!,MB_OK|MB_ICONERROR); return; int Counter = 0; for (_int64 i = 6854775807; i 60) & 0x0f; for (int j = 0; j (55 - j * 5) & 0x1f; Data14 = Data12; Data12 = CONST_OTHER_CHARS0; Data15 = Data5; Data5 = CONST_OTHER_CHARS1; Data16 = Data9; Data9 = CONST_OTHER_CHARS2; Data17 = Data7; Data7 = CONST_OTHER_CHARS3; unsigned long j; WriteFile( hFile,Data,20,&j,NULL); if (Co