Статьи

Алгоритм недели: интерполяционный поиск

Ноябрь 1, 2018

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

Почему это? Ну, этот алгоритм пытается следовать тому, как мы ищем имя в телефонной книге или слово в словаре. Мы, люди, заранее знаем, что если имя, которое мы ищем, начинается с буквы «B», например, «Bond», мы должны начать поиск в начале телефонной книги. Таким образом, если мы ищем слово «алгоритм» в словаре, вы знаете, что оно должно быть где-то в начале. Это потому, что мы знаем порядок букв, мы знаем интервал (az) и каким-то образом интуитивно знаем, что слова распределены одинаково. Этих фактов достаточно, чтобы понять, что бинарный поиск может быть плохим выбором. Действительно, алгоритм двоичного поиска делит список на два равных подсписка, что бесполезно, если мы заранее знаем, что искомый элемент находится где-то в начале или конце списка. Да,мы можем использовать такжепоиск с перескоком, если элемент находится в начале, но не в конце, в этом случае этот алгоритм не так эффективен.

Таким образом, интерполяционный поиск основан на некоторых простых фактах. Бинарный поиск делит интервал на два равных подсписка, как показано на рисунке ниже.

Базовый подход бинарного поиска

Алгоритм бинарного поиска делит список на два равных подсписка!

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

Интерполяционный поиск

Алгоритм интерполяционного поиска пытается улучшить бинарный поиск!

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

C = (x-L)/(R-L)

Теперь мы можем быть уверены, что мы ближе к искомому значению.

Реализация

Вот реализация интерполяционного поиска в PHP.

$list = array(201, 209, 232, 233, 332, 399, 400);
$x = 332;
 
function interpolation_search($list, $x)
{
	$l = 0;
	$r = count($list) - 1;
 
	while ($l <= $r) {
		if ($list[$l] == $list[$r]) {
			if ($list[$l] == $x) {
				return $l;
			} else {
				// not found
				return -1;
			}
		}
 
		$k = ($x - $list[$l])/($list[$r] - $list[$l]);
 
		// not found
		if ($k < 0 || $k > 1) {
			return -1;
		}
 
		$mid = round($l + $k*($r - $l));
 
		if ($x < $list[$mid]) {
			$r = $mid - 1;
		} else if ($x > $list[$mid]) {
			$l = $mid + 1;
		} else {
			// success!
			return $mid;
		}
 
		// not found
		return -1;
	}
}
 
echo interpolation_search($list, $x);

сложность

Сложность этого алгоритма составляет log 2 (log 2 (n)) + 1. Хотя я не буду рассматривать его доказательства, я скажу, что это очень медленно растущая функция, как вы можете видеть на следующем графике.

log (n) по сравнению с log (log (n))

Действительно, когда значения равномерно распределены по интервалу, этот алгоритм поиска может быть чрезвычайно полезным — намного быстрее, чем бинарный поиск. Как вы можете видеть журнал 2 (журнал 2 (100 М)) ≈ 4.73 !!!

заявка

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

$list = array(
	0 => array('year' => 1980, 'name' => 'John Smith', 'username' => 'John'),
	1 => array('year' => 1980, ...),
	...
	10394 => array('year' => 1981, 'name' => 'Tomas M.', ...),
	...
	348489 => array('year' => '1985', 'name' => 'James Bond', ...),
	...
	2808008 => array('year' => '1990', 'name' => 'W.A. Mozart', ...)
);

Теперь, если мы ищем кого-то, родившегося в 1981 году, хорошим подходом будет использование интерполяционного поиска.

 

Источник: http://www.stoimen.com/blog/2012/01/02/computer-algorithms-interpolation-search/

 

39
Share: