Сист. прогр. Ч2 (1085771), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

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

Т_ср = [время сравнения] x N/2

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

ДВОИЧНЫЙ ПОИСК

Когда мы ищем слово в словаре, мы для нахождения слова не просматриваем каждую страницу. Мы делаем приблизительную оценку места расположения нашего слова в словаре (т. е. номера страницы) и открываем словарь на этой странице. Если нужного слова на ней нет, мы переворачиваем несколько страниц вперед или назад и проверяем снова. Нам известно, как идти к цели, так как мы знаем о важном свойстве словаря, а именно о том, что он упорядочен (В следует за A, a S расположена после О). Такая упорядоченность букв называется лексикографическим порядком. Более систематический путь поиска в упорядоченной таблице можно представить следующим образом. Необходимо начать поиск с середины таблицы и сравнить ключевое слово с элементом, находящимся в середине таблицы. Ключевое слово может быть равно, больше или меньше проверяемой величины. Дальнейшие действия для каждого из элементов зависят от результата сравнения:

1. Если равно, то символ найден.

2. Если больше, взять верхнюю половину данной таблицы в качестве новой таблицы для поиска.

3. Если меньше, использовать нижнюю половину таблицы.

Этот метод фактически делит таблицу пополам при каждой проверке, систематически локализуя искомую величину. Поиск является безуспешным, если длина последней подтаблицы для поиска уменьшается до 1, а искомая величина не найдена.

Такой метод поиска в таблице принципиально прост, хотя его реализация может оказаться несколько сложнее. Он известен как двоичный или логарифмический поиск. Ясно, что, поскольку каждый раз интересующая нас часть таблицы делится пополам, при поиске требуется сделать максимально приблизительно log₂(N) проверок.

N

Р ис. 13.1 Зависимость времени поиска от размерности массива N

Сравнивая время линейного поиска с временем двоичного и обозначая через А и В время одной проверки соответственно для каждого из методов, получим

Т_лин = А х N/2

Т_двоичн = В х log₂ (N)

Поскольку алгоритм двоичного поиска более сложный, можно ожидать, что константа В значительно больше чем А. Диаграмма зависимости Т от N для двух методов поиска могла бы выглядеть, как показано на рис. 19.

Таким образом, для малых N нужно использовать линейный поиск, а для больших N - двоичный. Поскольку двоичный поиск постоянно делит таблицу на 2, мы предположим для эффективности и простоты, что размер таблицы представляет собой число, являющееся степенью двойки (например, 2, 4, 8, 16, ... и т. д.). Это условие легко удовлетворяется простым добавлением необходимого числа «фиктивных» элементов в конец таблицы (например, элементов для символа ZZZZ ZZZZ).

СОРТИРОВКА

Ясно, что для некоторых целей двоичный поиск является более эффективным, чем линейный, однако такой вид поиска требует упорядоченной таблицы, которую не всегда легко получить. Таблица машинных операций (МОТ) и таблица псевдо-операций (РОТ) ассемблера являются фиксированными таблицами и могут быть упорядочены вручную. Обычно, однако, таблица не генерируется упорядоченным образом. В самом деле, таблица символов, создаваемая ассемблером, совершенно не упорядочена, так как символы запоминаются в том порядке, в каком они появляются в поле метки.

Обменная сортировка

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

То есть, обменная сортировка существенно использует любую уже имеющуюся упорядоченность в таблице. Кроме того, при каждом просмотре по крайней мере одна величина, не участвующая в дальнейшем упорядочивании, добавляется к нижней части списка (в данном случае сначала 31, затем 27, .затем 26 и т. д.). Следовательно, эффективность сортировки повышается благодаря (1) сокращению на каждом просмотре сортируемой части списка и (2) проверке на досрочное завершение.

Такая оптимизированная сортировка по грубой оценке требует NX(N- l)/2 сравнений и, таким образом, занимает время, приблизительно пропорциональное N²/2.

Исходный 1-ый 2-ой 3-й 4 –й 5-й 6-й 7-й

Список проход

19 13 05 05 01 01 01 01

13 05 13 01 05 05 05 02

05 19 01 13 13 13 02 05

27 01 19 19 16 02 09 09

01 26 26 16 02 09 11 11

26 27 16 02 09 11 13 13

31 16 02 09 11 16 16 16

16 02 09 11 19 19 19 19

02 09 11 21 21 21 21 21

09 11 21 27 27 27 27 27

11 21 27 27 27 27 27 27

21 31 31 31 31 31 31 31

Рис. 13.2. Пояснения к обменной сортировке.

На самом деле желательно бы иметь более лучшие методы сортировки, которые бы требовали еще меньше времени. Все методы сортировки могут быть отнесены к одному из трех основных типов: (1) распределительные сортировки - сортируют путем анализа элементов по одной цифре за раз; (2) сравнительные сортировки- сортируют путем сравнения ключевых слов по два за раз и (3) сортировка вычислением адреса- преобразуют ключ в адрес, близкий к тому месту, где ожидается окончательное расположение символа.

Сортировка Шелла

Алгоритм быстрой сравнительной сортировки был предло­жен Шеллом [1] и называется по его имени сортировкой Шелла. Алгоритм близок к оптимальному для сравнительных сортировок. Сортировка Шелла подобна обменной сортировке в том смысле, что она перемещает вели­чины путем перестановки пар. Однако она начинает со сравнения величин, находящихся на расстоянии «d». Это приводит к тому, что величины, которые находятся не на месте, будут перемещаться быстрее, чем при простой обменной сортировке. На каждом просмотре значение d обычно уменьшается;

d_i+1= (d_i+ 1)/2

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

Временная оценка сортировки Шелла представляет собой довольно сложную задачу, поскольку трудно установить степень воздействия одного просмотра на другой. Если используется приведенный выше метод вычисления d, число просмотров должно быть приблизительно log₂(d), поскольку при d = 1 сортировка завершается.

Просмотр 1 Просмотр 2 Просмотр 3 Просмотр 4

d =6 d=3 d=2 d=1

19 -- 19 *09 *02 *01

13 13 *01 01 *02

05 *02 02 *09 *05

27 d *09 *19 *05 *09

01 01 **11 11 11

26 *21 *05 **13 13

31 -- 31 *27 **16 16

16 16 **13 *19 19

02 *05 *21 ***21 21

09 *27 *31 *26 26

11 11 *16 *27 27

21 *26 26 **31 31

* - обмен, ** - двойной обмен, *** - тройной обмен.

Рис. 13.3. Пример сортировки Шелла.

Эмпирические исследования показали,, что сортировка Шелла требует приблизительно В x Nx (log₂ N)² единиц времени для N-элементного вектора. Коэффициент В довольно мал, так что для малых N сортировка Шелла выполняется быстрее, чем поразрядно-обменная сортировка. Пример сортировки Шелла приведен на рис. 13.3

Сортировка поразрядным группированием

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

Рассмотрим пример поразрядной сортировки чисел, показанный на рис. 13.4, из которого совершенно ясно, как работает эта сортировка. В самом деле, это в точности тот же метод, какой используется на машинах для сортировки перфокарт. Однако, при использовании его на цифровой вычислительной машине (или при ленточных сортировках) этот метод имеет серьезные недостатки. Он предусматривает два отдельных процесса - выделение и объединение - и требует много дополнительной памяти для групп.

Исходная Первое Объединение Второе Окончательное

таблица распределение распределение объединение

19 01 01

13 0) 31 0) 01,02,05,09 02

05 1) 01,31,11,21 11 1) 11,13,16,19 05

27 2) 02 21 2) 21,26,27 09

01 3) 13 02 3) 31 11

26 4) 13 4) 13

31 5) 05 05 5) 16

16 6) 26,16 26 19

02 7) 27 16 21

09 8) 27 26

11 9) 19,09 19 27

21 09 31

Выделение по последней цифре Выделение по первой цифре

Рис. 13.4. Пример сортировки поразрядным группированием.

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

Поразрядно-обменная сортировка

Более совершенной распределительной сортировкой является поразрядно-обменная сортировка, которая применяется, когда ключи задаются (или могут быть представлены) двоичными числами. Сортировка осуществляется путем рассмотрения групп ключей с одинаковыми (М) первыми битами и упорядочения внутри этих групп в соответствии со значением (М -f- 1)-го бита.

Упорядочение группы по данному биту выполняется путем просмотра группы сверху вниз до обнаружения единичного бита и снизу вверх до обнаружения нулевого бита. Соответствующие величины меняются местами, после чего сортировка продолжается. Этот алгоритм требует от программы работы с большим числом групп, и если программа составлена плохо, то может потребоваться дополнительная таблица длины N. Однако в случае хорошей программы можно сохранять информацию о делении таблицы на группы, ведя список, в который помещаются данные о вершине таблицы и точках разбиения таблицы на части, по одной для каждого бита ключевого слова. (Таким образом, для сортировки 32-разрядных слов требуется таблица, состоящая всего из 33 элементов.)

Пример поразрядно-обменной сортировки показан на рис. 13.5. Это довольно сложный пример и может быть труден для понимания - отличительная черта большинства распределительных сортировок.

Десятичные Просмотр 1 Просмотр 2 Просмотр 3 Просмотр 4 Просмотр 5 числа

19 10011 01101 00101 00001 00001

13 01101 00101 00001 00010 00010

05 00101 00001 00010 00101 00101

27 11011 00010 01101 01001 01001

01 00001 01001 01001 01011 01011

26 11010 01011 01011 01101 01101

31 11111 10011 10011 10000 10000

16 10000 11011 10000 10011 10011

02 00010 11010 10101 10101 10101

09 01001 11111 11011 11010 11010

11 01011 10000 11010 11011 11011

21 10101 10101 11111 11111 11111

pиc. 13.5. Пример поразрядно-обменной сортировки.

Если алгоритм сортировки запрограммирован так, что сортировка прекращается, когда группа содержит только одну величину, время, требуемое для поразрядно-обменной сортировки, пропорционально N X log (N), по сравнению с N X log_p (К) для сортировки поразрядным группированием (где К — это максимальный размер ключа, а р - основание системы счисления). Заметим, что поразрядно-обменная сортировка не требует дополнительных таблиц для размещения групп ключей.

Сортировка вычислением адреса

Последний пример сортировок — это сортировка вычисле­нием адреса. Она может оказаться одной из наиболее быстрых сортировок, если имеется достаточно памяти. Сортировка осуществляется путем преобразования ключа в адрес таблицы. Например, если бы ключ имел длину 4 байта, то один из возможных методов вычисления соответствующего табличного адреса мог состоять в делении ключа на общее число элементов таблицы, умножении частного на длину элемента и сложении результата с адресом таблицы. Если длина таблицы выражается числом, являющимся степенью 2, то деление сводится к сдвигу. Эта сортировка потребовала бы только N х (время вычисления адреса) единиц времени, если было бы известно, что никаким двум ключам не будет присвоен один и тот же адрес. Однако в общем случае это не так и некоторым ключам будут приписаны одинаковые адреса.

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

Характеристики

Список файлов лекций