最近讨论到一个问题:
A、B两个文本文件里面都有手机号,A文件是千万甚至上亿行,B文件是上百万行,如何高效的将A文件手机号存在于B文件中有的提取出来?

比较常见的答案:
1、将文件导入数据库,用一条SQL解决,类似select * from A where num in (select distinct num from B)
2、将B文件号码按条取出,通过类似grep脚本逐个过滤A文件

这些由于涉及数据的导入导出、数据库查询机制、文件的多次遍历因素的影响,都不是最佳方案。


要想效率到极致,主要考虑两个方面:
1、A和B文件只能遍历一次
2、查询号码是否存在的效率一定要高,且复杂度应该为常数,而不是线性甚至指数


记得很久之前,在网上看到一篇文章介绍google在GMAIL中如何解决海量垃圾邮件名单的问题,大致是初始化一个很大的文件,将邮件地址摘要化(例如MD5),使用摘要作为文件偏移量,在文件对应位置写入标识,用一个bit代表一个邮件地址;查询的话也是先计算摘要,再通过摘要直接读取文件对应文字看有否标识,这样的话就解决了每次可以快速查询邮件列表是否是黑名单,且查询复杂度为常数;如果不同的邮件地址出现了相同的摘要会出现误判(虽然这个概率很低很低),但误判的邮件地址用户发现后可以选择加入白名单,白名单的数量从理论上来说就是很少很少的,查询效率有保障。


基于这个思路,我们可以考虑使用手机号码作为偏移量,直接在文件或内存中建立一个结构;现在号段是13、14、15、18,号码最大差值是6*10^9,如果用1 bit代表一个号码,只需要6*10^9 / 1024 / 1024 / 8 = 716MB,放在内存里面也不多,比磁盘效率高百倍!再来,还可以按1x号段来建立多个标识串,比如13、14、15、18分别1个,就只需要大概477MB内存;甚至还可以细分到1XX号段。


软硬件环境:Lenovo X230,i5-3320M CPU@2.6GHz,12GB RAM,日立7200转500G缓存32M硬盘(HTS725050A7E630),64位WIN7
开发环境:Microsoft Visual Studio 2008,C++,64位编译
测试文件:A文件有3000万手机号码,380MB;B文件有150万手机号码,19MB;随机产生的,可能有少量重复
测试结果(DEBUG模式):内存消耗约750MB;遍历B文件初始化数据结构耗时2秒;遍历A文件中B文件有的号码,保存到C文件耗时42秒,大小约196K,有1万5千多个号码。


一次遍历和高效查询,确保了结果也是很高效的!

测试代码猛击这里下载

下载文件 (已下载 439 次)

黑咖啡
2013-11-11 11:48
专业、高端。
分页: 1/1 第一页 1 最后页
发表评论   请注意:本站已经启用评论审核机制,审核通过才能显示!
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
昵称 *   
网址   电邮   [注册]
               

验证码 不区分大小写