Бинарный поиск

  Как было отмечено выше, если никаких дополнительных сведений о массиве, в котором хранятся данные, нет, то ускорить поиск нельзя. Если же заранее известна некоторая информация о данных, среди которых ведется поиск, например, известно, что массив данных отсортирован, то удается сократить время поиска, используя бинарный (двоичный, дихотомический, методом деления пополам — все это другие названия алгоритма, основанного на той же идее) поиск.   Итак, требуется определить место Х в отсортированном (например, в порядке неубывания) массиве А. Идея бинарного метода стара как мир. Еще древние греки говорили — "разделяй и властвуй". Вот и делим, делим пополам и сравниваем Х с элементом, который находится на границе этих половин. Отсортированность А позволяет по результату сравнения со средним элементом массива исключить из рассмотрения одну из половин. А остальное — технические детали, требующие пунктуальности — необходимого, но, к счастью, недостаточного навыка специалиста по информатике.

  Пример. Пусть Х = б, а массив А состоит из 10 элементов:                                                                              3 5 б 8 12 15 17 18 20 25.                     1-й шаг. Найдем номер среднего элемента: т=[(1+10)/2] = 5.                                      Так как 6 < А [5], далее можем рассматривать только элементы, индексы которых меньше 5:                                                                              3 5 6 8 12 15 17 18 20 25.

                    2-й шаг. Рассматриваем лишь первые 4 элемента массива, находим индекс среднего элемента этой части                                      т =[(1+4)/2] = 2, 6 > А [2], следовательно, первый и второй элементы ,из рассмотрения исключаются:                                                                               3 5 6 8 12 15 17 18 20 25.

                    3-и шаг. Рассматриваем два элемента, значение т =[(3+4)/2] = 3:                                                                               3 5 6 8 12 15 17 18 20 25.                                      А [3]= б. Элемент найден, его номер — 3.

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

Procedure Search;   Var i,j,m:Integer; f:Boolean;   Begin      i:=1; j:=N;{На первом шаге рассматривается весь массив.}      f:=False;(Признак того, что Х не найден.}      While (i<=j) And Not f Do Begin          m:=(i+j) Div 2;           {Или m:=i+.(j-i) Div 2; , так как i+(j-i) Div 2= (2*i+(j-i)) Div 2=(i+j) Div 2.}          If A[m]=X Then f:=True {Элемент найден, поиск прекращается.}           Else If A[m]<X Then i:=m+l {Исключаем из рассмотрения левую часть А.}                                       Else j:=m-l{Правую часть.}

     End   End;

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

Procedure Search (i,j:Integer;Var t:Integer); {Массив А и переменная Х глобальные величины}    Var m:Integer;    Begin       If i>j Then t:=0 Else Begin m:=(i+j) Div 2;               If A[m]<X Then Search(m+1,j,t) Else                If A[m]>X Then Search(i,m-l,t) Else t:=m        End    End;

Каждое сравнение уменьшает диапазон поиска приблизительно в два раза. Следовательно, общее количество сравнений имеет порядок O (logN).

Задания для самостоятельной работы

  1. Реализовать (рекурсивную и нерекурсивную) схему бинарного поиска с использованием "барьерной" техники.   2. Ниже по тексту приведены три версии процедуры бинарного поиска. Какая из них верная? Исправьте ошибки. Какая из них более эффективная?

Procedure Search;   Var i, j, k: Integer;   Begin      i:=l;j:=N;      Repeat         k:=(i+j) Div 2;         If X<=A[k] Then j:=k-l;         If A[k]<=X Then i:=k+l;      Until i>j   End;

Procedure Search;   Var i, j, k: Integer;   Begin      i:=l;j:=N;      Repeat         k:=(i+j) Div 2;         If X<A[k] then j:=k Else i:=k+l;      Until i>=j   End;

Procedure Search;   Var i, j, k: Integer;   Begin      i:=l;j:=N;      Repeat         k:=(i+j) Div 2;         If A[k]<X Then i:=k Else j:=k;      Until (A[k]=X) Or (i>=j)   End;

  3. Решить задачу поиска числа Х в двухмерном массиве A[1..N, 1..M] (элементы в строках и столбцах упорядочены) за время, пропорциональное O(N + M).

