Текст книги "Алгоритмы для жизни: Простые способы принимать верные решения"

Сортировка как профилактика поиска

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

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

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

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

Неизбежно возникает вопрос: как же заранее определить, чем вы воспользуетесь в будущем?

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

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

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

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

Стив Уиттакер – один из мировых экспертов, специализирующихся на особенностях работы с электронной почтой. Ученый-исследователь IBM и профессор Калифорнийского университета в Санта-Круз, Уиттакер почти два десятилетия изучает, как люди управляются со своей персональной информацией. (Статью о перегрузке электронной почты он написал в 1996 году – задолго до того, как многие люди стали таковой пользоваться.) В 2011 году Уиттакер возглавил исследование, касающееся привычек пользователей при поиске и сортировке электронных писем. В результате появилась статья под названием «Стоит ли тратить свое время на организацию электронной почты?». Вывод автора был однозначным: да. «С одной стороны, это эмпирическое заключение, но, с другой стороны, это также результат опытов, – указывает Уиттакер. – Но когда я интервьюирую людей на тему такого рода организационных проблем, то они обычно говорят, что впустую тратят на это часть своей жизни».

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

Сортировка и спорт

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

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

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

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

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

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

Жалоба Доджсона была направлена организаторам очередного турнира на выбывание, по правилам которого игроки должны были попарно играть друг с другом и выбывать из соревнований после первого же проигрыша. Доджсон решительно утверждал, что в реальности вторым по мастерству игроком может быть любой из игроков, выбывших даже на предварительном этапе, не обязательно тот, кто проиграл чемпиону. Как ни странно, даже на современных Олимпийских играх специально проводится дополнительный матч за бронзовую медаль. И даже такой подход вынуждает нас, по всей видимости, признать, что формат турнира на выбывание не дает нам достаточно информации, чтобы выявить заслуженного претендента на третье место[9]9
  Иногда, например в боксе, применяется другой подход. Чтобы боксеру не приходилось снова выходить на ринг после недавнего нокаута (что небезопасно с медицинской точки зрения), на соревнованиях вручаются сразу две бронзовые медали.


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

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

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

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

Чемпионаты мира, Олимпийские игры, турниры Национальной ассоциации студенческого спорта, Национальной футбольной, хоккейной, баскетбольной лиги, Главной лиги бейсбола – все эти соревнования неявно реализуют принципы сортировки. Сезонные соревнования, турниры, игры на выбывание и т. д. есть не что иное, как алгоритмы, способствующие определению места в общей «табели о рангах».

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

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

Тем не менее, возможно, наиболее распространенным форматом состязаний среди многих других является соревнование с использованием турнирной сетки – как, например, в известном баскетбольном турнире March Madness, проводимом Национальной ассоциацией студенческого спорта. Этот турнир прогрессирует от одной тридцатой финала и одной шестнадцатой финала к одной восьмой, затем – элитная восьмерка, финальная четверка и, наконец, финал. Каждый последующий раунд сокращает список участников наполовину, что выглядит привычно, не так ли? Эти турниры – эффективный пример использования сортировки с объединением, когда дело начинается с несортированных пар команд, которые затем сопоставляются и сравниваются.

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

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

В реальности турнир March Madness не может служить полноценным примером сортировки слиянием, поскольку в его рамках не производится полное упорядочение всех 64 команд. Ведь для того, чтобы по-настоящему ранжировать все команды, организаторы должны были бы вспомнить о линейно-логарифмической зависимости и назначить ряд дополнительных игр, чтобы определить серебряного призера, затем еще – для определения бронзового призера и т. д. Но этого не происходит на турнире. Вместо этого, точно копируя подход теннисного турнира, на который жаловался Доджсон, March Madness использует формат поочередного выбывания, где проигравшая команда, выбывая из соревнований, выбывает и из дальнейшей сортировки. Преимущество такого подхода заключается в том, что он использует линейную зависимость от времени, поскольку каждая игра исключает ровно одну команду. Поэтому, чтобы осталась одна команда, на турнире должно быть сыграно только (n − 1) игр. Минусом является тот факт, что вы никогда не поймете, какое место занимает ваша команда в общей турнирной таблице, если только не займете первое место.

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

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

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

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

Более того, спортивные соревнования не ставят перед собой цель минимизировать количество игр. И это важно помнить всегда, потому что в противном случае некоторые аспекты планирования спортивных игр могут показаться весьма загадочными для программистов. Как говорил Трик, комментируя возможность проведения 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]10
  Стоит отметить, что расписание игр в турнире March Madness сознательно строится так, чтобы смягчить этот недостаток алгоритма. Казалось бы, самой большой проблемой в турнире на выбывание, как мы уже отмечали, должен быть сценарий, при котором какая-нибудь команда, будучи побежденной и располагаясь в нижней (несортированной) части таблицы, становится затем серебряным призером. Ассоциация принимает это во внимание и организовывает посев команд с высоким рейтингом так, чтобы топовые команды не могли встретиться друг с другом на ранних стадиях турнира. Такой подход к посеву команд оказывается оправданным и более надежным в большинстве случаев. В истории турнира еще не было случая, когда посеянная под шестнадцатым номером команда вдруг побеждала бы команду, посеянную под первым номером.


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

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

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

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