blocks|key|1593913|text|由于您的文件已经按排序顺序存储IP地址，所以可以使用二进制搜索在O(log(n))时间内快速找到特定的IP地址。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1593914|如果您想进一步加快速度，您可以缓存内存中的每100行，并首先使用内存中的二进制搜索，然后您知道需要读取的文件的哪一部分才能完成搜索。|1593915|话虽如此，131+to实际上并不多，所以最简单和最快的解决方案是购买更多的内存，并将整个文件缓存在哈希表中。|1593916|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Since your file stores the IP addresses in sorted order already you can quickly find a specific IP address in O(log(n)) time by using a binary search.

If you want to speed this up even further you can cache for example every 100th row in memory and use an in-memory binary search first, then you know which part of the file you need to read in to finish the search.

Having said that 131kB is really not that much, so the simplest and fastest solution is to buy more memory and cache the entire file in memory in a hash table.

blocks|key|43916|text|编辑--我没有注意到php标记，我不知道在该语言中是否可以使用以下类型的东西。但无论如何我还是会把它留给这个想法的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|CODE|entityRanges|data|43917|IPv4地址可以表示为32位数字，所以我只需创建一个int32数组，用下面的Python+psuedocode将您的地址转换为‘into’：|43918|x+=+0
i+=+24
s+=+'111.222.333.444'
for+part+in+s.split('.'):
++++x+%2B=+part.toint()+<<+i
++++i+-=+8
IPlist.append(x)|code-block|syntax|javascript|43919|然后，您可以获得输入地址，以同样的方式将其转换为int，并对数组进行二进制搜索。|43920|对于10k线，阵列需要40+kBytes。|43921|entityMap^0|0|2|A|3|0|Q|5|0|0|O|3|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@$9|U|A|V|B|C]|$9|W|A|X|B|D]]|E|@]|F|$]]|$1|G|3|H|5|6|7|Y|8|@$9|Z|A|10|B|D]]|E|@]|F|$]]|$1|I|3|J|5|K|7|11|8|@]|E|@]|F|$L|M]]|$1|N|3|O|5|6|7|12|8|@$9|13|A|14|B|D]]|E|@]|F|$]]|$1|P|3|Q|5|6|7|15|8|@]|E|@]|F|$]]|$1|R|3|-4|5|6|7|16|8|@]|E|@]|F|$]]]|S|$]]

EDIT I didn't notice the <code>php</code> tag, I don't know if the following type of thing is possible in that language. But I'll leave it for the idea anyway.

An IPv4 address is representable as a 32-bit number, so I'd just make an array of <code>int32</code>, translate your addresses into the 'ints` with the following Python-ish psuedocode:

<pre><code>x = 0
i = 24
s = '111.222.333.444'
for part in s.split('.'):
 x += part.toint() &lt;&lt; i
 i -= 8
IPlist.append(x)
</code></pre>

Then you can get the input address, convert it to an <code>int</code> the same way, and do binary search on the array.

For ~10 k lines, the array will take ~40 kBytes.

blocks|key|1593980|text|可能不太快，但我会尝试这样做:如果IP地址文件变化不大，请将文件读入数组并缓存它(可能是Memcache)，然后在每个请求中进行搜索。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1593981|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Might not be fast, but I'd try this out: If the IP address file doesn't change much, read the file into an array and cache it (maybe Memcache) and search from there on every request.

blocks|key|1593983|text|逐行扫描文件以查找IP，如果在到达232.0.17.1之前需要检查9,000个非匹配项，则似乎很痛苦。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1593984|您的文件是否被限制为单个文件？例如，假设这个列表是被禁止的，你只想看看其中一个是否“在”列表中。|1593985|如果您创建了一个包含多个文件的DIR，该怎么办：|1593986|BannedIPs
++%2B-+0.ips
++%2B-+1.ips
++%2B-+37.ips
++%2B-+123.ips
++%2B-+253.ips
++%2B-+254.ips|code-block|syntax|javascript|1593987|每个文件只包含以该编号开头的IP地址。|1593988|如果你够幸运的话，能有均匀的分布。您将有256个文件，但每个文件只有37个条目。|1593989|因此，当您想要测试：232.0.17.1时，您可以查看232.ips文件并对其进行扫描。|1593990|entityMap^0|H|A|0|0|0|0|0|0|A|A|R|7|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Z|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|10|8|@]|D|@]|E|$]]|$1|J|3|K|5|L|7|11|8|@]|D|@]|E|$M|N]]|$1|O|3|P|5|6|7|12|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|13|8|@]|D|@]|E|$]]|$1|S|3|T|5|6|7|14|8|@$9|15|A|16|B|C]|$9|17|A|18|B|C]]|D|@]|E|$]]|$1|U|3|-4|5|6|7|19|8|@]|D|@]|E|$]]]|V|$]]

Scanning the file line by line to find an IP seems like a pain if you have 9,000 non-matches to check before you get to <code>232.0.17.1</code>

Is your file constrained to a single file? e.g. lets say this list is banned IPs and you just want to see if one is "in" the list.

What if you made a DIR to contain multiple files:

<pre><code>BannedIPs
 +- 0.ips
 +- 1.ips
 +- 37.ips
 +- 123.ips
 +- 253.ips
 +- 254.ips
</code></pre>

Each file only contains IP addresses that start with that number.

If you were lucky enough to have even distribution... you'd have 256 files, but each would only have ~37 entries.

Thus when you want to test: <code>232.0.17.1</code> you look in the <code>232.ips</code> file and scan for it.

Question

What is the fastest way to find if an IP address exists in a file that contains IP addresses sorted as:

<blockquote>
<pre><code>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
</code></pre>
</blockquote>

Constraints

<ul>
<li>No database (e.g., MySQL, PostgreSQL, Oracle, etc.)</li>
<li>Infrequent pre-processing is allowed (see possibilities section)</li>
<li>Would be nice not to have to load the file each query (131Kb)</li>
<li>Uses under 5 megabytes of disk space</li>
<li>No extra PHP modules</li>
</ul>

File Details

<ul>
<li>One IP address per line</li>
<li>9500+ lines</li>
</ul>

Possible Solutions

<ul>
<li>Create a directory hierarchy (<a href="http://en.wikipedia.org/wiki/Radix_tree" rel="nofollow noreferrer">radix tree</a>?) then use <code>is_dir()</code> (sadly, this uses 87 megabytes)</li>
</ul>

Fast file search algorithm for IP addresses

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

问题如何最快地找到一个IP地址是否存在于包含如下IP地址的文件中：219.93.88.62 219.94.181.87 219.94.193.96 220.172.201 220.110.162.50 220.126.52.187 220.126.52.247约束没有数据库(如MySQL、PostgreSQL、Orac...

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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