== Идея Определения==Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".
== Алгоритм ={{Определение|definition =Пусть <tex> a </tex> Таблица маршрутизации {{---}} отсортированный массив таблица, состоящая из <tex> n </tex> чисел, <tex> x </tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом сетевых маршрутов и текущим значением элементапредназначенная для определения наилучшего пути передачи сетевого пакета. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
Формула для разделительного элемента <tex> m </tex> получается из следующего уравнения: <tex dpi = "170"> \frac{x - a_l}{m - l} Определение|definition = \frac{a_r - a_l}{r - l} </tex> Сетевой маршрут {{---}}откуда следуетзапись таблицы маршрутизации, содержащая в себе адрес сети назначения (destination), что <tex> m = l + </tex> <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> маску сети назначения (r - lnetmask) </tex>. На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на томшлюз (gateway), что наш массив представляет из себя что-то наподобии арифметической прогрессииинтерфейс (interface) и метрику (metric).[[Файл:interpolation_search_from_gshark.png|450px|center|Размещение разделительного элемента]] }}
== Псевдокод =Пример таблицы маршрутизации=<code> '''int''' interpolationSearch(a : '''int[]''', key : '''int''') <font color=green> // a должен быть отсортирован </font> left = 0 <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) </font> right {| border= a.length - "1 <font color=green> // правая граница поиска </font>" |- '''while''' a[left] < key '''and''' key < a[right]!Destination||Netmask||Gateway||Interface||Metric mid = left + (key - a[left]) * (right - left) / (a[right] |- a[left]) <font color=green> // индекс элемента, с которым будем проводить сравнение </font> '''if''' a[mid] < key left = mid + |0.0.0.0||0.0.0.0||192.168.0.1||192.168.0.100||10 '''else if''' a[mid] > key|- right = mid - |127.0.0.0||255.0.0.0||127.0.0.1||127.0.0.1||1 '''else'''|- '''return''' mid|192.168.0.0||255.255.255.0||192.168.0.100||192.168.0.100||10 |- '''if''' a[left] == key|192.168.0.100||255.255.255.255||127.0.0.1||127.0.0.1||10 '''return''' left|- '''else if''' a[right] == key '''return''' right '''else''' '''return''' -|192.168.0.1 <font color=green>// если такого элемента в массиве нет </font>||255.255.255.255||192.168.0.100||192.168.0.100||10</code>|}
== Время работы ==
Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>. То есть, после <tex>k</tex>-ого шага количество проверяемых элементов уменьшается до <tex dpi = 170>n^{\frac{1}{2^k}}</tex>. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда <tex dpi = 150>\frac{1}{2^k} = \log_{n}2 = \frac{1}{\log_{2}n} </tex>. Из этого вытекает, что количество шагов, а значит, и время работы составляет <tex>O(\log \log n)</tex>.
При "плохих" исходных данных ==Описание компонентов=={{Определение|definition = Адрес сети назначения (напримерDestination) {{---}} собственно, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>адрес конечного узла пути передачи сетевого пакета.}}
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время {{Определение|definition = Маска сети назначения (пока таблица не очень великаNetmask). Кроме того{{---}} битовая маска, определяющая, типичные таблицы недостаточно случайныкакая часть IP-адреса узла сети относится к адресу сети, да а какая — к адресу самого узла в этой сети. В двоичной записи всегда выглядит как множество единиц в начале и разница между значениями нулей в конце.}} ===Пример получения адреса сети==={| class="simple" border="1"|-! ||Двоичная запись||Десятичная запись|-|IP-адрес||<textt>\log \log n11000000 10101000 00000001 00000010</textt> и ||192.168.1.2|-|Маска|| <textt>\log n11111111 11111111 11111110 00000000</textt> становится значительной только при очень больших || 255.255.254.0|-|Адрес сети|| <textt>n11000000 10101000 00000000 00000000</textt>||192.168. На практике при поиске 0.0|} Чтобы вычислить адрес сети, нужно применить логическое ''и'' к адресу и маске. {{Определение|definition = Шлюз (Gateaway) {{---}} адрес узла в больших файлах оказывается выгодным сети, на ранних стадиях применять интерполяционный поисккоторый необходимо отправить пакет, следующий до указанного адреса назначения. Шлюзы бывают ''по умолчанию'', тогда значения адреса назначения и маски указываются как 0.0.0.0.}} {{Определение|definition = Интерфейс (Interface) указывает, какой локальный интерфейс отвечает за достижение шлюза. Например, шлюз 192.168.0.1 (интернет-маршрутизатор) может быть достижим через локальную сетевую карту, адрес которой 192.168.0.100.}} {{Определение|definition = Метрика (Metric) {{---}} числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние (необязательный параметр).}} ==Принцип действия==При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации. Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя и имеют наименьшую метрику. Если ни один из маршрутов не подходит, пакет уничтожается, а затемего отправителю возвращается ICMP-сообщение ''No route to host''. Внутри каждого пакета есть поле TTL (Time to live) при каждой пересылке значение уменьшается на единицу, когда диапазон существенно уменьшитсяи если оно становится нулем, переходить к двоичномуто пакет выбрасывается. ICMP-сообщение в данном случае ''TTL expired in transit''. ==Просмотр таблицы маршрутизации==Ниже приведены команды в разных операционных системах, с помощью которых можно посмотреть таблицу маршрутизации Windows: '''route print''' Linux: '''route -n'''
==Источники информации==
* Дональд Кнут [http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Искусство программирования. Том 3Алгоритм Эрли]* Ахо А. Сортировка и поиск. / Knuth D.E, Ульман Д. {{---}} The Art of Computer ProgrammingТеория синтакcического анализа, перевода и компиляции. VolТом 1. 3Синтаксический анализ. Sorting and SearchingПер.*[http://en.wikipediaс англ.org/wiki/Interpolation_search Wikipedia {{---}} Interpolation searchМ.:«Мир», 1978. С. 358 — 364. [[Категория: Теория формальных языков]]*[http[Категория://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия {{Контекстно---}}Интерполирующий поисксвободные грамматики]][[Категория: Алгоритмы разбора]]
