Сист. прогр. Ч2 (Методические указания к выполнению лабораторных работ по СПО), страница 8

Десятичные Просмотр 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 х (время вычисления адреса) единиц времени, если было бы известно, что никаким двум ключам не будет присвоен один и тот же адрес. Однако в общем случае это не так и некоторым ключам будут приписаны одинаковые адреса.

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

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

Номер данных 1 2 3 4 5 6 7 8 9 10 11 12

Данные 19 13 05 27 01 26 31 16 02 09 11 21

Вычисленный 6 4 1 9 0 8 10 5 0 3 3 7

адрес

Адреса 0 0 1 3 3 5 6 7 8 9 10

Данные 01 02 05 09 11 16 19 21 26 27 31

Рис. 13.6. Пример сортировки вычислением адреса.

Пример сортировки вычислением адреса приведен на рис. 13.6. В таблице должны быть размещены 12 элементов; так как известно, что максимальное значение ключа меньше чем 36, max 31, преобразование адреса состоит в делении ключа на 3 и выделении целой части (например, 19/3 = 6 + 1/3, поэтому используется адрес 6.

Сравнение сортировок

Рассмотрим пять различных видов сортировок: обменную; Шелла; поразрядным группированием; поразрядно-обменную и вычислением адреса. Характеристики для каждой из этих сортировок представлены ниже:

Здесь N - размер таблицы, К - максимальный размер ключа (обычно 32 для Системы 360), р - основание системы счисления, А, В, С, D и Е - коэффициенты пропорциональности.

Сравнительные сортировки могут требовать время, приблизительно пропорциональное некоторой величине в диапазоне от N² до N х Iog(N). Они нечувствительны к распределению величин, хорошо используют естественную упорядоченность данных и обычно не требуют дополнительной памяти.

Распределительные сортировки обычно требуют время, грубо оцениваемое как пропорциональное N х log_p (К) (где р - основание применяемой системы счисления, К- максимальный размер ключа), потому что существует N проверяемых чисел и log_p (К) цифр в числе. Однако распределительные сортировки чувствительны к распределению величин элементов и плохо используют естественный порядок данных; кроме того, они часто требуют значительной дополнительной памяти.

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

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

ПОИСК МЕТОДОМ ПРЯМОГО ДОСТУПА

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

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

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

Первая проблема состоит в генерации случайного числа, основываясь на значении ключа. Конечно, мы на самом деле не хотим получить случайное число в том смысле, что данное ключевое слово определяет сегодня одну позицию, а завтра другую. Мы хотим задать процедуру, которая будет для заданных ключевых слов генерировать определенные позиции в таблице. Одной из хороших возможностей для четырехсимвольных ключевых слов в коде EBCDIC является простое деление ключевого слова на длину таблицы N и использование остатка. Эта схема хорошо работает, пока N и размер ключа (32 бита в нашем слу­чае) не имеют общих множителей. Для данной группы из М ключевых слов остатки должны быть довольно равномерно распределены в диапазоне 0 ... (N - 1). Другой метод состоит в обращении с ключевым словом как с двоичной дробью и в умножении ее на другую двоичную дробь:

L 1,SYMBOL

М 0,RHO

Результат - 64-битовое произведение в регистрах 0 и 1. Если значение RHO выбрано соответствующим образом, то младший 31 бит будет равномерно распределен между 0 и 1, а последующее умножение на N даст числа, равномерно распределенные на интервале 0...(N- 1). Этот метод известен как метод степенных вычетов. Он имеет то преимущество, что первый результат длиной в 31 бит может быть использован для генерирования другой равномерно распределенной величины (путем умножения вновь на RHO) в случае, если первая попытка помещения в таблицу оказалась неудачной.

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

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

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

3. Открытая адресация. Если первая проба дает позицию К и эта позиция заполнена, то проверяется следующая, К + 1 позиция и т. д. до тех пор, пока не будет найдена свободная позиция. Если поиск выходит за пределы таблицы, он возобновляется с ее начала (т. е. считается, что таблица циклическая).

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

Предположим, что таблица имеет 17 позиций (N=17), в которых должны быть размещены следующие двенадцать чисел-19, 13, 05, 27, 01, 26, 31, 16, 02, 09, 11, 21. Эти числа должны быть введены в таблицу в позиции, определяемые остатком от деления на 17; если эта позиция заполнена, то проверяется следующая позиция и т. д. На рис. 13.7 показан процесс заполне­ния таблицы двенадцатью величинами; обратите внимание на решение конфликтов для чисел 02, 09 и 11. Колонка «Число про­верок на обнаружение» дает число попыток, необходимое для того, чтобы найти соответствующие величины в таблице; таким образом, требуется 3 попытки для того, чтобы найти величину 09, и одна, чтобы найти величину 26.

Позиция Величина Число проверок Число проверок
на обнаружение на отсутствие

0 1

1 01 1 6

2 19,02* 1 5

3 02 2 4

4 21 1 3

5 05 1 2

6 1

7 1

8 1

9 26,09* 1 7

10 27,09* 1 6

11 09,11* 3 5

12 11 2 4

13 13 I 3

14 31 1 2

15 1

16 16 1 1

16 54
Рис. 13.7. Пример открытой адресации.

Колонка «Число проверок на отсутствие» дает число попыток, необходимое для того, что­бы определить, что величины в таблице нет. Таким образом, по­иск числа 54 дал бы первоначальную позицию 3 и потребовал бы 4 попытки для того, чтобы определить, что это число в таб­лице отсутствует. Известно, что число отсутствует, если при его поиске встречается пустая позиция (позиция 6 в данном слу­чае). В дальнейшем будут употребляться следующие обозначе­ния:

Длина таблицы N = 17
Количество запоминаемых величин М = 12
Плотность р =12/17 = 0,705
Число попыток для заполнения таблицы T_s = 16
Среднее число проверок на обнаруже- Т_р = 16/12 = 1,33
ние величины

Среднее число проверок на отсутствие Тп =54/16 = 3,37