11Заполни полки
Терри учится на втором курсе престижного вуза Medlock High в Беверли-Хиллз (Калифорния). Он наказан (оставлен после занятий) за затеянную на лекции по социологии провокационную дискуссию на тему «Не во всем должны быть авокадо и капуста». В качестве воспитательной меры куратор отправил Терри в школьную библиотеку и велел выставить книги на только что купленную полку. Старая полка недавно обрушилась, и около 250 книг оказалось на полу. Все, что нужно сделать второкурснику-бунтарю, – выстроить книги на полке в алфавитном порядке по фамилиям авторов. Терри собирается вечером сходить в кино с друзьями и не хочет застрять в университете до полуночи. Ему удастся все сделать, но нельзя терять ни минуты.
ЦЕЛЬ: ВЫСТАВИТЬ ВСЕ КНИГИ НА ПОЛКУ В АЛФАВИТНОМ ПОРЯДКЕ.
МЕТОД 1: ВЗЯТЬ КНИГУ И ПОСТАВИТЬ ЕЕ НА ПОЛКУ. ВЗЯТЬ ДРУГУЮ И ПОСТАВИТЬ ЕЕ ПЕРЕД ИЛИ ПОСЛЕ ПЕРВОЙ, В ЗАВИСИМОСТИ ОТ ФАМИЛИИ АВТОРА. И ТАК ДАЛЕЕ.
МЕТОД 2: ИСПОЛЬЗОВАТЬ КНИЖНЫЕ ДЕРЖАТЕЛИ, ЧТОБЫ ОСТАВЛЯТЬ МЕСТО ПОСЛЕ КАЖДОЙ БУКВЫ АЛФАВИТА, ЗАТЕМ СТАВИТЬ КНИГИ, ПЕРЕМЕЩАЯ ДЕРЖАТЕЛИ ПО МЕРЕ НАДОБНОСТИ.
Давайте вначале решим, как Терри может поступить с заданием. Мы видели в главе 15, что подходы к сортировке, которые строятся на сравнении смежных элементов и определении, какой из них больше, а какой меньше, занимают квадратичное время. Мы говорили, что примеры такого подхода на практике включают в себя сортировку вставкой, сортировку выбором и пузырьковую сортировку и что все они работают, используя образец с минимальными различиями. Метод 1 Терри – это тот же подход, что и метод 1 Чарли из главы 5.
Здесь интересно, что усовершенствованный метод Терри не останавливается на алгоритме разбивания, как в случае с Чарли. Он модифицирует оригинальный алгоритм квадратичного времени. Это происходит при внедрении относительно простой инновации. Если мы возьмем такой алгоритм, как сортировка вставкой, мы обнаружим, что самым медленным действием будет помещение элемента на правильное место. Каждый раз после того, как мы делаем это, приходится менять расположение всех последующих элементов, передвигая их один за другим.
Что происходит при применении метода 2 Терри? Он заранее учитывает эти сдвиги, создавая пустые пространства по всей длине полки через равные промежутки. Найдя нужное место для вставляемой книги, Терри, вероятнее всего, передвинет лишь несколько других книг. Чем больше и шире эти свободные пространства, тем меньше книг ему придется сдвигать каждый раз.
Эта модернизация метода сортировки путем вставки ведет от алгоритма квадратичного времени к линейно-логарифмическому «с высокой вероятностью», как выразился его автор, и называется библиотечной сортировкой. Вспомните идею из главы 10: расставление книжных держателей по полке может сделать этот подход медленнее, если книг мало, но при их достаточно большом количестве он обладает преимуществом перед альтернативным алгоритмом.
Вот как два этих подхода выглядят на графике:
Возможно, мы лучше поймем выигрышность этого подхода, рассмотрев альтернативный, чуть более ограниченный сценарий. Вот какую мрачную картину рисуют авторы библиотечной сортировки: технологическая индустрия накрылась медным тазом, мир устал от ее глупых идей. Тысячи уволенных работников нашли убежище в некоем месте, где применяют свои таланты в обмен на бесплатную пиццу с приправами. Приток специалистов привел в восторг университеты по всей стране. Все рады, кроме архивариуса в том самом колледже. Да, пятнадцать лет назад его звали Терри. Он заведует полками с ячейками, которые промаркированы именами всех выпускников кафедры, расположенными в алфавитном порядке, и затем двигает поверх всех остальных лейблов один.
Теперь, когда частота движения ячеек достигла космической скорости, Терри вспомнил об алгоритме, который он применял когда-то в школе. Он признает, что подобный подход поможет снизить его стресс за счет высвобождения свободного пространства. И вот он создает пустые кармашки между занятыми ячейками.[42]
Недавнее упоминание о «высокой вероятности» подводит нас к важной теме и одновременно сути этой главы. Прежде мы мимоходом упоминали о «худших случаях» и «средних случаях» для разных алгоритмов. Эти существенные показатели позволяют спрогнозировать, сколько времени уйдет у определенного алгоритма на перебор всего ряда элементов.
Время осуществления алгоритма зависит от многих условий. Например, в коде мы можем столкнуться с присутствием логических ветвей (если это не ваш случай, то пропустите этот абзац). Исходя из того, какой путь выбран, время пробега может варьироваться. Хороший пример – быстрая сортировка, которая упомянута в главе 5. При быстрой сортировке разделение начинается в первую очередь с выбора опорного элемента. Этот элемент используется для разделения массива данных на две группы: в одной содержатся элементы меньше опорного, в другой – больше него. Когда опорный элемент выбирается наугад, быстрая сортировка в среднем случае проходит в логарифмическом времени. Если опорный элемент слишком велик или слишком мал, быстрая сортировка может идти в квадратичном времени в худшем случае. Это изменение в производительности происходит из-за того, что опорный элемент не справляется с разделением массива элементов на каждом этапе, и приходится проверять почти каждый элемент на каждом из тех этапов, которые, как мы видели в ранних главах, являются атрибутами квадратичного алгоритма.
Анализ быстрой сортировки показывает, что алгоритм имеет высокую вероятность прохождения в линейно-логарифмическом времени. Мы знаем, что нужно сделать, чтобы достичь этого, – убедиться, что опорный элемент не является самым верхним или самым нижним в массиве. Таким образом элемент с усредненным значением применим практически для всех случаев и может гарантировать, что быстрая сортировка пройдет в линейно-логарифмическом времени.
Но иногда вероятной гарантии все же недостаточно. Если наш алгоритм работает с таким приложением, как управление космическим шаттлом, или представляет угрозу для чьей-то жизни, регулирует работу инфузионного насоса или дефибриллятора, то показатель наихудшего случая будет нас сильно беспокоить. Классификация потенциального результата полезна и в других приложениях, применимых в повседневной жизни.
Для Терри средний случай линейно-логарифмического времени более чем предпочтителен, хотя поиск по его алгоритму в худшем случае будет проходить в квадратичном времени. Сейчас ему не о чем волноваться. Пока у него достаточно книжных разделителей, он успевает в кино вовремя.
12В супермаркете
Вурзма Моне до недавнего времени работал менеджером в фонде управления инвестиционными бумагами. Непостижимое решение стать рэпером возникло у него после того, как он прочитал в одной из школ лекцию о страховке кредиторов от дефолта. Беседа прошла под лозунгом «Кем работает мой отец», и к полудню Вурзма решил вести более осмысленную жизнь. Он ходит в местный супермаркет каждые две недели и часто ловит себя на том, что бродит по проходам из одного конца в другой в поисках нужных ему вещей из списка покупок. Туда-сюда, туда-сюда – у него уходит целая вечность на покупки. Визит в магазин еще больше затягивается из-за странной походки Вурзмы, которая мало походит на «крутую пацанскую» и больше напоминает ребят, которые своим видом будто говорят: «Я пропустил очередную консультацию у психотерапевта». Другие рэперы сразу замечают это несоответствие, и хрупкое доверие к Вурзме со стороны уличной продвинутой молодежи еще больше слабеет. Ему надо перестать выглядеть идиотом и избавиться от мыслей, обрекающих его на смехотворное существование.
Вурзма находится на перепутье. Но у нас хорошая новость: похоже, мы знаем, как ему помочь, и в этой главе рассмотрим варианты, о которых уже говорили в предыдущих главах. Есть два способа, которые Вурзма может использовать, бродя по супермаркету в поисках продуктов из списка.
ЦЕЛЬ: СВЕСТИ К МИНИМУМУ КОЛИЧЕСТВО РЯДОВ, ПО КОТОРЫМ НУЖНО ПРОЙТИ.
МЕТОД 1: ПРОСМОТРЕТЬ ВЕСЬ СПИСОК ПОКУПОК ПО ПУНКТАМ.
МЕТОД 2: ПОДГОТОВИТЬ СПИСОК ЗАРАНЕЕ, ЧТОБЫ ВСЕ БЫЛО РАЗЛОЖЕНО ПО КАТЕГОРИЯМ. ПРОСМАТРИВАТЬ ОДНУ КАТЕГОРИЮ ЗА ДРУГОЙ, СОВЕРШАЯ ПОКУПКИ.
Я положу свой массив в твой массив, чтоб ты не стартовал, не спросив
До сих пор мы говорили о массивах как о фундаментальной структуре, предназначенной для хранения набора элементов. В главе 6 мы ввели еще одну полезную структуру под названием матрица, которая также нужна для хранения групп элементов. Но здесь они сохраняются в двух измерениях, а не в одном. Что общего у этих двух структур? А то, что массив может быть преобразован в матрицу. Все, что нужно для этого сделать, – вместо сохранения литер (как, например, цифра, буква или слово) в каждом расположении сохранить массив. Массив массивов называется двумерным, или в более общем виде многомерным массивом.
Многомерные массивы позволяют нам с Вурзмой сделать одну полезную вещь – сохранить список покупок в двух измерениях, что позволит нашему герою двигаться по любому подмассиву в зависимости от отдела, в котором он сейчас находится.
Итак, список покупок из простого перечня пунктов становится списком категорий, причем каждая из них, в свою очередь, представляет собой список пунктов.[43] Поскольку продукты в магазине обычно группируются по категориям, Вурзма может просто отправиться в ту часть магазина, где находятся, например, предметы личной гигиены, пробежаться по массиву под названием «личная гигиена» и взять нужные ему вещи со стеллажа. То же самое – для всех остальных покупок. Вот как занимаются шопингом по методу 2. Если бы Вурзма использовал обычный список – массив, как в методе 1, то он бы бродил примерно 13 минут от одного ряда к другому, в худшем случае – просто изучая полки.