agentsib/binary-search

PHP的二分搜索库

1.1.0 2023-12-22 10:39 UTC

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