Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

Более того, спортивные соревнования не ставят перед собой цель минимизировать количество игр. И это важно помнить всегда, потому что в противном случае некоторые аспекты планирования спортивных игр могут показаться весьма загадочными для программистов. Как говорил Трик, комментируя возможность проведения 2430 игр в рамках регулярного сезона соревнований по бейсболу, «мы знаем, что (n log n) – правильное количество сравнений для проведения полной сортировки. Это вам любой скажет. Тогда почему же они все-таки ориентируются на n2, ведь такая формула требует провести даже больше сравнений для выявления победителя?». Другими словами, зачем использовать цикличный алгоритм O(n2) полностью, а затем еще организовывать дополнительные игры, если полную сортировку можно выполнить гораздо раньше, выявить менее чем за n игр ни разу не проигравшего чемпиона и увенчать его лавровым венком? Ответ прост: в реальности минимизация количества игр не в интересах лиги. Это в информатике ненужные сравнения всегда плохи, поскольку это пустая трата времени и усилий. А вот в спорте это далеко не так. В конце концов (и со многих точек зрения), именно в самих играх заключены смысл и суть соревнований.

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

Говоря о некоторых видах спорта, Майкл Трик поясняет, что «в бейсболе, например, вполне естественно, что какая-нибудь команда предполагает проиграть 30 % своих игр, а другая, наоборот, собирается выиграть 30 % игр». Такой подход – тревожный сигнал для формата соревнований на выбывание. Судите сами: если, например, в Национальной ассоциации студенческого спорта сильная баскетбольная команда выиграет 70 % игр и для окончательной победы в турнире должна будет победить еще в шести матчах на выбывание, шансы этой команды на то, чтобы стать лучшей в турнире, можно оценить как 0,70 к 6, что составит менее 12 %! Иными словами, такой турнир будет короновать реально лучшую команду лишь раз в 10 лет.

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

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

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

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

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

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