IP范围集合之间的不同IP

Question

我有两套多IP范围。每个IP范围都是一对(startIP, endIP) ( longs )。我有两套a和b -

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

我希望找到a中的I，而不是b中的I。或者换句话说，set(ips_a) - set(ips_b)。

我试过用暴力来检查a中的每个IP和b，但是这个过程需要花费很长时间，因为每组IP中都有超过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)。