【经典问题】给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

简介: 【1月更文挑战第26天】【经典问题】给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

【方案一】使用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)的技术,结合哈希算法。


下面是一个基本的步骤:

  1. 分块排序: 首先,将两个文件分成适当大小的块,然后在内存中加载并对每个块进行排序。这是外部排序的第一步。
  2. 归并: 对于每个文件,创建一个指向排序后块的指针。然后,从两个文件中读取每个块中的第一个元素,将它们进行比较,并找到两个文件中相等的元素。如果找到相等的元素,就将其输出为交集元素。如果不相等,将较小的元素的文件的指针向前移动。
  3. 迭代: 重复执行归并步骤,直到两个文件的所有块都被处理。这样可以找到两个文件的交集元素。

这个方法的核心思想是在排序的基础上使用指针进行归并,以便逐块处理文件而不是一次性加载整个文件。

请注意,这里的关键在于如何在内存有限的情况下处理大文件。在实际实现中,可能需要根据实际情况进行调整,并考虑使用哈希算法来进一步优化处理过程。


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')
相关文章
|
3月前
|
存储 缓存 Java
释放C盘空间:释放Windows休眠文件和关闭虚拟内存
在 Windows 11 专业版中,可以通过以下步骤来释放休眠文件(Hibernate File),以释放磁盘空间。休眠文件是系统休眠(Hibernate)功能所需要的文件,它保存了系统的当前状态,以便在休眠状态下恢复。如果你不使用休眠功能,如果因为C盘空间不足,可以考虑释放这个文件来腾出磁盘空间。
3501 0
|
2月前
|
存储 负载均衡 算法
负载均衡案例:如何只用2GB内存统计20亿个整数中出现次数最多的整数
负载均衡案例:如何只用2GB内存统计20亿个整数中出现次数最多的整数
32 2
|
3月前
|
存储 编译器 C语言
learn_C_deep_10 extern在多文件下的理解、struct 关键字的理解与柔性数组、union 的内存级布局理解、enum 关键字的基本理解、typedef 的理解与分类、关键字总结
learn_C_deep_10 extern在多文件下的理解、struct 关键字的理解与柔性数组、union 的内存级布局理解、enum 关键字的基本理解、typedef 的理解与分类、关键字总结
|
3月前
|
移动开发 安全 图形学
如何绕过某讯手游保护系统并从内存中获取Unity3D引擎的Dll文件
如何绕过某讯手游保护系统并从内存中获取Unity3D引擎的Dll文件
28 0
|
4月前
|
存储 小程序 编译器
整数和浮点数在内存中的存储​(大小端详解)
整数和浮点数在内存中的存储​(大小端详解)
|
4月前
|
存储 编译器 C语言
数据在内存中的存储(浮点数与整数的类型转换)
在c语言操作符那一篇文章中我们讲到整数的二进制表示方法有三种,即原码、反码和补码。 它们都由符号位和数值位组成,数值位中的最高位就是符号位,符号位中0表示”正“,1表示”负“,
|
1月前
|
存储 JSON 监控
Higress Controller**不是将配置信息推送到Istio的内存存储里面的**。
【2月更文挑战第30天】Higress Controller**不是将配置信息推送到Istio的内存存储里面的**。
14 1
|
1月前
|
存储 C语言
C语言--------数据在内存中的存储
C语言--------数据在内存中的存储
26 0
|
4天前
|
存储 NoSQL Oracle
Oracle 12c的内存列存储:数据的“闪电侠”
【4月更文挑战第19天】Oracle 12c的内存列存储以超高速度革新数据处理,结合列存储与内存技术,实现快速查询与压缩。它支持向量化查询和并行处理,提升效率,但需合理配置以平衡系统资源。作为数据管理员,应善用此功能,适应业务需求和技术发展。
|
14天前
|
存储 C语言
数据在内存中的存储2
数据在内存中的存储2

热门文章

最新文章