不同的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)。