介绍一个简单的程序,用于计算无法直接加载到内存(1GB)的大文件(100GB)中最常出现的url的topn。
用法生成测试数据makedata使用1GB网址进行测试maketest使用100GB网址运行makerun算法根据hash(url)将输入文件拆分为1009个小文件。
加载每个小文件,通过dict计算url的出现次数,然后通过堆获取topn出现次数。
合并步骤2中所有出现的topn事件,并获得最终的topn并进行打印。
复杂度分析N是网址数。
NS是分割文件的数量,等于1009。
K是我们想要的结果URL的数量,等于100。
BS是缓冲区大小的大小,可能是4096或8192,请参见步骤1从输入文件读取或写入拆分文件的时间均为N/BS*T(diskio),哈希计算的时间为N*T(hash),因而时间复杂度为O(max(2*N
2022/9/25 16:57:51
14.13MB
C
1