Самый быстрый способ найти самое длинное соответствие в CSV-файле размером 50 КБ в PHP

Question

В голосовом приложении я должен найти самое длинное совпадение префикса на международном телефонном номере. У меня есть таблица ставок, которая составляет 50 тыс. Строк и хранится в файле CSV, который периодически обновляется новыми тарифами (заголовки столбцов CSV содержат префикс, тариф страны и т. Д.). Приложение использует REST API, чтобы показать пользователям стоимость звонка в пункт назначения на основе введенного ими телефона. Невозможно использовать простой KVS, так как существует несколько совпадений и требуется совпадение самого длинного префикса. API получает удар ALOT, поэтому непосредственное использование БД слишком медленное / тяжелое (здесь используется APC, но, похоже, это не имеет большого значения). Лучший алгоритм, который я могу придумать, показан ниже, но на приличной машине он все еще занимает почти 1 секунду. У любого гуру алгоритма PHP есть лучший метод?

    function getRate($phoneNumber) { 

        if (!apc_fetch('ALL_RATES')){

            $all_rates = array_map('str_getcsv', file('/var/billing/rates.csv'));
            apc_store('ALL_RATES', $all_rates);

        } else {

            $all_rates = apc_fetch('ALL_RATES');
        } 

        $noOfCountries = sizeof($all_rates);    
        $bestMatch = 0;


        for ($n=1;$n<$noOfCountries;$n++) {

            $country = $all_rates[$n];
            $country_prefix = $country[0];

            $match = stripos($phoneNumber, $country_prefix);

            if ($match===0){

                if (strlen($country_prefix) > $bestMatch) {

                    $bestMatch = strlen($country_prefix);
                    $matchedCountry = $n;

                }

            }

        }

        $prefix = $all_rates[$matchedCountry][0];
        $country = $all_rates[$matchedCountry][1];
        $rate = $all_rates[$matchedCountry][2];

        return array($country,$prefix,$rate);

    }
}

Answer 1

Что ж, вы можете сбрасывать 200-300 мсек, если вы пишете свои собственные стрипы, так как вам нужно только выполнить сопоставление префикса, а не пытаться сопоставить префикс в любой позиции.

Тем не менее, это то, что я рекомендую:

1) Откажитесь от формата CSV и начните использовать достойную реляционную базу данных, MySQL хорош. PS утверждение "дБ слишком медленное / тяжелое" не имело смысла. Если вы все настроите правильно, сопоставление префикса с базой данных займет 0 секунд (да, вы все правильно прочитали, несколько миллисекунд). SQL поддерживает полнотекстовое сканирование с префиксами. Сохраните длину каждого телефонного номера и индексируйте его тоже.

2) Запустить кеширование запросов.

Что касается вашего CSV-решения, вы можете получить хороший прирост производительности, если у вас есть номера телефонов, сохраненные как prefixTree.csv, после этого вы можете быстро получить все номера телефонов, которые начинаются с определенного префикса. Ps, не загружайте файл CSV каждый раз в память, когда вы получаете запрос. Это супер медленно! Кэшируйте это как статическое (есть ли в PHP статика?)

Дополнительная информация: http://phpir.com/tries-and-wildcards/