求交集

给定两个整数集合 A 和 B，每个集合都包含 20 亿个不同整数，请给出快速计算 A∩B 的算法，算法可使用外存，但是要求占用内存不能超过 4GB。如果这里的整数是 32 位整数，那么每个集合用一个大小 2^32 位的 bitmap 表示，分别遍历集合算出对应 bitmap 后，直接遍历每一字节取交即可。每个 bitmap 的大小是 2^32bit / 2^3(bits per Byte) = 512MB，一共使用 1GB 内存。构造 bitmap 的时候，除去 bitmap 还有 3GB 可以使用，一共可以存储 3 _ 2^30 / 4 = 3 _ 2 ^28 = 8 亿个整数。那每个集合要按每 8 亿个切分到外存中，分成 3 个部分。这样构造的时候每个集合读取 3 次外存，一共读取 6 次。然后如果结果交集很大而且要得到具体整数，也要对结果做切分，最多存储 3 次外存。