Java实现,给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

知行合一1 发布于 2016/06/15 16:44
阅读 1K+
收藏 1
Java实现,给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
加载中
1
呼啦_小呆
呼啦_小呆

方案1:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

    dizengrong:
方案2:这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下:
又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。

    然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
与要查找的数的最高位比较并接着进入相应的文件再查找

    再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1

    并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);
与要查找的数的次最高位比较并接着进入相应的文件再查找。
…….
以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。

头号大宝贝
头号大宝贝
套路少一点。翻译成白话 : 1,遍历。2,二分查找。
西红柿幽幽子
西红柿幽幽子
回复 @蓝色番薯 : 都说这么清楚了还写不出代码?
知行合一1
知行合一1
代码??
0
公孙二狗
公孙二狗
这几十亿个数可能是 0 到 1000 亿,bit map 的方式行不通
御清绝
御清绝
int 最大值 2147483647 位图法可用
0
公孙二狗
公孙二狗
可以使用全文索引的方式
0
eechen
eechen
楼主都没说这40亿个整数是存储在哪,怎么存储的.
如果是以"4,3,1,2,"的形式存储在文件num.txt,直接grep即可:
php > echo (shell_exec('grep "3," ./num.txt')) ? '存在' : '不存在';
存在
气质舞王尼古拉斯赵四
气质舞王尼古拉斯赵四
回复 @回去干活 : 看见没,就算调用shell的grep,都要用php,哈哈哈我笑死了
宿舍楼顶
宿舍楼顶
40亿个数里面含有3的数字太多了,我不敢想象
回去干活
回去干活
你就是个2货,别人问的解决思路,你来个grep.
西红柿幽幽子
西红柿幽幽子
根据我微薄的理解,数字有"12,13,14"也含有"3,"
0
银杏卡卡
银杏卡卡
不知道二叉搜索树能不能满足你的需求,或者是hash
0
张亦俊
张亦俊
扫一遍咯,还能咋地,在上边建任何索引的过程都不会比扫一遍更快吧
宿舍楼顶
宿舍楼顶
按照我浅薄的知识点,我知道有比扫一遍更快的做法
0
仪山湖
仪山湖

如果从算法层面考虑,布隆过滤器,有一定的误报率,调整的好,可以做到极低,40亿的数据也就会出现一两个误报。商数过滤器,新一代精确的过滤器,不会有错误率问题,但空间要求比前者大多了。如果数据重复率高,hash也能搞定这个问题;如果要求不高,从系统层面解决,用ElasticSearch或者solor,优化的好,可以达到亚毫秒级


0
云豹直播
云豹直播
脑洞又开了
0
回去干活
回去干活

引用来自“呼啦_小呆”的评论

方案1:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

    dizengrong:
方案2:这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下:
又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。

    然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
与要查找的数的最高位比较并接着进入相应的文件再查找

    再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1

    并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);
与要查找的数的次最高位比较并接着进入相应的文件再查找。
…….
以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。

这个方案1是可行的.

但有一个要求就是这40亿个数中每个数都要在2^64以内.

这样才好标记每个数所在的位置.判断 一个新的数时才能o(1)判断出来.

方案2无非就是一个二分法,在40亿这么大的数据中,性能是低效的,不建议.

0
b
beastxiao

1.如果内存充足,可以一次放到Set中,时间复杂O(1);不知道你尝试过没

2.int 最大值2^32 = 4294967296 减去 4000000000  = 294967296 如果内存不够可以尝试找出不在40亿内的2900多万放到Set中,反向判断。

没有专门去读这方面的资料,不行就当我随口瞎掰。。

返回顶部
顶部