如何降低嵌套循環的複雜性來生成所有IP地址

ALGO

loop i in 0 -> 255 
    loop j in 0 -> 255 
     loop k in 0 -> 255 
      loop l in 0 -> 255 
       output string(i.j.k.l) //ip-address

能否請你告訴的方式，從爲O（n^4）降低其複雜性的東西少了？任何幫助將不勝感激。

來源

2016-01-28 Amarjeet Singh

有很多的IP地址。列出很多事情需要很長時間。你爲什麼需要把它們全部列出來？你想做什麼？ – Teepeemm

@Teepeemm我需要記錄ip-api.com/json/*ip-address*的json響應。一些私人IP範圍正在豁免，但在if語句輸出，這是我沒有打擾提及，因爲這不會有任何幫助。 –

所以你想要得到一個幾乎每個IP地址的Ajax響應？這將花費太長時間，api將停止回答你。你需要重新思考你的方法。 – Teepeemm

您不能生產O(f(n))的輸出時間小於O(f(n))。如果你想讓它運行得更快，你需要減少輸出。

你知道，IP地址往往是物理上接近附近的IP地址......

來源

2016-01-28 17:28:03 btilly

首先，我不知道你實際上是試圖解決什麼問題，但它是不可能的，它需要你查找每個可能的IP地址。如果你給了我們更多的上下文（即你認爲需要這種解決方案的更大的問題是什麼？），也許我們可以給你一些更現實的選擇。下面的信息解釋了爲什麼你不能改進你的算法，如果你真的想查找所有可能的地址。

有40億左右可能的IP地址。有些處於私人範圍，您無法查詢，其他組合可能無效。除非你進行一些前端過濾，否則你必須檢查所有40億次。儘管過濾，但你會檢查整個可能範圍的很大一部分。

如果n的範圍是0..255，那麼你的代碼只有O（n^4）。這是看待事物的一種奇怪的方式。另一種看待它的方法是n是2^32（即40億和變化），並且你需要檢查每一個。然後是O（n）。你可以很容易地通過他們都在一個循環：

uint ip = 0; 
do 
{ 
    // convert the integer to an IP address by extracting the individual bytes. 
    if (ip not in private address range) 
    { 
     // do the lookup 
    } 
    ++ip; 
} while (ip != 0);

我要強調，雖然，除了在前面的過濾，這並不比原來的算法或多或少效率。

你最好先做私人IP範圍過濾（在查找之前）。這樣你就不會浪費時間尋找你不知道的東西。

順便說一句，如果您的本地網絡上有DNS服務器，DNS查找的平均時間好在60毫秒左右。假設你可以保持這一點，查找每個可能的IP地址的時間將是：

60 ms * 2^32 addresses = 257,698,037.76 seconds

這可以工作到8年多一點。

後來補充：根據Ami Tavory在他的回答（Reserved IP addresses）中發佈的鏈接，大約有6億個保留地址。如果你將這些過濾出來，你可以按時間要求降低約15％。你只需7年即可完成！）

你需要以不同的方式處理你的問題。

來源

2016-01-28 17:50:40

好的解釋順便說一下 – surajsn

從「如何加速這4個嵌套循環」的角度來解釋這個問題，根據定義，無法提高複雜性。

儘管如此，你需要這樣的做法來處理每個IP地址，其中一些是無關緊要的。例如，Here是保留IP地址的列表。

你可能會想出一些不同的，或更具體的，爲你的情況。

如果您可以以某種方式將這些限制編碼到循環中，則可以降低複雜性。例如：

for i0 in 0 - > 255 if not restriction0(i0): 
    for i1 in 0 -> 255 if not restricion1(i0, i1): 
     for i2 in 0 - > 255 if not restriction2(i0, i1, i2: 
       for i3 in 0 -> 255 if not restricion3(i0, i1, i2, i3): 
        do something

來源

2016-01-28 17:52:43

如何降低嵌套循環的複雜性來生成所有IP地址

回答

相關問題