AOP_Tom3 (1021738), страница 109
Текст из файла (страница 109)
Жино был первым человеком, сформулировавшим и объяснившим важность соотношений, подобных закону "80 — 20" (10). Люди, как правило, не понимают сути таких распределений; они часто говорят о законе "75-25" или "90 -10", как если бы главное, что придает смысл закону, заключалось в том„что в законе "и — 6" выполняется равенство а+ 6 = 100. Однако, как можно убедиться из (12), сумма 80+ 20 здесь нн при чем... Еще одно дискретное распределение, аналогичное (11) и (13), было предложено Д. Удни Юлом (С, Пдпу Уи1е) при изучении увеличения со временем количества биологических видов при различных моделях эволюции (Р)д)ов.
Тгапв. В213 (1924), 21 — 87). Распределение Юла допускает значения В ( 2: [ю — в) [м-в) . (1б) Граничные значения с = 1/Нм и с = 1/з1' получаются при д = 0 и д = 1. Имеется еще одна часто цитируемая работа, однако ее популярность связана не с ес важностью, а лишь с тем, что это первая работа американского автора на эту тему [А!Егеп Л. (,отиса,,У 'г)ээ!ппдвоп Аеас!ету оГЯс!епсеэ 16 (1928), 317-323[. С. =1+2 ~ "'"' =-+~ 16(<вбей 16(« и 1 в (17) Например, если р, = 1/!1' при 1 < 1 < Х, самоорганизующаяся таблица будет находиться в неупорядоченном состоянии, а приведенная формула сведется к хорошо известному нам значению (Х + 1)/2.
В общем случае полученное в (17) значение всегда меньше удвоенного оптимального значения из (3), так как См < 1+ 22„'', (в' — 1) р. = 2См — 1. В действительности См всегда меньше, чем (л/2) См [С!1пп8, Йа1е!а, апб Яеушопг, .!. Со|пр. Яуэй Ясй 36 (1988), 148-1э7[. Эту константу нельзя улучшить, так как при рм пропорциональных 1Дэ, достигается равенство. Посмотрим, насколько хорошо этот метод работает при распределении вероятностей по закону Зипфа (8).
В этом случае мы имеем: 1 (с/1)(с/1) 1 1 См =-+ ~, =-+с ~ 1<ЬУ<п '/ '/~ ~<чу<<к м 1 эм м = — +с'~ (Нмз; — Н;) = — +с~ Н; — ге~~ Н; а=1 сц ~=1 = 1 + с((2Х+ 1)Нэм — 2Н вЂ” 2(У+ 1)Нвг + 2%) "Самоорганнзующийся" файл. Приведенные вычисления вероятностей хороши, однако в большинстве случаев распределение вероятностей априори не известно. Можно было бы хранить в каждой записи счетчик обращоний к ней и на основании полученных показаний переупорядочивать записи.
Конечно, во многих ситуациях, как мы видели, такое переупорядочение приведет к значительной экономии времени; тем не менее зачастую не стоит выделять память для счетчиков — гораздо разумнее использовать ее, например, для технологии непоследовательного поиска, о чем будет рассказано ниже в данной главе. Существует используемая многие годы простая схема, происхождение которой, увы, не известно. Эта схема позволяет получить неплохие результаты без привлечения счетчиков: когда запись успешно обнаружена, она перемещается в начало таблицы.
Идея этой "самоорганизующейся" технологии заключается в том, что наиболее часто используемые записи в результате будут располагаться в начале таблицы. Предположим, что Х ключей встречаются среди аргументов поиска с вероятностями (рм рэ,...,рм) и при этом каждый поиск совершается неаависимо от других.
В таком предположении можно показать, что среднее количество сравнений, необходимых для поиска записи в таком самоорганнзующемся файле стремится к предельному значению (см. упр. 11): (18) = -'+ с(Х!п4 — 1пбб+ 0(1)) -2М/!8Х (см. формулы 1.2.7 — (8) и 1.2.7 (3)). Полученная величина существенно лучше, чем -'Х при достаточно больших Х, и только в!п4 1.386 раз превышает количество сравнений при оптимальном размещении записей (см. (9)). Вычислительные эксперименты с реальными таблицами символов компиляторов показали, что зачастую метод самоорганизации работает даже лучше, чем предсказывается: это связано с тем, что последовательные успешные поиски ие являются независимыми и небольшие группы ключей зачастую вместе участвуют в поиске. Впервые такая гамоорганизующаяся схема была исследована Джоном Мак-Кэйбом (доЬп МсСаЬе) (ОрегаБоиа Веэеагс!1 13 (1965), 609 618], который и получил соотношение (17). Мак-Кэйб предложил также другую интересную схему, при которой успешно обнаруженный ключ, не находящийся в начале таблицы, просто меилетисл местами с предыдущим, а не перемещается в начало таблицы.
Ои также установил, что предельное среднее время поиска для этого метода, в предположении независимости поисков, не превышает значения из (17). Несколькими годамн позже Рональд Л. Ривест (Вопа16 Ь. В!неэг) доказал, что метод перестановки при длительной работе использует строго меньше сравнений, чем метод перемещения в начало таблицы— естественно, исключая случаи, когда Х < 2 или когда все ненулевые вероятности равны (САСИ 19 (1976), 63 67). Однако переход к асимптотическому пределу в этом случае происходит более медленно, чем при перемегцении записей в начало таблицы (3. В. В!ьпег, 81СОМР 8 (1979), 82 — 110). Более того, Дж.
Л. Бентли (5. Ь. Вепь1еу), К. К. Мак-Геч (С. С. МсСеосЬ), Д. Д. Слитор (В. В. 81еасог) и Р. Е. Таржан (В. Е. Тат!ап) доказали, что при методе перемещения в начало таблицы количество обращений к памяти никогда не превысит более чем в четыре раза это количество для любого алгоритма при работе с линейными списками, заданного любой последовательностью обращений; методы же подсчета частот и перестановки таким свойством не обладают !САСМ 28 (1985), 202 — 208, 404 — 411!. См. также БОВА 8 (1997), 53 — 62, где приведены интересные результаты эмпирического изучения более 40 эвристических методов самоорганизующихся списков, проведенных Р.
Бачрачем (В. ВасЬгасЬ) и Р. Эль-Янивом (Н. Е1-Уап!ч). Поиск на ленте с неравными записями. Рассмотрим теперь несколько иную задачу. Предположим, что таблица, в которой проводится поиск, хранится на ленте и при этом отдельные записи имеют различную длину. Примером такого хранения информации может служить лента системной библиотеки старых операционных систем.
Стандартные системные программы (например такие, как компиляторы, ассемблеры, загружаемые подпрограммы н генераторы отчетов) являются "записями" на чтой ленте, и большинство пользовательских заданий должно начинать выполнение с поиска необходимого программного обеспечения, Такая постановка задачи делает неприемлемым анализ алгоритма 8, поскольку шаг 83 теперь выполняется за разные промежутки времени для разных записей. Поэтому мы не можем ограничиться в нашем анализе только количеством сравнений. Пусть Ь; — длина записи Д, и пусть р, — вероятность того, что выполняется поиск именно этой записи.
В таком случае среднее время поиска примерно пропорционально Р1 Ег + РгЯг + Ег) + ' ' '+ Рлч(йг + гг + Вг + ' ' '+ г л). (19) При Вг — — Вг = = Ьл = 1 это выражение сводится к уже исследованному нами случаю (3). Представляется разумным и логичным разместить записи, обращения к которым происходят чаще, чем к другим, в начале ленты, однако в данном случае зто вовсе не такая хорошая мысль, как кажется! Например, предположим, что у нас есть лента с двумя программами - — А и В, причем обращения к А происходят в два раза чаще, чем к В, но при этом она в четыре раза длиннее. Тогда Х = 2, рл = г, Вл = 4, Рн = -', Ьн = 1.
Ег ш мы поместим на ленту сначала А, а затем В. руководствуясь описанной '"'логикой", среднее время поиска станет равным '; 4+ -' 5 = ' —,г. Если же воспользоваться "нелогичным" решением, поместив на ленту сначала В, а затем .4, среднее время поиска сократится до у 1+ — 5 = —. г и Оптимальное расположение информации на ленте (с точки зрения скорости поиска) можно определить, используя следующую теорему. Теорема Б. Пусть Рн и Р< †. числа, определенные выше. Размещение записей в гвбгпгце оптимально тогда и только тогда, когда Рг/Вг ~ Рг/1г ~ ''' 'Рл'/ьм. (20) Другими словами, минимальное значение Рю Та1 +Раг(Тю + Таг) + ' ' ' + Р и (~а1 + ' ' ' 1 Так) по всем перестановкам а, аг... ам из множества (1,2,..., лг) равно (19) тогда и только тогда, когда выполняется условие (20), Доказаглельстоо. Предположим, что мы поменяли местами на лепте Вн и В, Тогда значение величины (19) станет равным не +Р(г1+- +Ь, г+Ь,)+Р; 1(ьг+ +г., г)+...
" + Р;,.г(Вг + " + ~,, + Т„.„,) +Р,(11 + " + В„,) + " Прн этом изменение будет равно Р,Т,.ь1 — рг ы Т, Если предположить оптимальность размещения (19), то любая перемена мест двух соседних записей должна приводить к Увеличению вРемени Работы, т. е. Р,/А, ) Р,ч.1/В,.ы. Таким обРазом, посколькУ из оптимальности размещения следует набор неравенств (20), нами доказана необходимость условия (20) для оптимального размещения. Докажем теперь достаточность выполнения условия (20) для оптимальности размещения. Приведенные выше рассуждения доказывают "'локальную оптимальность" расположения в том смышге, что любая перестановка двух рядом стоящих записей приведет к увеличению среднего времени работы.
Однако это не доказывает невозможности сложного многоступенчатого обмена для улучшения производительности поиска, не доказывает, так сказать, "глобальной оптимальности". Мы рассмотрим два доказательства, в одном из которых используются знания из области компьютерных наук, а другое основано на некоторой математяческой хитрости. Первое доказательство. Предположим, что условие (20) выполнено. Известно, что любую перестановку записей можно привести к "рассортированному" состоянию, т. е.
привести ее к виду В, Вз... Вгя с использованием только перестановок двух соседних элементов. Каждая нз таких перестановок заменяет ... В)В;... на ... В,В,... для некоторых 1 ( 1, тем самым уменьшая время поиска на неотрицательную величину р,? — рэЦ. Следовательно, порядок расположения записей Вг Вз . Вл должен иметь минимальное время поиска, т. е. быть оптимальным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
