Определение региона на PHP без использования сторонних сервисов

в 23:50, , рубрики: php, бинарный поиск в массиве, Веб-разработка, метки: ,

Здравствуйте!
Передо мной стояла задача сделать определение региона используя вот эту базу российских, украинских и европейских ip-адресов своими силами без привлечения сторонних сервисов средствами PHP.

В архиве имеются txt-файл со списком соответствия диапазонов ip номерам регионов (cidr_optim.txt) и, соответственно, файл со списком регионов (cities.txt). В распакованном виде файлы занимают cidr_optim.txt — 8Мб и cities.txt — 74.6Кб.

Как сделать, что бы это работало быстро?

Для начала сокращаем объем данных. Что мы делаем — считаем сколько строк в первом (8Мб) файле (я насчитал 146476), извлекаем из этого числа корень квадратный, округляем в большую сторону до целого и получаем в итоге число (383). Что оно означает? 383 дополнительных файла в которых будет содержаться по 383 записи + еще один файл (индексный), в котором будут содержаться 383 записи о 383 файлах. Зачем это всё? А затем, что мы будем теперь обращаться не к 1-му (8Мб) файлу, а к 2-м (84Кб и 31Кб).

Теперь всё по порядку:

1. Подготовительная часть.

a) cities.txt пробегаем циклом, создаем массив, где ключ — id региона, а значение — смещение указателя файла, соответствующее началу строки, содержащей запись об этом регионе. Позже это позволит нам не загружать полностью весь файл в оперативную память, а обратиться сразу к нужной строке.

б) cidr_optim.txt тоже циклом разбиваем на корень квадратный из количества строк в этом файле и округленный до целого в большую сторону (ceil(sqrt($count_str));) частей, представленных в виде многомерного массива вида:

...
    [146309] => Array
        (
            [0] => 3653525504 // начало диапазона
            [1] => 3653529599 // конец диапазона
            [2] => RU // страна
            [3] => 40750 // id региона заменяем на смещение указателя в файле cidr_optim.txt
        )

    [146310] => Array
        (
            [0] => 3653529600
            [1] => 3653533695
            [2] => CZ
            [3] => 76405
        ) 
...

Такие массивы мы сериализуем и помещаем в файлы в имени которых будет номер блока диапазонов (те самые файлы, которые занимают по 31Кб). Из этого номера, а так же из минимального и максимально значений диапазона мы формируем массив такого вида:

...
    [3] => Array // номер блока диапазонов (он же имя файла)
        (
            [0] => 532250624 // минимальное значение в блоке
            [1] => 533293823 // максимальное значение в блоке
        )

    [4] => Array
        (
            [0] => 533293824
            [1] => 621019135
        )
...

Этот массив тоже сериализуем и сохраняем в файл index (тот самый, что занимает 84Кб)
На этом подготовительная часть заканчивается. Выполнять ее можно каждый раз, когда вы соберетесь обновить базу либо вручную, либо можно возложить это дело на планировщика заданий на вашем хостинге.
Выполнение подготовительного скрипта (на сервере моего хостера):

Time: 1.747959 sec
Memory: 1.152 Mb

Думаю приемлемо для столь нечастого мероприятия.

2. Основная часть.

а) Преобразуем ip адрес в целое число $ip2l = sprintf("%u", ip2long($_SERVER['REMOTE_ADDR']));

б) Получаем содержимое файла index, преобразуем обратно в массив $f = unserialize(file_get_contents($dir.'index'));

в) Бинарный поиск по массиву соответствующего диапазона и получаем номер диапазона (он же название файла) key(bisectionSearch($ip2l, $f));.

<?php
function bisectionSearch($n, $a) { // $n значение - ip2long, $a - массив диапазонов с ключами равными номерам диапазона
	while (count($a)>1) { // пока в массиве 2 и более значения
		$ta = array_chunk($a, ceil(count($a)/2), true); // делим массив на 2 части
		$f = key($ta[1]); // получаем номер первого элемента второй половины массива
		$a = $ta[1][$f][0] <= $n ? $ta[1] : $ta[0]; // сравниваем нижнюю границу диапазона второй половины массива со значением ip2long и выбираем первую или вторую половину массива и присваиваем ее значение первоначальному массиву.
	}
	return (is_array($a)) ? $a : null; // возвращае результат
}

г) Получаем содержимое файла, название (число), которое мы получили в пункте (в) unserialize(file_get_contents($dir.$f));, где $f — число

д) Производим такой же бинарный поиск bisectionSearch($ip2l, $f), но на выходе необходимо сделать array_shift, для того, что бы получить значение вложенное на 1 уровень:

Array
(
    [0] => 3642351616 - начало диапазона
    [1] => 3642355711 - конец диапазона
    [2] => RU - страна
    [3] => 25408 - смещение указателя файла, которое нам понадобится для получения названия региона из файла со списком регионов
)

е) Открываем на чтение файл со списком регионов $handle = fopen($dir.'../cities.txt','r');, устанавливаем смещение fseek($handle, $f[3]);, получаем нужную строку $f = explode(' ', iconv('cp1251', 'utf-8', fgets($handle, 10000))); — приходится менять кодировку (по крайней мере мне).

Примерно вот такие цифры на выходе (на сервере моего хостера):
Time: 0.001336 sec
Memory: 0.496 Mb

Посмотреть как работает вторая часть, а так же
скачать исходники можно по соответствующим ссылкам.

В примере и в исходниках все работает через файлы, но в рабочем проекте у нас реализовано через memcache. Скорость на порядок выше.

Надеюсь статья будет вам полезна.

Спасибо за внимание.

Автор: web36m

Поделиться

* - обязательные к заполнению поля