Радости и муки сортировки: способы создания порядка, заимствованные у компьютера

Отрывок из книги «Алгоритмы для жизни: простые способы принимать верные решения».

Издательство «Альпина» выпустило книгу «Алгоритмы для жизни: простые способы принимать верные решения». Авторы — журналист Брайан Кристиан и ученый-когнитивист Том Гриффитс — объясняют, как математические алгоритмы, которые используют компьютеры, могут помочь в решении повседневных задач.

Редакция vc.ru приводит главу «Сортировка», посвящённую тому, как классический компьютерный метод находит отражение в обычной человеческой жизни: от сортировки носков до организации электронной почты.

До того как Данни Хиллис основал корпорацию Thinking Machines и изобрел машину логических связей, он был обычным студентом Массачусетского технологического института, жил в студенческом общежитии и был в ужасе от носков своего соседа по комнате. В ужас Хиллиса приводило вовсе не несоблюдение гигиены, часто свойственное студентам колледжа. Дело было не в том, что сосед Хиллиса не стирал свои носки. Он их как раз стирал.

Проблема заключалась в том, что происходило после. Молодой человек доставал носок из корзины с чистым бельем. Потом наугад доставал второй. Если носки не оказывались парными, он бросал второй носок обратно в корзину. Этот процесс продолжался до тех пор, пока он не находил пару первому носку. Итак, при десяти разных парах носков ему приходилось в среднем 19 раз вытаскивать разные носки, чтобы подобрать одну пару, и еще 17 раз, чтобы составить вторую.

В общей сложности сосед Хиллиса мог вылавливать по одному носку 110 раз, чтобы собрать 20 пар. Этого было достаточно, чтобы начинающий компьютерный специалист переехал жить в другую комнату. Сегодня обсуждение техники сортировки носков может пробудить в программистах удивительное красноречие. Вопрос о носках, опубликованный на программистском сайте Stack Overflow в 2013 году, вызвал настоящие дебаты.

«Проблема с носками ставит меня в тупик!» — признался легендарный специалист по криптографии и информатике, лауреат премии Тьюринга Рон Ривест, когда мы заговорили с ним об этом вопросе. Во время встречи на нем были сандалии на босу ногу.

Сортировка лежит в основе работы компьютеров. Фактически именно необходимость сортировки послужила причиной создания компьютера. В конце 19 века прирост населения Соединенных Штатов составлял 30% за десятилетие, и количество «объектов исследования» Бюро переписи населения за десять лет с 1870 по 1880 год возросло с пяти до более чем двухсот.

Подведение итогов переписи 1880 года заняло восемь лет, и почти сразу после окончания работ стартовала перепись 1890 года. Как выразился один писатель того времени, было удивительно, как «канцелярские работники, заваленные бессчетным количеством бумаг, не ослепли и не сошли с ума». Само ведомство едва не рухнуло под собственным весом. Нужно было срочно что-то делать.

Вдохновленный существовавшей в то время системой компостирования железнодорожных билетов изобретатель Герман Холлерит решил использовать технологию компостирования карточек из манильской бумаги для хранения информации. Для учета и сортировки карточек им была изобретена первая табулирующая машина, которая позднее была названа его именем.

Он получил патент на устройство в 1889 году, а уже в 1890-м машина Холлерита была одобрена правительством для использования при переписи населения. До этого никто не видел ничего подобного. Восхищенный обозреватель писал: «Этот аппарат работает с божественной точностью, но по скорости превосходит даже высшие силы». Другой обозреватель тем не менее отметил, что область применения машины ограничена и «изобретатель вряд ли разбогатеет на этом устройстве, поскольку никто кроме правительства не станет его использовать».

Этому прогнозу, который Холлерит взял на заметку, не было суждено сбыться в точности. Фирма Холлерита объединилась с рядом других компаний в 1911 году и вошла в промышленный конгломерат CTR (Computing-Tabulating-Recording Company). Спустя несколько лет компания была переименована в IBM (International Business Machines).

Техника сортировки продолжала подстегивать развитие компьютерной науки на протяжении следующего столетия. Первым в мире кодом, написанным для ЭВМ с запоминаемой программой, стала программа для эффективной сортировки. В сущности, именно способность компьютера заменить аппараты IBM, заточенные исключительно под сортировку перфокарт, убедила американское правительство в том, что колоссальные инвестиции в создание универсальной машины оправданны.

Согласно проведенному исследованию, к 60-м годам 20 века более четверти мировых компьютерных ресурсов были задействованы в процессах сортировки. Что неудивительно, ведь сортировка — неотъемлемая часть работы практически с любым видом информации. Будь то определение наибольшей или наименьшей величины, общего или частного, суммирование, индексирование, выявление дублирующей информации или просто поиск того, что вам нужно, — все это, в сущности, начинается с процесса сортировки.

На самом деле применение сортировки выходит далеко за рамки этих процессов, поскольку одна из ее основных целей — продемонстрировать человеку возможную пользу вещей. Из этого мы делаем вывод, что сортировка — это также ключ к человеческому восприятию информации.

Отсортированные списки в наше время применяются повсеместно и так естественно внедрились в нашу среду обитания, что нужно быть внимательными и сосредоточенными, чтобы обнаружить их (как рыбе, которая захотела бы узнать, что такое вода). Но, заметив их однажды, вы будете замечать их всегда.

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

В блоге обычно показан список записей, отсортированных по дате. Лента новостей в Facebook, поток твитов в Twitter и домашняя страница Reddit представляют собой списки, составленные по тому или иному определенному критерию. Мы считаем сайты вроде Google или Bing поисковыми системами, на самом деле это не совсем корректно: в сущности это системы сортировки.

Вся сила Google как средства доступа к мировой информации заключается не в его способности найти наш текст среди сотен миллионов веб-страниц (это было под силу еще его конкурентам в 90-е годы), но в умении эффективно сортировать эти веб-страницы, показывая нам только те десять, которые максимально соответствуют нашему запросу.

Срез бесконечного множества — упорядоченный список в определенном смысле представляет собой универсальный пользовательский интерфейс. Информатика помогает нам понять, что стоит за всеми этими ситуациями, а это знание в свою очередь позволяет проанализировать те моменты, когда мы сами сталкиваемся с необходимостью навести порядок в наших счетах, бумагах, книгах, носках и так далее. А происходит это гораздо чаще, чем мы думаем.

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

