Алгоритмы для жизни: Простые способы принимать верные решения - [32]
Ключ к преодолению линейно-логарифмического барьера – в знании классификации сортируемых элементов. Неправильно выбранные корзины загонят вас в тот же угол, в котором вы находились в начале процесса сортировки. Если, к примеру, в конце процесса все книги окажутся в одной корзине, то вы не добились никакого результата. Верно подобранные корзины разделят ваши элементы на примерно равные по величине группы, что само по себе – учитывая фундаментальную характеристику сортировки «масштаб убивает» – огромный шаг на пути к полному порядку. В Престонском сортировочном центре, задачей которого в первую очередь является сортировка книг по тематике и потом уже в алфавитном порядке, подбор корзин происходит на основании статистики обращения. Некоторые тематики пользуются гораздо большей популярностью, и для соответствующих книг может быть выделено несколько корзин.
Аналогичное знание материала будет полезным и в жизни. Чтобы увидеть, как работают эксперты в области сортировки, мы организовали научную командировку в библиотеки Доу и Моффитт при Университете Беркли, книжные коллекции которых собраны на полках в общей сложности длиной в 50 миль. И отобраны книги были вручную.
Книги, которые вернули в библиотеку, вначале попадают в техническое помещение вне общего доступа, затем перемещаются на полки под номерами, присвоенными Библиотекой Конгресса. Например, на определенной группе полок стоит беспорядочный набор возвращенных в библиотеку книг с номерами от PS3000 до PS9999. Затем студенты, работающие в библиотеке, перекладывают эти книги в тележки (по 150 книг в правильном порядке), чтобы вернуть их на полки в общем зале библиотеки. Студенты проходят небольшую базовую подготовку по сортировке, но со временем они разрабатывают собственные методы и стратегии. При наличии некоторого опыта они могут отсортировать полную тележку из 150 книг менее чем за 40 минут. И в большинстве своем этот опыт зависит от понимания результата.
Студент Беркли Джордан Хо, изучающий химию в качестве основной дисциплины и весьма преуспевший в сортировке, подробно рассказал нам о своей технологии, пока разбирал книги на полках PS3000–PS9999.
«По своему опыту я знаю, что обычно здесь собирается много книг под номерами до 3500, поэтому в первую очередь я ищу любые книги с номерами именно в этом промежутке. После этого я сортирую эти книги. Далее, я знаю, что раздел номеров 3500 (то есть от 3500 до 3599) сам по себе тоже большой. Поэтому я берусь сразу за весь раздел. Если книг слишком много, я могу сортировать десятками, например: 3510, 3520 и т. д.».
Цель Джордана – положить стопку из примерно 25 книг в тележку прежде, чем собрать их все в окончательном порядке, что он и делает, используя сортировку методом вставок. И его слаженная стратегия – это тот самый верный путь к решению задачи: сортировка группировками при понимании конечного результата (то есть то, сколько книг с разными номерами у него получится) подскажет ему, какие корзины необходимо выбрать.
Сортировка как профилактика поиска
Знание всех этих алгоритмов сортировки, несомненно, пригодится вам в следующий раз, когда вы решите расставить книги на книжной полке в алфавитном порядке. Как и президент Обама, вы будете знать, что для этой цели не стоит прибегать к пузырьковой сортировке. Лучшим решением, которое на данный момент одобрено не только человеком, но и библиотечной автоматикой, будет использование блочной сортировки, по крайней мере до тех пор, пока вы не получите достаточно маленькие стопочки. Теперь наиболее приемлемым станет другой тип сортировки, методом вставки, или же вам придется заказать пиццу и позвать на помощь друзей, как нам предписывает метод сортировки с объединением.
Но если вы обратитесь к программисту с просьбой помочь вам как-то внедрить этот процесс, то первый вопрос, который он задаст, – а нужна ли вам вообще эта сортировка?
Компьютерная наука, по крайней мере как ее преподают студентам, есть наука о компромиссах. И у нас уже была возможность наблюдать это в сложных отношениях в парах «отмерь – отрежь» и «исследуй – эксплуатируй». Одним из самых ключевых компромиссов здесь является компромисс между начальной сортировкой и последующим поиском. Основной вывод: усилия, затраченные на начальную сортировку материалов, ничтожно малы по сравнению с теми усилиями, которые придется затратить, чтобы позже попытаться что-нибудь найти, воспользовавшись этой самой сортировкой. При этом точный баланс усилий должен основываться на конкретной оценке ситуации, потому что попытка представить сортировку как что-то ценное и необходимое для поддержки будущего поиска приводит нас к удивительному умозаключению: ошибка на стороне беспорядка.
Попытка сортировать то, что вы никогда не будете потом искать, – пустая трата времени. Но, с другой стороны, искать что-либо, что вы никогда не сортировали, – просто неэффективно.
Неизбежно возникает вопрос: как же заранее определить, чем вы воспользуетесь в будущем?
Для понимания преимуществ использования сортировки стоит обратить внимание на работу поисковой системы, например Google. Трудно даже представить, что Google может взять фразу, которую вы набрали в поисковой строке и затем в поисках совпадений «прочесать» весь интернет менее чем за полсекунды. Это просто невозможно, это и не нужно. На месте Google вы были бы почти уверены, а) что ваши данные будут искать, б) что эти данные будут искать неоднократно и в) что время, необходимое для сортировки, будет куда менее ценным, чем время, необходимое для поиска. Вот почему сортировка производится машинным способом намного раньше того момента, когда вам потребуется результат поиска, а поиском занимаются пользователи, для которых время – крайне важный критерий. Все эти факторы демонстрируют огромную пользу предварительной сортировки, которую производит Google и другие его «коллеги» – поисковые системы.
