Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 10
Текст из файла (страница 10)
Это пРавило гласит, что 80% транзакций работают с 20% файла. Оно фрактально, т. е. оно применимо и к активным 20% файла; следовательно, 64% транзакций работают с 4% файла н т. д. Другими словами, Р! + Рэ + ' ' ' + Рдон ( О) кт .80 (10 В + Рэ+Рз+ ' ' '+Р одно из точно удовлетворяющих правилу распределений (при и, для всех и.
Вот кратных 5): Р1 =с1 Рэ =(2 — 1)с, Рз =(3 — 2 )с, (лс (кс 1)з) где с = 1/Хз, 9 = = 0.1386. 108.80 (12) !08.20 Как ны мо кете убедиться. в этом случае для всех и Рв + Рэ+ ° . +Р = спз. Вероятности из (11) не очень удобны для работы; однако пз — (п — 1)з = Юпз ' (1+ О(1/и)), е Инеетсн в внлу случай равнэверонтного понвленнн ключей, — Нрн.н. ред. и при оптимальном размещении записей экономится около трети времени, которое уходит на поиск, по сравнению со временем, необходимым при случайном размещении записей*. Естественно, распределении (5) и (6) сугубо искусственны и не могут служить хорошим приближением реальных примеров.
Более типично для реальных ситуаций распределение Зипфа: н поэтому можно воспользоватьсв более простым распределением, приближенно удовлетвориюшим правилу "80-20": р1=с/1, рг=с/2, ..., рл=с/Н (13) гдес= 1/Н~~ ~. Здесь,каки ранее,й= )о8.80/!а8.20,аН~~', -- Х-егармоническое число парвдка е, а именно — 1 '+2 '+ ° ° + Х '. Обратите внимание на схожесть этого распределения вероятности с законом Зипфа (8); с изменением 6 от 1 до О закон распределении изменвется от равномерного к закону Зипфа. Применив формулу (3) к распределению (13), получим среднее число сравнений длн закона "80-20" (см. упр.
8): Сл = Н' ю/Н" "= ~~ +Ор"-а) = 0.122Х 6+1 (14) Изучав частоту употребления слов, Ю. С. Шварц (Е. Б. Бс)птагсг) (см. интересный график на с. 422 в дАСМ 10 (1963)) предложил использовать в качестве более точного приближении распределение (13) с небольшими ошрицательпмми значениями 6. Тогда значение Н!-В) Н!1-е! Н О 771-~.2В 1-ьв = (1.6)а — ) '"" (15) с 2с (Х вЂ” 1)! с с 2 - 6 ' Рз (3 - 6)(2 - 6) ' " ' " Р - В) ... (2 - 6) ( -~) ' получаетсл существенно меньше, чем в случае (9) при Х вЂ” > ао.
Распределении, подобные (11) и (13), были впервые изучены Вильфредо Парето (ЧШгсч)о Раге1о) в связи с распределением богатства людей (Сошв д'Есопопне Рой- 1!Оие 2 (1 аизаппе: Коибе, 1897), 304-312). Пусть рь пропорционально састоинию к-га по богатству индивидуума, а рм — состоянию более бедного индивидуума, занимающего в списке богатых Н-е место. Тогда /с/Х представляет собой вероятность того, что состояние более богатого человека не менее чем в х = рь/рм раз превосходит состояние более бедного. Таким образом, при рь = оке ' и т. = (Й/ "т')е ' описанная вероятность равна х '7!' ~!.
Такое распределение в настовщее время называется распределением Парешо с параметра и 1/(1 — 6). Любопытно, что Парето не понимал сути собственного распределения; он полагал, что значение 6, близкое к О, ссютветствует более уравнительному обществу, чем значение, близкое к 1! Ега ошибка была исправлена Коррадо Жнни (Саггадо Ои1!) !Агг1' де!!а Ш В!ишане дейа Бос!ега Найапа рег Б Ргойгееео с!е!!е Бс1епге (1910), переиздана в его Мешине с5 Мегода)айза Бгаг!ебсл 1 (Наше, 1955), 3-120).
Жлна бьп первым человеком, сформулировавшим и объяснившим важность соотношений, подобных закону "80-20" (10). Люди, как правило, не понимают сути таких распределений; они часто говорит о законе "75-25" или "90-10", как если бы главное, что придает смысл закону, заключалось в том, что в законе "и-5" выполнвется равенство а+5 = 100.
Однако, как можно убедиться из (12), сумма 80+ 20 здесь ни при чем... Еще одно дискретное распределение, аналогичное (11) и (13), было предложено Д. Удни Юлом (О. (Мпу Уи!е) при изучении увеличения са временем количества биологических видав прн различных наделах эволюции ~Р л!оа Тгапя. В213 (1924), 21 — 87).
Распределение Юла допускает значения 6 < 2: (17) Например, ели р, = 1/Х при 1 < 1 < Н, самоорганизующаяся таблица будет находиться в неупорядоченном состоянии, а приведенная формула сведется к хорошо известному нам значению (Х + 1)/2. В общем случае полученное в (17) значение всегда меньше удвоенного оптимального значения из (3), так как См < 1+ 2Я„., (у — 1) рв = 2Сп — 1. В действительности См всегда меньше, чем (к/2) Са (С)шпй, На)е)а, апб Яеуп1опг, з. Сошр. Яуза Ясб 36 (1988), 148-157).
Эту константу нельзя улучшить, так как при ру, пропорцпональных 1/у'-, достигается равенство. Посмотрим, насколько хорошо этот метод работает прн распределении вероятностей по закону Зипфа (8). В этом случае мы имеем: 1 (%)(с/у) 1 1 2,, с/(+ с/у 2, 1+ у в ('„-') с (м-в) . (Рб) Граничные значения с = 1/Нм и с = 1/Л получаются при В = 0 и В = 1.
Имеется еще одна часто цитируемая работа, однако ее популярность связана не с ее важностью, а лишь с тем, что это первая работа американского автора на эту тему (А11гед Л. 1 огха, 2 )тазй1пйгоп Асадешу оГ Яаепсев 16 (1926), 317-323). "Самоорганизующийсян файл. Приведенные вычисления вероятностей хороши, однако в болыпннстве случаев распределение вероятностей априори не известно. Можно было бы хранить в каждой записи счетчик обращений к ней и на основании полученных показаний переупорядочивать записи. Конечно„ во многих ситуациях, как мы видели, такое переупорядочение приведет к значительной экономии времени; тем не менее зачастую не стоит выделять память для счетчиков — гораздо разумнее использовать ее, например, для технологии непоследовательного поиска, о чем будет рассказано ниже в данной главе. Существует используемая многие годы простая схема., происхождение которой, увы, не известно. Эта схема позволяет получить неплохие результаты без привлечения счетчиком когда запись успешно обнаружена, она перемещается в начало таблицы.
Идея этой "самоорганизующейся" технологии заключается в том, что наиболее часто используемые записи в результате будут располагаться в начале таблицы. Предположим, что Ю ключей встречаются среди аргументов поиска с вероятностями (рырэ,...,рм) и при этом каждый поиск совершается независимо от других. В таком предположении можно показать, что среднее количество сравнений, необходимых для поиска записи в таком самоорганизующемся файле стремится к предельному значению (см. упр. 11): С,=„2Е: — =-, 2 р в 1 упру „,«у Р1+Ру . Р!+Ру = з1 + с((2Х + 1)Нем — 2Х вЂ” 2(Л + 1)Нн + 2Ю) = 1' + с (д' )и 4 — !и Ю + О (1) ) ~ 2Ю/ !8 Х (18) Поиск на ленте с неравнымн записями.
Рассмотрим теперь несколько иную задачу. Предположим, что таблица, я которой проводится поиск, хранится на ленте и при этом отдельные записи имеют различную длину. Примером такого хранения информации может служить лента системной библиотеки старых операционных систем.
Стандартные системные программы (например такие, как компиляторы, ассемблеры, загружаемые подпрограммы н генераторы отчетов) являются '"записямн" на этой ленте, н болыпинство пользовательских заданий должно начинать выполнение с поиска необходимого программного обеспечения.
Такая постановка задачи делает неприемлемьгм анализ алгоритма Б, поскольку шаг 83 теперь выполняется за разные промежутки времени для разных записей. Поэтому мы не можем ограничиться в нашем анализе только количеством сравнений. Пусть Ц вЂ” длина записи В, и пусть р; — веронтность того, что выполняется поиск именно этой записи. В таком случае среднее время поиска примерно (см. формулы 1.2.7-(8) и 1.2.7 — (3)), Полученнан величина существенно лучше, чем 1 йЮ при достаточно больших Х, и только в!п4 1.386 раз превышает количество сранненнй при оптимальном размещении записей (см. (9)). Вычислительные эксперименты с реальными таблицами символов компиляторов показали, что зачастую метод самоорганизации работает даже лучше, чем предсказывается; это связано с тем, что последовательные успешн ые поиски не являются независимыми и небольшие группы ключей зачастую вместе участвуют в поиске. Впервые такая самоорганизующаяся схема бьша исследована Джоном Мак-Кзйбом (,ХоЬп МсСаЬе) !Орегабопл Иелеагсй 13 (1965), 609-618), который и получил соотношение (17) .
Мак-Кэйб предложил также другую интересную схему, прн которой успешно обнаруженный ключ, не находящийся н начале таблицы„просто меняется местами с предыдущим, а не перемещается в начало таблицы. Он также установил, что предельное среднее время поиска для этого метода, и предположении независимости поисков, не превышает значения из (17).
Несколькими годами позже Рональд Л. Ривест (ВопаЫ Ь. Б!тезт) доказал, что метод перестановки прн длительной работе использует строго меньше сравнений, чем метод перемещения в начало таблицы— естественно, исключан случаи, когда 7т' < 2 или когда все ненулевые вероятности равны [САСМ 19 (1976), 63-67!. Однако переход к асимптотическому пределу в этом случае происходит более медленно, чем при перемещении записей н начало таблицы (Л. В. В!!пег, 51СОМР 8 (1979), 82-110). Более того, Дж. Л.
Бентлн (Л, 1. Вепс!еу), К. К. Мак-Геч (С. С. МсОеосЬ), Д. Д. Слитор (Р. В. 5!сапог) и Р. Е. Таржан (В.. Е. Таг1ап) доказали, что при методе перемещения н начало таблицы количество обращений к памяти никогда не превысит более чем в четыре раза это количество для любого алгоритма при работе с линейными списками, заданного любой последовательностью обращений; методы же подсчета частот и перестановки таким свойством не обладают (САСМ 28 (1985), 202-208, 404-41Ц. См.
также БОВА 8 (1997), 53 — 62, где приведены интересные результаты эмпирического изучении более 40 эвристических методов самоорганизующихся списков, проведенных Р. Бачрачем (В.. ВасЬгасЬ) и Р. Эль-Янином (В. Е1-Уап!т). пропорционально Р~ То + Рз(~л + Х з) + ' ' ' + Ргг(/ ь + Вз + Вз + ' ' ' + Вп). (19) При Л~ = Вз = = Т,м — — 1 зто выражение сводится к уже исследованному нами случаю (3), Представляется разумным н логичным разместить записи, обращения к которым происходят чаще, чем к другим, в начале ленты, однако в данном случае зто вовсе не такая хорошая мысль, как кажется! Например, предположим, что у нас есть лента с двумя программами — А и В, причем обращения к А происходят в два раза чаще, чем к В, но при этом она в четыре раза длиннее.
Тогда Ю = 2, Рл = 1~, Ьл = 4, Рв = -', Вв = 1. Еоли мы поместим на ленту сначала А, а затем В, руководствуясь описанной "логикой", среднее время поиска станет равным = 4+ 1 5 = 1зе. Если же воспользоваться "нелогичным" решением, поместив на ленту сначала В, а затем А, среднее время поиска сократится до 1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