Использование принципов компьютерных технологий оказалось неожиданно полезным, к примеру, на боксерском ринге. Все потому, что даже минимальное знание основ сортировки может объяснить, как люди способны мирно сосуществовать, периодически вступая в драку. Другими словами, техника сортировки может поведать нам удивительные вещи о природе нашего общества — того большого и важного порядка, авторами которого мы являемся.

«Чтобы снизить себестоимость одной единицы продукции, люди обычно увеличивают объемы производства», — писал Джордж Хоскен в 1955 году в первой научной статье, посвященной технике сортировки. Эта теория экономии на масштабе знакома любому студенту, изучающему бизнес.

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

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

У вас в два раза больше объектов для сортировки и в два раза больше места, на которое можно поставить тот или иной объект. Чем глобальней ваша задача, тем хуже. Это самое первое и наиболее фундаментальное наблюдение о теории сортировки. Масштаб убивает. Из этого следует: чтобы уменьшить боль и страдания, нам необходимо сократить количество вещей для сортировки.

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

Действительно, если бы сосед Хиллиса следовал своей излюбленной процедуре, но сократил бы перерыв между стирками с 14 дней до 13, одно это могло бы сэкономить ему 28 «вытягиваний» носков из корзины. (А если бы он увеличил интервал между стирками на день, ему пришлось бы «вылавливать» пару лишние 30 раз.)

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

Для этого, как сказал герой фильма «Челюсти», нам понадобится лодка побольше — и алгоритм получше. Но, чтобы ответить на вопросы, как мы должны осуществлять сортировку и какие ее методы наиболее эффективны, нам необходимо прежде всего решить, как мы будем производить учет.

Чешский иллюзионист Зденек Брадак попал в Книгу рекордов Гиннесса, установив рекорд по сортировке колоды карт. 15 мая 2008 года Брадак смог разложить в правильном порядке колоду из 52 карт всего за 36,16 секунды. Как ему это удалось? Какую технику сортировки он применял?

И хотя его ответ, очевидно, пролил бы свет на теорию сортировки, сам Брадак воздержался от комментария. Мы, несомненно, уважаем мастерство и ловкость маэстро, но при этом мы на 100% уверены, что можем побить его рекорд. Фактически мы уверены, что можем поставить рекорд, который никто не сможет побить.

Все, что нам нужно, — это около 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000 попыток в борьбе за звание рекордсмена. Это число, значение которого немного больше 80 унвигинтиллионов (52 факториал, или 52! в математическом обозначении), — число возможных перестановок в колоде карт.

Предпринимая такое количество попыток, вы рано или поздно обязательно сложите колоду в правильном порядке, при этом абсолютно случайно. Таким образом, теперь мы можем с гордостью вписать в Книгу рекордов Гиннесса имя Кристиана Гриффитса, выступившего с не таким уж и плохим временем — 0 минут 0 секунд.

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

Именитые господа из Книги рекордов Гиннесса беспокоятся только о показателях в наилучшем случае. Конечно, едва ли их можно винить за это, ведь все спортивные рекорды — не что иное, как показатели одного лучшего выступления. Однако информатику практически никогда не волнует наилучший случай.

Вместо этого ученые хотели бы знать, сколько в среднем занимает тасование карт у того же Брадака: было бы здорово заставить его тасовать колоду все 80 унвигинтиллионов раз (или что-то в этом роде) и оценивать его по средней скорости на протяжении всех попыток (теперь вы понимаете, почему программистов не допускают до таких вещей).

Более того, специалисту по информатике было бы интересно узнать и наихудшее время при тасовании колоды. Анализ наихудшего случая позволяет нам получить четкие гарантии, что процесс в принципе конечен, что срок исполнения задачи не будет сорван. Таким образом, до конца этой главы, да и, пожалуй, всей книги мы будем обсуждать действие алгоритмов в наихудших случаях, если не указано иное.

В программировании есть обозначение, придуманное специально для определения сценария алгоритма в наихудшем случае. Это прописная «О», или «О большое». За понятием «О большого» стоит одна небольшая хитрость, которая с первого взгляда не совсем очевидна.

Идея в том, что «О большое» не столько выражает действие алгоритма в минутах и секундах, сколько может характеризовать тип взаимосвязи между размером задачи и временем, потраченным на ее решение. Поскольку «О большое» намеренно проливает свет на некоторые важные детали, перед нами появляется схема разделения задач на различные широкие категории.

Представьте, что вы организуете ужин с друзьями, количество которых мы обозначим как n. Время, которое вам необходимо на уборку дома до их прихода, не зависит от n. Это самая простая категория задач, которая называется «О большое от единицы» (обозначается как «О(1)») и также известна как временная константа.

Примечательно, что для «О большого» абсолютно не важно, сколько времени у вас на самом деле занимает уборка. Главное — что временной промежуток всегда один и тот же, вне зависимости от списка гостей. От вас требуется выполнить одну и ту же работу, не важно, пригласили вы одного друга, десять, сто или любое другое количество.

Теперь время, которое займет передача жаркого вокруг стола, мы обозначим как «О большое от n» (письменно — «O(n)»). Это понятие также имеет другое название — «линейное время». Если количество гостей увеличивается в два раза, то же происходит и с линейным временем.

И снова, для «О большого» безразлично, какое количество блюд вы подаете или, например, сколько раз гости попросят добавки. В каждом случае время линейно зависит от количества приглашенных гостей и график зависимости времени от количества гостей будет представлять собой прямую.

Более того, существование любых линейно-временных факторов — в случае «О большого» — будет перекрывать все факторы временных констант. Другими словами, «передача жаркого вокруг стола» и «передача жаркого вокруг стола после трехмесячной перепланировки вашей столовой» — для программиста, по сути, абсолютно равнозначные величины.

Если вам это кажется безумным, подумайте о том, что компьютеры работают с величинами n, которые могут исчисляться тысячами, миллионами или миллиардами. Иначе говоря, программисты мыслят очень, очень большими объемами данных.

Если у вас миллион гостей, то по сравнению с единичной передачей блюда вокруг стола весь процесс перепланировки дома покажется вам ничтожным. А что если каждый прибывающий гость будет обнимать остальных при приветствии? Ваш первый гость обнимет только вас, второму придется обнять уже двоих, третий гость обнимет уже троих. Сколько объятий случится за вечер?

