Сист. прогр. Ч2 (Лекции по СПО), страница 8

Бремя, требуемое для сортировки, может быть уменьшено путем отведения для таблицы большей памяти, чем требуется для размещения сортируемых величин. Это обеспечит больше свободного пространства в таблице и создаст меньшую вероятность конфликтов адресов, длительных поисков и перемещений. При использовании таблицы, большей приблизительно в 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

величины

Ниже приведены сравнительные времена для упакованной таб­лицы, использующей поразрядно-обменную сортировку и двоич­ный поиск;

Количество попыток для за- T_s = М + М х Iog₂ (M) = 55

полнения и сортировки

Среднее число проверок на Т_р = Iog₂ (М) = 3,58

обнаружение величины

Среднее число проверок на Т_п= Iog₂ (M) =3,58

отсутствие величины

Таким образом, оказывается, что метод открытой адресации имеет значительное преимущество в скорости, но платит за это тем, что использует таблицу, размер которой приблизительно на 50 процентов больше. Более того, таблица не может быть уплот­нена после ее первоначального заполнения, а выделенная об­ласть не может быть легко разделена между несколькими таб­лицами. Последний и очень серьезный недостаток состоит в том, что очень трудно удалить какую-либо величину из таблицы - нельзя просто обнулить эту ячейку, поскольку это может нару­шить цепочку адресов.

Интересно рассмотреть ожидаемое время проверок для мето­дов со случайными элементами. Более простым методом для оценки является метод случайного элемента с повторениями. Бу­дем считать, что таблица из N позиций с К— 1 элементами уже заполнена. Определяем плотность р = (К— 1)/N.

Число проверок для запоминания К-го элемента;

L_k = 1 / ( 1-р)

Число проверок для поиска:

Tp = 1/p x log_e (1/ (1 — р))

Эти формулы очень интересны и хорошо иллюстрируют зависи­мость между временем поиска и плотностью таблицы.

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

Tp (p) = 1 + p/2 x 1/ (1 — р)

-а число проверок на отсутствие величины в таблице приблизи­тельно равно

Tn (p) = 1/ (1 — р)

Для плотности р = 12/17 это дает:

Tp = 1 + 6/5 = 2.2

Tn = 17/5 = 3.4

что хорошо согласуется с результатами рассмотренного при­мера. ГЕНЕРИРОВАНИЕ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Существует много алгоритмов генерирования псевдослучай­ных чисел, причем одним из наиболее часто используемых яв­ляется метод степенных вычетов. Мы отсылаем читателя к книге Хэмминга (Hamming) [2] или Кнута [3].

РЕЗЮМЕ

Мы рассмотрели структуру двупросмотрового ассемблера. Во время первого просмотра определялись значения символов, а во втором просмотре генерировалась объектная программа. При этом подчеркивалось, что в процессе проектирования ассемблера или любого другого компонента программного обеспечения вы­деляется шесть основных этапов: