快速的文件搜索算法解決

什麼是發現如果一個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

限制條件

文件詳細信息

可能的解決方案

沒有具體的，但可能是一個靈感：http://www.scribd.com/doc/10988897/IP-Address-Lookup-Algorithms – elias 2010-04-18 00:24:08

逐行掃描文件網上找到一個IP似乎是一個痛苦，如果你有9000的非匹配你到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-18 00:34:51 scunliffe

由於您的文件已按排序順序存儲IP地址，您可以快速找到特定的IP地址n O（log（n））時間通過使用二進制搜索。

如果您想進一步提高速度，您可以緩存例如內存中的第100行，並首先使用內存中的二進制搜索，然後您知道需要讀入的文件的哪一部分才能完成搜索。

話雖如此，131kB真的不是那麼多，所以最簡單和最快的解決方案是購買更多的內存並將整個文件緩存在內存中的哈希表。

2010-04-18 00:08:46

編輯我沒有注意到php標籤，我不知道下列類型的東西在該語言中是否可能。但是，無論如何我都會留下這個想法。

IPv4地址可表示爲一個32位的數字，所以我只是做的int32陣列，您的地址翻譯成「ints`與下面的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-18 00:16:13 mtrw

可能不是很快，但我會試試這個：如果IP地址文件沒有太大變化，請將文件讀入數組並將其緩存（可能是Memcache）並從每個請求中進行搜索。

2010-04-18 00:18:30 Shiki

回答