Алгоритм Т {Последовательный поиск в упорядоченной таблице). Дана таблица записей i?i, i?2, •. -, Rn, ключи которых расположены в порядке возрастания: Ki < К2 < < Kn- Алгоритм предназначен для поиска записи с заданным ключом К. Для удобства и ускорения работы алгоритма предполагается наличие фиктивной записи Rn+1 с ключом Kn+i = 00 > К.

Т1. [Инициализация.] Установить г (- 1.

Т2. [Сравнение.] Если К < Ki, перейти к шагу Т4.

ТЗ. [Продвижение.] Увеличить г на 1 и перейти к шагу Т2.

Т4. [Равенство?] Если К = Ki, алгоритм заканчивается успешно. В противном случае - неудачное завершение алгоритма.

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

Во всех приведенных здесь алгоритмах использовалась запись с индексами для элементов таблиц (она более удобна для описания алгоритмов). Однако все описанные алгоритмы применимы и к другим типам данных, например к таблицам со связанным представлением данных, поскольку в них данные также расположены последовательно (см. упр. 2-4).

Частота обращений. До сих пор мы предполагали, что все аргументы поиска равновероятны. В общем случае это не так: вероятность запроса на поиск с ключом Kj

равна Pj, причем pi +Р2-\-----i-pN = 1. Время, требуемое для успешного завершения

поиска, пропорционально количеству сравнений С, которое имеет среднее значение

Cn =Р1 + 2р2 + --- + NpN. (3)

Если мы можем размещать записи в таблице в любом порядке, значение Cn минимально при

Pl>P2>-->PN, (4)

т. е. когда Наиболее часто используемые записи находятся в начале таблицы.

Рассмотрим случаи различных распределений вероятностей и выясним, какой выигрыш может дать оптимальное расположение записей в таблице, указанное в (4). В случае равновероятного появления ключей pi = Р2 = • • = Pjv = 1/- формула (3) сводится к Cn = {N + 1)/2, т. е. к ранее полученному нами результату (2). Теперь предположим, что распределение вероятностей имеет вид

Pi = 2 -Рг = , = jv> pn =-n- (о)

Согласно упр. 7 в данном случае Cn = 2 - 2~; при этом среднее количество сравнений, если записи расположены в надлежащем порядке, меньше двух. Еще одно, клиновидное, распределение вероятностей определяется как

Pi=Nc, p2 = {N~l)c, pn = c, (6)

где с = ]v(ll+Ty- Здесь мы не получим такого эффекта, как при распределении (5). В случае клиновидного распределения

= cMiV + l-fc) = , (7)

И при оптимальном размещении записей экономится около трети времени, которое уходит на поиск, по сравнению со временем, необходимым при случайном размещении записей*.

Естественно, распределения (5) и (6) сугубо искусственны и не могут служить хорошим приближением реальных примеров. Более типично для реальных ситуаций распределение Зипфа:

Р1=с/1, р2 = с/2, pN = c/N, (8)

где с = l/H]\f. Оно получило известность благодаря работам Д. К. Зипфа (G. К. Zipf), который, исследуя естественные языки, обнаружил, что п-е по частоте употребления слово языка встречается с частотой, примерно обратно пропорциональной п [см. Tie Psycho-Biology of Language (Boston, Mass.: Houghton Mifflin, 1935); Human Behavior and the Principle of Least Effort (Reading, Mass.: Addison-Wesley, 1949)]. .Аналогичные распределения встречаются, например, в таблицах переписи населения, в которых районы расположены в порядке убывания численности населения. В случае подчинения ключей в таблице закону Зипфа находим

См = N/Hn. (9)

Поиск в таком файле осуществляется примерно в In iV раз быстрее, чем в неупорядоченном файле [см. А. D. Booth, L. Brandwood, and J. P. Cleave, Mechanical Resolution of Linguistic Problems (New Yorlc: Academic Press, 1958), 79].

