Линейный поиск на PHP в одномерном массиве.

Рассмотрим задачу, когда нам надо найти X в произвольном одномерном массиве.

У нас имеется:
Искомое значение $x
Массив $m

Давайте рассмотрим несколько реализаций такого поиска. Первая реализация выглядит так:

function linearSearch($m, $x)
{
    for($i=0; $i < count($m); i++)
    {
        if ($m[$i] == $x)
        {
            return $i;
        }
		
        if($i == count($m))
        {
            return "NotFound";
        }
    }
}

Давайте посмотрим, что происходит в данной функции.
На вход мы передаем две переменные:
1. массив
2. Искомое значение

    Далее, каждую итерацию цикла происходит:
  • 1. $i < count($m) Проверка на то не достигнут ли конец массива
  • 2. При проверке не достигли ли мы конца цикла вызывается отдельная функция count() которая возвращает количество элементов в массиве.
  • 3. $m[$i] == $x Далее мы проводим проверку на соответствие текущего элемента массива искомому значанию.
  • 4. $i == count($m) В конце цикла делаем проверку на достижение конца цикла, и если мы его достигли, то явно не нашли искомое значение и возвращаем NotFound. Причем заметьте мы опять применяем count().
  • 5. В конце итерации цикла мы увеличиваем i на единицу.

Проведем замер времени работы. При 100 000 размерности массива на моем хостинге время работы составляет около 30 миллисекунд.

Давайте подумаем, что тут можно упростить, вернее, как можно уменьшить количество операций за одну итерацию цикла:
1) Первое и самое явное это использование функции count().
Ее из цикла можно вообще убрать заменив на заранее определенную переменную.

2) Проверка выполнения условия $i == count($m) каждую итерацию тоже лишний элемент. Так как у нас поиск обрамлен в виде функции данное условие можно вообще вынести за пределы цикла, и если мы не нашли нужный элемент в массиве, то выходим из цикла и возвращаем notFound.

function betterLinearSearch($m, $x)
{
    $countMas = count($m);
    for($i=0; $i < $countMas; $i++)
    {
        if ($m[$i] == $x)
        {
            return $i;
        }
    }
    return "notFound";
}

Это уже, что то более менее приемлемое.
Проведем замер. При такой же размерности цикла время работы составляет около 5 миллисекунд! Это в шесть раз быстрее, чем наша первая функция. Наибольший буст скорости дает удаление count() из итераций цикла.

Не смотря на то, что обе функции имеют одинаковую асимптотическую сложность тета от n, второй вариант получается менее нагруженным, то есть более быстрым.

Но можно ли сделать поиск еще быстрее?
Мы можем убрать внутреннее условие $m[$i] == $x переместив его в сам цикл.

function linearSearch2($m, $x)
{
    $masCount = count($m)-1;
    $last = $m[$masCount];
    $m[$masCount] = $x;
    $i = 1;
	
    while($m[$i] != $x)
    {
        $i++;
    }
	
    if ($i == $masCount && $last != $x)
    {
        return "notFound";
    }
    else
    {
        return $i;
    }
}

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

Делаем замер и получаем 12 миллисекунд! :)
Что же тут не так спросите вы? А все дело в записи в массив $m[$masCount] = $x причем, чем больший индекс используется при записи, тем больше времени уходит на это.

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

function linearSearch2($m, $x)
{
    $i = 1;
    while($m[$i] != $x)
    {
        $i++;
    }
    return $i;
}

Проведем замер и получим 4 миллисекунды!
Не такой уж большой выигрыш по сравнению со вторым вариантом алгоритма.
В целом я бы не рекомендовал использовать последний вариант, не значительный прирост скорости не может нивелировать потенциальное зацикливание программы.

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


comments powered by Disqus