Как ускорить поиск элементов по двумерному массиву?

Question

[Chernichko]

Суть задачи в том, чтобы выпадал список городов, которые начинаются с символов, которые вводит пользователь.

Из двумерного массива выбираются только нужные элементы и выводятся на экран.
Но уж очень большой массив у меня и каждый раз проходить его это долго.

У меня это примерно так

$word = $_GET['name'];
  $newCities=array();
if(!empty($word)){
  foreach ($arCityList as $cCity) {
      //$cCity['cityName'] = iconv('windows-1251','utf-8',$cCity['cityName']);
        if(preg_match('/^'.$word.'/i', $cCity['cityName'])){
          $array1=array();
          $array1['cityId']=$cCity['cityId'];
          $array1['cityName']=$cCity['cityName'];
          $newCities[]=$array1;
        }
  }
}

но это очень долго работает.

Как можно ускорить поиск?
В данном примере я работаю с плагином ui-query autocmplete.
И этот autocmplete очень долго ищет подходящие города(

Comments

[Дмитрий Кравченко]

$arCityList откуда берете?

Answer 1

[Rsa97]

Поскольку поиск идёт по началу слова, то:
1. Используйте не список, а предварительно отсортированный массив и ищите бинарным поиском.
2. Используйте хэш. Даже разбиение по первой букве даст в русском языке сокращение перебора раз в 20.

Comments

[Chernichko]

Можете привести пример?

[Rsa97]

Chernichko: Пример чего? Хэша?

$cities = [
    'а' => ['Абакан', 'Актюбинск', 'Астрахань'],
    'б' => ['Благовещенск', 'Бузулук'],
    ...
    'я' => ['Яренга']
];

Или бинарного поиска?

function di_find($array, $str) {
    $find = mb_strtolower($str);
    $first = 0;
    $max = $last = count($array)-1;
    while (true) {
        if ($first > $last)
            return array();
        $cur = floor(($first+$last)/2);
        $city = mb_strtolower($array[$cur]);
        if (mb_strpos($city, $find) === 0)
            break;
        if ($city < $find)
            $first = $cur+1;
        else
            $last = $cur-1;
    }
    $first = $last = $cur;
    while ($first > 0 && mb_stripos($array[$first-1], $find) === 0)
        $first--;
    while ($last < $max && mb_stripos($array[$last+1], $find) === 0)
        $last++;
    return(array_slice($array, $first, $last-$first+1));
}

[Rsa97]

Chernichko: Да, и самый простой способ - держать всё в базе данных с соответствующим индексом и получать просто по LIKE

[Chernichko]

Rsa97: список городов я получаю со стороннего сервера и никак по другому(

[Chernichko]

Rsa97: Спасибо!)

Answer 2

[romy4]

1. список можно заранее подготовить как указал Rsa97 и сложить в отдельном файле
2. используйте разбиение по 1, 2 и 3 букве.

Comments

[Chernichko]

Можете привести пример?

[romy4]

Chernichko: нет. у вас есть алгоритм — сами его кодите, а тогда можете показать, чтобы обсудить. я за кого-то делают только платно