производительность — сопоставление строки с лучшим частичным соответствием
У меня есть файл CSV, который содержит частичные (или полные, переменные длины) британские почтовые индексы в первом столбце и различную информацию о тарифах в последующих столбцах.
У меня есть веб-сайт, который просит пользователей ввести свой полный почтовый индекс в Великобритании.
Затем приложение должно найти наилучшее совпадение своего почтового индекса с файлом CSV. Все символы совпадающей записи должны быть в их фактическом почтовом индексе, и лучшим совпадением для этой цели будет совпадение из CSV, в котором большинство символов их почтового индекса находятся в том же порядке, и нет символов, которые не включены в почтовый индекс. ,
Я играл с добавлением этих CSV-данных в базу данных MySQL, но я не думаю (пожалуйста, исправьте меня, если неправильно), это было бы более эффективно.
CSV-файл содержит почтовые индексы различной длины для сравнения.
Например.
B1 (должно совпадать с чем угодно, начиная с B1, где в другом месте нет более точного соответствия)
B13
B12 1NA
Таким образом, почтовый индекс B1 2NB должен соответствовать первой записи.
B12 1NB также должен соответствовать первому примеру.
B13 2PQ будет соответствовать второму примеру.
По сути, мне нужно найти в CSV-файле наиболее близкое совпадение, а затем загрузить всю строку в массив, который можно использовать для дальнейших вычислений.
Что было бы наиболее эффективным способом сделать это?
Предполагается, что загрузка всего CSV в память не лучший подход?
Решение
Имея около 1000 строк и, скажем, 50-100 байт данных на строку, это «всего лишь» 50–100 КБ памяти, что не так уж много.
Оперативное кэширование в PHP довольно хорошо, поэтому APC или Zend OpCache будут выполнять все необходимое кэширование в памяти, пока ваши файлы являются PHP, а не загружаются из & Разбор CSV каждый раз.
Хотя БД, безусловно, более масштабируема, накладные расходы на соединения TCP и сетевая задержка могут не сделать ее наиболее производительной.
Я предлагаю этот пример кода как способ реализации этого ЕСЛИ Вы решаете, что решение PHP в памяти — лучшее для вас.
<?php
/**
* Class PostcodeLookup
*
* Keeping the lookup data in a PHP file like this means that it will be cached in memory by APC or OpCache
*/
class PostcodeLookup
{
/**
* This will contain our lookup data and payload
*
* @var array
*/
private $arr_pc = [];
/**
* Populate the lookup array on construction
*/
public function __construct()
{
$this->arr_pc = [
'M1' => 'test1',
'M12' => 'test2',
'M123' => 'test3',
'G1' => 'test4',
'G2' => 'test5',
];
}
/**
* Our public function for running lookups
*
* This is here so we normalise the data ONCE and strlen() ONCE
*
* @param $str_pc
* @return bool
*/
public function run($str_pc)
{
$str_normalised = strtoupper(str_replace(' ', '', $str_pc));
return $this->check($str_normalised, strlen($str_normalised));
}
/**
* Reducing, recursive lookup
*
* @param $str_pc
* @param $int_length
* @return bool
*/
private function check($str_pc, $int_length)
{
if(isset($this->arr_pc[$str_pc])) {
return $this->arr_pc[$str_pc];
}
return $int_length > 1 ? $this->check(substr($str_pc, 0, -1), --$int_length) : false;
}
}
// Some example usage
$obj_lookup = new PostcodeLookup();
var_dump($obj_lookup->run('M123'));
var_dump($obj_lookup->run('M1'));
var_dump($obj_lookup->run('M19999'));
var_dump($obj_lookup->run('G2'));
Другие решения
Других решений пока нет …