给两个文件，分别有100亿个整数，我们只有1G内存，如何找到

[问答题]

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集

yuri

保险的方法应该是使用：桶分+组内bitmap。如果这里的整数是32bit的话，直接使用bitmap的方法就能实现了。所有整数共2^32种可能，每个数用2bit来表示，“00”表示两个文件均没出现，“10”表示文件1出现过，“01”表示文件2出现过，“11”表示两个文件均出现过，共需(2^32)*2/8=1GB内存，遍历两个文件中的所有整数，然后寻找bitmap中“11”对应的整数即是两个文件的交集，这样即可线性时间复杂度完成。

发表于 2015-08-30 21:57:22 回复(0)

一辰

1. 其实这个问题考的知识点是分治法（Divide and Conquer），具体做法楼上通过hash切割文件的答案已经给出来了

2. 使用bitmap的从内存占用方面感觉不太合适，使用分治法的算法内存占用少，大不了我多创建几个进程同时跑，从性能和内存综合来讲还是最优的

发表于 2018-07-29 07:51:33 回复(1)

江山如画君

使用hash函数将第一个文件的所有整数映射到1000个文件中，每个文件有1000万个整数，大约40M内存，

内存可以放下，把1000个文件记为 a1,a2,a3.....a1000,用同样的hash函数映射第二个文件到1000个文件中，这1000个文件记为b1,b2,b3......b1000，由于使用的是相同的hash函数，所以两个文件中一样的数字会被分配到文件下标一致的文件中，分别对a1和b1求交集，a2和b2求交集，ai和bi求交集，最后将结果汇总，即为两个文件的交集

发表于 2015-05-30 12:49:04 回复(3)