agentsib / binary-search
Binary Search Library for php
1.1.0
2023-12-22 10:39 UTC
Requires
- php: ^7.4|^8.0
- psr/log: ^3.0
Requires (Dev)
- phpunit/phpunit: ^8.0
This package is auto-updated.
Last update: 2024-10-22 12:17:39 UTC
README
This is a fork of keepper/binary-search, the original maintainer does not continue maintenance.
Binary Search Library for php
Реализация алгоритма бинарного поиска на PHP
Умеет работать с большими файлами без чтения файла целиком в память.
Пример использования
1. Получаем файл при помощи
wget http://www.fms.gov.ru/upload/expired-passports/list_of_expired_passports.csv.bz2
2. Распаковываем
bzip2 -d list_of_expired_passports.csv.bz2
3. Сортируем
sort list_of_expired_passports.csv > source.csv
4. Консольная утилита для поиска просроченного файла в БД недействительных паспортов ФМС
touch fms.php
Редактируем файл fms.php пишем простой код
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
Не найдено
real 0m0.095s
user 0m0.018s
sys 0m0.009s
5.2. На присутствующем значении:
time php5 ./test.php ./source.csv 0000,000435
Найдено на позиции: 434
Значение: [0000,000435]
real 0m0.104s
user 0m0.009s
sys 0m0.018s