Другое близкое к реальному распределение - это распределение, соответствующее правилу "80-20", которое часто наблюдается в коммерческих приложениях [см., например, W. Р. Heising, IBM Systems J. 2 (1963), 114-115]. Это правило гласит, что 80% транзакций работают с 20% файла. Оно фрактально, т. е. оно применимо и к активным 20% файла; следовательно, 64% транзакций работают с 4% файла и т. д. Другими словами,

Р1+Р2+РЗ + +Рп

для всех п. Вот одно из точно удовлетворяющих правилу распределений (при п, кратных 5):

Р1=с, р2 = (2-1)с, рз = (3-2*)с, PN = {N -iN-lf)c, (11)

c=l/N, =Uf = 0.1386. (12)

Как вы можете убедиться, в этом случае для всех п pi-{-p2-\-----hPn = cn*. Вероятности из (11) не очень удобны для работы; однако ~{п - 1)* = вп~ (1 -f- 0(1/п)),

* Имеется в виду ачучай равновероятного появления ключей. - Прим. ред.

и поэтому можно воспользоваться более простым распределением, приближенно удовлетворяющим правилу "80-20":

Pl=c/ll- P2 = c/2l- pN = clN-o, (13)

где с = 1/Я". Здесь, как и ранее, в = log .80/ log .20, а Я - iV-e гармоническое

число порядка s, а именно - 1~* + 2~ Н-----h TV"*. Обратите внимание на схожесть

этого распределения вероятности с законом Зипфа (8); с изменением от 1 до О закон распределения изменяется от равномерного к закону Зипфа. Применяя формулу (3) к распределению (13), получим среднее число сравнений для закона "80-20" (см. упр. 8):

Cn = Я-УЯ;- = + 0{N-) « 0.122iV. (14)

Изучая частоту употребления слов, Ю. С. Шварц (Е. S. Schwartz) (см. интересный график на с. 422 в JACM 10 (1963)) предложил использовать в качестве более точного приближения распределение (13) с небольшими отрицательными значениями в. Тогда значение

»=<"/яГ" = г4+0(~«) (15)

получается существенно меньше, чем в случае (9) при TV -> оо.

Распределения, подобные (11) и (13), были впервые изучены Вильфредо Парето (Vilfredo Pareto) в связи с распределением богатства людей [Cours dEconomie Politique 2 (Lausanne: Rouge, 1897), 304-312]. Пусть pit пропорционально состоянию к-го по богатству индивидуума, apN - состоянию более бедного индивид>ума, занимающего в списке богатых iV-e место. Тогда k/N представляет собой вероятность того, что состояние более богатого человека не менее чем в х = Pk/PN раз превосходит состояние более бедного. Таким образом, при pk = ск~ ш х = (k/N)" описанная вероятность равна Такое распределение в настоящее время называется

распределением Парето с параметром 1/(1 - в).

Любопытно, что Парето не понимал сути собственного распределения; он полагал, что значение в, близкое к О, соответствует более уравнительному обществу, чем значение,близкое к 1! Его ошибка была исправлена Коррадо Жини (Corrado Gini) [Atti della Ш Riunione della Societa Italiana per il Progresso delle Scienze (1910), переиздана в его Memorie di Metodologia Statistica 1 (Rome, 1955), 3-120]. Жино был первым человеком, сформулировавшим и объяснившим важность соотношений, подобных закону "80-20" (10). Люди, как правило, не понимают сути таких распределений; они часто говорят о законе "75-25" или "90-10" как если бы главное, что придает смысл закону, заключалось в том, что в законе "а-Ь" выполняется равенство а + Ь= 100. Однако, как можно убедиться из (12), сумма 80 + 20 здесь ни при чем...

Еще одно дискретное распределение, аналогичное (11) и (13), было предложено Д. Удни Юлом (G. Udny Yule) при изучении увеличения со временем количества биологических видов при различных моделях эволюции [Philos. Trans. В213 (1924), 21-87]. Распределение Юла допускает значения в < 2:

с 2с {N-iy.c с

Pi =С, Р2 = --, РЗ = -7К7-7 PN

2- (3-)(2-) {N-в)...{2-в) {- [У