Эта задача перейдет уже в разряд «О большое от n в квадрате» («О(n²)»), или квадратичного времени. Опять же для нас важны только общие черты связей между переменной n и временем. Не существует формулы O(2n²) для двух объятий на каждого или формулы O(n² + n) для объятий и передачи блюда. Таким образом, O(n²) охватывает все процессы.

Вот здесь становится трудно, потому что появляется экспоненциальное время, которое рассчитывается по формуле O(2^n), когда каждый дополнительный гость удваивает вашу работу. Еще сложней все обстоит с факториальным временем, определяемым по формуле O(n!).

Это категория задач столь бесчеловечно трудных, что программисты упоминают их только в шутку (как мы, говоря, например, о сортировке колоды до победного конца) или когда им на самом деле очень-очень хотелось бы пошутить.

Когда Обама, находясь еще в статусе сенатора, в 2007 году посетил офис Google, глава компании Эрик Шмидт в шутку начал общение в манере собеседования и задал вопрос, как лучше отсортировать миллион 32-битных целых чисел. Обама саркастически улыбнулся и без промедления ответил: «Думаю, пузырьковая сортировка здесь не подойдет».

Толпа инженеров Google разразилась аплодисментами. «Он меня поразил пузырьковой сортировкой», — вспоминал один из них позднее. Обама был прав, что сразу отверг «этот алгоритм, который стал чем-то вроде боксерской груши для студентов-программистов: он достаточно прост, интуитивно понятен и весьма эффективен».

Представьте, что вы хотите расставить в алфавитном порядке одну из ваших книжных коллекций. Самым естественным подходом в этом случае было бы просмотреть книги на полке, чтобы выявить неупорядоченные пары (Уоллес, который «стоит» перед Пинчоном, к примеру) и поменять их местами.

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

Есть n неупорядоченных книг, и в результате каждого осмотра полки вы можете переставить только одну книгу на другое место (решаем проблемы по мере поступления). То есть в худшем случае, если все книги на полке стоят в обратном порядке, то по меньшей мере одну книгу придется переставить на другое место n раз.

Таким образом, мы получаем максимум n осмотров полки, на которой стоит n книг, то есть O(n²) в худшем случае. Но это не слишком ужасно по одной причине: это в миллион раз лучше, чем наша идея сортировки «до победного конца» по формуле O(n!) из предыдущего кейса.

И все же вместе с тем этот квадратный корень может очень скоро вас напугать. Например, квадратный корень означает, что сортировка пяти книжных полок займет не в пять раз больше времени, чем сортировка одной, а в 25 раз больше. В принципе вы можете взять и другой курс — вытащить все книги из шкафа и поставить их в правильном порядке одну за другой.

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

Повторяя этот процесс, вы постепенно расставите все книги на полке в нужном порядке, и ваша миссия будет выполнена. Программисты именуют этот способ довольно логично — сортировкой методом вставок. Хорошая новость в том, что это, возможно, еще более интуитивно понятный метод, чем пузырьковая сортировка, и у него отнюдь не плохая репутация.

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

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

После рассмотрения двух абсолютно разумных подходов, которые переходят в плоскость нерационального квадратичного времени, напрашивается вопрос: а существуют ли способы ускорить процесс сортировки? Вопрос, в сущности, о продуктивности.

Но если обсудить этот вопрос с программистом, то он становится ближе к метафизике — сродни размышлениям о скорости света, путешествиях во времени, сверхпроводниках и термодинамической энтропии. Каковы фундаментальные законы и границы вселенной? Что возможно? Что позволено?

Так программисты пытаются узреть божьи планы наряду с учеными в области физики частиц и космологии. Каково минимальное усилие, необходимое для установления порядка? Возможно ли найти параметр сортировки О(1) (как в случае уборки дома перед приездом компании друзей), по которому можно было бы сортировать любой объем единиц за равное количество времени?

В принципе мы даже не можем утверждать, что процесс сортировки n книг на полке постоянен во времени, поскольку он требует проверки n книг, и это количество, по сути, конечно. Поэтому сортировка книг в условиях временной константы даже не обсуждается.

А если рассмотреть параметр линейного времени О(n), который подобен передаче блюд по кругу за столом, когда удвоение количества объектов удваивает и объем работы? Размышляя о вышеописанных примерах, сложно представить, как же они могут работать. Значение n² в каждом из этих случаев мы получаем в связи с необходимостью переместить n книг, и работа, которую мы должны проделать при каждом перемещении книги, пропорциональна значению n.

Так как же нам уйти от n в степени n и вернуться к самой величине n? При пузырьковой сортировке мы получили значение O(n²) применительно ко времени выполнения задачи, исходя из манипуляций с каждой из n книг и перемещения каждой из них с места на место n раз.

В сортировке методом вставок время выполнения задачи было возведено в квадрат, поскольку мы перемещали с места на место n книг и сравнивали их с тем же количеством (n) других книг прежде, чем выбрать место для очередной книги.

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

Возможно, наш лимит находится где-то между линейным и квадратичным временем. Существуют ли какие-либо алгоритмы между линейным и квадратичным, между n и n × n? Существуют и лежат на поверхности. Как упоминалось ранее, процессы обработки информации были запущены в США во время проведения переписей населения в 19 веке в результате разработки Германом Холлеритом и впоследствии компанией IBM устройств по сортировке перфокарт.

В 1936 году IBM приступила к производству линейки раскладочно-подборочных машин, которые могли объединить две отдельно упорядоченные стопки перфокарт в одну. Если каждая из пачек была разложена в верном порядке, то сам процесс их консолидации был невероятно простым и происходил в линейном времени: необходимо было просто сравнить две верхние карты из каждой стопки между собой, карту с наименьшим порядковым номером переместить в начало новой формируемой пачки и продолжать таким образом до выполнения задачи.

В программе, которую Джон фон Ньюманн написал в 1945 году, чтобы продемонстрировать преимущество ЭВМ с запоминаемой программой, была использована идея подборки и упорядочения перфокарт. Отсортировать две карты легко: просто переложите карту с меньшим порядковым номером поверх второй.

