agentsib/binary-search

Binary Search Library for php

binary-search

This is a fork of keepper/binary-search, the original maintainer does not continue maintenance., _(*1)

Binary Search Library for php, _(*2)

Реализация алгоритма бинарного поиска на PHP, _(*3)

Умеет работать с большими файлами без чтения файла целиком в память., _(*4)

Пример использования

1. Получаем файл при помощи

wget http://www.fms.gov.ru/upload/expired-passports/list_of_expired_passports.csv.bz2, _(*5)

2. Распаковываем

bzip2 -d list_of_expired_passports.csv.bz2, _(*6)

3. Сортируем

sort list_of_expired_passports.csv > source.csv, _(*7)

4. Консольная утилита для поиска просроченного файла в БД недействительных паспортов ФМС

touch fms.php, _(*8)

Редактируем файл fms.php пишем простой код, _(*9)

include_once 'vendor/autoload.php';

if (count($argv) < 3) {
    // Вывод справки
    print "Используйте php5 test.php файл искомая строка\n";
    exit;
} else {
    // Берем атрибуты переданные с коммандной строки
    $filepath = $argv[1];
    $pattern = $argv[2];
}

// Создаем объект источник данных для поиска
$dataSource = new \BinarySearch\DataSource\FileData($filepath);

// Инициализируем класс бинарного поиска
$searcher = new \BinarySearch\BinarySearch($dataSource);

// Для отладки можем инжектировать объект логгер
//$searcher->injectLogger(new \BinarySearch\ConsoleLog());

// Производим поиск позиции в источники данных, в которой находится искомое значение
$position = $searcher->search($pattern);

if ( is_null($position) ) {
    print 'Не найдено'."\n";
    exit;
} 

print 'Найдено на позиции: '.$position."\n";

// Идем на указаную позицию и читаем найденое
$dataSource->moveTo($position);
print 'Значение: ['.$dataSource->getData().']'."\n";

5. Пробуем (размер файла source 1,2 Гб)

5.1. На отсутствующем значении:

time php5 ./test.php ./source.csv 5005,000435, _(*10)

Не найдено

real    0m0.095s
user    0m0.018s
sys     0m0.009s

5.2. На присутствующем значении:

time php5 ./test.php ./source.csv 0000,000435, _(*11)

Найдено на позиции: 434
Значение: [0000,000435]

real    0m0.104s
user    0m0.009s
sys     0m0.018s