Алгоритм быстрого поиска файлов по IP-адресам - PullRequest
Новая
       21

Алгоритм быстрого поиска файлов по IP-адресам

4 голосов
/ 18 апреля 2010

Вопрос

Какой самый быстрый способ найти, если 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 + строк

Возможные решения

  • Создайте иерархию каталогов ( radix tree ?), Затем используйте is_dir() (к сожалению, это использует 87 мегабайт)

Ответы [ 4 ]

3 голосов
/ 18 апреля 2010

Сканирование файла построчно, чтобы найти IP, кажется болезненным, если у вас есть 9 000 несоответствий, чтобы проверить, прежде чем вы получите 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 и сканируете его.

3 голосов
/ 18 апреля 2010

РЕДАКТИРОВАТЬ Я не заметил тег php, я не знаю, возможен ли следующий тип вещей на этом языке. Но я все равно оставлю это для идеи.

Адрес IPv4 представлен в виде 32-разрядного числа, поэтому я просто создал бы массив int32, переведя ваши адреса в 'ints' с помощью следующего псевдокода Python-ish: 

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 тыс. Строк массив будет занимать ~ 40 кбайт.

3 голосов
/ 18 апреля 2010

Поскольку ваш файл уже хранит IP-адреса в отсортированном порядке, вы можете быстро найти определенный IP-адрес за время O (log (n)) с помощью двоичного поиска.

Если вы хотите еще больше ускорить это, вы можете кэшировать, например, каждую сотую строку в памяти и сначала использовать двоичный поиск в памяти, а затем вы знаете, какую часть файла необходимо прочитать, чтобы завершить поиск.

Сказав, что 131 КБ на самом деле не так уж много, поэтому самое простое и быстрое решение - купить больше памяти и кэшировать весь файл в памяти в хэш-таблице.

1 голос
/ 18 апреля 2010

Может не быть быстрым, но я бы попробовал это: если файл IP-адреса не сильно меняется, считайте файл в массив и кэшируйте его (возможно, Memcache) и ищите оттуда по каждому запросу.

...