IPアドレスがアドレス範囲内にあるかどうかを調べる

Question

IPアドレスのジオロケーションを担当するサービスを構築しようとしています。 IPアドレスのオープンデータベースは、次の形式のCSVファイルです。starting_ip、ending_ip、region

IPアドレスを整数に変換し、指定された整数が開始と終了の範囲内にあるかどうかを確認しようとしました。しかし、この時点では、500Kのエントリのサイズを考慮に入れて、効率的な方法でこの比較がどのように実行されるのかはよく分かりません。

最初に私は次のdictを使用してメモリにすべてをロードしようとしていた。

{(ip_start, ip_end): 'region', ....} 

しかし、この時点で私は、IPアドレスで、この辞書にキーを見つける方法が表示されません。

Answer 1

範囲が重複していないと仮定すると、ip_startで一度並べ替えてから、バイナリ検索を使用して候補範囲を見つけることができます。候補範囲を見つけたら、IPアドレスがip_startとip_endの間にあるかどうかを確認するだけです。

組み込みのbisectモジュールを使用してバイナリ検索を実行できます。

これは、O(logn)ルックアップコストを示します。

Answer 2

私はあなたが好き一度何でも使用可能な形式でソートされたデータを永続化することをお勧めしていますが、スタート順にソートソートコレクションを、持っていたらsortedtcontainersSortedDictを使用すると、あなたがログのn時間で比較を行うことができますIP：

import csv 
from sortedcontainers import sorteddict 

with open("ips.csv") as f: 
    ips = ["192.168.43.102", "10.10.145.100", "192.168.1.1", "192.168.43.99","127.0.0.1"] 
    reader = csv.reader(f) 
    # Use start ip as the key, creating tuple or using netaddr to turn into an int 
    sorted_dict = sorteddict.SortedDict((tuple(map(int, sip.split("."))),(eip, rnge)) for sip, eip, rnge in reader) 

    for ip in ips: 
     # do the same for the ip you want to search for 
     ip = tuple(map(int, ip.split("."))) 
     # bisect to see where the ip would land 
     ind = sorted_dict.bisect(ip) - 1 
     start_ip = sorted_dict.iloc[ind] 
     end_ip = tuple(map(int, sorted_dict[sorted_dict.iloc[ind]][0].split("."))) 
     print(start_ip, ip, end_ip) 
     print(start_ip <= ip <= end_ip) 

我々はテストファイル上でコードを実行した場合：

In [5]: !cat ips.csv 
192.168.43.100,192.168.43.130,foo 
192.168.27.1,192.168.27.12,foobar 
192.168.1.1,192.168.1.98,bar 
192.168.43.131,192.168.43.140,bar 
10.10.131.10,10.10.131.15,barf 
10.10.145.10,10.10.145.100,foob 

In [6]: import csv 

In [7]: from sortedcontainers import sorteddict 

In [8]: with open("ips.csv") as f: 
    ...:   ips = ["192.168.43.102", "10.10.145.100", "192.168.1.1", "192.168.43.99","127.0.0.1"] 
    ...:   reader = csv.reader(f) 
    ...:   sorted_dict = sorteddict.SortedDict((tuple(map(int, sip.split("."))),(eip, rnge)) for sip, eip, rnge in reader) 
    ...:   for ip in ips: 
    ...:     ip = tuple(map(int, ip.split("."))) 
    ...:     ind = sorted_dict.bisect(ip) - 1 
    ...:     start_ip = sorted_dict.iloc[ind] 
    ...:     end_ip = tuple(map(int, sorted_dict[sorted_dict.iloc[ind]][0].split("."))) 
    ...:     print(start_ip,ip, end_ip) 
    ...:     print(start_ip <= ip <= end_ip) 
    ...:   
(192, 168, 43, 100) (192, 168, 43, 102) (192, 168, 43, 130) 
True 
(10, 10, 145, 10) (10, 10, 145, 100) (10, 10, 145, 100) 
True 
(192, 168, 1, 1) (192, 168, 1, 1) (192, 168, 1, 98) 
True 
(192, 168, 27, 1) (192, 168, 43, 99) (192, 168, 27, 12) 
False 
(10, 10, 145, 10) (127, 0, 0, 1) (10, 10, 145, 100) 
False 

あなたはまた、唯一のコにbisect_rightを修正することができます最初の要素nsiderと通常のPythonリストを使用します。二分がcレベルで行われているように、結果は同じになり、私はSortedDictを使用して想像

def bisect_right(a, x, lo=0, hi=None): 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(a) 
    while lo < hi: 
     mid = (lo+hi) // 2 
     if x < a[mid][0]: 
      hi = mid 
     else: 
      lo = mid + 1 
    return lo 

with open("ips.csv") as f: 
    ips = ["192.168.43.102", "10.10.145.100", "192.168.1.1", "192.168.43.99", "127.0.0.1"] 
    reader = csv.reader(f) 
    sorted_data = sorted(((tuple(map(int, sip.split("."))), eip, rnge) for sip, eip, rnge in reader)) 
    for ip in ips: 
     ip = tuple(map(int, ip.split("."))) 
     ind = bisect_right(sorted_data, ip) - 1 

     ip_sub = sorted_data[ind] 
     start_ip, end_ip, _ = sorted_data[ind] 
     end_ip = tuple(map(int, end_ip.split("."))) 
     print(start_ip, ip, end_ip) 
     print(start_ip <= ip <= end_ip) 

が速くほぼ確実です。