Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 11
Текст из файла (страница 11)
1 + ~1 5 = '— '. Оптимальное расположение информации па ленте (с точки зрения скорости поиска) можно определить, используя следующую теорему. Теорема Я. Пусть У.; и р; — числа, определенные выше. Размещенгге записей в таблице оптимально тогда и только тогда, когда Р~//~ > Рз/Вз > ' ' ' > Рл'/Тп. Другими словами, минимальное значение ,1, +Р (В, +1 )+ +Р к(В, + +В„) по всем перестановкам а~аз...ая из множества (1,2,...,Х) равно (19) тогда и только тогда, когда выполняется условие (20), Докааательсшво.
Предположим, что мы поменяли местами на ленте Я; и Лг о Тогда значение величины (19) станет равным не '' +Р (Тч + ' + 1ч-~ + тч) +Рыл(/~+ ''+ Хм))+ " +Ргы(Х|+" +~;, +Х.„.,)+Р(~,+" +Т,;...)+" При этом изменение будет равно Р,Л;~.~ — Р;~тЛь Если предположить оптимальность размещения (19), то любая перемена мест двух соседних записей должна приводить к увеличению времени работы, т. е.
р,/Тч > Р;~~/Ь;~п Таким образом, поскольку нз оптимальности размещения следует набор неравенств (20), нами доказана необходимость условия (20) для оптимального размещения. Докажем теперь достаточность выполнения условия (20) для оптимальности размещения. Приведенные выше рассуждения доказывают "локальную оптимальность" расположения — в том смысле, что любая перестановка двух рядом стоящих записей приведет к унелнчению среднего времени работы. Однако зто не доказывает невозможности сложного многоступенчатого обмена для улучшении производительности поиска, не доказывает, так сказать, "глобальной оптимальности". Мы рассмотрим два доказательства, в одном из которых используются знания из области компьютерных наук, а другое основано на некоторой математической хитрости.
Первое доказаптельставо. Предположим, что условие (20) выполнено. Изнестно, что любую перестановку записей можно привести к "рассортированному" состоянию, т. е. привести ее к виду 11т 1тз...Вм с использованием только перестановок даух соседних элемеитоя. Каждая из таких перестановок заменяет ... 111йт...
иа ...йтй ... длЯ некотоРых т ( 1, тем самым Уменьшал вРемЯ поиска на неотРицательиую величину ртХ1 — Р„Ь,. Следовательно, порндок расположения записей Вт Вз... Лн должен иметь минимальное время поиска, т. е. быть оптимальным, Второе доказаптсльсглво, Заменим каждую нероятиость р, иа от(с) =)тт+с — (е +т +'''+с )/Т., (21) где с — очень малое положительное число. При этом равенство хтрт(с) + - ° + янртс(с) = ртрт(с) + . + трнртс(с) спрааедлипо только н том случае, когда ят = рт, ..., ял = рм. Отсюда, я частности, следует, что я (20) равенство никогда ие будет аьтпозняться. Рассмотрим Ф! перелаионок записей. Среди иих есть, по меньшей мере, одна оптимальная, которая и соотяетстаии с нерпой частью доказательства удовлетворяет утшоаию (20). Однако поскольку теперь а условии (20) рааеистиа невозможны, то и оптимальная перестановка может быть только одна.
Следовательно, условие (20) однозначно определяет некоторую оптимальную перестановку для вероятностей р;(с), причем с достаточно мало. Исходя из иепрерыяности тот же порядок должен быть оптимален и при с = О. (Такой тип доказательств нередко используется в комбииаторной оптимизации.) Теорема 8 была доказана В. И. Смитом (тат.
Е. ВтпЫЦ [№га1 Ва~агсЫлятвттсв 1впагтег)у 3 (1956), 59-66]. В принедениых ниже упражнениях содержатся дополнительные результаты оптимальной организации файлов. УПРАЖНЕНИЯ 1. [МЗО[ Пусть все ключи поиска раяновероятны. Определите стандартное среднекеа. дратнчное отклонение числа сравнений прн успешном последовательном пояске в таблице с Ю записями. 2. [15] Измените алгоритм 6 для непользования связанных записей аместо индексов.
(Если Р указЫвает На записЬ э таблице, полагаем, что ХЗУ1Р) — ключ, 1ИРО(Р) — связанная с ключом информация и ь1йх(Р) — указатель на следующую запись. Полагаем также, что Р1йзт указывает иа первую запись, а последняя запись указывает на Л.) 3. [16] Напишите и11-программу для алгоритма нз упр. 2, Чему равно время выполнения программы (с использованием С и 5 из (1))2 ° 4. [1т] Можно ля использовать идею алгоритма т;) для таблиц э виде связанных записей (см, упр.
2)2 б. [Зд] Программа 11' выполняется существенно быстрее программы 1) прн больших значениях С, Суще«снуют лн значения С н о, при которых программа ГЗ' будет выполняться дольше, чем программа ОЗ б. [ЗО] Добавьте трн инструкции в программу тЗ', которые позволят ей выполняться за время около (З.ЗЗС + сопвтапт) и. 7. [МЗО] Определите среднее число сравнений (3) в случае "бинарного" распределения вероятности (3). 8.
[ЛМЗЗ] Найдите асимптотнческнй ряд для Н~ т прн и -+ сю; я тт 1. Исходя из множества Х из и переменных (хц..., х,), положим 1 <)и 1 — ху — — х )йп «.»1 йч Реп* = ~ Уп~(ХЛ и Ху 1<п«- 1-6и Например, Рп = гз(хм хе) ч-уз(хм ха) + Уз(хз,хз) и гхзз = 1/(1 — хг — хз) + 1!(1 — х1— хз) + 1/(1 — ха - хз). По определению полагаем Р е = Юио = 1. а) Предположим, что в самоорганизующийся файл запросы на поиск элемента??, поступакп с вероятностью ри Покажите, что после достаточно длительной работы системы элемент Л; оказывается на гл-м месте с предельной вероятностью р;Р~л гц ц, где множество Х предсчввляет собой (рц...,р~ цр'+ц °,рк).
Ь) Суммируя результат (а) для т = 1, 2,..., получаем тождество Р +Рщ -ц+- +Ре=(г' Получите отсюда следующие соотношения: /п — ги+ 11 ? и — ш+ си 1 Р. +~ ~Р<ои-ц +' ''+ ( )Ро=(;) 9л ( 1 )(З<(т-ц+ ''+( 1) ~ )Ячо = Ри с) Вычислите предельяое среднее расстояние 6, = 3 >, щр,Рл ц 1 записи Рн от начала таблицы; затем вычислите Сл = 3,, р;4. Ф 12. [Мйу[ Используйте (17) для вычисления среднего количества сравнений, необходимого для поиска в самооргаиизующемсн файле при бинарном распределении вероятностей ключей поиска (5). 13.
[Мй?[ Используя (17), вычислите Сл для распределения вероятностей (6). 14. [МЯ1 [ Даны две последователыюсти действительных чисел — (хм хз,..., х„) и (ю, рз, ..., р„), Какая перестановка индексов а1 аз... а„делает сумму 3,',. хоу „, максимальной, минимальной? ь 9. [НОВ) В тексте отмечено, что распределения вероятностей, данные в (11)., (13) и (16), приблизительно одинаковы при О < д < 1 и что среднее число сравнений с использованием (13) равно 3+, АГ+ О(?Ч' ~). а) Означает ли это, что число сравнений равно +,Х+ О(?з' ') при использовании распределения (1Ц? Ь) Верно ли это утверждение для распределения (16)? с) Сравните (11) и (16) с (13) при д < О. 10.
[МЯ0[ Наилучшее расположение записей в последовательной таблице определяется условием (4). А что собой представляет наихудшее расположение? Покажите, что имеется простое соотношение между средним количеством сравнений при наилучшем и наихудшем размещениях записей, 11. [МЯ0[ Цель этого упражншсяя заключается в анализе предельного поведения само- организующегося файла при использовании эвристического метода перемещения записи в начало файла. Сначала введем некоторые обозначения. Пусть (ик(хцхп...,х ) равно бесконечной сумме всех различных упорядоченных произведений хп х„... х„, таких, по 1 < ?ц...,?ь < нг, причем каждое хц хз,..., х~ входит во все произведения.
Йапример, Ь(х,у)= К(х'~зй(х+Р) +Р ' '(х+Р) ) =, „( —,х+ — 1). ?Л>0 ° 1б. [МЯЯ[ В тексте было показано, как оптимально расположить программы на ленте системной библиотеки для поиска только одной программы. Однако при работе с библиотекой подпрограмм, когда для работы программы пользователя необходимо загрузить различные подпрограммы, следует принять другой набор гпюдположений, В этом случае предположим, что запрос на подпрограмму у поступает с вероятностью Рз, причем вызовы различных подпрограмм независимы, Тогда, например, вероятность того, что не потребуется ни одна подпрограмма, равна (1 — Р~)(1 — Рз) .. (1 — Рл), а вероятность того, что поиск прекратится после загрузки у>й подпрограммы, равна Р, (1— Рд.н).
(1 — Рл) Если Ь1 — длина 2-й подпрограммы, то среднее время поиска будет пропорционально И Р~ (1 — Рз)... (1 — Рк) * (Ь| + бз)Рз (1 Рз) .. (1 Рл) + ' ' ' + (Яч + + г л)Рл. Каким в этом случае должна быть оптиыальиое расположение подпрограмм на ленте? 16. [МЯЯ[ (Г Ризель (Н. Шезе!).) Зачастую необходимо проверить, выполняются ли одновременно п заданных условий. (Например, может понадобиться проверить, что х > О и у < г~, и при этом не ясно, какое условие должно проверяться первым.) Предположим, что проверка 2-го условия занимает Т, единиц времени и что условие выполняется с вероятностью р, (причем эта вероятность не зависит от результатов выполнения других условий).
В каком порядке должны выполняться проверки? 17. [МЯЯ[ (В. И. Смит (Ъ'. Е. Яш)гЬ).) Предположим, имеется и заданий; уте задание занимает Т, единиц времени; крайний срок его выполнения — 11,. Другими словами, 2-е задание должно быть выполнено не позже момента )21. Какое расписание работ а~ аз... а» минимизирует»шксиыальное загшздыеание, т е. шах(Т»т»»Т»+2» '~» г Т ~+Т»+'''+2 ~ ) 19. [МУО[ (Сцепленный поиск,) Предположим, что Х записей расположены а памяти в виде линейного массива В,...Ял н вероятность поиска записи В~ равна р,. Поиск называется "сцепленным", если каждый последующий поиск начинаетсл с того места, где завершился предыдущий.
Если последовательные поиски независимы, то среднее время поиска составляет ) р;р»((ь 2), где И(1,2) — время, которое необходимо для поиска, »Я лбл начинающегося в позиции 1 и заканчивающегося в позиции у. Эта модель может быть применима, например, ко времени поиска дискового файла (при этом п(КУ) представляет собой время перемещения между 1- и у'-м пилиндрами диска). Пель данного упражнения — описать оптимальное размеп1ение записей лля сцепленного поиска в случае, когда <111, 2) представляет собой монотонно возрастающую фуихцию от [1 — 2[, т.е.
п(»,2) = бв д и И~ < Яз < . < Ил-~ (величина де не существенна). Докажите, что размещение будет оптимально тогда и только тогда, когда будет выполняться Условие либо р~ < рч < рз < рл-~ < " < р1лг 1еп либо рл < р. < рл-~ < рз < ' < р1лгю (Другими словами, наилучшее расположение — в виде "органных труб'; показанных на рис. 2.) Указанпе. Рассмотрите расположение, которому соответствуют верояттшети Ш дз .. де е гь... гз г~ 1~, . 1,„лля некоторых т > О и й > О; 14 = 2й+ ш+ 1. Покажите, что расположение о', дз...д„'зг'„...г',г',1,,1 лучше, если о'; = ппп(йог;) и г[ = шах (оо г,), за исключением случая, когда е; '= е, и ~'; = г, для всех 1, и случая о,' = г„ г'; = д, и 1з = О для всех 1 и,1.
То же самое справедливо при отсутствии з н Ю = 29+ пз. 19, [МЯО[ Продолжая выполнять упр. 13, найдите оптимальное расположение для сцепленного поиска, если функция Я(г,у) обладает следующим свойством: л(бу) + л(2 1) = с для всех 1 зе,~'. (Такая ситуация возможна, например, прл поиске на ленте без возможности обратной перемотки и с неизвестным нам направлением поиска; для 1 < 2 имеем И(1,2) Рв Рт рн Рис, 2. Распатожение в виде "органных труб" минимизирует среднее время сцепленного поиска. и+Ь(Хвчы+ . +хо) и а(11) = а+Ь(хоев+ +Хн)+т+Ь(ьв+ +гн), где т — время перемотки.) 20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
