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

Муки сортировки

«Чтобы снизить себестоимость одной единицы продукции, люди обычно увеличивают объемы производства», – писал Дж. Хоскен в 1955 году в первой научной статье, посвященной технике сортировки. Эта теория экономии на масштабе знакома любому студенту, изучающему бизнес.

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

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

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

Это факт: одна из лучших превентивных мер во избежание трудностей с подсчетами при сортировке носков – просто стирать их почаще. Если заниматься стиркой в три раза чаще, можно сократить затраты на вычисления в девять раз.

Действительно, если бы сосед Хиллиса следовал своей излюбленной процедуре, но сократил бы перерыв между стирками с 14 дней до 13, одно это могло бы сэкономить ему 28 «вытягиваний» носков из корзины. (А если бы он увеличил интервал между стирками на день, ему пришлось бы «вылавливать» пару лишние 30 раз.)

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

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

«О» большое: эталон для худшего случая

Чешский иллюзионист Зденек Брадак попал в Книгу рекордов Гиннесса, установив рекорд по сортировке колоды карт. 15 мая 2008 года Брадак смог разложить в правильном порядке колоду из 52 карт всего за 36,16 секунды[7]7
  Это далеко не единственный рекорд Брадака. Он также может освободиться из трех пар наручников, находясь под водой, примерно за то же время.


[Закрыть]. Как ему это удалось? Какую технику сортировки он применял? И хотя его ответ, очевидно, пролил бы свет на теорию сортировки, сам Брадак воздержался от комментария. Мы, несомненно, уважаем мастерство и ловкость маэстро, но при этом мы на 100 % уверены, что можем побить его рекорд. По сути, мы уверены на 100 %, что можем поставить рекорд, который никто не сможет побить. Все, что нам нужно, – это около 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000 попыток в борьбе за звание рекордсмена. Это число, значение которого немного больше 80 унвигинтиллионов (52 факториал, или 52! в математическом обозначении), – число возможных перестановок в колоде карт. Предпринимая такое количество попыток, вы рано или поздно обязательно сложите колоду в правильном порядке, при этом абсолютно случайно. Таким образом, теперь мы можем с гордостью вписать в Книгу рекордов Гиннесса имя Кристиана Гриффитса, выступившего с не таким уж и плохим временем – 0 минут 0 секунд. По правде говоря, таким способом мы бы точно пытались установить новый рекорд до конца света. Тем не менее этот факт явно указывает на огромные фундаментальные различия между рекордсменами и учеными-компьютерщиками. Именитые господа из Книги рекордов Гиннесса беспокоятся только о показателях в наилучшем случае. Конечно, едва ли их можно винить за это, ведь все спортивные рекорды – не что иное, как показатели одного лучшего выступления. Однако информатику практически никогда не волнует наилучший случай. Вместо этого ученые хотели бы знать, сколько в среднем занимает тасование карт у того же Брадака: было бы здорово заставить его тасовать колоду все 80 унвигинтиллионов раз (или что-то в этом роде) и оценивать его по средней скорости на протяжении всех попыток (теперь вы понимаете, почему программистов не допускают до таких вещей).

Более того, специалисту по информатике было бы интересно узнать и наихудшее время при тасовании колоды. Анализ наихудшего случая позволяет нам получить четкие гарантии, что процесс в принципе конечен, что срок исполнения задачи не будет сорван.

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

В программировании есть обозначение, придуманное специально для определения сценария алгоритма в наихудшем случае. Это прописная «О», или «О большое». За понятием «О большого» стоит одна небольшая хитрость, которая с первого взгляда не совсем очевидна. Суть в том, что «О большое» не столько выражает действие алгоритма в минутах и секундах, сколько может характеризовать тип взаимосвязи между размером задачи и временем, потраченным на ее решение. Поскольку «О большое» намеренно проливает свет на некоторые важные детали, перед нами появляется схема разделения задач на различные широкие категории.

