複数のIP範囲のセット間の異なるIP

Question

複数のIP範囲のセットが2つあります。各IP範囲は、長さが(startIP, endIP)のペアです。

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

私はaではなくbにあるIPアドレスを見つけたい - だから私は二組aとbを持っています。つまり、set(ips_a) - set(ips_b)です。

私はの各IPをbに対してチェックしていましたが、各セットには1億以上のIPが存在するので、プロセスは永久にかかります。

これを行う最も最適な方法は何ですか？また、既存のモジュールがこれを行う場合もあります。

Answer 1

あなたはアドレスの数に対してO(n log n)だ次のアルゴリズム試みることができる：私は、各リストの中に、IPアドレスの範囲が重複していないことを前提とし

• を。そうした場合は、それらの重複を取り除く（マージ範囲）。
• 両方のリストを範囲の先頭で並べ替えます。
• 最初のリストの現在の位置をトラッキングする2つの変数を使用するループをiとし、2番目のリストの現在の位置をトラッキングするもう1つの変数をjとします。
• b[j] < a[i]の間に、増分はjです。つまり、a[i]と重複しないでa[i]の前にあるb[j]をスキップします。
• b[j]と重複する場合は、重複部分をa[i]から削除し、iを増やしてください。
• aの最後に達するまで繰り返します。その結果、aにあるbのすべての範囲がaから削除されます。

このアルゴリズムの時間的複雑さは、ソートステップのためにO(n log n)です。