| 学裕 的个人资料土拨鼠照片日志列表 |  工具  帮助 |
|
12月12日 一个给计算机系学生面试的算法题目，很少学生能在 2min里解答一个很大的文件，存放10G个整数的数列，该数列是乱序排列。 因为文件很大，10G*4Byte = 40GB的大小。无法一次读入内存一次处理完。需要学生有一些分步骤处理的算法思考。 ======================================================================================= 2006-12-12 偶认为可以用位来判断计数，从最高位到最低位，为了方便表述我们假设为无符号整数，即0x00000000~0xFFFFFFFF依次递增，那么可以遍历所有数据，并记录最高位为0和1的个数（最高位为0的肯定是小于最高位为1的）记为N0、N1 那么根据N0和N1的大小就可以知道中位数的最高位是0还是1 假设N0>N1，那么再计算N00和N01， 如果N00>(N01+N1)，则说明中位数的最高两位是00 再计算N000和N001.。。。依次计算就能找到中位数 【优化】 为了减少遍历次数，可以通过提高比较的粒度来实现，以16位为计算粒度，例如第一次遍历计算 {N0000000000000000, 内存使用2^16*64（应该是这么算吧，计数器大小为64位）应该不大吧 然后根据这些计数就可以知道中位数的前16位了，后面的我就不用说了，再确定后16位就行了。 不知道这样做是否正确，欢迎讨论！ 一下是代码VC6可以编译通过，没有任何测试（包括逻辑的正确性），没有读文件部分 #define COUNTER_SIZE 0x10000 //16位为粒度 #define HALF_SIZE 0x500000000 //没写错的话应该是5G=10G/2 unsigned int readANum() { //这里可以用缓存提高速度 return 0; } void calHi16BitCounter(long * counter){ unsigned int num = 0; int countLooper = COUNTER_SIZE + 1; memset(counter, 0, COUNTER_SIZE*sizeof(long)); while (--countLooper) { num = readANum(); num = (num & 0xFFFF0000) >> 16; ++(counter[num]); } } void calLo16BitCounter(long * counter, unsigned int hi16Mask) { unsigned int num = 0; int countLooper = COUNTER_SIZE + 1; memset(counter, 0, COUNTER_SIZE*sizeof(long)); while (--countLooper) { num = readANum(); if (!( (num & 0xFFFF0000) ^ hi16Mask )) { num = (num & 0x0000FFFF); ++(counter[num]); } } } unsigned int findMidNum(){ long *counter = new long[COUNTER_SIZE]; long sum = 0; unsigned int midNum = 0; calHi16BitCounter(counter); //计算前16位应该是落在哪个计数器上 sum = 0; long *loopStart = counter; long *loopEnd = counter + COUNTER_SIZE; while (loopStart < loopEnd) { sum += *loopStart; ++loopStart; if (sum > HALF_SIZE) { break; } } --loopStart; //所以高16位就是loopStart指向的单元的下标 unsigned int hi16bit = (loopStart - counter)<<16; //中位数的位置在以hi16bit开头的数中的位置位 int loMidPos = (*loopStart) - (sum - HALF_SIZE); //下面开始计算以hi16bit为高16位的各个低16位出现的次数 calLo16BitCounter(counter, hi16bit); sum = 0; loopStart = counter; while (loopStart < loopEnd) { sum += *loopStart; ++loopStart; if (sum > loMidPos) { break; } } --loopStart; unsigned int lo16bit = loopStart - counter; //就是它了 midNum = hi16bit | lo16bit; delete[] counter; return midNum; } |
|
|