И если у вас есть пара стопок по две карты каждая, сложенных в верном порядке, вы таким же способом можете легко сложить их в одну упорядоченную стопку из четырех карт. Повторяя этот прием несколько раз, вы будете получать все большие и большие стопки разложенных в нужном порядке карт.

Довольно скоро вы соберете идеально упорядоченную стопку путем финального кульминационного объединения всех карт. Этот подход сегодня известен как сортировка с объединением — один из легендарных алгоритмов компьютерной науки.

Как было сказано в одной газете в 1997 году, «появление этого метода так же значимо в истории теории сортировки, как появление самой сортировки в истории развития программирования». Все преимущество этого метода заключается в том, что в нем применяется и линейное, и квадратичное время, а именно линейно-логарифмическое время, которое обозначается формулой O(nlog n).

Каждое перекладывание карты удваивает количество отсортированных пачек. Таким образом, чтобы полностью отсортировать n карт, вам необходимо переложить карты количество раз, равное цифре 2, умноженной на себя столько раз, чтобы конечный результат был равен n.

Другими словами, это логарифм n по основанию 2. Вы можете одновременно сортировать до четырех карт в два действия, до восьми карт третьим действием и до шестнадцати с помощью четвертого перекладывания. Подход «дели и побеждай», лежащий в основе метода сортировки с объединением, вдохновил на создание ряда других линейно-логарифмических алгоритмов, которые начали динамично развиваться.

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

Неудивительно, что этот метод выбирают для решения крупномасштабных промышленных задач. Сортировка с объединением применяется также и в решении задач бытового масштаба. Отчасти причина популярности этого метода лежит в том, что такие сортировки легко выполняются параллельно.

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

Процесс необходимо продолжать до тех пор, пока у вас не сложится две стопки книг и вам останется только объединить их в одну и поставить на полку. Только постарайтесь избежать жирных пятен от пиццы на книгах.

В неприметной промзоне неподалеку от города Престон округа Вашингтон, спрятавшись за общим входом в многочисленные офисы, расположился цех чемпиона Национальной библиотеки 2011 и 2013 года по сортировке.

Длинный сегментированный конвейер переносит 167 книг в минуту — 85 000 в день — в сканер штрихкодов, где они автоматически перенаправляются к своего рода створкам бомбового отсека, через которые книги выбрасываются в одну из 96 корзин.

Сортировочный центр Престона — один из крупнейших и наиболее эффективных объектов в мире в области книжной сортировки. Центром управляет Библиотечная система округа Кинг. Она соперничает с аналогично оснащенной Публичной библиотекой Нью-Йорка уже четыре года, на протяжении которых организации попеременно передают пальму первенства друг другу.

«Библиотека округа Кинг в этом году обойдет нас? — спросил заместитель директора управления библиотеки Нью-Йорка по работе с книжным фондом Сальваторе Магаддино прежде, чем вступить в новую схватку в 2014 году. — Даже не думайте».

С теоретической точки зрения, организация работы в Престонском сортирочном центре тоже не может не впечатлить. Книги, проходящие через его системы, сортируются в условиях линейного времени O(n). Важно отметить, что линейно-логарифмическое время O(n log n), которое применяется в методе сортировки с объединением, — действительно лучший показатель, которого мы только можем добиться.

Было доказано, что если мы хотим полностью отсортировать n элементов посредством прямого сравнительного исследования, то у нас только один выход — сравнивать их O(nlog n) количество раз. Это фундаментальный закон Вселенной, и нет способа его обойти.

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

Два вышеупомянутых принципа, вместе взятые, предусматривают возможность проведения грубых практических сортировок быстрее линейно-логарифмического времени. Этот факт очень наглядно демонстрирует алгоритм, известный как сортировка группировками, который и применяется в Престонском сортировочном центре.

При применении этого метода элементы разбиваются на группы по количеству категорий сортировки без проведения межкатегорийной сортировки (это можно сделать позднее). (В компьютерной науке термин «корзина» обозначает фрагмент неупорядоченных данных, но некоторые довольно-таки буквально воспринимают название метода и применяют его в своей работе, как, например, это делают в Библиотечной системе округа Кинг.)

А вот и изюминка этого метода: если вы хотите сгруппировать n единиц в m корзин, то весь процесс займет у вас время, рассчитываемое по формуле O(n x m), — то есть время, прямо пропорциональное количеству категорий, умноженному на количество корзин.

И поскольку количество корзин относительно невелико по сравнению с количеством сортируемых единиц, то «О большое» округлит показатель времени до O(n), или до линейного времени. Ключ к преодолению линейно-логарифмического барьера — в знании классификации сортируемых элементов.

Неправильно выбранные корзины загонят вас в тот же угол, в котором вы находились в начале процесса сортировки. Если, к примеру, в конце процесса все книги окажутся в одной корзине, то вы не добились никакого результата. Верно подобранные корзины разделят ваши элементы на примерно равные по величине группы, что само по себе — учитывая фундаментальную характеристику сортировки «масштаб убивает» — огромный шаг на пути к полному порядку.

В Престонском сортировочном центре, задачей которого в первую очередь является сортировка книг по тематике и потом уже в алфавитном порядке, подбор корзин происходит на основании статистики обращения. Некоторые тематики пользуются гораздо большей популярностью, и для соответствующих книг может быть выделено несколько корзин.

Аналогичное знание материала будет полезным и в жизни. Чтобы увидеть, как работают эксперты в области сортировки, мы организовали научную командировку в библиотеки Доу и Моффитт при Университете Беркли, книжные коллекции которых собраны на полках в общей сложности длиной в 50 миль.

И отобраны книги были вручную. Книги, которые вернули в библиотеку, вначале попадают в техническое помещение вне общего доступа, затем перемещаются на полки под номерами, присвоенными Библиотекой Конгресса. Например, на определенной группе полок стоит беспорядочный набор возвращенных в библиотеку книг с номерами от PS3000 до PS9999.

Затем студенты, работающие в библиотеке, перекладывают эти книги в тележки (по 150 книг в правильном порядке), чтобы вернуть их на полки в общем зале библиотеки. Студенты проходят небольшую базовую подготовку по сортировке, но со временем они разрабатывают собственные методы и стратегии.

