agentsib/binary-search
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-09-22 12:06:46 UTC
README
这是keepper/binary-search的分支,原始维护者不再维护。
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. 用于在FMS无效护照数据库中搜索过期文件的命令行工具
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.2GB)
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