【方案一】使用Hash函数 + 分文件的方式
使用hash函数将第一个文件的所有整数映射到1000个文件中，每个文件有1000万个整数，大约40M内存， 内存可以放下，把1000个文件记为 a1,a2,a3.....a1000，用同样的hash函数映射第二个文件到1000个文件中，这1000个文件记为b1,b2,b3......b1000，由于使用的是相同的hash函数，所以两个文件中一样的数字会被分配到文件下标一致的文件中，分别对a1和b1求交集，a2和b2求交集，ai和bi求交集，最后将结果汇总，即为两个文件的交集。
【方案二】BitMap
桶分+组内bitmap。如果这里的整数是32bit的话，直接使用bitmap的方法就能实现了。所有整数共2^32种可能，每个数用2bit来表示，“00”表示两个文件均没出现，“10”表示文件1出现过，“01”表示文件2出现过，“11”表示两个文件均出现过，共需(2^32)*2/8=1GB内存，遍历两个文件中的所有整数，然后寻找bitmap中“11”对应的整数即是两个文件的交集，这样即可线性时间复杂度完成。
使用外部排序（External Sort）和归并（Merge）的技术，结合哈希算法。
下面是一个基本的步骤：
- 分块排序： 首先，将两个文件分成适当大小的块，然后在内存中加载并对每个块进行排序。这是外部排序的第一步。
- 归并： 对于每个文件，创建一个指向排序后块的指针。然后，从两个文件中读取每个块中的第一个元素，将它们进行比较，并找到两个文件中相等的元素。如果找到相等的元素，就将其输出为交集元素。如果不相等，将较小的元素的文件的指针向前移动。
- 迭代： 重复执行归并步骤，直到两个文件的所有块都被处理。这样可以找到两个文件的交集元素。
这个方法的核心思想是在排序的基础上使用指针进行归并，以便逐块处理文件而不是一次性加载整个文件。
请注意，这里的关键在于如何在内存有限的情况下处理大文件。在实际实现中，可能需要根据实际情况进行调整，并考虑使用哈希算法来进一步优化处理过程。
def find_intersection(file1, file2, output_file): block_size =1000000# 块大小，根据实际情况调整 buffer_size =100000# 缓冲区大小，根据实际情况调整 with open(file1, 'r') as f1, open(file2, 'r') as f2, open(output_file, 'w') as output: while True: block1 = read_and_sort_block(f1, block_size, buffer_size) block2 = read_and_sort_block(f2, block_size, buffer_size) if not block1 or not block2: break # 文件已处理完毕 intersection = merge_blocks(block1, block2) write_intersection(output, intersection) def read_and_sort_block(file, block_size, buffer_size): block = [] buffer = [] for i in range(block_size): line = file.readline() if not line: break # 文件已处理完毕 buffer.append(int(line)) if i % buffer_size ==0: block += sorted(buffer) buffer = [] if buffer: block += sorted(buffer) return block def merge_blocks(block1, block2): intersection = [] i, j =0, 0while i < len(block1) and j < len(block2): if block1[i] == block2[j]: intersection.append(block1[i]) i +=1 j +=1elif block1[i] < block2[j]: i +=1else: j +=1 return intersection def write_intersection(output, intersection): for num in intersection: output.write(str(num) +'\n')
