Алгоритмы для жизни: Простые способы принимать верные решения - [36]

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

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

Поэтому, несмотря на то что авторитетная книга «Сортировка и поиск» безапелляционно заявляет, что «пузырьковая» сортировка не имеет характеристик, явно оправдывающих ее применение», исследование Экли и его сотрудников свидетельствует, что в конце концов и для этого вида сортировки может найтись свое место в ряду алгоритмов. Его существенная «неэффективность» проявляется в том, что за один раз можно перемещать элемент только на одну позицию, и это как раз делает его довольно устойчивым по отношению к шуму и гораздо более надежным, чем такие быстрые алгоритмы, как, например, сортировка с объединением, при использовании которой каждое сравнение потенциально перемещает элемент достаточно далеко. Сортировка с объединением делает этот алгоритм хрупким. Ошибка, допущенная на раннем этапе в сортировке с объединением, подобна случайному проигрышу в первом раунде турнира, который может не только перечеркнуть все надежды любимой команды на победу в чемпионате, но еще и постоянно держать ее в нижней части турнирной таблицы[10]. При этом в соревнованиях, использующих пузырьковую сортировку (лэддер), случайный проигрыш подвинул бы игрока всего лишь на одну позицию вниз.

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

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

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

Кровавая сортировка: неофициальная иерархия и доминирование

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

Для ответа на этот вопрос рассмотрим игру в онлайн-покер.

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