При наличии некоторого опыта они могут отсортировать полную тележку из 150 книг менее чем за 40 минут. И в большинстве своем этот опыт зависит от понимания результата. Студент Беркли Джордан Хо, изучающий химию в качестве основной дисциплины и весьма преуспевший в сортировке, подробно рассказал нам о своей технологии, пока разбирал книги на полках PS3000–PS9999.

Цель Джордана — положить стопку из примерно 25 книг в тележку прежде, чем собрать их все в окончательном порядке, что он и делает, используя сортировку методом вставок. И его слаженная стратегия — это тот самый верный путь к решению задачи: сортировка группировками при понимании конечного результата (то есть то, сколько книг с разными номерами у него получится) подскажет ему, какие корзины необходимо выбрать.

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

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

Но если вы обратитесь к программисту с просьбой помочь вам как-то внедрить этот процесс, то первый вопрос, который он задаст, — а нужна ли вам вообще эта сортировка? Компьютерная наука, по крайней мере как ее преподают студентам, есть наука о компромиссах.

И у нас уже была возможность наблюдать это в сложных отношениях в парах «отмерь — отрежь» и «исследуй — эксплуатируй». Одним из самых ключевых компромиссов здесь является компромисс между начальной сортировкой и последующим поиском.

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

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

Попытка сортировать то, что вы никогда не будете потом искать, — пустая трата времени. Но, с другой стороны, искать что-либо, что вы никогда не сортировали, — просто неэффективно. Неизбежно возникает вопрос: как же заранее определить, чем вы воспользуетесь в будущем?

Для понимания преимуществ использования сортировки стоит обратить внимание на работу поисковой системы, например Google. Трудно даже представить, что Google может взять фразу, которую вы набрали в поисковой строке и затем в поисках совпадений «прочесать» весь интернет менее чем за полсекунды.

Это просто невозможно, это и не нужно. На месте Google вы были бы почти уверены, а) что ваши данные будут искать, б) что эти данные будут искать неоднократно и в) что время, необходимое для сортировки, будет куда менее ценным, чем время, необходимое для поиска.

Вот почему сортировка производится машинным способом намного раньше того момента, когда вам потребуется результат поиска, а поиском занимаются пользователи, для которых время — крайне важный критерий. Все эти факторы демонстрируют огромную пользу предварительной сортировки, которую производит Google и другие его «коллеги» — поисковые системы.

И что, станете ли вы теперь расставлять ваши книги в алфавитном порядке? Для вашей домашней библиотеки в большинстве случаев ни одно из условий, которое может оправдать сортировку, не выполняется. Довольно редко мы ищем книгу под конкретным названием.

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

Редко случается, что нам необходимо настолько срочно найти конкретную книгу, что мы готовы заранее тратить часы на подготовку поиска, чтобы потом сэкономить несколько секунд непосредственно в поиске. Более того, можно сказать, что глаза находят быстро, а руки сортируют медленно.

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

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

Стив Уиттакер — один из мировых экспертов, специализирующихся на особенностях работы с электронной почтой. Ученый-исследователь IBM и профессор Калифорнийского университета в Санта-Круз Уиттакер почти два десятилетия изучает, как люди управляются со своей персональной информацией. (Статью о перегрузке электронной почты он написал в 1996 году — задолго до того, как многие люди стали таковой пользоваться.)

В 2011 году Уиттакер возглавил исследование, касающееся привычек пользователей при поиске и сортировке электронных писем. В результате появилась статья под названием «Стоит ли тратить свое время на организацию электронной почты?».

Вывод автора был однозначным: да. «С одной стороны, это эмпирическое заключение, но, с другой стороны, это также результат опытов, — указывает Уиттакер. — Но когда я интервьюирую людей на тему такого рода организационных проблем, то они обычно говорят, что впустую тратят на это часть своей жизни».

Компьютерная наука демонстрирует, что обе опасности — путаница и порядок — как ни странно, поддаются измерению. И более того, для оценки их стоимости может быть использована общая валюта — время.

Попытка оставить что-либо в несортированном виде может рассматриваться как факт отложенного платежа — перекладывания ответственности на самого себя в будущем, поскольку, если мы решим не платить за это сейчас, потом придется заплатить с довеском. Но в общем и целом все это трудноуловимо. Иногда выбор в пользу беспорядка не означает просто выбор легкого пути. Зачастую это оптимальный выбор.

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

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

Обычные зрители могли бы списать сетования спортсмена на горечь поражения, но слух Доджсона уловил еще и нечто иное. И жалобы теннисиста подтолкнули его к началу глубоких исследований природы спортивных соревнований.

Стоит отметить, что Доджсон был не просто математиком из Оксфорда. По его воспоминаниям, он был чуть ли не единственным математиком. На сегодня этот человек более известен под творческим псевдонимом Льюис Кэрролл, его перу принадлежат «Приключения Алисы в Стране чудес» и многие другие любимые произведения литературы 19 века.

Объединив математический талант с литературным, Доджсон создал одно из своих менее известных произведений «Соревнования по теннису: верные правила присуждения призов с обоснованием ошибочности ныне действующих правил».

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

Как ни странно, даже на современных Олимпийских играх специально проводится дополнительный матч за бронзовую медаль. И даже такой подход вынуждает нас, по всей видимости, признать, что формат турнира на выбывание не дает нам достаточно информации, чтобы выявить заслуженного претендента на третье место.

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

«В качестве математического обоснования можно сказать следующее, — продолжил он. — Вероятность того, что второй по мастерству игрок получит приз, который он заслуживает, может оцениваться только как 16 к 31. В то время как вероятность того, что четыре лучших игрока получат соответствующие призы, настолько мала, что может расцениваться как 12 к 1 против того, что это случится!».

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

Но, если решение Доджсона было громоздким, его критика существующих проблем тем не менее попала в цель. (Хотя, к сожалению, серебряные медали и по сей день все так же выдаются в турнирах на выбывание.) Но логику Доджсона можно понять и на более глубоком уровне.

Мы, люди, сортируем не только наши данные, не только наше окружение. Мы сортируем сами себя. Чемпионаты мира, Олимпийские игры, турниры Национальной ассоциации студенческого спорта, Национальной футбольной, хоккейной, баскетбольной лиги, Главной лиги бейсбола — все эти соревнования неявно реализуют принципы сортировки.

