4

问题

查找包含 IP 地址的文件中是否存在 IP 地址的最快方法是：

219.93.88.62
219.94.181.87
219.94.193.96
220.1.72.201
220.110.162.50
220.126.52.187
220.126.52.247

约束

  • 没有数据库（例如 MySQL、PostgreSQL、Oracle 等）
  • 允许不频繁的预处理（参见可能性部分）
  • 不必每次查询都加载文件会很好（131Kb）
  • 使用低于 5 兆字节的磁盘空间
  • 没有额外的 PHP 模块

文件详情

  • 每行一个 IP 地址
  • 9500+ 行

可能的解决方案

  • 创建一个目录层次结构（基数树？）然后使用is_dir()（遗憾的是，这使用了 87 兆字节）
4

4 回答 4

3

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

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

说了这么多，131kB真的不算多，所以最简单最快的解决办法就是多买些内存，把内存中的整个文件缓存在一个哈希表中。

于 2010-04-18T00:08:46.463 回答
3

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

IPv4 地址可以表示为 32 位数字，所以我只需创建一个数组int32，使用以下 Python 式伪代码将您的地址转换为“整数”：

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

然后你可以得到输入地址，将其转换为int相同的方式，并在数组上进行二进制搜索。

对于 ~10 k 行，数组将占用 ~40 kBytes。

于 2010-04-18T00:16:13.120 回答
3

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

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

如果您制作了一个包含多个文件的 DIR 怎么办：

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

每个文件仅包含以该数字开头的 IP 地址。

如果你足够幸运，分布均匀......你将拥有 256 个文件，但每个文件只有约 37 个条目。

因此，当您想测试时：232.0.17.1您查看232.ips文件并扫描它。

于 2010-04-18T00:34:51.423 回答
1

可能不会很快，但我会尝试一下：如果 IP 地址文件没有太大变化，请将文件读入数组并缓存它（可能是 Memcache），然后在每个请求上从那里搜索。

于 2010-04-18T00:18:30.623 回答