Хеширование

  Выше рассматривался поиск, основанный на сравнении значений элементов массива с некоторым заданным значением переменной Х (ключом). В конечном итоге определялся индекс, номер элемента в массиве, где записано данное значение X. Рассмотрим простую задачу. Количество различных буквосочетаний длиной не более 4 символов из 32 букв русского алфавита чуть больше 10^6. Мы проанализировали какой-то текст и выписали в соответствующий массив все встреченные буквосочетания. После этого на вход нашей простой системы анализа текста поступает некоторое буквосочетание. Нам необходимо ответить, встречалось оно ранее или нет. Очевидно, что каждому буквосочетанию соответствует некоторый цифровой код. Поэтому задача сводится к поиску в массиве некоторого цифрового значения — ключа. Эта задача рассмотрена ранее (разумеется, можно хранить и сами буквосочетания). При линейном поиске в худшем случае для ответа на вопрос "есть или нет" потребуется 10⁶ сравнений, при бинарном — порядка 50. Можно ли уменьшить количество сравнений и уменьшить объем требуемой оперативной памяти, резервировать не 10⁶, а, например, 10³ элементов памяти? Обозначим цифровой аналог буквосочетания символом R, 'а адрес в массиве (таблице) через А. Если будет найдено преобразование (R), дающее значение А такое, что выполняется достаточно быстро; случаев, когда (R1) = (R2), будет минимальное количество, то задача поиска трактуется совсем иначе, чем рассмотрено выше. Этот способ поиска называется хешированием (расстановкой ключей, рандомизацией и т.д.). Итак, ключ преобразуется в адрес, в этом суть метода. Требование по быстродействию очевидно — это одна из задач при составлении любого алгоритма, ибо быстродействие компьютера ограничено. Второе требование не столь очевидно. Предположим, что анализируется текст из специфической страны "Д..", в которой все слова начинаются с буквы "о" и в качестве выбран цифровой аналог первой буквы. В этом случае получаем одно значение А для всех слов (от чего уходили, к тому и пришли, но в стране "Д..." все возможно). Следовательно, необходимо выбирать такое преобразование , чтобы количество совпадений адресов (А) для различных значений ключей (R) (такие совпадения называют коллизиями) было минимально. Полностью избежать коллизий не удается. Для любого преобразования (хеш-функции) можно подобрать такие исходные данные, что рассматриваемый метод поиска превращается в линейный поиск. Однако цель построения хеш-функции ясна — как можно более равномерно "разбрасывать" значения ключей по таблице адресов (ее размер обозначим через М) так, чтобы уменьшить количество коллизий. Итак, реализация метода логически разбивается на две составляющие:   •построение ;   • схема разрешения коллизий.   Коротко рассмотрим их.   Первый вопрос. Так или иначе для значения ключа R находится цифровой аналог, обозначим его через t.   Первый способ: в качестве М выбирается простое число и находится остаток от деления t на М(t MOD М).   Второй способ: находится значение t². Из этого значения "вырезается" q каких-то разрядов (лучше средних).   Значение q выбирается таким образом, чтобы 2^q было равно М; третий способ: w разрядов для представления ключа t разбиваются на части длиной q разрядов. Выполняется, например, логическое с ложение этих частей, и его результатом является номер элемента в таблице адресов. Считается (если не заниматься подбором специальных входных данных), что все эти способы дают достаточно хорошие в смысле количества возможных коллизий хеш-функции.   Из известных методов разрешения коллизий рассмотрим один — "метод цепочек". Его суть в том, что элементом таблицы является ссылка на список элементов, имеющих одно значение хеш-функции. Рисунок справа иллюстрирует этот метод.                                                       

  Качество хеш-функции оценивается средней длиной списков. Рассмотрим следующую простую задачу. Дано N(1<=N<=15 000) различных двоичных чисел длины L (1 <= L <= 100), а также Q (1 <= Q <= 20 000) запросов или двоичных чисел также длины L. Требуется определить для каждою запрошенного числа, встречается оно или нет среди N ранее определенных чисел. Время решения задачи ограничено 30 секундами.   Заметим, что сложность "лобового" решения имеет порядок O(N • L• M), поэтому по временному ограничению оно вряд ли приемлемо. Используем метод хеширования. Построим три различные хеш-функции, а для разрешения коллизий будем использовать "метод цепочек". Проверим решения на случайных тестах. Обозначим цифрой "1" хеш-функцию, использующую деление на простое число, "2" — возведение в квадрат, "3" — логические операции с подстроками фиксированной длины, выделяемые из значения ключа. Оцениваем минимальную и максимальную длины списков (Мin, Мах) и время решения ( t ). В таблице приведены результаты нескольких экспериментов.