Сезонные соревнования, турниры, игры на выбывание и так далее есть не что иное, как алгоритмы, способствующие определению места в общей «табели о рангах». Один из наиболее известных алгоритмов в спорте — циклический алгоритм, при котором каждая из n команд в итоге играет с каждой из остальных (n − 1) команд.

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

Турнир на выбывание, популярный в таких видах спорта, как бадминтон, сквош и ракетбол, расставляет игроков с использованием линейного рейтинга. При этом каждый игрок имеет право бросить прямой вызов игроку, находящемуся непосредственно над ним в этом рейтинге. А в случае победы — поменяться с ним местами.

Турнир на выбывание, будучи типичным примером пузырьковой сортировки в спорте, также характеризуется квадратичной зависимостью, требуя O(n²) количества игр для формирования стабильного рейтинга. Тем не менее, возможно, наиболее распространенным форматом состязаний среди многих других является соревнование с использованием турнирной сетки — как, например, в известном баскетбольном турнире March Madness, проводимом Национальной ассоциацией студенческого спорта.

Этот турнир прогрессирует от одной тридцатой финала и одной шестнадцатой финала к одной восьмой, затем — элитная восьмерка, финальная четверка и, наконец, финал. Каждый последующий раунд сокращает список участников наполовину, что выглядит привычно, не так ли?

Эти турниры — эффективный пример использования сортировки с объединением, когда дело начинается с несортированных пар команд, которые затем сопоставляются и сравниваются. А поскольку мы знаем, что сортировка с объединением характеризуется линейно-логарифмической зависимостью от времени — O(n log n), то, с учетом того факта, что соревнуются 64 команды, мы можем ожидать, что для проведения турнира потребуется всего около шести раундов (192 игры), а не бесконечных 63 раунда (2016 игр), которые понадобились бы, чтобы сформировать турнир.

«Шесть раундов March Madness» — звучит прекрасно. Но погодите секунду: 192 игры? Ведь этот турнир Национальной ассоциации студенческого спорта длится всего 63 игры. В реальности турнир March Madness не может служить полноценным примером сортировки слиянием, поскольку в его рамках не производится полное упорядочение всех 64 команд.

Ведь для того, чтобы по-настоящему ранжировать все команды, организаторы должны были бы вспомнить о линейно-логарифмической зависимости и назначить ряд дополнительных игр, чтобы определить серебряного призера, затем еще — для определения бронзового призера и так далее. Но этого не происходит на турнире.

Вместо этого, точно копируя подход теннисного турнира, на который жаловался Доджсон, March Madness использует формат поочередного выбывания, где проигравшая команда, выбывая из соревнований, выбывает и из дальнейшей сортировки.

Преимущество такого подхода заключается в том, что он использует линейную зависимость от времени, поскольку каждая игра исключает ровно одну команду. Поэтому, чтобы осталась одна команда, на турнире должно быть сыграно только (n − 1) игр.

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

Вспомните, например, игру «Царь горы»: одна из команд вызывает на бой одного за другим своих соперников до тех пор, пока её саму кто- нибудь не свергнет. И совершенно не важно, в какой момент произойдет смена царя горы и кто именно будет побежден. Новый царь горы займет место на троне, и игра вновь продолжится до победного конца.

Этот вариант имеет недостаток: в любом случае вам понадобится проведение 63 отдельных раундов, поскольку игры не могут идти параллельно. Кроме того, может оказаться так, что одна команда должна будет играть все 63 игры подряд, что достаточно утомительно. Хотя Майкл Трик и родился позже Доджсона почти на целый век, возможно, никто в 21 веке не продвинулся столь же далеко в своих математических исследованиях в спорте.

Мы уже встречались с Майклом в этой книге, но спустя десятилетия с момента незадачливого применения им правила 37% к своей личной жизни многое изменилось: он стал не только мужем и профессором в области операционных исследований, но и одним из основных организаторов матчей для Главной лиги бейсбола, а также таких конференций Национальной ассоциации студенческого спорта, как Big Ten и АСС.

Майкл широко использует в работе принципы информатики. Как отмечает Трик, спортивные лиги не ставят перед собой задачу как можно быстрее и оперативнее сформировать рейтинги. Как раз наоборот, спортивные календари явно составляются так, чтобы держать зрителей в напряжении на протяжении всего сезона. Но это уже вряд ли имеет отношение к теории сортировки.

Более того, спортивные соревнования не ставят перед собой цель минимизировать количество игр. И это важно помнить всегда, потому что в противном случае некоторые аспекты планирования спортивных игр могут показаться весьма загадочными для программистов.

Как говорил Трик, комментируя возможность проведения 2430 игр в рамках регулярного сезона соревнований по бейсболу, «мы знаем, что (n log n) — правильное количество сравнений для проведения полной сортировки. Это вам любой скажет.

Тогда почему же они все-таки ориентируются на n², ведь такая формула требует провести даже больше сравнений для выявления победителя?». Другими словами, зачем использовать цикличный алгоритм O(n²) полностью, а затем еще организовывать дополнительные игры, если полную сортировку можно выполнить гораздо раньше, выявить менее чем за n игр ни разу не проигравшего чемпиона и увенчать его лавровым венком?

Ответ прост: в реальности минимизация количества игр не в интересах лиги. Это в информатике ненужные сравнения всегда плохи, поскольку это пустая трата времени и усилий. А вот в спорте это далеко не так. В конце концов (и со многих точек зрения), именно в самих играх заключены смысл и суть соревнований.

Другой, возможно, даже более важный способ формирования алгоритмического взгляда на спорт, — это попытаться выяснить не то, насколько обоснованно мы вручаем серебряную медаль, а то, насколько мы можем быть уверены, что заслуженно вручаем золотую.

Говоря о некоторых видах спорта, Майкл Трик поясняет, что «в бейсболе, например, вполне естественно, что какая-нибудь команда предполагает проиграть 30% своих игр, а другая, наоборот, собирается выиграть 30% игр». Такой подход — тревожный сигнал для формата соревнований на выбывание.

Судите сами: если, например, в Национальной ассоциации студенческого спорта сильная баскетбольная команда выиграет 70% игр и для окончательной победы в турнире должна будет победить еще в шести матчах на выбывание, шансы этой команды на то, чтобы стать лучшей в турнире, можно оценить как 0,70 к 6, что составит менее 12%.

