0

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

两个列表的格式如下：

清单 A

1.2.3.4
145.2.3.0/24
6.5.0.0/16
3.4.1.0/24

清单 B

1.5.6.7
10.0.3.0/24
1.2.3.0/24
3.4.0.0/16

两个列表 A ∩ B 相交的预期结果：等

1.2.3.4
3.4.1.0/24

我的第一次测试很天真：

此方法适用于小列表。但是，此解决方案不适用于数千个网络（即数百万个 IP 地址），因为我没有足够的内存。此外，该解决方案不适用于IPv6网络。

将两个列表相交的最有效方法是什么？

另外：我还必须在列表 A 和其他列表之间重复此操作为 B：A ∩ C、A ∩ D 等。

我愿意接受所有建议，即使是猪:-)

解决方案 ：

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)
4

2 回答 2

1

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

首先，考虑如果 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 内存的笔记本电脑上，两个 5,000 个随机定义的网络列表（长度 8 到 24 位）的交集只需要几秒钟：

制作两个 IP 地址列表：

import random

f = open('iplist1.txt','w')
for i in range(5000):
    ip = '.'.join([str(random.randint(1,254)) for i in range(4)])
    ip += '/'+str(random.randint(8,24))
    f.write(ip+'\n')
f.close()

f = open('iplist2.txt','w')
for i in range(5000):
    ip = '.'.join([str(random.randint(1,254)) for i in range(4)])
    ip += '/'+str(random.randint(8,24))
    f.write(ip+'\n')
f.close()

将它们相交：

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"
于 2013-03-23T14:36:54.333 回答
0

好吧，如果您对 Pig 持开放态度，那么没有什么比这更容易了。它不会出现内存不足的问题，并且交叉点很简单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';

完毕。

于 2013-03-24T04:35:49.947 回答