с = л (VL fi6)

i-i-(V)-

Граничные значения с - I/Hn и с = 1/iV получаются при в = Q и в = 1.

Имеется еще одна часто цитируемая работа, однако ее популярность связана не с ее важностью, а лишь с тем, что это первая работа американского автора на эту тему [Alfred J. Lotka, J Washington Academy of Sciences 16 (1926), 317-323].

"Самоорганизующийся" файл. Приведенные вычисления вероятностей хороши, однако в большинстве случаев распределение вероятностей априори не известно. Можно было бы хранить в каждой записи счетчик обращений к ней и на основании полученных показаний переупорядочивать записи. Конечно, во многих ситуациях, как мы видели, такое переупорядочение приведет к значительной экономии времени; тем не менее зачастую не стоит выделять память для счетчиков - гораздо разумнее использовать ее, например, для технологии непоследовательного поиска, о чем будет рассказано ниже в данной главе.

Существует используемая многие годы простая схема, происхождение которой, увы, не известно. Эта схема позволяет получить неплохие результаты без привлечения счетчиков: когда запись успешно обнаружена, она перемещается в начало таблицы.

Идея этой "самоорганизующейся" технологии заключается в том, что наиболее часто используемые записи в результате будут располагаться в начале таблицы. Предположим, что N ключей встречаются среди аргументов поиска с вероятностями {pi,P2, ,Pn} и при этом каждый поиск совершается независимо от других. В таком предположении можно показать, что среднее количество сравнений, необходимых для поиска записи в таком самоорганизующемся файле стремится к предельному значению (см. упр. 11):

Например, если Pi = 1/N при 1 < г < N, самоорганизующаяся таблица будет находиться в неупорядоченном состоянии, а приведенная формула сведется к хорошо известному нам значению {N + 1)/2. В общем случае полученное в (17) значение всегда меньше удвоенного оптимального значения из (3), так как Cn < 1 + Yf=i и - l)Pj = 2Cjv -1- В действительности Cn всегда меньше, чем (7г/2) • Сn [Chung, Hajela, and Seymour, J. Сотр. Syst. Sci. 36 (1988), 148-157]. Эту константу нельзя улучшить, так как при pj, пропорциональных достигается равенство.

Посмотрим, насколько хорошо этот метод работает при распределении вероятностей по закону Зипфа (8). В этом случае мы имеем:

~ 1 (с/г)(с/Я 1 V- 1

n 2N n

= -+ cJ2iHN+i -Hi) = -+cJ2Hi-2cJ2Hi

г=1 i=l i=l

= i + c((2iV + l)H2N -2n- 2{N + 1)Hn + 2n)

(см. формулы 1.2.7-(8) и 1.2.7-(3)). Полученная величина существенно лучше, чем iV при достаточно больших Л, и только в 1п4 1.386 раз превышает количество сравнений при оптимальном размещении записей (см. (9)).

Вычислительные эксперименты с реальными таблицами символов компиляторов показали, что зачастую метод самоорганизации работает даже лучше, чем пред-сказьшается; это связано с тем, что последовательные успешные поиски не являются независимыми и небольшие группы ключей зачастую вместе участвуют в поиске.

Впервые такая самоорганизующаяся схема была исследована Джоном Мак-Кэй-бом (John McCabe) [Operations Research 13 (1965), 609-618], который и получил соотношение (17).

Мак-Кэйб предложил также другую интересную схему, при которой успешно обнаруженный ключ, не находящийся в начале таблицы, просто меняется местами с предыдущим, а не перемещается в начало таблицы. Он также установил, что предельное среднее время поиска для этого метода, в предположении независимости поисков, не превышает значения из (17). Несколькими годами позже Рональд Л. Ривест (Ronald L. Rivest) доказал, что метод перестановки при длительной работе использует строго меньше сравнений, чем метод перемещения в начало таблицы - естественно, исключая случаи, когда N < 2 или когда все ненулевые вероятности равны [САСМ 19 (1976), 63-67]. Однако переход к асимптотическому пределу в этом случае происходит более медленно, чем при перемещении записей в начало таблицы [J. R. Bitner, SICOMP 8 (1979), 82-110]. Более того, Дж. Л. Бентли (J. L. Bentley), К. К. Мак-Геч (С. С. McGeoch), Д. Д. Слитор (D. D. Sleator) и Р. Е. Таржан (R. Е. Tarjan) доказали, что при методе перемещения в начало таблицы количество обращений к памяти никогда не превысит более чем в четыре раза это количество для любого алгоритма при работе с линейными списками, заданного любой последовательностью обращений; методы же подсчета частот и перестановки таким свойством не обладают [САСМ 28 (1985), 202-208, 404-411]. См. также SODA 8 (1997), 53-62, где приведены интересные результаты эмпирического изучения более 40 эвристических методов самоорганизующихся списков, проведенных Р. Бачрачем (R. Bachrach) и Р. Эль-Янивом (R. El-Yaniv).

