В реальной жизни при сортировке каких-либо вещей вручную, как это делает Чарли, допустимы некоторые вариации метода 1, которые он скорее всего использовал бы. Как мы видели из прежних сравнительных графиков, общее правило таково: для сортировки нескольких вещей годится любой метод. И только когда предметов много, один из методов может оказаться намного лучше другого. Хотя метод 2 не всегда имеет практическую корреляцию в реальной жизни, по крайней мере при сортировке, мы обсудим общий подход в концептуальных терминах.[23]
Для начала заметим, что метод 1 несет в себе определенный ритм. Чарли берет одну пачку конвертов, затем просматривает другие пачки, чтобы определить, куда ее положить. Затем он берет другую пачку конвертов, просматривает остальные пачки и так далее. Мы видели подобный подход раньше, когда разбирали носки, не так ли? Разница в том, что с каждым конвертом Чарли просматривает все другие только один раз, в то время как с носками Марджи могла потратить много времени, выискивая к каждому пару в куче белья.
Подход Чарли в методе 1 – характерная черта алгоритма с квадратичным временем.[24] Каждый раз, когда у вас есть набор предметов (независимо от того, одинаковые ли они или разные) и вы перебираете их все в поисках одного, у вас есть алгоритм с квадратичным временем. Другие примеры подобного алгоритма – примерка нескольких рубашек с целью выбрать подходящую к вашим брюкам или сравнение списка покупок с продуктами на полке в магазине.
В информационных технологиях многие простые способы сортировки данных протекают в квадратичном времени. Подобно методу 1 Чарли, они все работают путем сравнивания смежных пунктов и перемещения их в зависимости от того, какой больше, а какой меньше. Все подходы, построенные на принципе сравнения прилегающих точек, в среднем происходят в квадратичном времени (n2). Иначе говоря, если n – количество конвертов, мы можем описать функцию, которая располагает эти конверты в нужном порядке с помощью сравнения, как «ограниченные n2», то есть в среднем (это ключевое слово!) мы не можем это сделать быстрее. Существует также сортировка методом вставок, методом выделения и пузырьковым методом.
Когда я впервые услышал о сортировке, будучи 16-летним школьником, я сперва не понял, что может быть лучше метода с квадратичным временем. График показывает, что метод 2 значительно быстрее, чем метод 1, поэтому стоит сортировать элементы в субквадратичном времени.
Общий подход к субквадратичному способу сортировки подразумевает такие методы, как разделение и присваивание, то есть разбивание группы предметов на более мелкие группы и сортировку этих групп.[25] Разделение группы пополам есть логарифмический метод, как мы видели ранее, а помещение предметов в одну группу снова – линейный, так как мы берем один предмет один раз. Этот подход к сортировке называют линейно-логарифмическим, и можно представить, что он гораздо быстрее, чем метод с квадратичным временем и немного медленнее, чем метод с линейным временем.[26] Его можно называть лог-линейным, или просто n log n, – этот порядок складывается из времени, затрачиваемого на разделение группы (log n) и на компоновку предметов заново (n). При умножении они дают n log n. Слово «линейно-логарифмический» образовано из двух: «линейный» и «логарифмический». Это создает концепцию, более сложную, чем составляющие ее части, – совсем как с Джедвардом.[27]
Два хорошо известных линейно-логарифмических алгоритма – сортировка слиянием, изобретенная Джоном фон Нейманом в 1945 году, и быстрая сортировка, придуманная Тони Хоаром в 1959 году. Метод 2 для Чарли сходен с сортировкой слиянием. Этап разделения соответствует раскладыванию пачек конвертов на отдельные кучки. А этап обратного слияния – сравнению и совмещению этих пачек. На последнем этапе в первый раз у нас остается набор двух упорядоченных групп. Во второй раз мы получаем уже четыре упорядоченные группы. В случае с Чарли процесс будет выглядеть так:
Заметьте, как он переходит от набора неотсортированных конвертов в первом этапе к набору отсортированных конвертов, хоть и одного размера, на втором. На каждом последующем этапе он совмещает группы, создавая все более длинные ряды отсортированных конвертов, пока у него не останется один ряд, содержащий все конверты. Если мы рассмотрим поближе один из таких этапов, например этап 4, то сможем увидеть, как происходит слияние.
И все же метод 2 – лучший выбор исходя из увеличения скорости, которого он позволяет достичь. Преимущество Чарли в том, что у него всего 33 пачки конвертов для сортировки. Любой метод спасет его от недельных страданий из-за обожженной кожи. Если бы у него было больше конвертов, то скоростной метод 2 оказался бы более предпочтителен, и Чарли, несомненно, извлек бы пользу от знания, как быстрее сортировать почту. Ну, а пока он заканчивает свой рабочий день.
ЗАВЕРШАЯ РАЗВОЗКУ ПОЧТЫ, ЧАРЛИ СЧАСТЛИВ КАК НИКОГДА: СЕГОДНЯ ОН УЗНАЛ КОЕ-ЧТО НОВОЕ. «ВЕЗДЕ ЕСТЬ МЕСТО ДЛЯ ОТКРЫТИЙ, – ГОВОРИТ ОН СЕБЕ, – ДАЖЕ ТАМ, ГДЕ НЕ ОЖИДАЕШЬ».
ПОЛЬЗУЙТЕСЬ НА ЗДОРОВЬЕ. ТОНИ ХОАР. ИЗОБРЕТАТЕЛЬ МЕТОДА БЫСТРОЙ СОРТИРОВКИ
6Стань крутым
Фой недавно переехал в Эшленд. Несмотря на ухоженную бородку-эспаньолку и непременный атрибут при выходе в свет – последний номер журнала «New Yorker» (он носит его под мышкой и никогда не читает, но любит небрежно бросить перед собой на столик в кафе или ресторане); несмотря на все это, он остается аутсайдером на новом месте. Его неизменный ответ на любой серьезный вопрос «Милтон бы не пришел в восторг от этого, поверьте мне», очень скоро начинает звучать банально и претенциозно. «Что вы думаете о новой книге Карла Ова Кнаусгарда?» – Милтон бы не пришел в восторг от этого, поверьте мне». «Вам понравился новый сингл Адели, Фой?» – «Милтон бы не пришел в восторг от этого, поверьте мне».
Переживая за свой имидж, Фой стремится стать настоящим знатоком культуры и искусства. Для начала он решил ознакомиться с наиболее известными представителями музыкального мира и купаться в их славе. Но, оказавшись перед огромным выбором дисков в музыкальных магазинах Эшленда, он растерян и не знает, что делать.
ЦЕЛЬ: ИЗУЧИТЬ ПОПУЛЯРНУЮ МУЗЫКУ.[28]
МЕТОД 1: ВЫБРАТЬ ПОПУЛЯРНОГО ИСПОЛНИТЕЛЯ ИЛИ ИСПОЛНИТЕЛЬНИЦУ И ПОЗНАКОМИТЬСЯ С ЕГО ИЛИ ЕЕ ПЕСНЯМИ, ПОТОМ НАЙТИ ЕЩЕ ОДНОГО И ИЗУЧИТЬ ЕГО ТВОРЧЕСТВО И ТАК ДАЛЕЕ.
МЕТОД 2: ПОЙТИ В МУЗЫКАЛЬНЫЙ МАГАЗИН, ВЫБРАТЬ КУЧУ ПЕСЕН И ПРОСЛУШАТЬ ИХ.
Давайте начнем со способов приобретения новых знаний о музыке.
Можно выбрать метод 1, исходя из того, что веб-сайты то и дело подсовывают нам рекомендации, основанные на анализе наших предпочтений. Этот подход известен как анализ связей и гласит: если имеется набор предметов, содержащих что-то общее, будь то песни, фильмы, люди или запчасти для машины, то, анализируя отношения между этими элементами – их связи, мы можем ответить на вопрос «Какой из этих элементов наиболее важен?». Именно в этом мы сейчас заинтересованы больше всего.
Самый простой пример – цитаты. Частое цитирование и большое количество публикаций, упоминающих некую работу, считаются хорошим показателем, подтверждающим ее важность. Этот подход приписывания более высокой значимости участникам, на которых ссылаются другие, помог Google вырваться на передовые позиции. Их результаты на первой странице выглядят для пользователей более значимыми, чем те, что следуют за ними.
Мы изучим два типа связей: степень, с которой вещи связаны друг с другом, и насколько похожи друг на друга эти связанные элементы.
Степень: допустим, у нас есть богатая коллекция, сборник всех песен мира, и мы можем выделить те пары песен, где автор одной повлиял на другого. Мы посмотрим, кто из них творил раньше или обратимся к информации, опубликованной в открытом доступе. Наша схема будет первоначально иметь такой вид:
Если мы сделаем это со всеми песнями, то в конечном итоге у нас получится много кругов и связей или целая сеть. Но в этой сети не хватает важной части, а именно – непрямых ссылок. Если Боб Марли повлиял на Эрика Клэптона, а тот оказал влияние на Пола Маккартни, то резонно предположить, что влияние Боба Марли распространяется также и на Пола Маккартни. Чтобы отследить эти непрямые ссылки, выполним процедуру, известную под названием умножение матриц. Мы размещаем всех исполнителей на квадратной матрице, ставим точку каждый раз, когда артист слева повлиял на артиста в верхней строке и потом поднимаем матрицу каждого по мере роста его влияния, постоянно отслеживая более давний набор ссылок. Когда мы уже не можем идти дальше (это называется достижением транзитивного замыкания матрицы), мы суммируем все данные и получаем что-то похожее на такую схему.
Посчитав количество точек в ряду каждого исполнителя, мы узнаем имена тех, кто сильнее повлиял на других, и сможем выстроить список самых влиятельных артистов и их песен.
Нельзя применить ту же последовательность шагов к деталям машины. Здесь точка может означать техническую зависимость: колесо зависит от оси, а ось – от шасси. Однако метод анализа связей поможет ответить на вопрос типа: «Поступает много жалоб. Мы думаем, что все дело в сложности этой модели. Можете ли вы сделать список наиболее тесно соединенных между собой частей?» Колесо связано с двумя другими частями прямо или опосредованно. Связаны ли они с четырьмя другими узлами, или пятью, или десятью? Большое число связей для певца отражает его значимость. Но для узлов машины много связей – это плохой показатель, так как он может указывать на потенциальную склонность машины к поломкам.