Само выражение «линейный поиск в отсортированных списках» звучит странно. Почему мы должны использовать этот алгоритм для отсортированных списков, когда есть много других алгоритмов, которые гораздо более эффективны? Как я упоминал в моем предыдущем посте, последовательный поиск в большинстве случаев очень неэффективен и в основном используется для неупорядоченных списков. Действительно, иногда бывает более полезно сначала отсортировать данные, а затем использовать более быстрый алгоритм, такой как бинарный поиск. С другой стороны, анализ показывает, что для списков, содержащих менее десяти элементов, линейный поиск намного быстрее, чем двоичный поиск.
Хотя, например, бинарный поиск более эффективен в отсортированных списках, последовательный поиск может быть лучшим решением в некоторых конкретных случаях с небольшими изменениями. Проблема в том, что когда разработчики слышат выражение «отсортированный список», они напрямую выбирают алгоритм, отличный от линейного поиска. Возможно, проблема заключается в том, как мы понимаем, что такое упорядоченный список?
Что такое отсортированный список?
Раньше мы думали, что этот список (1, 1, 2, 3, 5, 8, 13) отсортирован. На самом деле мы так думаем, потому что он … отсортирован, но список (3, 13, 1, 3, 3.14, 1.5, -1) также отсортирован, за исключением того, что мы не знаем как. Таким образом, мы можем думать, что любой массив отсортирован, хотя это не всегда очевидно, как.
Есть в основном два случая, когда последовательный поиск может быть очень полезным. Сначала, когда список очень короткий или когда мы заранее знаем, что есть некоторые значения, которые очень часто ищутся.
Допустим, у нас очень большой список с сотнями тысяч элементов, но на самом деле большинство запросов в этом списке всегда находят одинаковые десять значений. Эта дополнительная информация говорит нам, что использование бинарного поиска в этом случае будет весьма неэффективным. Конечно, возможный подход — поместить эти значения в начало списка и выполнить последовательный поиск.
Вы должны выбрать алгоритм поиска, внимательно изучив данные, которые вы ищете.
К сожалению, поиск будет медленным, когда мы будем искать какое-то значение, отсутствующее в начале списка, но тогда мы можем использовать другой алгоритм в отсортированных списках.
Тем не менее, есть один вопрос, на который нужно ответить. Мы знаем, что в большинстве случаев мы ищем одни и те же значения, но мы не знаем точно эти значения. Поэтому вопрос заключается в том, как поместить наиболее часто используемые значения в начало списка, поскольку мы их не знаем. Здесь нам нужна какая-то автоматическая настройка списка.
Самоорганизация
Самоорганизация практически означает, что каждый раз, когда мы ищем и находим желаемое значение, мы каким-то образом меняем список, чтобы следующий поиск был намного более эффективным.
Есть два основных подхода к этому.
- Чтобы переместить элемент на одну позицию вперед, в начало списка;
- Чтобы переместить элемент прямо в начало списка.
Конечно, это зависит от вашего случая, какой подход вы выберете, но предполагается, что второй вариант, перемещающий элемент непосредственно перед списком, лучше.
Действительно, если мы выберем первый вариант и список будет (…, 24, 31) после постоянного поиска этих двух значений, массив изменится с (…, 24, 31) на (…, 31, 24) и еще раз на (…, 24, 31) и так далее и тому подобное.
Таким образом, лучшее решение — переместить нужный элемент прямо в начало списка. Теперь, если мы посмотрим на значение «5» в списке (1, 2, 4,…, 5,…, 398), оно станет (5, 1, 2,…, 398) после того, как значение будет найдено.
Выбирая этот подход, мы можем быть уверены, что по мере увеличения числа поисков наиболее часто используемые значения помещаются в начале списка. Теперь последовательный поиск — неплохое решение!
Вот пример последовательного поиска из моей предыдущей статьи. Единственное изменение заключается в том, что после того, как мы находим желаемое значение, нам нужно переместить его в начало списка.
/**
* Performs a sequential search using sentinel
* and changes the array after the value is found
*
* @param array $arr
* @param mixed $value
*/
function sequential_search(&$arr, $value)
{
$arr[] = $value;
$index = 0;
while ($arr[$index++] != $value);
if ($index < count($arr)) {
// put the item at the front of the list
array_unshift($arr, $arr[$index-1]);
// remove the value from its previous position
unset($arr[$index]);
// unset the sentinel
unset($arr[count($arr)+1]);
return true;
}
return false;
}
// the list
$arr = array(1, 2, 3, 3.14, 5, 4, 6, 9, 8);
// the value
$x = 3.14;
if (sequential_search($arr, $x)) {
// now the array is changed to
// (3.14, 1, 2, 3, 5, 4, 6, 9, 8)
echo "The value $x is found!";
} else {
echo "The value $x doesn't appear to be in the list!";
}
заявка
Использование последовательного поиска в отсортированных списках может быть очень полезным и быстрым — единственное, что нам нужно заранее знать, что есть некоторые значения, которые часто ищут. Типичным примером такого случая является список контактов на вашем телефоне. Возможно, у вас там много имен, но в большинстве случаев вы ищите в них номера своих лучших друзей и родственников. Вот почему большинство производителей сотовых телефонов добавляют в свои телефоны возможность предварительно задавать сочетания клавиш для наиболее часто набираемых номеров.
Вот еще один вариант использования. Допустим, у нас тот же сценарий, что и в моем предыдущем посте , где пары имя пользователя / имя хранятся в файле CSV. Мы можем получить эти значения в массиве PHP.
// list with username/name pairs
$arr = array(
array('name' => 'James Bond', 'username' => 'jamesbond007'),
array('name' => 'John Smith', 'username' => 'jsmith'),
array('name' => 'John Silver', 'username' => 'hohoho'),
array('name' => 'Yoda', 'username' => 'masteryoda900'),
array('name' => 'Darth Vader', 'username' => 'vader'),
);
Каждый раз, когда пользователь заходит на сайт, мы ищем его имя по его имени, и отображается приветственное сообщение. Мы знаем, что некоторые пользователи заходят на сайт очень часто, в то время как другие делают это один раз в месяц, поэтому мы можем не только выполнять последовательный поиск, но и использовать самоорганизацию для массива и в конце изменять файл CSV.
/**
* Performs a sequential search using a sentinel.
* Returns the index of the item if the item was found
* and FALSE otherwise.
*
* @param array $arr
* @param mixed $value
*/
function sequential_search(&$arr, $value)
{
// usign a sentinel
$arr[] = array('username' => $value, 'name' => '');
$index = 0;
while ($arr[$index++]['username'] != $value);
// if the desired element is in the array
if ($index < count($arr)) {
// push the element at the front of the list
array_unshift($arr, $arr[$index-1]);
// remove the item from its previous place
unset($arr[$index]);
// remove the sentinel
unset($arr[count($arr)]);
// return the index of the value
return $index;
}
// the element has not been found
return FALSE;
}
if (FALSE !== ($iterations = sequential_search($arr, 'vader'))) {
echo "Hello, {$arr[0]['name']}";
echo "Found after $iterations iterations!";
} else {
echo "Hi, guest!";
}
if (FALSE !== ($iterations = sequential_search($arr, 'vader'))) {
echo "Hello, {$arr[0]['name']}";
echo "Found after $iterations iterations!";
} else {
echo "Hi, guest!";
}
Результат:
Hello, Darth Vader Found after 5 iterations! Hello, Darth Vader Found after 1 iterations!
Теперь каждый раз, когда Дарт Вейдер пытается войти в систему, вы не будете мешать ему ждать много времени. Однако держу пари, что никто не использует файлы CSV для хранения такой информации … но это только пример.
Примечание: все примеры в этой статье написаны на PHP .
Источник: http://www.stoimen.com/blog/2011/12/02/computer-algorithms-linear-search-in-sorted-lists/