《给40亿个不重复的unsigned int的整数》由会员分享，可在线阅读，更多相关《给40亿个不重复的unsigned int的整数（9页珍藏版）》请在金锄头文库上搜索。
1、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. 使用位图法判断整形数组是否存在重复 判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循
2、环法就不可取了。 位图法比较适合于这种情况，它的做法是按照集合中最大元素 max 创建一个长度为 max+1 的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上 1，如遇到 5 就给新数组的第六个元素置 1，这样下次再遇到 5 想置位时发现新数组的第六个元素已经是 1 了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为 2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。-D. 我的解法，看看还能不能优化了。 #include #include #define BITPERINT
3、 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(BitLi
4、st &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 intBitIndex); return 1; /清除标志位，将堆中内存的第 intIndex 位设置为 0(关) int ClrList(BitList &BL,int intIndex) int intListIndex = intIndex/BITPERCHAR; int i
5、ntBitIndex = 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 int main() BitList b
6、l; InitBitList(bl,SIZE); for(int i =0;i 5 = bx5&(1 5&(1 =20亿（这相当于折半了） ； 与要查找的数的最高位比较并接着进入相应的文件再查找 再然后把这个文件为又分成两类: 1.次最高位为 0 2.次最高位为 1 并将这两类分别写入到两个文件中，其中一个文件中数的个数 =10亿（这相当于折半了） ； 与要查找的数的次最高位比较并接着进入相应的文件再查找 . 以此类推，就可以找到了,而且时间复杂度为 O(logn) 不过有个问题是怎样读取数据？ 高手再指点指点2. 求一种快速生成随机数的算法，问题如下：从 09、a-z 中随机抽取 18 个字
7、符组成一个 18 位随机数，一共需要生成 10 亿个这样的随机数，然后把这些随机数写入文件，算法需要尽量快速，本算法需解决的两个最大的问题就是：1、10 亿数据量的规模对算法速度和文件存储方式的要求。 2、生成不重复数据的算法。需要严格的可证明的不重复算法，不能用概率论的方式/知道这个随机的要求是什么,是要完全的随机,还是可以是一个建立在某种算法上的随机序列? 如果是后者的话,需要找一个大于 10 亿的与 1018 互质的一个数 M(可以随机产生一个这样的数),然后再随机一个起始项 S, S % 1018 为第一个数,S+M % 1018 为第二个数.S + (109 - 1) * M % 1
8、018 为第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;
9、while( i=0 )s18*offset+i=(ei)-i; int main(int argc, char *argv) srand(GetTickCount();char bit90, S90;for( int i=0; i 60) for (int j = 0; j (55 - j * 5) Data14 = Data12;Data12 = CONST_OTHER_CHARS0;Data15 = Data5;Data5 = CONST_OTHER_CHARS1;Data16 = Data9;Data9 = CONST_OTHER_CHARS2;Data17 = Data7;Data7
10、 = CONST_OTHER_CHARS3;unsigned long j;WriteFile( hFile,Data,20,if (Counter = 1000000) break;CloseHandle(hFile);QueryPerformanceCounter(LARGE_INTEGER u64_pfmc_freq, timer;QueryPerformanceFrequency(timer.QuadPart = (u64_pfmc_end.QuadPart - u64_pfmc_start.QuadPart) * 1000 / u64_pfmc_freq.QuadPart;char
11、msg100;_ui64toa(timer.QuadPart,msg,10);MessageBox(GetActiveWindow(),msg,消耗时间(毫秒),MB_OK);/穷举0-9a-z0-9a-z给一个链表 m 要计算 36*36*给链表赋值的时间次 a10 对 a0-9 每个数组都随机给这个链表的 n/10 项（也可以项数不等） ，链表被复制的项删除 36*36*链表删除的时间 之类， 对 00000001-999999999 分别按位在该位数的区间内随机取值，这个数必然不重复。 要计算比 10 亿*8*n/10 多一些的次数。 这个算法应该不算慢了吧？ 知道算法想硬碰一个数的概率是(10/(36*36)的 10 次幂 安全性可能比完全随机的数要差，但我感觉在平常应该足够了吧？似乎也挺低了。 而且如果顺序保存的话查找也会省不少时间。/
