与えられたIPアドレスがPythonのIPサブネットワークに属しているかどうかを効率的に調べる方法は？

Question

私は約200,000のIPアドレスのセットとフォーム（1.1.1.1/24）の10,000のサブネットを持っています。すべてのIPアドレスについて、これらのサブネットの1つに属しているかどうかを確認する必要がありますが、そのような大規模なデータセットであり、計算能力が低いので、これを効率的に実装したいと思います。

from netaddr import IPNetwork, IPAddress 
if IPAddress("192.168.0.1") in IPNetwork("192.168.0.0/24"): 
    print "Yay!" 

しかし、私は、各アドレスループの10,000以上のサブネットをループにこの200,000以上のIPアドレスを持っており、以来、私はこの場合はわからない午前：検索について

は、私が見つけた一つの方法は、この（https://stackoverflow.com/a/820124/7995937）でした効率的です。 私の最初の疑問は、IPNetwork（）の "IPAddress（）"をリニアスキャンだけにチェックしているのですか、それとも何らかの方法で最適化されていますか？

私が思いついたもう一つの解決策は、IPサブネットに含まれるすべてのIP（重複することなく約13,000,000のIPになる）でリストを作成し、それを並べ替えることでした。私がこれを行うと、200,000のIPアドレスの私のループでは、より大きなIPアドレスのセットに対して、各IPのバイナリ検索を行うだけです。

for ipMasked in ipsubnets: # Here ipsubnets is the list of all subnets 
     setUnmaskedIPs = [str(ip) for ip in IPNetwork(ipMasked)] 
     ip_list = ip_list + setUnmaskedIPs 
ip_list = list(set(ip_list)) # To eliminate duplicates 
ip_list.sort() 

私はその後、ちょうど次のようにバイナリ検索を実行できます。

for ip in myIPList: # myIPList is the list of 200,000 IPs 
    if bin_search(ip,ip_list): 
     print('The ip is present') 

は、他のものよりもより効率的なこの方法ですか？または、このタスクを実行するための他の効率的な方法がありますか？

Answer 1

おそらくベストの解決策ではありませんが、リストではなくセットを使用することをおすすめします。セットは、指定された値がセットに存在するかどうかをチェックするために最適化されているので、バイナリ検索を1回の操作で置き換えます。代わりに：

ip_set = set(ip_list) 

をして、あなたのコードの他の部分は次のようになります：

ip_list = list(set(ip_list)) 

だけで行う

for ip in myIPList: # myIPList is the list of 200,000 IPs 
    if ip in ip_set: 
     print('The ip is present') 

編集：と物事はもう少しメモリ - にします効率的に中間リストを作成することはできません。

ip_set = set() 
for ipMasked in ipsubnets: 
    ip_set.update([str(ip) for ip in IPNetwork(ipMasked)]) 

Answer 2

さて、ソートにはO（nlogn）が必要です.1,300万件の場合はO（13000000log（13000000））になります。次に、200000以上のIPを繰り返し、13000000のソートされたリストでバイナリ検索O（logn）を実行しています。 私はそれが最善の解決策であることを心から疑っています。私はNがそのアドレス一致のビットをリードするN Nビットのサブネットの1のビットをリードする場合は、マップ

from netaddr import IPNetwork, IPAddress 
l_ip_address = map(IPAddress, list_of_ip_address) 
l_ip_subnet = map(IPNetwork, list_of_subnets) 

if any(x in y for x in l_ip_address for y in l_ip_subnet): 
    print "FOUND" 

Answer 3

サブネット内でのあなたのIPアドレスを使用することをお勧め。ですから、まず空のセットのリストを作成します。末尾のビットをマスクして32ビット整数として各サブネットをエンコードします。たとえば、1.2.3.4/23と等しい（0x01020304 & 0xfffffe00）は0x01020200に等しくなります。この番号をリストの23番目のセット、つまりsubnets[23]に追加します。すべてのサブネットを続行します。IPアドレスは、あなたのサブネットにある場合

は、32ビットの数値 ipaddrと同じ方法でIPアドレスをエンコードしてから（のようなもの、未テストコード）

for N in range(32, 0, -1) 
    mask = (0xffffffff >> (32-N)) << (32-N) 
    if (ipaddr & mask) in subnets[N] : 
     # have found ipaddr in one of our subnets 
     break # or do whatever... 
else 
    # have not found ipaddr 

番号を探し、表示するには最悪の集合O（log N）であり、Nは集合の要素数である。このコードは、サブネットのセットに含まれていないIPアドレスの最悪の場合、最大32回です。アドレスの大部分が存在することが予想される場合は、最も優先順位の高いセットをテストする最適化があります。それは

for N in (24, 16, 8, 29, 23, 28, 27, 26, 25, 22, 15, 21 ...) 

であるか、実行時に最適なシーケンスを計算することができます。