如何降低嵌套循环的复杂性来生成所有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地址

回答

相关问题