更快的IP库查找方法以及AWK中的二分查找
浏览:5242次 出处信息
最近在工作中遇到一个需要将IP地址定位国家的问题,中间遇到了一些问题,希望记录下来被需要的人看到。
问题如下:
1.已有一个IP库文件,文件名ip,它的内容大致如下:
16909312 16909567 China 16909568 16909823 China 16909824 16910335 China 16910336 16910591 China 16910592 16910847 China 16910848 16911359 China 16911360 16912383 China 16912384 16916479 China 16916480 16924671 China 16924672 16941055 China 16941056 16973823 Thailand 16973824 17039359 China 17039360 17039615 Australia</pre> 40370176 40894463 Denmark 40894464 41418751 Italy 41418752 41943039 United Kingdom 41943040 42205183 Denmark 42205184 42467327 Kazakhstan 42467328 42991615 Spain 42991616 43253759 Iran (ISLAMIC Republic Of) 43253760 43515903 Norway 43515904 43778047 Spain 43778048 44040191 Italy 44040192 45088767 Germany 45088768 46137343 Iran (ISLAMIC Republic Of)
这个IP库大概有12.5万条,第一列为IP段起始,第二列为IP段结束,第三列为对应的国家。
你可以在以下地址下载此IP库 http://dev.maxmind.com/geoip/geolite
2.又有一个注册用户的id和他们的注册ip的对照文件,文件名users,它的内容大致如下:
1 465404162 2 3721192783 3 2937196809 4 1020397490 5 1971850434 6 1857609753 7 3397328438 8 3549172330 9 2005600694 10 1885381301 11 1885524157 12 1971855024 13 3549172339 14 3402379245 15 606131729 16 3719536933 17 1971847530 18 1971848520 19 1864696671
这个文件大概有4万行,其中第一列为uid,第二列为此uid的IP地址。
3.现在问题是,需要将注册用户按照国家来分类统计,它的结果应该是这样:
China 100 Malaysia 70 Italy 30 Spain 12
4.要解决这个问题,我们首先用简单最容易想到的方法来实现,在IP库中遍历每一个用户的IP地址:
awk 'NR==FNR{a[$2]=$1;next} {for(ip in a) {if(int(ip)>=$1 && int(ip)<=$2) {print a[ip]"\t"$3}}}' users ip
注意:在这里我们先不考虑users中IP重复的问题。
使用以上方法全部遍历一次,大概耗时40分钟左右。
5.虽然问题可以解决,但是花费时间太长。于是我尝试使用二分查找算法来完成这个问题,以下为AWK中的二分查找:
awk -F "\t" ' NR==FNR{ip[k++]=$0;next} { start=0; end=k-1; while(start<=end) { middle=int((start+end)/2); split(ip[middle], a, "\t"); if($2<a[1]) end=middle-1; else if($2>a[2]) start=middle+1; else {print $1","a[3];break;}; } }' ip users
使用二分查找后,users中的IP全部检索一次仅需要不到2分钟,整整加快了20倍。
至此问题解决。
PS:也许还有别的算法更能提高速度,在这里就不再一一累述了。
不过这个问题改变了我认为在低级语言中不适合使用算法的观点。
建议继续学习:
- Linux命令行里的“瑞士军刀” (阅读:10145)
- AWK 简明教程 (阅读:8134)
- awk命令,实现文件的合并与拆分 (阅读:6583)
- 你是那10%可以实现二分查找算法的程序员吗? (阅读:6508)
- AWK介绍 (阅读:5457)
- awk 实例之二维数组 (阅读:4984)
- 操作大文本,awk vs vim (阅读:3758)
- SED命令行脚本快速参考,AWK命令行脚本快速参考,perl命令行脚本快速参考 (阅读:3769)
- 从shell中向awk传递变量实例 (阅读:3599)
- bash shell - sed及awk文本捕获及替换 (阅读:3431)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
文章信息
- 作者:zorro 来源: 数据挖掘学习记录
- 标签: AWK 二分查找
- 发布时间:2013-05-01 22:59:07
建议继续学习
近3天十大热文
- [53] IOS安全–浅谈关于IOS加固的几种方法
- [52] 如何拿下简短的域名
- [51] 图书馆的世界纪录
- [50] android 开发入门
- [50] Oracle MTS模式下 进程地址与会话信
- [49] Go Reflect 性能
- [46] 【社会化设计】自我(self)部分――欢迎区
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [36] 程序员技术练级攻略
- [29] 视觉调整-设计师 vs. 逻辑