Иными словами, такой турнир будет короновать реально лучшую команду лишь раз в десять лет. Вполне возможно, что в некоторых видах спорта даже 70% уверенность в результате игры могла бы сильно повлиять на финальный счет.

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

«Так, например, шанс, что команда, выигрывающая со счетом 3 : 2, станет победителем матча, можно оценить лишь как 5 к 8. Лично я не считаю, что это очень впечатляет. Даже победа со счетом 6 : 1 оставляет 7% шанс того, что это была статистическая случайность».

Программисты назвали это явление шумом. Все сортировочные алгоритмы, которые мы упоминали до сих пор, рассматривались нами как совершенные, безупречные, «защищенные от дурака», то есть это были такие алгоритмы, обеспечивавшие сравнения, которые невозможно случайно исказить и по ошибке назвать большей меньшую из двух величин.

И если вы допускаете существование «устройства сравнения шума», то некоторые из наиболее почитаемых алгоритмов информатики можно смело выбрасывать в окно. И наоборот, те, которые были оклеветаны, нужно будет восстановить в правах.

Дэйв Экли, профессор из Университета Нью-Мексико, работающий на стыке наук о компьютерных технологиях и искусственной жизни, считает, что компьютеры могут использоваться для того, чтобы познать некоторые аспекты биологии. Хотя бы потому, что микроорганизмы живут в мире, где некоторые процессы имеют примерно такой же уровень устойчивости, который может характеризовать работу компьютера.

То есть можно сказать, что они выращены с нуля до того уровня, который исследователи характеризуют словом «устойчивость». Поэтому Экли утверждает, что пришло время оценивать алгоритмы также и с точки зрения их устойчивости.

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

Его существенная «неэффективность» проявляется в том, что за один раз можно перемещать элемент только на одну позицию, и это как раз делает его довольно устойчивым по отношению к шуму и гораздо более надежным, чем такие быстрые алгоритмы, как, например, сортировка с объединением, при использовании которой каждое сравнение потенциально перемещает элемент достаточно далеко.

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

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

Это почетное звание — единственного и лучшего — принадлежит алгоритму, который называется «сортировка путем сравнения и подсчета». Каждый элемент сравнивается со всеми остальными, генерируя число, показывающее количество элементов, больших, чем исходный.

Это число может напрямую использоваться в качестве ранга данного элемента. Поскольку при этом попарно сравниваются все элементы, то сортировка путем сравнения и подсчета является таким же квадратично зависимым от времени алгоритмом, как и пузырьковая сортировка.

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

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

Поскольку сортировка путем сравнения и подсчета — единственный наиболее устойчивый алгоритм, то квадратичная или любая другая системы должны предложить болельщикам что-то уж совсем специфическое — и такое, чтобы никто потом не ныл, если его команда не попала в плей-офф.

Использование сортировки с объединением в рамках плей-офф — рискованное мероприятие, в то время как использование сортировки путем сравнения и подсчета в рамках регулярного сезона таковым не является. Сам круговой чемпионат нельзя назвать устойчивым, но турнирные таблицы, формирующиеся на основе его показателей, весьма и весьма устойчивы.

Иными словами, если даже вашу команду вышибают в самом начале плей-офф, это все равно удача. Но если ваша команда не может даже добраться до плей-офф, это уже жестокая реальность. И если ваш расстроенный приятель-болельщик еще может вам посочувствовать, то от ученого вы этого никогда не дождетесь.

Во всех примерах, рассмотренных до сих пор, процесс сортировки в каждом случае происходил сверху вниз: библиотекарь расставлял книги на полке, Национальная ассоциация студенческого спорта указывала командам, когда и с кем играть. Но что, если такие сравнения происходили бы только на добровольной основе? Как бы выглядела сортировка, если бы она производилась более органично — снизу вверх?

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

И хотя некоторые высокоуровневые турниры все-таки сортируют участников явным образом (и вознаграждают их, соответственно), тем не менее значительная часть игроков до сих пор сражается в то, что известно как кеш-игра, где двое или более игроков спонтанно решают сыграть между собой, ставя на кон реальные деньги.

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

Но Хакстон объясняет, что «в некотором смысле самый важный навык профессионального игрока в покер — это умение оценить, насколько хорош твой противник. Если не говорить о тех, кто входит в список лучших игроков в покер в мире, любой игрок может быть уверен в том, что он разорится, если он, конечно, ставит цель играть с профессионалами».

Хакстон возглавляет мировые рейтинги, он всегда готов сразиться один на один, предлагая самые высокие ставки, которые ограничиваются только тем, что есть «на кармане» и чем может ответить соперник. Когда за столом сидят несколько игроков, часто случается так, что один из игроков бывает откровенно слабее, например богатенький любитель поиграть.

И тогда сидящие за столом профессионалы не слишком озабочены выяснением, кто из них играет лучше. В мире профи так не делается. «Разногласия между вами и остальными игроками на тему того, кто играет лучше, возможны только в том случае, если кто-то из вас реально намерен проиграть».

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

Большинство сайтов для игры в онлайн-покер имеют лишь конечное число доступных мест. «Так что, если вы хотите играть, оперируя блайндами в 50 и 100 долларов, в вашем распоряжении только десять доступных столов, — комментирует Хакстон, — да и то подразумевается, что за столом сейчас отсутствуют десять лучших рейтинговых игроков, а все остальные сидят и ждут, что кто-то придет и покажет, что просто хочет поиграть».

И если вдруг за один из этих столов приходит и садится суперигрок, тогда любой игрок, который не желает участвовать в анте, просто покидает стол. «Представьте себе двух обезьян, — говорит Кристоф Нойманн, — одна из которых сидит и мирно ест бананы, срывая их с дерева. В это время к дереву подходит другая обезьяна. Тогда первая просто слезает и уходит».

Будучи университетским биологом, изучавшим поведение и принципы доминирования в семье макак, Нойманн на живом примере описал то, что сейчас известно как замещение. Замещение происходит тогда, когда животное, используя свои знания об иерархии в стае, само принимает решение, что в данный момент не стоит вступать в конфронтацию.

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

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

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

Наблюдение за поведением животных с точки зрения информатики выявляет несколько моментов. С одной стороны, это означает, что число враждебных столкновений для каждой особи будет существенно возрастать — как минимум логарифмически, а возможно, даже и в квадратичной зависимости, поскольку группа становится все больше.