Поиск на ленте с неравными записями. Рассмотрим теперь несколько иную задачу. Предположим, что таблица, в которой проводится поиск, хранится на ленте и при этом отдельные записи имеют различную длину. Примером такого хранения информации может служить лента системной библиотеки старых операционных систем. Стандартные системные программы (например такие, как компиляторы, ассемблеры, загружаемые подпрограммы и генераторы отчетов) являются "записями" на этой ленте, и большинство пользовательских заданий должно начинать выполнение с поиска необходимого программного обеспечения. Такая постановка задачи делает неприемлемым анализ алгоритма S, поскольку шаг S3 теперь выполняется за разные промежутки времени для разных записей. Поэтому мы не можем ограничиться в нашем анализе только количеством сравнений.

Пусть Li - длина записи Ri и пусть pi - вероятность того, что вьшолня-ется поиск именно этой записи. В таком случае среднее время поиска примерно

пропорционально

PiLi +p2{Li + L2) + --- + pn{Lx +L2 + L3 + --- + Ln). (19)

При Ll = L2 - = Ln = I это выражение сводится к уже исследованному нами случаю (3).

Представляется разумным и логичным разместить записи, обращения к которым происходят чаще, чем к другим, в начале ленты, однако в данном случае это вовсе не такая хорошая мысль, как кажется! Например, предположим, что у нас есть лента с двумя программами - Аш В, причем обращения к А происходят в два раза чаще, чем к В, но при этом она в четыре раза длиннее. Тогда TV = 2, рд = , = 4, рв = I, Lb = 1. Если мы поместим на ленту сначала А, а затем В, руководствуясь описанной "логикой", среднее время поиска станет равным • 4 -(-1 5 = . Если же воспользоваться "нелогичным" решением, поместив на ленту сначала В, а затем А, среднее время поиска сократится до jl-f-5 = .

Оптимальное расположение инфор.мации на ленте (с точки зрения скорости поиска) можно определить, используя следующую теорему.

Теорема S. Пусть Lj п pi - числа, определенные выше. Размещение записей в таблице оптимально тогда и только тогда, когда

Pi/Li>P2/L2>-->Pn/Ln- (20)

Другими словами, минимальное значение

PmLai +Pa2{Lm +La2) + ---+Pa„{La, + + L)

ПО всем перестановкам 0102...ад- из множества {1,2,...,TV} равно (19) тогда и только тогда, когда вьшолняется условие (20).

Доказательство. Предположим, что мы поменяли местами на ленте Ri и iZj+i. Тогда значение величины (19) станет равным не

•• +pi{Li+--- + Lii+Li)+pi+i{Li + ---+Li+i) + -- - ,

• +Pi+iiLi + + Li-i + Li+i)+pi{Li + + Li+i) + .

При этом изменение будет равно Pil/j+i -pi+iLi. Если предположить оптимальность размещения (19), то любая перемена мест двух соседних записей должна приводить к увеличению времени работы, т. е. pt/Li > p, , i/Lt i. Таким образом, поскольку из оптимальности размещения следует набор неравенств (20), нами доказана необходимость условия (20) для оптимального размещения.

Докажем теперь достаточность выполнения условия (20) для оптимальности размещения. Приведенные выше рассуждения доказывают "локальную оптимальность" расположения - в том смысле, что любая перестановка двух рядом стоящих записей приведет к увеличению среднего времени работы. Однако это не доказывает невозможности сложного многоступенчатого обмена для улучшения производительности поиска, не доказывает, так сказать, "глобальной оптимальности". Мы рассмотрим два доказательства, в одном из которых используются знания из области компьютерных наук, а другое основано на некоторой математической хитрости.