Упорядоченные таблицы

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

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

Алгоритм двоичного поиска можно описать следующей процедурой на языке Алгол-60:

procedure bisearch (T, n, К, i);

value n, К; integer n, К, i; integer array T;

comment T[1:n] — массив, содержащий значения ключей,

К — заданное значение ключа.

Результат выполнения процедуры:

i ¹ 0 — номер табличной записи, имеющей заданное значение ключа;

i = 0 — если в таблице нет записи с заданным значением ключа;

begin integer р; р:= 1;

for i:= (р + n)¸2 while p < n do

if T[i]<К then р:=i + 1 else n: = i;

i: = if T[р]=K then p else 0

End

Длина двоичного поиска D₂ определяется формулой (2.9), что при достаточно больших n почти равно теоретическому нижнему пределу для методов поиска, основанных только на сравнении признаков(значенийключа). Теоретический нижний предел равен

log₂(n+l).

В общем случае двоичный поиск значительно эффективнее последовательного просмотра. Например, для таблицы из 1000 записей средняя длина последовательного просмотра равна 500, а длина двоичного поиска —только 11.

Средняя длина последовательного просмотра в таблице, упорядоченной по частоте обращения к записям, существенно зависит от распределения частот обращения и определяется по общей формуле (2.7). Если относительно небольшое число записей приходится отыскивать очень часто, то средняя длина поиска может оказаться значительно меньше, чем при двоичном поиске. Это иногда используют при составлении постоянных таблиц транслятора, например таблиц основных символов входного языка.

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

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