И действительно, исследования антагонистического поведения кур обнаружили, что «агрессивные действия кур усиливались по мере возрастания численности группы». Теория сортировки, таким образом, предполагает, что «этичность» поведения животных повышается при ограничении размера стаи или стада. (В природе дикие куры объединяются в группы от десяти до двадцати особей, что гораздо меньше размера стаи на коммерческих фермах.)

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

Ключевым моментом в понимании сути децентрализованной сортировки в естественных условиях, как утверждает Джессика Флэк, один из директоров Центра вычислений Висконсинского университета, является тот факт, что доминирующая иерархия в конечном счёте сводится к иерархии информационной.

На такие децентрализованные системы сортировки, как подчеркивает Флэк, ложится очень большая вычислительная нагрузка. Количество драк, скажем в группах макак, сводится к минимуму лишь в той степени, в которой каждая обезьяна имеет подробное — и схожее с другими членами — понимание этой иерархии. В противном случае происходит насилие.

Если еще больше углубиться в вопрос о том, насколько хорошо в стае соблюдается установленный порядок, можно сделать вывод, что меньше конфронтаций происходит там, где животные могут лучше «рассуждать и помнить». Вполне возможно, что и люди аналогичным образом пытаются произвести оптимальную и эффективную сортировку.

Как говорит Хакстон о мире покера, «я один из лучших игроков в мире, и я постоянно держу в голове довольно специфический рейтинг двадцатки лучших, на мой взгляд, игроков. Уверен, что каждый из этих игроков в уме формирует примерно такой же рейтинг. Более того, я думаю, что мы в значительной степени единодушны касательно того, как этот список выглядит».

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

В противном случае они будут вынуждены вступать в бой, даже если им это и не нужно. Это напрягает не только тело, но и мозг. Необязательно всегда идти этим путем. Есть и менее затратные способы навести порядок.

Существует, например, одно спортивное соревнование, в котором десятки тысяч конкурентов полностью сортируются в течение ровно того времени, которое требуется для проведения этого мероприятия. (При этом мы должны помнить, что проведение турнира с 10 тысячами участников по цикличному алгоритму требует около 100 миллионов матчей.)

Единственный нюанс состоит в том, что длительность такого турнира определяется его самыми медленными участниками. Это спортивное соревнование называется марафон. И здесь возникает критический момент: гонка принципиально отличается от борьбы.

Давайте повнимательнее рассмотрим суть различий между боксерами и лыжниками, между фехтовальщиками и бегунами. Олимпийский боксер, чтобы подняться на подиум, не только сам рискует получить нокаут O(log n) раз (как пра- вило, в четырёх-шести боях), но и подвергает риску и ставит под угрозу здоровье большого количества других спортсменов.

А вот прыгуну с трамплина или фристайлеру нужно сделать лишь ограниченное число рискованных трюков, связанных с преодолением силы тяжести, причем независимо от дистанции. И если фехтовальщик отдает себя на милость противника O(log n) раз, то тот же марафонец должен выдержать только одну гонку с тем, чтобы, присвоив себе простой числовой показатель, характеризующий результат его работы в алгоритме постоянного времени, определить свой статус.

Такой переход от «порядковых» чисел (которые определяют ранг) к «количественным» показателям (которые служат прямой мерой чьих-то возможностей) естественным образом определяет порядок, в котором нет необходимости сравнивать пары.

Соответственно, это делает возможным появление доминантных иерархий, которые не требуют проведения прямых матчей. Список крупнейших компаний мира Fortune 500, формирующий своего рода корпоративную иерархию, является как раз одним из таких примеров.

Для того чтобы найти самую дорогую компанию Соединенных Штатов, аналитикам не нужно усердно трудиться, поочередно сравнивая Microsoft и General Motors, затем General Motors и Chevron, потом Chevron и Walmart и так далее.

Эти сопоставления, казалось бы, совершенно несопоставимого (программное обеспечение и фьючерсы на нефть) становятся возможными с помощью промежуточного звена — доллара. Наличие измерительного эталона любого вида решает вычислительную задачу при расширении масштабов сортировки.

В Кремниевой долине, например, бытует выражение, касающееся деловых встреч: «Деньги не придут к вам сами, это вы должны идти к ним». Поэтому поставщики идут к владельцам компаний, а владельцы компаний идут к венчурным капиталистам, которые, в свою очередь, идут к своим партнерам и так далее.

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

Несмотря на то что теория морского права с помощью ряда конвенций определяет правила преимущественного прохода судов, тем не менее на практике один простой принцип объясняет, кто кому в море должен уступить дорогу. Это закон «О водоизмещении».

Проще говоря, меньший корабль должен уйти с пути большего. Некоторые животные были бы весьма рады иметь столь четкие доминантные иерархии. Как отмечает Нойманн, «взгляните, например, на рыб — все очень просто: больший экземпляр доминирует».

И, поскольку это так просто, у рыб все происходит мирно. В отличие от кур и приматов, рыбы соблюдают порядок без кровопролития. Когда мы задумываемся о факторах, которые делают возможным существование крупномасштабных человеческих сообществ, нам проще сосредоточиться на технологиях: сельское хозяйство, металлообработка, машиностроение.

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

Этот же принцип работает в спорах как между народами, так и внутри них. Часто отмечается, что такой критерий, как ВВП страны, лежащий в основе рассылки приглашений на встречи на высшем дипломатическом уровне (например, на встречу правительств G20), непродуман и неполноценен.

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

Поскольку споры между народами часто переходят в военные действия, это экономит не только время, но жизни. Линейно-логарифмическое количество боев может выглядеть привычным для небольших групп. То же происходит и в реальной жизни.

Но в мире, где статус устанавливается посредством попарного сравнения (происходит ли это в рамках риторики или с помощью стрельбы), количество конфронтаций быстро выходит из-под контроля по мере количественного роста общества. Промышленный масштаб, когда тысячам или миллионам людей приходится делить одно пространство, требует другого подхода.

Здесь уже требуется скачок от порядкового к количественному. Как бы нас ни огорчала повседневная жизнь, напоминающая порой крысиные бега, один только факт, что это все-таки гонка, а не бой, коренным образом отличает нас от обезьян, кур и — если уж на то пошло — крыс.

#Библиотека