Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 53
Текст из файла (страница 53)
Предполагается, что в первой сумме для вычисления пер- вичной позиции н первых т — ! вторичных позиций требуется т а!агав Отметим, что при й(е пустая позиция всегда отыс- кивается не более чем за й+ ! попыток. Пример 10.6. Используем вероятности примера 10.3 для вы- числения Е(2, 3). По формуле (10.1.8) Е(2,3)=- ~', т ~, 'р(ш),Я~р(5) =р(0) р((1, 2))+ р(1) рЦО, 2))+р(2) р((0, 1)) -~-2[у(01) р([0, 2))+ р(! 0) р((1, 2))+ р(02) р((0, 1)) -1- р(20) рЦ(, 2))+р(12) р((0, Ц)+ р(21) р((0, 2)) +3[р(012) р((0, 1))+р(021) рЦО, 2))-)-р(102)Р((0, 1)) ф р(120) р((1, 2))+р(201) р((0, 2))+р(210) р((1, 2)) =2 008 !О.г. тлвлицы имен Правая сумма берется по всем множествам 5 иа двух злемен.
тов, содержащилл все символы цепочни ш, кроме последнего. Д Для опенки систем расстановки нам пригодится также ожидаемое число К(й, л) проб, требуемых для поиска объекта з таблице, з которой й из л позиций занятьи Однако этот показатель легко выразить через Е(й, л). Можно предположнтнч что калщый из й находящихся з таблице объектов отыскивается с равной вероятностью. Следовательно, ожидаемое время поиска равно среднему числу проб, которые раньше потребовались на то, чтобы внести эти й объектов в таблицу. Таким образом, л-л )с(й, л) =- — ~Е((, и) Поэтому основным показателем мы будем считать Е(й, л).
Естественно думать, что случайная система расстановки лучше всех остальных, поскольку любая неслучайность может привести только к тому, что вероятность заполнения для одних позиций будет больше, чем длн других, и прн попытке внести новые объекты эти позиции будуг чаще проверяться. Оливка мы покажем, что зто ие совсем так, и точный оптимум не известен. Мы полагаем, что случайная расстановка оптимальна в смысле минимального времени поиска, а другие используемые системы расстановки существенно ей уступают. Поэтому вычислим Е(й, л) для случайной системы расстановки. Лемма 10.1. Если система рсгстиясеки случшни, то (1) длл всех последовательностей ш позиций, для которых 1 ъ.'[ш [(л, р (ш) = (л — [ш [)!)л( (2) для всех подмножеств 5 множегтяа (О, !...
„л — 1) ! Р(з) = — „ [,А) Доказательство. (1) Зто доказывается эяементарной индукцней по (л — (ш!), начиная [ш( п и кончая [ш( 1, с учетом формулы (10.1.2). (2) Простые рассуждения с использованием симметрии приводят к выводу, что значение р(5) одинаково для всех подмножеств 5 из й элементов. Поскольку число множеств мощлюсти й /зт равно [л), утверждение (2) доказано. Лемма 10.2. Если л)й, то ~ [З 1) =(" Ь ).
Доказательство. Упражнение. (Д ГЛ 1Б. ОРГАНИЗАЦИЯ ИНФОРМАЦИИ 10 1 ТАБЛИЦЫ ИМВН Теорема !0.1. Если система расстановки случаона, гло Е(й, л)= =(и+ 1)/(л+ 1 — й) Доказательство. Предположим, что в таблице расстановки /1 из л позиций заполнены. Требуется внести (0+1)-й обьеит и. Из леммы 10.1(2) следует, что для любого множества из й пазвций вероятность быть заполненным одинакова. Таким образам, Е(й, п) не зависит от того, какие именно й позиций заполнены. Поэтому без потери общности можно считать, что заполнены позиции О, 1, 2, ..., й — 1.
При вычислении ожидаемого числа проб, требуемых для внесения а, нас интересует последовательность адресов, получаемых при применении Д к о. Пусть этой последовательностью будет й,(а), 61(а), ..., Ь„ ,(и). По определению все такие последовательности вз л позиций равновероятны. Пусть 0 — вероятность того, что первые ! — 1 позиций в этой последовательности принадлежат (О, 1, ..., й — 1), а новация ! не принадлежит. Ясно, что ожидаемое число Е(й, и) проб, необхо. 111 днмых для внесения а, равно ~~!0 .
Заметам, что 1=1 111 111 АА!А+1 (!0.1.б) ,'й,!'0/= Х Ху.= Х Хй. А 1 Но ~,0 — это как раз вероятность того, что первые ! — 1 позиций в последовательности ЙА(а), ЙА(а), ..., 6„,(а) лежат между 0 и й — 1, т. е, что для внесения (й-(-1)-го обьекта требуется по крайней мере ! проб. По лемме 10.1(1) эта величина равна /а — ! .» !) ( )( ) )-— — !А — .! 2) А! (А — !Аг)! (А — ! ь!) А! (А — !! ''(А — ! ! 2! (А — ! 1-!)' Л! !») Тогда, применяя лемму 10.2, получаем „, „, ; ( ":(- ') (" ~') (л) (А) А — ат-! Иэ теоремы 10.1 видно, что прн больп!Их л и й функция Е(й, л) зависит только от отнощения й/и н приблизительно равна !д! — р), где р=!1/и.
График этой функпии приведен на рис. 10.0. Отношение й/п называется коэффициентом загрузки. Когда коэффнпиент загрузки мал, время внесения как функция числа й заполненных позиций растет медленнее, чем !ой й, и расста- нонка предпочтительнее двоичного поиска. Конечно, прн приближении к л, т. е. Ио мере заполнения таблицы, внесение становится дорогим, а ори в=а вообще невозможным, если нет специальных механизмов обработки переполнений. Один метод, связанный с переполнением, предлагается в упр.
10,1.11 н 10.1 12. 10 е гр 4 0.4 ОД 0.0 Ьб йггл рве. !0.0. Еф, А) зак руяквия хоэффявэемта Азгртзкя хля случайное расстсновка. 0 0.2 Ох!идаемое число попыток при внесении обьекта является не единственным критерием качества сХемы расстановки, Желательно также, чтобы вычисление функций расстановки было простым.
В схемах расстановки, которые мы до сих пор рассматривали, вторичные функцви 61(а). .. й„ ,(и) вычислялнсь не от а, а от ДА(и), и это характерно для болыпинства схем расстановки. Такая организация эффентнвна, поснольку Н„(о)— целое чисто известной длины, в то время как п может иметь произвольную длину, Зтот метод мы будем называть рассглонсокой ло позициям. Частный случай этого метода, еще более лег. кий с точки зрения выполнения, †линейн расстановка, где й,(п) вычисяяется как (й„(а)+1)щобл.
В этом случае перебираются последовательные ячейки, пока ие отыскивается птстая; если достигнут конел таблицы, переходим на ее начало. Линенная расстановна используется в примере 10.4. Приведем теперь пример, показывающий, что по ожидаемому числу попыток внесения линейная расстановка может быть хуже случайной. Затем ГЛ Ы.ОРГАНИЗАЦИЯ ИНЧОРМАЦИИ рассмотрим расстановку по позициям и покажем, что по крайней мере в одном случае она также хуже случайной расстановки. Пример 10.7.
Рассмотрим систему линейной расстановки с л=4 и вероятностью 'А для каждой из четырех перестановок [О!23[, [1230), [2301] и [30!2]. Читатель может убедиться в том, что если вероятности сделать неравными, то система станет только хуже. Для случайной раестааовки теорема 10.1 дает Е(2,4) ='!я. По формуле (10.1.4) можно вытюлить вероятности того, что заполнено множество из двух пози!!ий, Эти вероятности таковы: р((0, 1)) =Р((1, 2))-р((2, 3)).=р((з, 0)) =Я)м Р((0, 2)) =Р((1, 3)) ="А Затем по формуле (10.1.5) находим, что для линейной рас. становкн Е(2,4)=27(16, а это болыпе я)я — стоимости случайной расстановки. С) Сравним теперь расстановку по позициям со случайной расстановкой в частном случае, когда в таблнцу вноситси третий объект.
Отметим, что при расстановке по позициям для каждой позиции ( точно одна перестановка П, начинается с 1 и нмеег ненулевую вероятность. Вероятность перестановки Пг обозначим через ре Второй элемент а Пи т. е. первтю вторичную позицию для г, обозначим через аг. Если р, 1(л для всех г, то систему будем называть глучайкой расстакоэкой ао позицики. Теорема !0.2. При эсех л > 3 Е(2„л) для случайной расстановки ленмиг, чел ддя случайной расстакоэки ло лозициял. Доказательство, По теореме 10.1 для случайной рас. становки Е(2, а) =(л+1))(л — 1).
Найдем нижнюю границу функ. ции Е(2, л) для расстановни по позициям. Предположим, что первые три объекта, вносимые в тзб.лицу, имеют перестановки По Ит и 11А соответственно. Рассмотрим отдельно случаи 1=1 и г чь!3 Случай !г гта!'. Это происходит с вероятностью (л — 1))л. Ожидаемое число попыток при внесении третьего объекта сказы. вается равным !+(2)л)+(2)л)[!)(гг !)1=(гя 1 !)((гг !) Случай 2г г=), Это пронсходет с вероятностью 1)а, Тогда третий объект вносится с первой попытни с вероятностью (л — 2)(л; при этом й~г в й~аг (аг — вторая заполненная по.
зиция). Вероятность того, что й —. а„равна 1ул; нужны по крайней мере две попытки, Вероятность лого, что й —.— ц также равна 1)л, и надо сделать три попытки, (Это вытекает из того, что УПРАЖНЕНИЯ вторая яюпытка делается для позиции а„которую занимает ),) Таким образом, в этом случае ожидаемое число проб ие менее [(л — 2)/л(-'(2 л)+(3/л) = (л+3)!л. Взвегпивая эти два случая в соответствии с их вероятностями, получаем для случайной расстановки по позициям Е (2, л) ) ( —,) ( — ) + ( — „' ) (-) = - — '„—, Последнее выражение превосходит (гг4-1)((гя — 1) для л ) 3. (Д Основное в предыдущем примере и теореме заключается в том, что многие простые схемы расстановки не удовлетворяют требованиям определения случайной расстановки.
Интуитивно это обьясняется тем, что при использовании неслучайвых схем стремятся пробовать одну и ту ясе позицию снова и снова. Даже если коэффициент загрузки мал, некоторые позиции с большой вероятностью испытываются многократно. При использова. нии такой схемы, как расстановка по позициям, каждый раз, когда заполняется первичная позиция йя(а), все вторичные по. вицин для йя(а), которые уже испытывались, будут испытываться снова, а это ведет к плохим характеристикаы. Из сказанного вовсе не следует, что не стбит пользоваться такнми схемами, как расстановка по позициям, особенно если Затраты во времени на одну попытну занесения компенсируются за счет простоты реализации.
В действительности весьма вероятно, что случайная расста. нонка †самое лучщее из всего, что можно применить. Следующий пример показывает, что при применении случайной расстановки Е(й, л) не всегда достигает минимума. Мы, однако. думаем, что случайкая расстановка дает минимум Аг(й, л) — ожидаемого времени поиска объекта. Пример 10.3. Пусть перестановки [01231 и [10321 имеют вероятности 0.2, [20131 [2103[, [3012( и [31 21 имеют вероятности 0 15, а все остальные имеют нулевые вероятности.
Можно вычислить Е(2,4) непосредственно по формуле (10.1.5) и полуюпь !.бб5. Это значение меныпе, чем Ч, для случайной расстановки. С) впРажнанмя 10.1.1. С помощью алгоритма 10.1 внесите в дерево двонч ного поиска последовательность объектов Т, П, Н, Р, А, Р, О, С) 'вг, ТО, ТН. Считайте, что объекты упорядочены по алфавиту !0.1.2, Разработайте аягоритм, на вход которого подается дерево двоичного поиска и который перечисляет по порядку зсе гл ~Р ОРГАнитхция инФОРИАции УПРАЖНЕНИЯ элементы, запомненные в дереве.
Примените этот алгоритм к дереву, построенному в упр. 10.1.1. 10.1.3. Покажите, что ожвдаемое время внесения (нлн поиска) одного объекта в дерево двоичного поиска составляет О((од л), где л — число вершин в дереве. Каково максимальное значение времени, требуемого для внесения одного произвольного объекта? *10.1.4. Какая информация о переменных и константах Фортрана необходима в таблице имен для генерации кола? 10.1.5. Опишите механизм хранения таблицы илген для языка с бточиай структурой, такого, иак Алгол, в котором область действия перемешюй Х ограничена данным блоком и всеми теми блокамя, содержащимися в данном, в которых переменная Х не переобъявлена. 10.1.0. Выберите размер таблипы и первичную функцию расстановки Й„, Вычислите й,(а), где О берется из множества (а) ключевых слов Фортрана, (б) ключевых слав Алгола и (в) ключевых слов ПЛ?!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
