首页 > 代码库 > 互联网_大数据
互联网_大数据
1,给定两个整数集合A和B,每个集合都包含20亿个不同整数,请给出快速计算A∩B的算法,算法可使用外存,但是要求占用内存不能超过4GB。
答:
基本思路:利用bitmap以及位运算来实现。
思考过程:整数最大为2的32次方-1;如果每位依次记录一个数,那么需要int的个数是(2的32次方-1)/32=1亿个。占用的内存大小为4byte*1亿=0.4G。不超过题目要求的4G.
因此,解决思路是:
1)申请两个[2的32次方-1]/32个int型的整数数组
2)依次扫描两个集合A和B,如果集合包含某一个整数,就将对应位置1
3)之后将两个用作标志位的两个整形数组做交运算
思考,如果是两个集合中都包含20亿个url呢,如何求出二者的交集(利用bloom过滤器)转换为一个查找操作?<具体实现?>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。