В моей предыдущей статье я обсуждал, как последовательный (линейный) поиск можно использовать в упорядоченных списках, но затем мы были ограничены специфическими особенностями данной задачи. Очевидно, последовательный поискупорядоченный список неэффективен, потому что мы последовательно проверяем каждый из его элементов. Есть ли способ, которым мы можем оптимизировать этот подход? Ну, поскольку мы знаем, что список отсортирован, мы можем проверить некоторые его элементы, но не все. Таким образом, когда элемент проверяется, если он меньше, чем желаемое значение, мы можем пропустить некоторые из следующих элементов списка, перепрыгивая вперед, а затем проверять снова. Теперь, если проверяемый элемент больше требуемого значения, мы можем быть уверены, что желаемое значение скрывается где-то между ранее проверенным элементом и текущим проверенным элементом. Если нет, снова мы можем прыгнуть вперед. Конечно, хороший подход — это использовать фиксированный шаг. Допустим, длина списка равна n, а длина шага — k. В основном мы проверяем список (0), затем список (k-1), список (2k-1) и т. Д. Как только мы находим интервал, где значение может быть (m * k-1 <x <= (m + 1) * k — 1), мы можем выполнить последовательный поиск между двумя последними проверенными позициями. Выбирая этот подход, мы избегаем многих недостатков алгоритма последовательного поиска. Многие сравнения из последовательного поиска здесь исключены.
Как выбрать длину шага
Мы знаем, что рекомендуется использовать шаг фиксированного размера. На самом деле, когда шаг равен 1, алгоритм представляет собой традиционный последовательный поиск. Вопрос в том, какой должна быть длина шага и существует ли какая-либо связь между длиной списка (n) и длиной шага (k)? Действительно, такая связь существует, и часто можно увидеть источники, прямо говорящие, что лучшая длина k = √n. Почему это?
Что ж, в худшем случае мы делаем n / k переходов, и если последнее проверенное значение больше, чем желаемое, мы делаем не более k-1 сравнений. Это означает n / k + k — 1 сравнение. Теперь вопрос в том, для каких значений k эта функция достигает своего минимума. Для тех из вас, кто помнит математические классы, это можно найти с помощью формулы -n / (k ^ 2) + 1 = 0. Теперь ясно, что для k = √n достигается минимум функции.
Конечно, вам не нужно доказывать это каждый раз, когда вы используете этот алгоритм. Вместо этого вы можете напрямую назначить √n длиной шага. Однако хорошо знать этот подход при попытке оптимизировать алгоритм.
Давайте посмотрим следующий список: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). Его длина составляет 16. Поиск в поиске найдет значение 55 со следующими шагами.
Поиск Jump пропускает некоторые элементы списка для повышения производительности!
Реализация
Давайте посмотрим пример прыжкового поиска, написанного на PHP .
$list = array();
for ($i = 0; $i < 1000; $i++) {
$list[] = $i;
}
// now we have a sorted list: (0, 1, 2, 3, ..., 999)
function jump_search($x, $list)
{
// calculate the step
$len = count($list);
$step = floor(sqrt($len));
$prev = 0;
while ($list[($step < $len ? $step : $len)] < $x) {
$prev = $step;
$step += floor(sqrt($len));
if ($step >= $len) {
return FALSE;
}
}
while ($list[$prev] < $x) {
$prev++;
if ($prev == ($step < $len ? $step : $len)) {
return FALSE;
}
}
if ($list[$prev] == $x) {
return $prev;
}
return FALSE;
}
echo (int)jump_search(674, $list);
Здесь у нас есть отсортированный список с 1000 элементами, который выглядит следующим образом: (0, 1, 2,…, 999). Очевидно, что при последовательном поиске мы найдем значение 674 точно на 674-й итерации. Здесь с помощью поиска с переходом мы можем достичь его на 44-й итерации, и это показывает нам преимущество поиска с переходом по сравнению с последовательным поиском по упорядоченным спискам.
Дальнейшая оптимизация
Хотя все примеры здесь имеют дело с небольшими списками на практике, это не всегда верно. Иногда сам шаг может быть очень большим числом, поэтому, когда вы знаете интервал, в котором может быть желаемое значение, вы можете снова выполнить поиск перехода.
Мы увидели, что лучший размер шага — √n, но начинать с первого элемента списка не рекомендуется, как это было в предыдущем примере. Лучший вариант — начать с k-го пункта. Теперь мы можем улучшить вышеуказанное решение.
Базовая реализация поиска перехода может быть немного оптимизирована!
сложность
Очевидно, что сложность алгоритма составляет O (√n), но как только мы знаем интервал, в котором находится значение, мы можем улучшить его, применив поиск с перескоком снова. Действительно, скажем, длина списка составляет 1 000 000. Интервал прыжка должен быть: √1000000 = 1000. Как видите, вы можете использовать поиск с новым шагом √1000≈31. Каждый раз, когда мы находим желаемый интервал, мы можем применить алгоритм поиска перехода с меньшим шагом. Конечно, в конечном итоге шаг будет 1. В этом случае сложность алгоритма больше не будет O (√n). Теперь его сложность приближается к логарифмическому значению. Проблема состоит в том, что реализация этого подхода считается более сложной, чем бинарный поиск, где сложность также составляет O (log (n)).
заявка
Так как почти каждый алгоритм поиска перехода очень удобен для определенного вида задач. Да, двоичный поиск легко реализовать, и его сложность составляет O (log (n)), но в случае очень большого списка прямой переход к середине может быть плохой идеей. Затем мы должны сделать большой шаг назад, если искомое значение находится в начале списка.
Возможно, каждый из нас выполнил какой-то примитивный поиск прыжка в своей жизни, даже не подозревая об этом. Вы помните кассетные магнитофоны? Мы использовали клавишу «перемотка вперед» и периодически проверяли, была ли лента на нашей любимой песне. Как только мы остановились в середине песни, мы использовали кнопку «перемотка назад», чтобы точно найти начало песни.
Этот неуклюжий пример может дать нам ответ, где поиск с переходом может быть лучше, чем бинарный поиск. Преимущество поиска с переходом заключается в том, что вам нужно вернуться назад только один раз (в случае базовой реализации).
Поиск прыжка очень полезен, когда прыжок назад значительно медленнее, чем прыжок вперед!
Если прыжок назад занимает значительно больше времени, чем прыжок вперед, используйте этот алгоритм.
Источник: http://www.stoimen.com/blog/2011/12/12/computer-algorithms-jump-search/