Поскольку сортировка путем сравнения и подсчета – единственный наиболее устойчивый алгоритм, то квадратичная или любая другая системы должны предложить болельщикам что-то уж совсем специфическое – и такое, чтобы никто потом не ныл, если его команда не попала в плей-офф. Использование сортировки с объединением в рамках плей-офф – рискованное мероприятие, в то время как использование сортировки путем сравнения и подсчета в рамках регулярного сезона таковым не является. Сам круговой чемпионат нельзя назвать устойчивым, но турнирные таблицы, формирующиеся на основе его показателей, весьма и весьма устойчивы. Иными словами, если даже вашу команду вышибают в самом начале плей-офф, это все равно удача. Но если ваша команда не может даже добраться до плей-офф, это уже жестокая реальность. И если ваш расстроенный приятель-болельщик еще может вам посочувствовать, то от ученого вы этого никогда не дождетесь.
Кровавая сортировка: неофициальная иерархия и доминирование
Во всех примерах, рассмотренных до сих пор, процесс сортировки в каждом случае происходил сверху вниз: библиотекарь расставлял книги на полке, Национальная ассоциация студенческого спорта указывала командам, когда и с кем играть. Но что, если такие сравнения происходили бы только на добровольной основе? Как бы выглядела сортировка, если бы она производилась более органично – снизу вверх?
Для ответа на этот вопрос рассмотрим игру в онлайн-покер.
В отличие от большинства видов спорта, которые регулируются каким-нибудь управляющим органом, покер остается чем-то беспорядочным, несмотря на его взрывную популярность за последнее десятилетие. И хотя некоторые высокоуровневые турниры все-таки сортируют участников явным образом (и вознаграждают их, соответственно), тем не менее значительная часть игроков до сих пор сражается в то, что известно как кеш-игра, где двое или более игроков спонтанно решают сыграть между собой, ставя на кон реальные деньги.
Исаак Хакстон, один из лучших в мире игроков в покер на деньги, разбирается в этом как никто другой. В большинстве видов спорта очень важно стремиться быть настолько классным, насколько это возможно, и чем меньше игрок стесняется своего умения, тем лучше. Но Хакстон объясняет, что «в некотором смысле самый важный навык профессионального игрока в покер – это умение оценить, насколько хорош твой противник. Если не говорить о тех, кто входит в список лучших игроков в покер в мире, любой игрок может быть уверен в том, что он разорится, если он, конечно, ставит цель играть с профессионалами».
Хакстон возглавляет мировые рейтинги, он всегда готов сразиться один на один, предлагая самые высокие ставки, которые ограничиваются только тем, что есть «на кармане» и чем может ответить соперник. Когда за столом сидят несколько игроков, часто случается так, что один из игроков бывает откровенно слабее, например богатенький любитель поиграть. И тогда сидящие за столом профессионалы не слишком озабочены выяснением, кто из них играет лучше. В мире профи так не делается. «Разногласия между вами и остальными игроками на тему того, кто играет лучше, возможны только в том случае, если кто-то из вас реально намерен проиграть».
Так что же происходит, если установлен некий необъявленный консенсус и никто не желает демонстрировать, что он играет лучше, чем кто-либо другой? Тогда это выглядит так, как будто игроки просто соревнуются в борьбе за место. Большинство сайтов для игры в онлайн-покер имеют лишь конечное число доступных мест. «Так что, если вы хотите играть, оперируя блайндами в 50 и 100 долларов, в вашем распоряжении только десять доступных столов, – комментирует Хакстон, – да и то подразумевается, что за столом сейчас отсутствуют десять лучших рейтинговых игроков, а все остальные сидят и ждут, что кто-то придет и покажет, что просто хочет поиграть». И если вдруг за один из этих столов приходит и садится суперигрок, тогда любой игрок, который не желает участвовать в анте, просто покидает стол.
«Представьте себе двух обезьян, – говорит Кристоф Нойманн, – одна из которых сидит и мирно ест бананы, срывая их с дерева. В это время к дереву подходит другая обезьяна. Тогда первая просто слезает и уходит».
Будучи университетским биологом, изучавшим поведение и принципы доминирования в семье макак, Нойманн на живом примере описал то, что сейчас известно как замещение.
Замещение происходит тогда, когда животное, используя свои знания об иерархии в стае, само принимает решение, что в данный момент не стоит вступать в конфронтацию. Во многих сообществах животных различные ресурсы и возможности – еда, друзья, жизненное пространство и т. д. – являются дефицитом, поэтому кто-то и как-то должен принять решение, кому это может принадлежать. Установление заранее известного и понятного порядка – менее жестокий вариант, чем драки или получение тумаков каждый раз, когда кто-то претендует на поляну сочной травы или возможность спаривания. Вполне возможно, что мы зря переживаем, наблюдая, как животные нацеливают когти и клювы друг на друга. В данном случае биологи склонны считать, что таким образом устанавливается порядок, который вытесняет насилие.
Выглядит знакомо, не правда ли? Именно это называется компромиссной сортировкой.
Создание такой иерархии можно назвать кулачным подходом к решению принципиальной вычислительной задачи. По этой причине, кстати, обрезание кончика клюва у цыплят на ферме, хоть и считается благим намерением, контрпродуктивно, поскольку снижает авторитет отдельных особей, призванных установить порядок, и, следовательно, усложняет птичьему сообществу задачу по организации любой процедуры общей сортировки.
Наблюдение за поведением животных с точки зрения информатики выявляет несколько моментов. С одной стороны, это означает, что число враждебных столкновений для каждой особи будет существенно возрастать – как минимум логарифмически, а возможно, даже и в квадратичной зависимости, поскольку группа становится все больше. И действительно, исследования антагонистического поведения кур обнаружили, что «агрессивные действия кур усиливались по мере возрастания численности группы». Теория сортировки, таким образом, предполагает, что «этичность» поведения животных повышается при ограничении размера стаи или стада. (В природе дикие куры объединяются в группы от десяти до двадцати особей, что гораздо меньше размера стаи на коммерческих фермах.) Исследования также показывают, что агрессия может и вовсе уходить через несколько недель, если в стае не будут появляться новые члены. Это лишний раз подтверждает, что группа сортирует себя.
Ключевым моментом в понимании сути децентрализованной сортировки в естественных условиях, как утверждает Джессика Флэк, один из директоров Центра вычислений Висконсинского университета, является тот факт, что доминирующая иерархия в конечном итоге сводится к иерархии информационной. На такие децентрализованные системы сортировки, как подчеркивает Флэк, ложится очень большая вычислительная нагрузка. Количество драк, скажем в группах макак, сводится к минимуму лишь в той степени, в которой каждая обезьяна имеет подробное – и схожее с другими членами – понимание этой иерархии. В противном случае происходит насилие.
