Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 52
Текст из файла (страница 52)
Содержимое теплеем расстановки. Содержимое таблицы расстановки к этому моменту приведено иа рис. 10.5. Предположим, что мы хотим выяснить, есть лн в таблице объект НХ. Находим 6,(НХ) =2. С помощью алгоритма 10.2 проверяем позицию 2 и видим, что возник коифлинт, поскольку позиция 2 занята, но не обьектом НХ.
Проверяем затем позицию 6,(НХ) =3 и снова получаем конфликт. Наконец, вычисляем 6,(НХ) = 4 и находим, что позипия 4 пуста. Приходим, таким образом, к выводу, что объекта НХ в таблице пет. 10.1.4. Функции расстановки Желательно пользоваться такой первичной функцией расстановки й„ которая распределяла бы объекты равномерно по всей таблице расстановки. Надо избегать функций, которые отображают не на все множество позиций илн выбирают одни позицин ') омоа Ь вЂ” это остаток от деления о на Ь. ГЛ.
70 ОРГАНИЗАЦИЯ ИНФОРМАЦИИ чаще, чем другие, а также функций, требующих больших вычислений. Перечислим наиболее широко используемые первичные функ- ЦИН: (1) Если ц занимает в машине несколько слов, можно вычислить арифметическую (илп логическую) сумму этнх слов, чтобы получить лредстаалгмие и в виде. гдимствгнносо слова. Зго слово теперь можно трактовать как число, извлечь квадратный корень и ваять в качестне Й,(а) средние 1однгг битов результа. та.
Поскольку средние биты киадратного корня завнсят от нсех символов объекта, различные объекты в среднеи будут давать различные адреса независимо от того, имеют ли объекты общие префиксы или суффиксы. (2) Единственное слово, представляющее а, можно разбить на несколько частей фиксированной длины (обычно по !ойнл битов). Затем можно просуммировать эти части и взять в качестве Йг(а) младшие !ой,п битов суммы.
(3) Единственное слово, представляющее а, можно разделить на размер и таблицы и ваять в качестве ЙР(а) остаток от де77ения (в этом случае а должно быть простым числом). Рассмотрим теперь методы разрешения конфликтов, т. е. построения дополнительных функций Йо Йю ..., Й . Прежде всего отметим, что значение Йг(а) должно отличаться от Йг(а) длн всех 1~).
Когда Йг(о) дает конфликт, бессмысленно пробовать Йгэг(а), если Йггг(и) =-Й,(а). В большинстве случаев хо~елось бы, чтобы было т=л — 1, поскольку всегда желательно найти в таблице пустую позицию, если она есть. В общем случае метод разрешения конфликтов оказывает сильное влияние на эффективность всей системы с распределенной памятью. Простейшим, но, как мы увидим, одним нз самых худших, набором функции Йю Й„ ..., Й,, является Йг(а) =(Й,(а) Ь() шобл 1 (1(77 — ! В этом случае мьг движемся вперед относительно значения Й,(а) первичной позиции до тех пор, пока не исчезнет конфликт. Если достигнута позиция и — 1, переходим на позицию б. Метод прос7 для выполнения, однако если уже возник коафликг,то запятые позиции имеют тенденцию скапливаться. Например, если из. всстно, что )гн(а) вызывает конфликт, то вероятность того, что Й,(и) также вызывает конфликт, выпге средней. Более эффективный метод получения вторичных адресов заилючается в выборе Йг(и) = (Й,(а)-)-г) шобл 1(1(и — ! где г,— псевдослучайное число.
Часто для этой цели достаточен самый элементарный генератор случайных чисел, дающий ~а ь тхэлицы имгн все числа в диапазоне от 1 до и — ! в точности по одному разу (см. упр. 10.!.6). Калгдый раз, когда используются вторичные функции, генератор случайных чисел устанавливается в одно и то же состояние. Таким образом, каждый раз, когда происходит обращение к Й, генерируется одна и та же последовательность г„ гю ..., и, следовательно, поведение генератора „слу.
чайных" чисел вполне детерминировано, В качестве вторичных функций можно взять также Й, (а) =[7'(Й„(а) 1-1)[гпобл н 777 (а) = [Йн(а) ф а!и + Ы[ пюб л где а и Ь вЂ” подходящие константы. Несколько отличный от этого метод разрешения конфликтов, называемый иетадом цепочек, разбирается в упражнсннях. 1ОЛНЕ Эффвитнвноеть табииц расстановки Сколько требуется в среднем времени для внесения и поиска данных в таблнце расстановки? С этим вопросом связан следующий: даны вероятности появлення различных объектов; как вйбрать функции Й„ ..., Й, „ чтобы оптимизировать работу с таблицей расстановки? Интересно, что здесь есть ряд нерешен- НЫХ ВОПРОСОВ. Как мы уже отмечали, было бы неразумно иметь повторе.
ниЯ в последовательности позиций Й,(а), ..., Й„ т(о) дла какого-нибудь объеита щ Будем считать, что хорошая система функций расстановки не допускает повторений. Наприл7ер, последовательность Йю ..., Й, из примера 1Огй такова, что ни для каиого объекта одна и та же позиция не будет проверяться дважды. Если л — разл7ер таблицы расстановки с позициями, занумерованными от О до и — 1, и Й„..., Й„,— функции расстановки, то каждом> объекту а можно поставить в соответствие перестанонку П„множества (О, ..., и — 1), а именно П„=[Й,(а), ..., Й,,(а)[. Таким образом, первая компонента перестановки П лает первичную позицию, отводимую для ц, вторая компонента— следующую возможную позицию и т. д.
Если для иаждого объекта а известна вероятность р„его появления, то можно определить вероятность пернстаноахи П как ~ р, где сумма берется по всем таким объектам ц, что П„= П'). Отныне будем полагать, что вероятности всех перестановок даны. ') Иннин слннанн, это сумма веронтнсстеа нонатеннн объектов, ноторые Образуют данную перестановку П. †Пр. Анрнэ.
279 гл. !а ОРганизхция инФОРмАции Ясно, что ожидаемое число позиций, которые надо проверить при внесении или поиске объекта, можно вычислить, зная только вероятности перестановок. Для вычислевия эффективности конкретной функции расстановин не обязательно знать реальные функции Й„ ..., Й„,. В этом разделе мы изучим свойства функций расстановки,ойределяемые вероятностями перестановои.
Основываясь на сказанном выше, можно дать следуюп!ее определение, которое сводит задачу построения таблицы рас. стацовки к вопросу а том, канон желательный набор вероятностей перестановок. Определение. Системой расстановки назовем пару, состоящую из размера таблицы н и функции вероятности р, определенной на перестановках целых чисел от 0 до л — 1.
Систему расстановки будем называть случайной, если р(П) = 1(л! для каждой из перестановок П. Укажем важные функции, связанные с системой расстановки: (1) р((г(!...!А) †вероятнос того, что некоторый объект имеет 1, в качестве первичной позиции, 1, в качестве первой вторичной, 1, в качестве следующей вторичйой и т. д.
(здесь каж. дое ! -это целое между 0 и л — !), (2~ р((1„ 1„ ..., 1„)) — вероятность того, что последовательность Й объектов заполнит в точности множество позиций (!ц 'И ° !А) Легко вывестн следующие формулы; (10.1.2) р(Д Л„) = ~', р(1!...)А)), если Й < и мк„.г„! (!О,!.3) р(г,...(„)=р(П) где П вЂ” перестановка [(н ..., 1„]. (10.1.4) р(3)= 2', р(3 — (1))Хр(ю() !ЕА где 5 — произвольное подмножество множества (О,, л — Ц, состояп!ее из Й элементов, а правая сумма берется по всем цепочкам ю нз Й вЂ” 1 или менее различных позиций в 5 — (!).
Полагаем, что р(Я!) =-1. Формула (10.1.2) позволяет вычислять по вероятное~ям перестановок вероятность любой последовательности вторичных позиций. Формула (10.1.4) позволяет вычислять вероятность того, что позициями, отведенными для Й объектов, являются в точности те, которые составляют множество 3, Эта вероятность равна сумме, взятой по всем 1 б 5, вероятностей того, что первые Й вЂ” 1 объектов займут все позиции в 3, кроме позиции г, а последний объект займет позицию !. ЕЗО !А.! Тлалицы имен Пример 10.3.
Пусть а =3, а вероятности шести перестановок приведены в табл. 10.1. талл чо тол П.Р- О. ! 0.2 О.! О.З 0.2 О.! 0,1,2! О, 2, !1 1, О, 21 1, 2, о) 2, О, !! 2, 1, О! По (10.1.3) вероятность того, что в результате применения функции расстановки к некоторому объекту будет выработана цепочка позиций 012, ранка просто вероятности перестановки 10, 1, 2). Таким образом, р(0!2) =- 0.1. По (10.1 2) вероятность того, что вырабатывается 01, равна р(012). Аналогично р(02)— вероятность перестановки 10, 2, Ц, равная 0.2. Применяя фор.
мулу (10.1.2), получаеьг, что р[0) = р(0!)-т-р(02) =- 0.3. Вероят. ность появления каждой цепочки длины 2 ияе 3 †э вероятность той единственной перестановки, префнксом которой служит данная цепочка. Вероятности появления цепочек ! и 2 равны соответственно р(10) +р(12) = 0.4 и р(20) †' р(21) =-0.3. Вычислим теперь вероятности заполнения различных множеств позиций. Для множеств 5, состоящих нз одного элемента, [10.1.4) сводится к р((!)) — р(!), Вычислим р((0, 1)) по формуле (10.1.4). Прямая подстановка дает р((0, 1)) рПО)) [р(!) 1 р(О!Ц+ р((1)) [р(0) р(10)) = 0.3)0.4+ О.
Ц+ 0.4 [0.3+ О. Ц = 0.31 Аналогично находим р((0,2)) ---0.30 и р((1,2)).=0.39 Для вычислении р((0,1,2)) по формуле (10.1.4) подсчитмваем Р((0,1)) [Р(2) -1- р(02) ф Р(12) )- р(012) -, 'р(102) ) + р((0 2) ) Гр(1) + р(0! ) + р(21) + р(02! ) + р(201)) , 'р((1,2)) (р(0) + р(10) + р(20) + р(120) + р(210)7 что, конечно, равно 1. С) Основной величиной, которая нал! понадобится длн оценки системы расстановки, будет ожидаемое число проб, необходимых для того, чтобы внести объект а в таблицу, в которой Й пози- гл ю аяглнизлция инеоямлцни ций нз л заполнены. Успех достигается ари первой же пробе, если й,(а) =! н ! — одна из л — й пустых позиций. Такич образом, вероятность того, что успех будет достигиуг при первой пробе, ранна -1 Х р(О ~р(5) где правая сумма берется по всем множествам 5 из й позиций, не содержал!им Е Если й„(а)Е5, но й,(а)ц5, то успех будет достигнут при второй пойытке.
Поэтому вероятность того, что первая попытка будет неудачной, а вторая †удачн, равна ,Х,Х р(()),з р(5) где правая сумма берется по всем множествам 5 из й позиций, содержащим л и не содержащим !. Отметим, что р(П) =0 при ! = ). Продолжая в том же духе, получаем формулу ожидаемого чиг,ю Е(й, л) проб, требуемых для внесения объекта з таблицу, з котороб й иэ л позиций заняты, й (п: л Е(й,л)= 2) тХр(ш)Х р(5) где (Ц средняя сумма берется по всем цепочкам ш различных позиций длины т, (2) правая сумма берется по всем таним множествам 5, со- стояц!нм яз й позиций, что в ш все символы, кролле последнего, принадлежат 5 (последний символ цепочки ш не принадлежит 5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
