Структуры данных и алгоритмы (1021739), страница 32
Текст из файла (страница 32)
Перезапись текущих элементовмножества в новую хеш-таблицу в среднем займет меньше времени, чем их ранее выполненная вставка в старую хеш-таблицу меньшего размера. Кроме того,затраченное время на перезапись компенсируется более быстрым выполнениемоператоров словарей.4.9. Реализация АТД для отображенийВернемся к АТД MAPPING (Отображение), введенным в главе 2, где мы определили отображение как функцию, ставящую в соответствие элементам области определения соответствующие элементы из области значений. Для этого АТД мы определили такие операторы.1.MAKENULL(A).
Инициализирует отображение А, где ни одному элементу области определения не соответствует ни один элемент области значений.2. ASSIGN(A, d, г). Задает для A(d) значение г.3. COMPUTE(A, d, r). Возвращает значение true и устанавливает значение г дляA(d), если A(d) определено,-в противном случае возвращает значение false.Отображения можно эффективно реализовать с помощью хеш-таблиц. Операторы ASSIGN и COMPUTE реализуются точно так же, как операторы INSERT иMEMBER для словарей.
Сначала рассмотрим применение открытых хеш-таблиц.Предполагаем, что хеш-функция h(x) распределяет элементы области определенияпо сегментам хеш-таблицы. Так же, как и для словарей, в данном случае сегментысодержат связанные списки, в ячейках которых находятся поля для элементов области определения и для соответствующих им элементов области значений. Дляреализации такого подхода надо в листинге 4.8 заменить определение типа ячеекследующим объявлением:typecelltype = recorddomainelement: domaintype;endrange: rangetype;next: tcelltypeЗдесь domaintype и rangetype — типы данных для элементов области определенияи области значений соответственно.
Объявление АТД MAPPING следующее:typeMAPPING = array[O..B-1] of Tcelltype128ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВПоследний массив — это массив сегментов для хеш-таблицы. Код процедурыASSIGN приведен в листинге 4.10. Написание процедур для операторов MAKENULLи COMPUTE оставляем для упражнения.Листинг 4.10.
Процедура ASSIGN для открытой хеш-таблицыprocedure ASSIGN ( var A: MAPPING; d: domaintype; r: rangetype ) ;varbucket: integer;current: Tcelltype;beginbucket:= h ( d ) ;current:= A[bucket];while current <> nil doif current^.domainelement = d then begincurrent?. range := r;{ замена старого значения для d }returnendelsecurrent:= currentt.next; { d не найден в списке }current:= A[bucket];{использование current для запоминания первой ячейки}new(A[bucket]);Л[bucket]T.domainelement:= d;A[bucket]t.range:= r;/A[bucket] f.next:=current;end; { ASSIGN }Подобным образом для реализации отображений можно использовать закрытоехеширование.
Ячейки хеш-таблицы будут содержать поля для элементов областейопределения и значений, а АТД MAPPING можно определить как массив такихячеек. Как и в случае открытого хеширования, хеш-функция применяется к элементам области определения, а не к элементам области значений. Мы оставляемчитателю в качестве упражнения реализацию соответствующих операторов для закрытых хеш-таблиц.4.10. Очереди с приоритетамиОчередь с приоритетами — это АТД, основанный на модели множеств с операторами INSERT и DELETEMIN, а также с оператором MAKENULL для инициализацииструктуры данных.
Перед определением нового оператора DELETEMIN сначала объясним, что такое "очередь с приоритетами". Этот термин подразумевает, что на множестве элементов задана функция приоритета (priority), т.е. для каждого элемента амножества можно вычислить функцию р(а), приоритет элемента а, которая обычнопринимает значения из множества действительных чисел, или, в более общем случае, из некоторого линейно упорядоченного множества. Оператор INSERT для очередей с приоритетами понимается в обычном смысле, тогда как DELETEMIN являетсяфункцией, которая возвращает элемент с наименьшим приоритетом и в качестве побочного эффекта удаляет его из множества.
Таким образом, оправдывая свое название, DELETEMIN является комбинацией операторов DELETE и МШ, которые былиописаны выше в этой главе.Пример 4.9. Название "очередь с приоритетами" происходит от того вида упорядочивания (сортировки), которому подвергаются данные этого АТД. Слово "очередь"предполагает, что люди (или входные элементы) ожидают некоторого обслуживания,4.10. ОЧЕРЕДИ С ПРИОРИТЕТАМИ129а слова "с приоритетом" обозначают, что обслуживание будет производиться не попринципу "первый пришел — первым получил обслуживание", как происходит сАТД QUEUE (Очередь), а на основе приоритетов всех персон, стоящих в очереди.
Например, в приемном отделении больницы сначала принимают пациентов с потенциально фатальными диагнозами, независимо от того, как долго они или другие пациенты находились в очереди.Более приемлемым для данной книги будет пример очереди с приоритетами, которая возникает среди множества процессов, ожидающих обслуживания совместноиспользуемыми ресурсами компьютерной системы. Обычно системные разработчикистараются сделать так, чтобы короткие процессы выполнялись незамедлительно (напрактике "незамедлительно" может означать одну-две секунды), т.е.
такие процессыполучают более высокие приоритеты, чем процессы, которые требуют (или уже израсходовали) значительного количества системного времени. Процессы, которые требуют нескольких секунд машинного времени, не выполняются сразу — рациональная стратегия разделения ресурсов откладывает их до тех пор, пока не будут выполнены короткие процессы. Однако нельзя переусердствовать в применении этойстратегии, иначе процессы, требующие значительно больше времени, чем "средние"процессы, вообще никогда не смогут получить кванта машинного времени и будутнаходиться в режиме ожидания вечно.Один возможный путь удовлетворить короткие процессы и не заблокироватьбольшие состоит в задании процессу Р приоритета, который вычисляется поформуле 10(ИИСп(.Р) - tM4(P).
Здесь параметр *исп равен времени, израсходованному процессом Р ранее, a *нгч — время, прошедшее от начала инициализации процесса, отсчитываемое от некоего "нулевого времени". Отметим, что в общем случае приоритеты будут большими отрицательными целыми числами, если, конечно, tHa4 не отсчитывается от "нулевого времени" в будущем. Число 100 вприведенной формуле является "магическим числом" (т.е. не поддается четкомулогическому обоснованию, а пришедшему из практики) и должно быть несколько больше числа ожидаемых активных процессов. Читатель может легко увидеть, что если всегда сначала выполняется процесс с наименьшим приоритетнымчислом и если в очереди немного коротких процессов, то в течение некоторого(достаточно продолжительного) времени процессу, который не закончился заодин квант машинного времени, будет выделено не менее 1% машинного времени.
Если этот процент надо увеличить или уменьшить, следует заменить константу 100 в формуле вычисления приоритета.Представим процесс в виде записи, содержащей поле id идентификатора процессаи поле priority со значением приоритета, т.е. тип процесса processtype определимследующим образом:•typeprocesstype = recordid: integer;pri ority. integerend;Значение приоритета мы определили как целое число. Функцию определения приоритета (но не его вычисления) можно определить так:function р ( a: processtype ) : integer;beginreturn(a.priori ty)end;Для того чтобы для выбранных процессов зарезервировать определенное количество квантов машинного времени, компьютерная система поддерживает очередь сприоритетом WAITING (Ожидание), состоящую из элементов типа processtype и использующую две процедуры: initial (инициализация) и select (выбирать). ОчередьWAITING управляется с помощью операторов INSERT и DELETEMIN.
При инициа130ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВлизации нового процесса вызывается процедура initial, которая указывает записи,соответствующей новому процессу, место в очереди WAITING. Процедура select вызывается тогда, когда система хочет "одарить" квантом машинного времени какойлибо процесс. Запись для выбранного процесса удаляется из очереди WAITING, носохраняется посредством select для повторного ввода в очередь (если процесс не закончился за выделенное время) с новым приоритетом — приоритет увеличивается на100 при пересчете времени (исп (когда £исп увеличивается на единицу).Можно использовать функцию currenttime (которая возвращает текущее машинное время) для вычисления временных интервалов, отводимых системойпроцессам; обычно эти интервалы измеряются в микросекундах.
Будем такжеиспользовать процедуру execute(P) для вызова процесса с идентификатором Р наисполнение в течение одного кванта времени. В листинге 4.11 приведены кодыпроцедур initial и select. ПЛистинг 4.11. Выделение процессам машинного времениprocedure initial ( Р: integer ) ,{initial указывает процессу с идентификатором Р место в очереди}varprocess: processtype;beginprocess.id:= P;process.priority.= - currenttime;INSERT(process, WAITING)end; { initial }procedure select;{select выделяет квант времени процессу с наивысшим приоритетом}varbegintime, endtirae: integer;process: processtype;beginprocess := TDELETEMIN ( WAITING ),-'{DELETEMIN возвращает указатель на удаленный элемент}begintime:= currenttime;execute (process.id);endtime:= currenttime;process, priority: =process. priority+100*(endtime-begintime);{ пересчет приоритета }INSERT (process, WAITING){ занесение процесса в очередь с новым приоритетом }end; { select }•4.11. Реализация очередей с приоритетамиЗа исключением хеш-таблиц, те реализации множеств, которые мы рассмотрелиранее, можно применить к очередям с приоритетами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