N	L	Q	Хеш-функция	Min	Мах	t
15000	100	20000	1 2 3	14 16 11	46 45 50	9 27 10.9
15000	80	20000	1 2   3	13 14 16	46 49 48	7.3 18 8.9
10000	50	20000	1 2 3	6 10 0	34 34 106	4.3 8.7 5.8

  Рассмотрим реализацию первой хеш-функции.   Структуры данных.

ConstInputFile='Input.Txt'; OutputFile'Output.TxT'; MaxN=15000; MaxL=100; MaxTbl=547; {Размер таблицы.} Type TNum=Array [0..MaxL Div 8] Of Byte;{Массив для хранения двоичного числа.                                                                                 В этом есть определенная сложность, "затемняющая"                                                                                 суть решения, но чисто техническая.}            PRec=^TRec;            TRec=Record num: TNum; next: PRec; End; Var N, Ln, Q, LnDv8: Integer;        Tbl: Array[0..MaxTbl-1] Of PRec;{Таблица указателей (ссылок).}

  Ряд вспомогательных процедур и функций.

Procedure ReadNum(Var nw: TNum);{Считываем число.}   Var i: Integer;ch: Char;   Begin      FillChar(nw, SizeOf (nw), 0);      For i:=0 To Ln-1 Do Begin         Read (ch);         nw[i Div 8]:=nw[i Div 8]*2+Ord (ch)-Ord('0');      End;      ReadLn   End;

Procedure AddTRec (Var P: PRec; Const nm: TNum) ; {Добавить запись в хеш-таблицу. Вставка осуществляется в начало списка.}   Var smp: PRec;   Begin      If P=nil Then Begin New (P) ;P^ .next:=nil; P^.num:=nrn End       Else Begin New (smp); smp^.next:=P^ .next; smp^.num:=nm; P^.next:=smp End   End; Function GetNum(Const p: TNum): Integer; {Получить хеш-значение для числа. Преобразовать представление в виде элементов массива в числовое значение и найти остаток   от деления на простое число, равное размеру таблицы указателей (ссылок).}   Var i, nw: LongInt   Begin      nw:=0;      For i:=0 To LnDv8 Do nw:=((nw shl 8)+p[i]) Mod MaxTbl;      GetNum:=nw   End; Procedure Init;   Var i: Integer; nm: TNum;   Begin      FillChar(Tbl, SizeOf (Тbl) , 0) ;      Assign (Input, InputFile); Reset(Input); ReadLn(N, Ln, Q); LnDv8:=(Ln-1) Div 8;      For i:=1 To N Do Begin         ReadNum (nm) ;         AddTRec(Тbl [GetNum(nm)], nm) {Добавляем элемент в хеш-таблицу.}      End;      Assign(Output, OutputFile); Rewrite(Output)   End; Function IfEq(Const a, b: TNum): Boolean;{Сравнение двух ключей.}   Var i: Integer;   Begin      i:=0;      While (i<=LnDv8) And (a [i] =b [i] ) Do Inc(i);      IfEq:=i > (LnDv8)   End;

  Основная процедура.

