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

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

Текст из файла (страница 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].

РЕЗЮМЕ

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

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

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