AOP_Tom3 (1021738), страница 108
Текст из файла (страница 108)
г+- О. ег пдрд агг. г Переход к Щ если К; ф К. цг,г' л Выход при отсутствии в таблице. $ О! БТАНТ ЫА К 02 БТА КЕМ+И+1 00 ЕИТ1 -И 04 ТИС1 1 00 СИРА КЕУ+И,1 06 1ИЕ л-2 07 11ИР БНССЕББ ОО РАШжЕ Е00 Используя те же значения С и Бг что и в программе Б, получим, что значение времени работы равно (4С вЂ” 4Б + 10)и; таким образом, мы получаем выигрыш по сравнению с предыдущим алгоритмом в случае С > 6 для успешного поиска и Аг > 8 - — для неудачного.
При переходе от алгоритма Б к алгоритму ь1 использован важный ускоряющий принцип — прн нескольких проверках во внутреннем цикле следует постараться свести их к одной. Вот еще один способ сделать программу 14 еще быстрее.
Программа Ц' (Быстрый последовательный поиск), гА = К, г11 г— в г — Х, 1 1 1 ((С вЂ” Б+ 2)/2) ((С вЂ” Б+ 2)/2) ((С вЂ” Б+ 2)/2) ((С вЂ” Б+ 1)/2) ((С вЂ” Б+ 1)/2) (С вЂ” Б) тог1 2 1 1 — Б Внутренний цикл дублирован, что позволяет избежать выпалнения половины ин- струкций Н +- 1+ 1", тем самым снижая затраты времени до (С вЂ” Б) шод 2 3.5С вЂ” 3.5Б+ 10+ 2 единиц времени. При работе с большими таблицами зто сохраняет до 30ге нашего времени. Такой способ ускорения применим ко многим существующим программам на языках высокого уровня (см., например, П.
Е. Кпп1Ьг Сошрпйпя Бпггеув 6 (1974), 2бб-200). Можно воспользоваться другим улучшенным алгоритмом, если ключи расположены в порядке возрастания: 01 БТАНТ 02 00 04 ЗН 05 00 07 00 ОЯ 10 4Н 11 ГАПЛВЕ ЮА К БТА КЕУ+И+1 ЕИТ1 -1-И 1ИС1 2 СИРА КЕМ+И,1 1Е 4Р СИРА ИВУ+И+1,1 1ИЕ ЗВ 1ИС1 1 11ИР БСССЕББ ЕЦ0 ь 1 1 1 С+1 — Б С+1 — Б С+1 — Б 1 1 — Б Ккг.г < — К г < — — 1. ег згг ° - ° ° г; ...г. б)22СЕаннеенгге Переход к шагу С)4, ее ли К = К,. ~с г~ -г.
Переход к шагу с)З, если К ф К,+г. Продвижение г. 1Ь Ь..гг~ Выход прн отсутствии в таблице. 2 Алгоритм Т (Лоследовательный поиск в упорядоченно>1 таблице). Дана таблица записей з>>, ггг,..., йя, ключи которых расположены в порядке возрастания: К> < Кг « . К>ч.
Алгоритм предназначен для поиска записи с заданным ключом К Для удобства и ускорения работы алгоритма предполагается наличие фиктивной записи Лк„.> с ключом К>чь, — — оо > К. Т1. (Инициализация.) Установить г з- 1. Т2. (Сравнение,) Если К < К„перейти к шагу Т4. ТЗ. (Продвижение.) Увеличиты на 1 и перейти к шагу Т2. Т4. [Равенствоу) Если К = К;, алгоритм заканчивается успешно.
В противном глучае — неудачное завершение алгоритма. 1 В предположении, что все входные аргументы-ключи равновероятны, алгоритм по скорости работы в случае успешного поиска аналогичен алгоритму Я; при неудачном же поиске отсутствие нужного ключа определяется примерно вдвое быстрее. Во всех приведенных здесь алгоритмах использовалась запись с индексами для элементов таблиц (она более удобна для описания алгоритмов). Однако все описанные алгоритмы применимы и к другим типам данных, например к таблицам со связанным представлением данных, поскольку в них данные также расположены последовательно (см.
упр. 2-4). С>у =Р>+2рг+ +>'>рн. Если мы можем размещать записи в таблице в любом порядке, значение С>ч минимально при р» >рг > >рн ( 1) т. е. когда наиболее часто испш>ьзуемые записи находятся в начале таблицы. Рассмотрим случаи различных распределений вероятностей и выясним, какой выигрыш может дась оптимальное расположение записей в таблице, указанное в (4). В случае равновероятного появления ключей р> = рг = = рк = 1/А'Фора>ула (3) сводится к Сн = (>>' т Ц/2, т. е. к ранее полученному нами результату (2).
Теперь предположим, что распределение вероятностей имеет вид 1 Рн = 2>У 1 р> 2 1 рг = 4 1 Рн > 2М-! ' (б) Согласно упр. 7 в данном случае Сл = 2 — 2' н; при этом среднее количество сравнений, если записи расположены в надлежащем порядке, меньше двух. Еще одно, клиновидное, распределение вероятностей определяется как (6) р> — — Хс, рг = (Х вЂ” 1)с,, рн — — с, 'Частота обращений. До снх пор мы предполагш>н, что все аргументы поиска равновероятны. В об>щем случае это не так: вероятность запроса на поиск с ключом К равна р>, причем р> +рг+ +р„= 1. Время, требуемое для успешного завершения поиска, пропорционально количеству сравнений С, которое имеет среднее значение где с = — —; —;~. Здесь мы не получим такого эффекта, как при распределении 15), В случае клиновидного распределения и при оптимальном размещении записей экономится около трети времени, которое уходит на поиск, по сравнению со временем, необходилгым при случайном размещении записей*.
Естественно, распределения (5) и !6) сугубо искусственны и не могут служить хорошим приближением реальных примеров. Более типично для реальных ситуаций распределение Зипфа: рг = с/1, ря = с/2, ..., Р.у = с/Аг, (8) где с = 1/Нм. Оно получило известность благодаря работам Д. К. Знпфа (С. К. 21РГ), который, исследуя естественные языки, обнаружил, что и-е по частоте употребления слово языка встречается с частотой, примерно обратно пропорциона.льной и !см.
Тйе Ряусйо-В!о!ойу оГ Г аггйиайе (Воя!оп, Маяяд Ноп81гтогг М1611гд 1935); Нитаи Ве!гауГог апг! йе РНпсгр!е оГ Ьеаяя Е!Гог! (Кеа61п8, Мвяяд АсЫ!яоп-%ея1еу, 1949)1 Аналогичные распределения встречаются, например, в таблицах переписи населения, в которых районы расположены в порядке убывания численности населения. В случае подчинения ключей в таблице закону Знпфа находим (9) Поиск в таком файле осуществляется примерно в -'1пХ рш быстрее, чем в неупорядоченном файле 1схг.
А. П. ВоосЬ, 1,. Вгапдууоос1, апг! Я. Р. С!еауе, Мес!гап!са! Кеяо!ибои оГ Ьтдп!яс!с РгоЫетя (Кевг Уог1с: Асаг)еппс Ргеяя, 1958), 79). Другое близкое к реальному распределение —. зто распределение, соответствующее правилу ЯВΠ— 20", которое часто наблюдается в коммерческих приложениях [сьь, например, ууг. Р. Не!я1пВ, ГВМ Яуясетя 2. 2 (1963)., 114 — 115). Это правило гласит, что 80% транзакций работают с 20% файла. Оно фрактально, т. е. оно применимо и к активным 20% файла; следовательно, 64% транзакций работают с 4% файла и т. д. Другимн словами Рг+Рэ+ ''+Рго Р1 + Рэ + РЯ + ' ' ' + Ря для всех гг.
Вот одно из точяо удовлетворяющих правилу распределений !угри и,, кратных 5): Р, = г;, рэ — — (2 — 1)с, ря — — (3 — 2 )с, ..., Рч = 1Х~ — (."у' — 1) )с, (11) где с = 1/Аг, В = — — = 0.1386. 1о8.80 (12) 1о8.20 Как вы мо.кете убедиться, в этом случае для всех и рг + рэ + .. + Рв яа спя. Вероятности из (11) не очень удобны для работы; однако п~ — (и — 1) = Оп~ '(1+0(1/и)), * Имеется в виду случай равиовероятиого яоявлеиия ключей. — Г!ригс ред. и поэтому можно воспользоваться более простым распределением, прнближенно удовлетворяющим правилу "80 — 20"; р~ = с/1 в, рз = с/2~ в,, р)ч = с/1У (13) где с = 1/Нв Здесь, как и ранее, В = !о8.80/!о8.20, а Н вЂ” Х-е гарлюническое О-в) О) число порядка в, а именно - 1 '+ 2 '+ . + Н '.
Обратите внимание на схожесть этого распределения вероятности с законом Знпфа (8): с изменением В от 1 до 0 закон распределения изменяется от равномерного к закону Зипфа. Применяя формулу (3) к распределению (13), получим среднее число сравнений для закона "80.20" (см. упр. 8): У С, = Н, 'в)/НО, " = — ' + О(,у'-в) = 0.122)у. (14) Изучая частоту употребления слов, Ю. С. Шварц (Е. Б.
Ясйиагтв) (см. интересный график на с. 422 в ЯАСМ 10 (1963)) предложил использовать в качестве более точного приближения распределение (13) с небольшими отрицаглельными значениями В. Тогда значение ;~ ~.ьв С =Н), )/НИ ) = +0(хьь ) (1+ В) Д1 — В) (15) с 2с (Х вЂ” Ц!с с 2 В (3 В)(2 В) (У В) (2 В) (о — в) ' получается существенно меньше, чем в случае (9) при 7в' — > со. Распределения, подобные (11) и (13), бьши впервые изучены Вильфредо Парето (ЪЧ1Ггедо РагеСо) в связи с распределением богатства людей [Соигв д'Есопопие Ро!1- Сгйие 2 (1гаизаппе: 11ои8е, 1897), 304 — 312). Пусть рь пропорционально состоянию )г-го по богатству индивидуума, а рм — состоянию более бедного индивидуума, занимающего в списке богатых Х-е место. Тогда 6/Дг представляет собой вероятность того, что состояние более богатого человека не менее чем в х = рь/рм раз превосходит состояние более бедного.
Таким образом, при рь = скв ' и г = (6/.У)в ' описанная вероятность равна х зД' в). Такое распределение в настоящее время называется распределением Парето с параметром 1/(1 — В). Любопытно, что Парето не понимал сути собственного распределения; он полагал, что значение В, близкое к О, соответствует более уравнительному обществу, чем значение, близкое к 1! Его ошибка бьша исправлена Коррадо Жини (Соггадо Спп) (АЫ де!!а Ш 11!ив)опе де11а Зос)ега 1га11апа рег Л Ргойгевво де11е Бс1епге (1910), переиздагга в его Мешопе о9 Ме)оде!о8)а ЯтаГ1вс1са 1 (Влше, 1955), 3 — 120].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
