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。即跳过a[i]之前的b[j]，不与a[i]重叠。
• 如果a[i]与b[j]重叠，从a[i]中删除重叠部分，并增加i。
• 重复直到到达 a 的末尾。因此，a 中同时也在 b 中的所有范围将从 a.
中删除

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