更快的IP库查找方法以及AWK中的二分查找

   最近在工作中遇到一个需要将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：也许还有别的算法更能提高速度，在这里就不再一一累述了。

   不过这个问题改变了我认为在低级语言中不适合使用算法的观点。