问IP地址的快速文件搜索算法

EN

逐行扫描文件以查找IP，如果在到达232.0.17.1之前需要检查9,000个非匹配项，则似乎很痛苦。

您的文件是否被限制为单个文件？例如，假设这个列表是被禁止的，你只想看看其中一个是否“在”列表中。

如果您创建了一个包含多个文件的DIR，该怎么办：

BannedIPs
  +- 0.ips
  +- 1.ips
  +- 37.ips
  +- 123.ips
  +- 253.ips
  +- 254.ips

每个文件只包含以该编号开头的IP地址。

如果你够幸运的话，能有均匀的分布。您将有256个文件，但每个文件只有37个条目。

因此，当您想要测试：232.0.17.1时，您可以查看232.ips文件并对其进行扫描。

由于您的文件已经按排序顺序存储IP地址，所以可以使用二进制搜索在O(log(n))时间内快速找到特定的IP地址。

如果您想进一步加快速度，您可以缓存内存中的每100行，并首先使用内存中的二进制搜索，然后您知道需要读取的文件的哪一部分才能完成搜索。

话虽如此，131 to实际上并不多，所以最简单和最快的解决方案是购买更多的内存，并将整个文件缓存在哈希表中。

编辑--我没有注意到php标记，我不知道在该语言中是否可以使用以下类型的东西。但无论如何我还是会把它留给这个想法的。

IPv4地址可以表示为32位数字，所以我只需创建一个int32数组，用下面的Python psuedocode将您的地址转换为‘into’：

x = 0
i = 24
s = '111.222.333.444'
for part in s.split('.'):
    x += part.toint() << i
    i -= 8
IPlist.append(x)

然后，您可以获得输入地址，以同样的方式将其转换为int，并对数组进行二进制搜索。

对于10k线，阵列需要40 kBytes。