二分法查找IP國家代碼

pymain

               
               
               
                #!/usr/bin/env python
import os
import struct
import socket

def ipToInt(ip):
    return struct.unpack("!I",socket.inet_aton(ip))[0]
def loadRegion():
    # apnic|CN|ipv4|58.16.0.0|65536|20050125|allocated
    regionList = []
    regionFile = 'regionmap.txt'
    if not os.path.isfile(regionFile): return []
    for line in open(regionFile,'r').readlines():
        line = line.strip()
        if line.find('ipv4')>-1:
            try:
                l = line.split('|')
                country = l[1]
                if country == 'ZZ': continue
                data = {}
                ipaddr = l[3]
                offset = l[4]
                ipInt = ipToInt(ipaddr)
                data[ipInt] = (offset,country)
                regionList.append(data)
            except Exception,e:
                pass
    return regionList
def binSearch(regionList, regionListLen, ipInt):
    try:
        low = 0
        high = regionListLen
        
        while low = high:
            mid = (low + high)/2
            if regionList[mid].keys()[0] == ipInt:
                return mid
         
            if regionList[mid].keys()[0] > ipInt and ipInt > regionList[mid-1].keys()[0]:
                return mid - 1
            if regionList[mid].keys()[0] > ipInt:
                high = mid - 1
            else:
                low = mid + 1
        return ''
    except Exception,e:
        return ''
def findCountry(regionList, regionListLen, ipaddr):
    try:
        ipaddr = ipToInt(ipaddr)
        rindex = binSearch(regionList, regionListLen, ipaddr)
        offset,region = regionList[rindex].items()[0][1]
        if (int(regionList[rindex].keys()[0]) + int(offset)) >= ipaddr:
            return region
        else:
            return '**'
    except:
        return '**'   
if __name__=='__main__':
    regionList = loadRegion()
    regionList.sort()
    regionListLen = len(regionList) - 1
    print findCountry(regionList, regionListLen, '127.0.0.1')
    print findCountry(regionList, regionListLen, '130.23.44.23')
    print findCountry(regionList, regionListLen, '218.12.250.3')
$python ipcountry.py
**
US
CN
效率一般般，查找100萬條記錄用了1分鐘左右時間。


本文來自ChinaUnix博客，如果查看原文請點：http://blog.chinaunix.net/u3/105486/showart_2093073.html