Представьте, что вы организуете ужин с друзьями, количество которых мы обозначим как n. Время, которое вам необходимо на уборку дома до их прихода, не зависит от n.

Это самая простая категория задач, которая называется «О большое от единицы» (обозначается как «О(1)») и также известна как временнáя константа. Примечательно, что для «О большого» абсолютно не важно, сколько времени у вас на самом деле занимает уборка. Главное – что временной промежуток всегда один и тот же, вне зависимости от списка гостей. От вас требуется выполнить одну и ту же работу, не важно, пригласили вы одного друга, десять, сто или любое другое количество.

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

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

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

А что если каждый прибывающий гость будет обнимать остальных при приветствии? Ваш первый гость обнимет только вас, второму придется обнять уже двоих, третий гость обнимет уже троих. Сколько объятий случится за вечер?

Эта задача перейдет уже в разряд «О большое от n в квадрате» («О(n2)»), или квадратичного времени. Опять же для нас важны только общие черты связей между переменной n и временем. Не существует формулы O(2n2) для двух объятий на каждого или формулы O(n2 + n) для объятий и передачи блюда. Таким образом, O(n2) охватывает все процессы.

Вот здесь становится трудно, потому что появляется экспоненциальное время, которое рассчитывается по формуле O(2n), когда каждый дополнительный гость удваивает вашу работу. Еще сложней все обстоит с факториальным временем, определяемым по формуле O(n!). Это категория задач столь бесчеловечно трудных, что программисты упоминают их только в шутку (как мы, говоря, например, о сортировке колоды до победного конца) или когда им на самом деле очень-очень хотелось бы пошутить.

Квадраты: «пузырьковая» сортировка и сортировка методом вставок

Когда Обама, находясь еще в статусе сенатора, в 2007 году посетил офис Google, глава компании Эрик Шмидт в шутку начал общение в манере собеседования и задал вопрос, как лучше отсортировать миллион 32-битных целых чисел. Обама саркастически улыбнулся и без промедления ответил: «Думаю, пузырьковая сортировка здесь не подойдет». Толпа инженеров Google разразилась аплодисментами.

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

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

Это и есть пузырьковая сортировка, и она погружает нас в квадратичное время. Есть n неупорядоченных книг, и в результате каждого осмотра полки вы можете переставить только одну книгу на другое место (решаем проблемы по мере поступления). То есть в худшем случае, если все книги на полке стоят в обратном порядке, то по меньшей мере одну книгу придется переставить на другое место n раз. Таким образом, мы получаем максимум n осмотров полки, на которой стоит n книг, то есть O(n2) в худшем случае[8]8
  На самом деле процесс пузырьковой сортировки занимает ничуть не меньше времени, поскольку в среднем книги будут находиться на n/2 позиций на полке дальше от тех, где должны оказаться в итоге. Программист все равно округлит n/2 осмотра n-ного количества книг на полке до O(n2).


[Закрыть]. Но это не слишком ужасно по одной причине: это в миллион раз лучше, чем наша идея сортировки «до победного конца» по формуле O(n!) из предыдущего кейса. И все же вместе с тем этот квадратный корень может очень скоро вас напугать. Например, квадратный корень означает, что сортировка пяти книжных полок займет не в пять раз больше времени, чем сортировка одной, а в 25 раз больше.

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

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

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

Прохождение через квадрат: дели и побеждай

После рассмотрения двух абсолютно разумных подходов, которые переходят в плоскость нерационального квадратичного времени, напрашивается вопрос: а существуют ли способы ускорить процесс сортировки?

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

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

Каково минимальное усилие, необходимое для установления порядка?

Возможно ли найти параметр сортировки О(1) (как в случае уборки дома перед приездом компании друзей), по которому можно было бы сортировать любой объем единиц за равное количество времени?

В принципе мы даже не можем утверждать, что процесс сортировки n книг на полке постоянен во времени, поскольку он требует проверки n книг, и это количество, по сути, конечно. Поэтому сортировка книг в условиях временной константы даже не обсуждается.

