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モジュールはありません

ファイルの詳細

  • 1行に1つのIPアドレス
  • 9500行以上

可能な解決策

  • ディレクトリ階層（基数木？）を作成してから使用しますis_dir()（残念ながら、これは87メガバイトを使用します）
4

4 に答える 4

3

に到達する前にチェックする9,000の不一致がある場合、IPを見つけるためにファイルを1行ずつスキャンするのは苦痛のように思えます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 に答える
3

ファイルにはすでに並べ替えられた順序でIPアドレスが格納されているため、バイナリ検索を使用すると、O（log（n））時間で特定のIPアドレスをすばやく見つけることができます。

これをさらに高速化したい場合は、たとえばメモリ内の100行ごとにキャッシュし、最初にメモリ内のバイナリ検索を使用できます。次に、検索を完了するためにファイルのどの部分を読み込む必要があるかがわかります。

131kBは実際にはそれほど多くはないので、最も簡単で最速の解決策は、より多くのメモリを購入し、ファイル全体をハッシュテーブルのメモリにキャッシュすることです。

于 2010-04-18T00:08:46.463 に答える
3

編集私はタグに気づかなかったphp、私はその言語で次のタイプのことが可能かどうかわからない。しかし、とにかくアイデアのためにそれを残しておきます。

IPv4アドレスは32ビットの数値として表現できるので、配列をint32作成し、次のPython風の擬似コードを使用してアドレスを「ints」に変換します。

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行の場合、アレイには〜40kバイトかかります。

于 2010-04-18T00:16:13.120 に答える
1

高速ではないかもしれませんが、これを試してみます。IPアドレスファイルがあまり変更されない場合は、ファイルを配列に読み込んでキャッシュし（Memcacheなど）、リクエストごとにそこから検索します。

于 2010-04-18T00:18:30.623 に答える