Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

90 ГЛАВА 4
вращения разделяет данные более равномерно. Выбор минимального эле- мента приводит к самому неравномерному распределению: все данные ухо- дят вправо, а слева ничего не остается. Таким образом, на каждом этапе мы перемещаем только саму точку вращения.
При более равномерном распределении перемещается не только выбран- ный нами элемент. Правильные позиции относительно него занимают все элементы, которые оказываются слева. Конечно, речь не идет об их окон- чательных позициях, но в целом они находятся в лучшем положении, чем раньше. Таким образом один элемент оказывается в идеальной позиции, а остальные улучшают свое положение.
Это оказывает важное влияние на производительность быстрой сорти- ровки: ее ожидаемая сложность составляет O(nlgn), что намного лучше, чем
O(n
2
). Если мы хотим отсортировать 1 миллион элементов, O(n
2
) понадобится
10 12
(триллион) операций, а O(nlgn) — около 20 миллионов.
Все зависит от выбора правильной точки вращения. Не следует каждый раз искать такие точки, которые разделяют наши данные оптимальным об- разом; это лишь усложнило бы весь процесс. Вместо этого лучше положиться на волю случая. Просто выберите произвольный элемент и используйте его для разделения данных.
Чтобы показать, что это хорошая стратегия, давайте сначала объясним, почему ее нельзя назвать плохой. Плохая стратегия ведет себя так, как мы только что видели: когда быстрая сортировка вырождается в сортировку вы- бором. Это происходит, если на каждом этапе выбирать такую точку враще- ния, которая в действительности не разделяет элементы. Например, мы мо- жем каждый раз выбирать наименьший или наибольший элемент (результат будет один и тот же). Общая вероятность этого равна 2
n-1
/n!.
Вероятность вида 1/n! сложно себе представить, так как она крайне низкая.
Для сравнения: если взять колоду с 52 игральными картами и перетасовать ее случайным образом, вероятность того, что она окажется упорядоченной, со- ставляет 1/52!. Это примерно то же самое, что получить решку 226 раз подряд при подкидывании монеты. Если умножить это на 2
n-1
, мало что поменяется.
2 51
/52! равно примерно 2,8×10
–53
. Если взглянуть на это с точки зрения косми- ческих величин, наша планета состоит где-то из 10 50
атомов. Если вы с вашим другом выберете по одному случайному атому, вероятность того, что это ока- жется один и тот же атом, будет равна 10
–50
, что на самом деле больше, чем ве- роятность патологической быстрой сортировки колоды карт (2 51
/52!).
Это объясняет, почему «обычно» мы разделяем данные более равно- мерно. Если не брать во внимание полосу невезения космических масштабов,

СОРТИРОВКА 91
не стоит волноваться о том, что на каждом этапе будет выбрана худшая точка вращения из всех возможных. Наши шансы довольно неплохие: сложность
O(nlgn) получается при выборе точек вращения случайным образом. Конечно, теоретически нам может не повезти, но вероятность этого представляет разве что академический интерес. На практике быстрая сортировка будет работать настолько хорошо, насколько можно ожидать.
Быстрая сортировка изобретена в 1959–1960 годах британским ученым
Тони Хоаром, который специализировался в области информатики. Это, на- верное, самый популярный алгоритм сортировки на сегодня, потому что, если его правильно реализовать, он превосходит все остальные. Это также первый из рассмотренных нами алгоритмов, который демонстрирует не со- всем детерминированное поведение. Он всегда сортирует правильно, но мы не можем гарантировать, что у него всегда будет одинаковая производи- тельность. Тем не менее вероятность того, что он поведет себя патологи- ческим образом, крайне мала. Это важная концепция, которая подводит нас к теме так называемых вероятностных алгоритмов, которые исполь- зуют в своей работе элемент случайности. Это может показаться нелогич- ным, ведь алгоритмы должны быть детерминированными, послушными су- ществами, которые четко следуют инструкциям, расставленным в заранее определенном порядке. И все же в последние годы можно наблюдать рас- цвет вероятностных алгоритмов. Оказывается, элемент случайности помо- гает решать задачи, с которыми не получается справиться более стандарт- ными способами.

92 ГЛАВА 4 15 27 59 82 95 21 35 51 56 69
Как видите, каждый ряд уже отсортирован. Мы хотим их объединить, чтобы создать единую упорядоченную группу. Это очень просто. Мы сравни- ваем первые элементы каждой группы. В нашем случае число 15 меньше, чем
21, поэтому с него будет начинаться третья группа.
27 59 82 95 21 35 51 56 69 15
Снова проверяем первые элементы в двух группах. На этот раз 21 из вто- рой группы меньше, чем 27 из первой. Поэтому мы берем число 21 и добав- ляем его в третью группу.
27 59 82 95 35 51 56 69 15 21
Продолжим в том же духе. Возьмем 27 из первой группы и 35 из второй и добавим их в конец третьей.
59 82 95 51 56 69 15 21 27 35
Теперь 51 меньше 59 и 56 меньше 59. Поскольку число 35 уже попало в ко- нец третьей группы, получается, что мы выбрали из второй группы три эле- мента подряд. Это нормально, поскольку таким образом мы упорядочиваем элементы в третьей группе. Первые две группы вовсе не должны уменьшаться одинаковыми темпами.

