Статьи

Алгоритм недели: последовательный поиск

Ноябрь 25, 2018

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

Основная реализация

Наиболее естественный подход — циклически проходить по списку, пока мы не найдем нужное значение. Вот реализация на PHP с использованием цикла FOR, который можно легко записать на любой другой компьютерный язык.

// unordered list
$arr = array(1, 2, 3, 3.14, 5, 4, 6, 9, 8);
 
// searched value
$x = 3.14;
$index = null;
 
for ($i = 0; $i < count($arr); $i++) {
	if ($arr[$i] == $x) {
		$index = $i;
	}
}
 
if (isset($index)) {
	echo "The value $x exists in the list on position $index!";
} else {
	echo "The value $x doesn't appear to be in the list!";
}

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

Прямой линейный поиск

Распространенная ошибка — продолжать поиск даже после того, как мы нашли желаемое значение!

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

Оптимизация прямого последовательного поиска

// unordered list
$arr = array(1, 2, 3, 3.14, 5, 4, 6, 9, 8);
 
// searched value
$x = 3.14;
$length = count($arr);
$index = null;
 
for ($i = 0; $i < $length; $i++) {
	if ($arr[$i] == $x) {
		$index = $i;
		break;
	}
}
 
if (isset($index)) {
	echo "The value $x exists in the list on position $index!";
} else {
	echo "The value $x doesn't appear to be in the list!";
}
Оптимизированный прямой линейный поиск

Важно разорвать цикл, как только вы найдете значение в списке!

Даже с этой небольшой оптимизацией алгоритм остается неэффективным. Как мы видим, на каждой итерации у нас есть два условных выражения. Сначала мы проверяем, достигли ли мы конца списка, а затем проверяем, равен ли текущий элемент искомому элементу. Таким образом, вопрос в том, можем ли мы уменьшить количество условных выражений?

Поиск в обратном порядке

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

// unordered list
$arr = array(1, 2, 3, 3.14, 5, 4, 6, 9, 8);
 
// searched value
$x = 3.14;
$index = count($arr);
 
while ($arr[$index--] != $x);
 
echo "The value $x found on position " . ($index+1) . "!";

Обратите внимание, что нам нужно настроить индекс из-за $ index-выражения.

Действительно, здесь у нас есть только одно условное выражение, но проблема в том, что эта реализация верна ТОЛЬКО, когда элемент существует в списке, что не всегда верно. Если элемент не появляется в списке, этот код может привести к бесконечному циклу. Хорошо, но как мы можем остановить цикл, даже если в списке нет нужного значения? Ответ заключается в добавлении искомого значения в список.

часовой

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

Sentinel Последовательный поиск

Вставив часового в конец списка, мы уверены, что значение существует в списке!

// unordered list
$arr = array(1, 2, 3, 3.14, 5, 4, 6, 9, 8);
 
// searche value
$x = 3.14;
$arr[] = $x;
$index = 0;
 
while ($arr[$index++] != $x);
 
if ($index < count($arr)) {
	echo "The value $x found on position " . ($index - 1) . "!";
} else {
	echo "The value $x not found!";
}

Этот подход можно использовать для преодоления проблемы подхода обратного линейного поиска из предыдущего раздела.

сложность

Как я уже говорил в начале этого поста, это один из самых неэффективных алгоритмов поиска. Конечно, лучший случай, когда искомое значение находится в самом начале списка. Таким образом, при первом сравнении мы можем найти его. С другой стороны, худший случай — это когда элемент находится в самом конце списка. Если предположить, что мы не знаем, где находится элемент, и возможность быть где-либо в списке абсолютно одинакова, то сложность этого алгоритма составляет O (n).

Разные случаи

Однако мы должны помнить, что сложность алгоритма может варьироваться в зависимости от того, встречается ли элемент один раз.

Это так неэффективно?

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

заявка

Линейный поиск действительно очень прост в реализации, и большинство веб-разработчиков переходят на прямую реализацию, которая является наиболее неэффективной. С другой стороны, этот алгоритм весьма полезен при поиске в неупорядоченном списке. Да, поиск в упорядоченном списке — это то, что может кардинально изменить алгоритм поиска. На самом деле алгоритмы поиска и сортировки часто используются вместе.

Типичным случаем является извлечение чего-либо из базы данных, обычно в форме списка, а затем поиск некоторого значения в нем. К сожалению, в большинстве случаев база данных упорядочивает возвращенный набор результатов, и все же большинство разработчиков выполняют последовательный поиск по списку. Еще раз, когда список упорядочен, лучше использовать бинарный поиск вместо последовательного поиска.
Допустим, у нас есть CSV-файл, содержащий имена пользователей и имена наших пользователей.

Username,Name
jamesbond007,James Bond
jsmith,John Smith
...

Теперь мы извлекаем эти значения в массив.

// work case
$arr = array(
	array('name' => 'James Bond', 'username' => 'jamesbond007'),
	array('name' => 'John Smith', 'username' => 'jsmith')
);

Теперь с помощью последовательного поиска …

// using a sentinel
$x = 'jsmith';
$arr[] = array('username' => $x, 'name' => '');
$index = 0;
 
while ($arr[$index++]['username'] != $x);
 
if ($index < count($arr)) {
	echo "Hello, {$arr[$index-1]['name']}";
} else {
	echo "Hi, guest!";
}

Примечание: все примеры в этой статье написаны на PHP.

 

Источник: http://www.stoimen.com/blog/2011/11/24/computer-algorithms-sequential-search/

34
Share: