看到不重复,海量数据!!!!bit排序...
1个int型可以表示32个数,也就是4byte就可以表示32个数....
40*(10^8)/32 = 1.25*(10^8)个int型 = 5*(10^8)byte/(10^6) = 500M，也就是说500M的内存就可以搞定这40亿个不重复的数了...我不停的重复时希望不会误导大家,最近CU总是出现些低级的回复...居然默认网关是MASK都出来了,汗!!! route -n好了说远了.
bit排序我那个排序大全里就有,大致意思就是
A[i>>5] |= 1<<(i&0x1F)
A[0] = 1;
A[1>>5] = 10;
A[2>>5] = 100;
...
A[31>>5] = 1(31个0)
发现这32个数都是A[0]!!!!
判断一个数是否出现就是 (A[i>>5] & (1<<(i&0x1F)))是否不为0就可以了....
这样的好处就是只用遍历一遍,可以求出任何数是否存在,其实现在这40亿个数也都排好序了,这是强大的...
唯一就是还是内存也有点恐怖!!!!
当然这题还有个解法,属于我这种hash狂热份子的,我最近只要海量,字符串就自然的想起hash...先对要判断是否存在的N个数做hash,然后遍历40亿个数看是否存在于hash中...这个的缺点是每次改变要查询的数据时,要重新做hash,也要重新遍历40亿个数,但是内存占用少,只用N个数的内存...这属于投机取巧^_^
阅读(1189) | 评论(0) | 转发(0) |