А если рассмотреть параметр линейного времени О(n), который подобен передаче блюд по кругу за столом, когда удвоение количества объектов удваивает и объем работы? Размышляя о вышеописанных примерах, сложно представить, как же они могут работать. Значение n2 в каждом из этих случаев мы получаем в связи с необходимостью переместить n книг, и работа, которую мы должны проделать при каждом перемещении книги, пропорциональна значению n. Так как же нам уйти от n в степени n и вернуться к самой величине n? При пузырьковой сортировке мы получили значение O(n2) применительно ко времени выполнения задачи, исходя из манипуляций с каждой из n книг и перемещения каждой из них с места на место n раз. В сортировке методом вставок время выполнения задачи было возведено в квадрат, поскольку мы перемещали с места на место n книг и сравнивали их с тем же количеством (n) других книг прежде, чем выбрать место для очередной книги. Применение параметра линейного времени означает, что наши манипуляции с каждой книгой происходят в условиях постоянного времени вне зависимости от количества других книг, среди которых мы должны найти место каждой отдельной книге. Это отнюдь не похоже на правду.

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

Существуют и лежат на поверхности.

Как упоминалось ранее, процессы обработки информации были запущены в США во время проведения переписей населения в XIX веке в результате разработки Германом Холлеритом и впоследствии компанией IBM устройств по сортировке перфокарт. В 1936 году IBM приступила к производству линейки раскладочно-подборочных машин, которые могли объединить две отдельно упорядоченные стопки перфокарт в одну. Если каждая из пачек была разложена в верном порядке, то сам процесс их консолидации был невероятно простым и происходил в линейном времени: необходимо было просто сравнить две верхние карты из каждой стопки между собой, карту с наименьшим порядковым номером переместить в начало новой формируемой пачки и продолжать таким образом до выполнения задачи.

В программе, которую Джон фон Ньюманн написал в 1945 году, чтобы продемонстрировать преимущество ЭВМ с запоминаемой программой, была использована идея подборки и упорядочения перфокарт. Отсортировать две карты легко: просто переложите карту с меньшим порядковым номером поверх второй. И если у вас есть пара стопок по две карты каждая, сложенных в верном порядке, вы таким же способом можете легко сложить их в одну упорядоченную стопку из четырех карт. Повторяя этот прием несколько раз, вы будете получать все бóльшие и бóльшие стопки разложенных в нужном порядке карт. Довольно скоро вы соберете идеально упорядоченную стопку путем финального кульминационного объединения всех карт.

Этот подход сегодня известен как сортировка с объединением – один из легендарных алгоритмов компьютерной науки. Как было сказано в одной газете в 1997 году, «появление этого метода так же значимо в истории теории сортировки, как появление самой сортировки в истории развития программирования».

Все преимущество этого метода заключается в том, что в нем применяется и линейное, и квадратичное время, а именно линейно-логарифмическое время, которое обозначается формулой O(nlog n).

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

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

Сортировка с объединением применяется также и в решении задач бытового масштаба. Отчасти причина популярности этого метода лежит в том, что такие сортировки легко выполняются параллельно. Если в ваши планы все еще входит наведение порядка на полке, то решение задачи согласно методу сортировки с объединением будет таким: закажите пиццу и пригласите несколько друзей; затем поделите количество книг поровну между вашими друзьями, и пусть каждый отсортирует свою часть; после этого пусть друзья разобьются по парам и отсортируют книги вдвоем. Процесс необходимо продолжать до тех пор, пока у вас не сложится две стопки книг и вам останется только объединить их в одну и поставить на полку. Только постарайтесь избежать жирных пятен от пиццы на книгах.

За гранью сравнения: перехитрить алгоритм

