不同的IP组之间的IP范围

Question

我有两组多个IP范围。每个IP范围是一对(startIP, endIP)多头。所以，我有两套a和b -

a = [(start11, end11), (start12, end12)...] 
b = [(start21, end21), (start22, end22)...] 

我希望能够找到这在a但不是在b的IP地址。换句话说，set(ips_a) - set(ips_b)。

我试图蛮力检查a中的每个IP对b，但这个过程需要永久，因为每个集合中有超过1亿个IP。

想知道什么是最优化的方式来做到这一点。此外，如果任何现有的模块这样做。

Answer 1

你可以尝试下面的算法，关于这O(n log n)到的地址数：

• 我假定每个列表中的IP地址范围的无重叠。如果他们这样做，消除这些重叠（合并范围）。
• 按范围的开始对两个列表排序。
• 循环中使用两个变量，一个跟踪在第一列表中的当前位置，让我们称之为i，另一个跟踪在第二列表中的当前位置，让我们称之为j。
• 虽然b[j] < a[i]，增加j。也就是说，跳过b[j]之前a[i]，不与a[i]重叠。
• 如果a[i]与b[j]重叠，请从a[i]中删除重叠部分，并增加i。达到
• 重复，直到a末。因此，a中也在b中的所有范围将从a中删除。

由于排序步骤，此算法的时间复杂度为O(n log n)。