СОРТИРОВКА 93 59 82 95 69 15 21 27 35 51 56
Возвращаемся к первой группе. Число 59 меньше, чем 69, поэтому добав- ляем его в третью группу.
82 95 69 15 21 27 35 51 56 59
После перемещения 69 вторая группа полностью исчерпывается.
82 95 15 21 27 35 51 56 59 69
В конце мы перемещаем оставшиеся элементы первой группы в третью — они точно больше последнего перемещенного элемента, иначе мы их уже пе- реместили бы. Итак, наши элементы полностью отсортированы.
15 21 27 35 51 56 59 69 82 95
Это хорошо, что мы можем получить единую упорядоченную группу из двух отдельных, но как это поможет нам отсортировать список неупорядо- ченных элементов? Действительно, никак. Тем не менее это важный аспект общего решения.
Представьте, что у вас есть группа людей. Мы поручаем одному человеку отсортировать набор элементов. Этот человек не знает, как сортировать, но зато он умеет объединять два набора отсортированных элементов в ито- говый упорядоченный набор. Поэтому он разделяет набор элементов на две части и передает их двум другим людям. Каждому из них он говорит следую- щее: «Возьми эти элементы, отсортируй их и верни мне».
Первый человек не умеет сортировать, но если два других упорядочат эле- менты, которые им доверили, и вернут их ему, он сможет составить из них

94 ГЛАВА 4
итоговый отсортированный набор. Проблема в том, что два других человека знают о сортировке не больше первого: они могут лишь объединять уже упо- рядоченные наборы с помощью алгоритма слияния. Так чего же мы этим до- бились?
На самом деле мы решили задачу, если исходить из того, что все люди в группе делают одно и то же: разделяют полученные элементы на две части, делегируют их двум другим людям, затем ждут, когда те завершат свою ра- боту и вернут два отсортированных набора.
Это выглядит как перекладывание ответственности из рук в руки, но да- вайте посмотрим, что произойдет, если применить данный метод к нашему примеру. Вначале у нас есть числа 95, 59, 15, 27, 82, 56, 35, 51, 21 и 79. Мы от- даем их Элис (A), которая разделяет их на две части и передает Бобу (B) и Кэ- рол (C). Это можно наблюдать на первом уровне перевернутого дерева, пред- ставленного ниже.
A: 95, 59, 15, 27, 82, 56, 35, 51, 21, 79
B: 95, 59, 15, 27, 82
D: 95, 59, 15
H: 95, 59
P: 95 Q: 59
I: 15
E: 27, 82
J: 27 K: 82
C: 56, 35, 51, 21, 79
F: 56, 35, 51
L: 56, 35
R: 56 S: 35
M: 51
G: 21, 79
N: 21 O: 79
Затем Боб разделяет свои числа на две части и передает их Дейву (D) и Иви (E). Тем временем Кэрол разделяет свои числа между Фрэнком (F) и Грейс (G). Ответственность продолжает передаваться из рук в руки. Дейв разделяет числа между Хайди (H) и Иваном (I); Иви распределяет свои два числа между Джуди (J) и Карен (K); Фрэнк и Грейс передают элементы Лео
(L) и Мэллори (M) и, соответственно, Нику (N) и Оливии (O). В конце Хайди разделяет свою пару между Пегги (P) и Квентином (Q), а Leo — между Робер- том (R) и Сибил (S).
Тем, кто находится на листьях дерева, не остается никакой работы. Пегги и Квентин получили по одному числу и теперь должны выполнить сортировку.
Но одно число уже и так упорядочено по определению: оно находится в пра- вильном положении относительно самого себя. Поэтому Пегги и Квентин просто возвращают свои числа Хайди. То же самое делают Иван, Джуди, Ка- рен, Роберт, Сибил, Мэллори и Оливия.

