javascript - 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 和 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)由于排序步骤。