上千个网络的两个列表之间的交叉点

Question

我有一个巨大的网络列表（称为a），我需要检查这些网络的地址是否存在于另一个网络列表（称为B）中：

两份清单的格式如下：

列表A

1.2.3.4
145.2.3.0/24
6.5.0.0/16
3.4.1.0/24

列表B

^{pr2}$

两个列表A∩B:等交集的预期结果

1.2.3.4
3.4.1.0/24

我的第一个测试很天真：

• 列出带有ipaddr模块的所有IP
• 将每个列表的IP放入两个set
• 对两个集合的intersection执行操作。在

此方法适用于小列表。但是，这种解决方案不适合于数千个网络（即几百万个IP地址），因为I don't have enough memory。此外，该解决方案不适用于IPv6网络。在

怎样做两个列表的交集最有效？

另外：我还要在列表A和其他列表B之间重复这一点：A∩C，A∩D等

我愿意接受所有的建议，即使是pig:-）

解决方案：

def chunks(l, n):
  for i in xrange(0, len(l), n):
    yield l[i:i+n]

res = []
for chunk_a in chunks(A, 1000):
  for chunk_b in chunks(B, 1000):
      C = IPSet(chunk_a) & IPSet(chunk_b)
      if C > IPSet([]):
          res.append(C)

Answer 1

好吧，如果你对猪敞开心扉，那么没什么比这更容易的了。它不会遇到内存不足的问题，并且使用JOIN进行交集非常简单：

A = LOAD '/path/to/A' AS (ip:chararray);
B = LOAD '/path/to/B' AS (ip:chararray);

intersection = FOREACH (JOIN A BY ip, B BY ip) GENERATE A::ip;
STORE intersection INTO '/path/to/output';

完成了。在

Answer 2

这里有一种基于实现IP地址/网络集的netaddr包的可能性。在

首先，假设A=A1∪A2和B=B1∪B2，那么A∩B=（A1∩B1）∪（A1∩B2）∪（A2∩B1）∪（A2∩B2）。在

因此，您可以将列表分解为多个小集合，并使用上面的方法递增地计算交集。例如：

from netaddr import IPSet

A1 = IPSet(['1.2.3.4','145.2.3.0/24'])
A2 = IPSet(['6.5.0.0/16','3.4.1.0/24'])
B1 = IPSet(['1.5.6.7','10.0.3.0/24'])
B2 = IPSet(['1.2.3.0/24','3.4.0.0/16'])

A1B1 = A1 & B1
A1B2 = A1 & B2
A2B1 = A2 & B1
A2B2 = A2 & B2

A1B1 | A1B2 | A2B1 | A2B2
-> IPSet(['1.2.3.4/32', '3.4.1.0/24'])

但是考虑到，当使用IPSet时，您不需要列出所有的地址，您可能能够执行交集而不必求助于将列表分解为小集合。在

---

更新：在一台拥有4GB内存的笔记本电脑上，由5000个随机定义的网络（长度8到24位）组成的两个列表的交集只需几秒钟：

列出两个IP地址列表：

^{pr2}$

使它们相交：

import time
import netaddr

ipset1 = netaddr.IPSet(open('iplist1.txt','r').readlines())
ipset2 = netaddr.IPSet(open('iplist2.txt','r').readlines())

print "Set 1:", len(ipset1), "IP addresses"
print "Set 2:", len(ipset2), "IP addresses"

start = time.time()
ipset = ipset1 & ipset2
print "Elapsed:", time.time() - start
print "Intersection:",len(ipset),"IP addresses"