В неприметной промзоне неподалеку от города Престон округа Вашингтон, спрятавшись за общим входом в многочисленные офисы, расположился цех чемпиона Национальной библиотеки 2011 и 2013 года по сортировке. Длинный сегментированный конвейер переносит 167 книг в минуту – 85 000 в день – в сканер штрихкодов, где они автоматически перенаправляются к своего рода створкам бомбового отсека, через которые книги выбрасываются в одну из 96 корзин.

Сортировочный центр Престона – один из крупнейших и наиболее эффективных объектов в мире в области книжной сортировки. Центром управляет Библиотечная система округа Кинг. Она соперничает с аналогично оснащенной Публичной библиотекой Нью-Йорка уже четыре года, на протяжении которых организации попеременно передают пальму первенства друг другу. «Библиотека округа Кинг в этом году обойдет нас? – спросил заместитель директора управления библиотеки Нью-Йорка по работе с книжным фондом Сальваторе Магаддино прежде, чем вступить в новую схватку в 2014 году. – Даже не думайте».

С теоретической точки зрения, организация работы в Престонском сортирочном центре тоже не может не впечатлить. Книги, проходящие через его системы, сортируются в условиях линейного времени O(n).

Важно отметить, что линейно-логарифмическое время O(n log n), которое применяется в методе сортировки с объединением, – действительно лучший показатель, которого мы только можем добиться. Было доказано, что если мы хотим полностью отсортировать n элементов посредством прямого сравнительного исследования, то у нас только один выход – сравнивать их O(n log n) количество раз. Это фундаментальный закон Вселенной, и нет способа его обойти.

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

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

А вот и изюминка этого метода: если вы хотите сгруппировать n единиц в m корзин, то весь процесс займет у вас время, рассчитываемое по формуле O(n · m), – то есть время, прямо пропорциональное количеству категорий, умноженному на количество корзин.

И поскольку количество корзин относительно невелико по сравнению с количеством сортируемых единиц, то «О большое» округлит показатель времени до O(n), или до линейного времени.

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

Аналогичное знание материала будет полезным и в жизни. Чтобы увидеть, как работают эксперты в области сортировки, мы организовали научную командировку в библиотеки Доу и Моффитт при Университете Беркли, книжные коллекции которых собраны на полках в общей сложности длиной в 50 миль. И отобраны книги были вручную.

Книги, которые вернули в библиотеку, вначале попадают в техническое помещение вне общего доступа, затем перемещаются на полки под номерами, присвоенными Библиотекой Конгресса. Например, на определенной группе полок стоит беспорядочный набор возвращенных в библиотеку книг с номерами от PS3000 до PS9999. Затем студенты, работающие в библиотеке, перекладывают эти книги в тележки (по 150 книг в правильном порядке), чтобы вернуть их на полки в общем зале библиотеки. Студенты проходят небольшую базовую подготовку по сортировке, но со временем они разрабатывают собственные методы и стратегии. При наличии некоторого опыта они могут отсортировать полную тележку из 150 книг менее чем за 40 минут. И в большинстве своем этот опыт зависит от понимания результата.

Студент Беркли Джордан Хо, изучающий химию в качестве основной дисциплины и весьма преуспевший в сортировке, подробно рассказал нам о своей технологии, пока разбирал книги на полках PS3000–PS9999.

«По своему опыту я знаю, что обычно здесь собирается много книг под номерами до 3500, поэтому в первую очередь я ищу любые книги с номерами именно в этом промежутке. После этого я сортирую эти книги. Далее, я знаю, что раздел номеров 3500 (то есть от 3500 до 3599) сам по себе тоже большой. Поэтому я берусь сразу за весь раздел. Если книг слишком много, я могу сортировать десятками, например: 3510, 3520 и т. д.».

Цель Джордана – положить стопку из примерно 25 книг в тележку прежде, чем собрать их все в окончательном порядке, что он и делает, используя сортировку методом вставок. И его слаженная стратегия – это тот самый верный путь к решению задачи: сортировка группировками при понимании конечного результата (то есть то, сколько книг с разными номерами у него получится) подскажет ему, какие корзины необходимо выбрать.