Procedure Solve;   Var i: Integer; nw: TNum; fn: Boolean; uk: PRec;   Begin   For i:=l To Q Do Begin     ReadNum (nw);{Читаем очередное число.}     uk:=Tbl[GetNum(nw)];{Вычисляем адрес в хеш-таблице.}     fn:=False;     While (uk<>nil) And (Not .fn) Do Begin {Просматриваем список.}          fn:=IfEq(nw, uk^ .num) ; {Проверяем, есть ли совпадение?}          uk:=uk^ .next {Переходим к следующему элементу списка.}     End;     If fn Then WriteLn ('YES') Else WriteLn ('NO') {Выводим результат.}   End End;

  Основная программа.

Begin Init; Solve; Close(Input); Close(Output) End.

Задания для самостоятельной работы

  1. Для реализации второй хеш-функции (средние биты квадрата числа) требуется изменить функцию GetNum и добавить одну константу. Проведите данную модификацию программы, используя следующую "заготовку".

Const... HwBite=9; МахТbl=1 shl HwBite; {Размер таблицы указателей 2⁹.} Function GetNum(Const p: TNum): Integer;{Найти адрес таблицы указателей для значения ключа р. Программный код "утяжелен" из-за                                                                                  необходимости использовать массив для хранения значения ключа.}   Var i, j, nw: LongInt;clc: Array[0..(MaxL Div 8)*2] Of LongInt;   Begin      FillChar(clc, SizeOf(clc), 0);      For i:=0 To LnDv8 Do {Необходимо перемножить значения всех байт.}        For j:=0 To LnDv8 Do Begin           Inc(clc[i+j], p[i]*LongInt (p[j]));Inc(clc[i+j+1], clc[i+j] Div (1 shl 8));           clc[i+j]:=clc[i+j] Mod (1 shl 8)        End;        nw:=0; j:=((HwBite-1) Div 8+1);        For i:=LnDv8-(j Div 2) To LnDv8+(j+l) Div 2-1 Do        nw:=(nw shl 8+clc[i]) Mod MaxTbl;        GetNum:=nw   End;

  2. Реализация третьей хеш-функции также требует изменения только одной составной части рассмотренной выше логики. Выполните модификацию программы с использованием нижеприведенной "заготовки".

Const ... HwBite=9;MaxTbl=1 shl HwBite; Function GetScBt (p: Byte): Byte;   Var sc: Integer;   Begin      sc:=0; While p<>0 Do Begin p:=p shr 1; If p Mod 2=1 Then Inc (sc) End;      GetScBt:=sc Mod 2   End; Function GetNum(Const p: TNum): Integer;{Получить хеш-значение для ключа.}   Var i, nw, geth, pp: LongInt;   Begin      nw:=0;      If LnDv8+1<=HwBite Then       For i:=0 To LnDv8 Do nw:=nw*2+GetScBt(p[i])      Else Begin pp:=(LnDv8+l) Div HwBite; geth:=0;        For i:=0 To LnDv8 Do Begin           geth:=geth Xor GetScBt(p[i]) ;           If (i>0)And(((i Mod pp=0) And (i Div pp<HwBite)) Or (i=LnDv8))            Then Begin nw:=nw*2+geth; geth:=0 End        End      End;      GetNum:=nw   End;

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

20. Методы сортировки.

Алгоритмы сортировки

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

  Const NMax=... ;   Type MyArray=Array[l..NMax] Of Integer;   Var A:MyArray;

  Суть большинства алгоритмов сортировки от такого упрощения не изменяется. Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки. В основном мы будем оценивать эффективность количеством операций сравнения (порядком этого значения). Заметим, что элементы массива можно сортировать:   • по возрастанию — каждый следующий элемент больше предыдущего — А [1] < А [2] < ... < A[N];

  • по неубыванию — каждый следующий элемент не меньше предыдущего А[1] <= А [2] <= ... <= A[N];

  • по убыванию — каждый следующий элемент меньше предыдущего А[1] > А [2] > ... > A[N];   • по невозрастанию — каждый следующий элемент не больше предыдущего А [1] >= А [2] >= ... >= A [N].   Научившись выполнять одну сортировку, изменить ее, чтобы получить другую, не составляет особого труда.   Рассмотрим некоторые из алгоритмов сортировки так, как они излагались и изучались на занятиях по этой теме.