СОРТИРОВКА 95
Теперь давайте перейдем к трем сортировщикам на следующей странице.
В этом дереве мы двигаемся от листьев, расположенных сверху, к корню, ко- торый находится внизу (мы перевернули диаграмму, чтобы она больше по- ходила на нормальное дерево). Давайте сосредоточимся на Хайди. Она по- лучает обратно два числа, каждое из которых (само собой) отсортировано.
Хайди знает, как объединить две группы упорядоченных чисел в одну, по- этому она получает набор 59, 95. Затем она возвращает его Дейву. То же самое делает и Лео: он получил числа 35 и 56, которые уже (сами собой) отсорти- рованы, поэтому он объединяет их в упорядоченный набор 35, 56 и возвра- щает Фрэнку.
Дейв, который сначала не знал, что делать с числами 95, 59, 15, получил набор 59, 95 от Хайди и 15 от Ивана. Оба эти набора уже отсортированы, по- этому Дейв может их объединить в 15, 59, 95. Точно так же Фрэнк, получив
35, 56 от Лео и 51 от Мэллори, может вернуть 35, 51, 56.
A: 15, 21, 27, 35, 51, 56, 59, 79, 82, 95
C: 21, 35, 51, 56, 79
G: 21, 79
O: 79
N: 21
F: 35, 51, 56
M: 51
L: 35, 56
S: 35
R: 56
B: 15, 27, 59, 82, 95
E: 27, 82
K: 82
J: 27
D: 15, 59, 95
I: 15
H: 59, 95
Q: 59
P: 95
Если все продолжат в том же духе, то к моменту, когда очередь дойдет до Элис, останется два отсортированных списка: один от Кэрол, а другой от Боба. Элис объединит их в итоговый упорядоченный список.
Эти два дерева лежат в основе сортировки слиянием. Упорядочивание де- легируется настолько, насколько это возможно, вплоть до того, что его во- обще не нужно проводить, поскольку отдельные элементы и так упорядо- чены сами по себе. Затем мы «сливаем» все большие и большие наборы, пока не объединим все элементы в финальный отсортированный список.
Каждый из участников должен обладать лишь минимальными умениями.
Вы можете видеть, что в первом дереве Иви получила от Боба набор чисел, ко- торые оказались уже упорядоченными: 27, 82. Но это неважно. Она не при- нялась проверять, в каком порядке они находятся, и мы не хотели, чтобы она тратила на это время. Она просто разделила эти числа и передала их дальше.
Позже она получила их обратно и создала тот же набор, который у нее был

изначально. Это нормально; такое бессмысленное па-де-труа в исполнении
Иви, Джуди и Карен не оказало особого влияния на производительность ал- горитма.
Сложность сортировки слиянием не хуже, чем у быстрой сортировки,
O(nlgn). Это означает, что у нас есть два алгоритма с одинаковой производи- тельностью. На практике программисты руководствуются в своем выборе до- полнительными факторами. Программы с быстрой сортировкой обычно ра- ботают быстрее программ на основе сортировки слиянием, потому что они лучше реализованы на конкретном языке программирования. В сортировке слиянием данные сначала разделяются, а затем объединяются; это означает, что этот процесс можно распараллелить так, чтобы огромные объемы инфор- мации сортировались в компьютерном кластере. В этом случае каждый ком- пьютер играет роль отдельного сортировщика.
Этот подход появился вместе с первыми компьютерами. Его автором яв- ляется американец венгерского происхождения, Янош Лайош Нейман, более известный под своим американским именем, Джон фон Нейман (1903–1957).
В 1945 году он написал от руки 23-страничный документ, посвященный од- ному из первых цифровых компьютеров, EVDAC (Electronic Discrete Variable
Automatic Computer). Вверху первой страницы было написано карандашом
(и позже стерто) «СОВЕРШЕННО СЕКРЕТНО», так как в 1945 году работу над компьютерами тесно связывали с военными и поэтому засекретили. Темой документа стало нечисленное применение компьютеров: сортировка. Метод, описанный фон Нейманом, позже стал известен как сортировка слиянием.

PAGERANK 97
ГЛАВА 5
PAGERANK
Если вы достаточно молоды, слова HotBot, Lycos, Excite, AltaVista и Infoseek мо- гут ничего для вас не значить. Но даже если вы о них слышали, то, наверное, не как о поисковых системах. Тем не менее какое-то время назад все они бо- ролись за наше внимание, пытаясь стать нашим окном в Интернет.
Но это дела уже давно минувших дней, так как на рынке поисковых си- стем сейчас доминируют Google от Aphabet и Bing от Microsoft. Появление множества конкурирующих решений на новом рынке и их последующая кон- солидация — привычное явление во многих отраслях. Однако рынок поиско- вых систем примечателен тем, что большое влияние на его развитие оказал успех Google, ставший возможным благодаря алгоритмам, которые разрабо- тали основатели этой компании. Ларри Пейдж и Сергей Брин, получившие свои докторские степени в Стэндфордском университете, назвали изобретен- ный ими алгоритм PageRank (в честь Пейджа, а не от слов page и rank, как можно было бы подумать).
Прежде чем приступать к описанию PageRank, необходимо понять, чем именно занимаются поисковые системы. В действительности ответ состоит из двух частей. Во-первых, они обходят Интернет, читая и индексируя все веб- страницы, которые им встречаются. Таким образом, когда вы вводите свой запрос, поисковая система анализирует уже сохраненные ею данные и нахо- дит то, что вы ищете. Например, если ввести «изменение климата», система пройдется по данным, которые она насобирала, и выдаст веб-страницы, со- держащие эти ключевые слова.
Если наш поисковый запрос относится к популярной теме, результатов может быть огромное множество. На момент написания этой книги запрос
«изменение климата» в Google выдает более 700 миллионов результатов; ко- гда вы будете читать эти строки, цифры могут быть другими, но вы можете себе представить, о каких масштабах идет речь. Это подводит нас ко вто- рой составляющей того, чем занимаются поисковые системы. Они должны