За гранью сравнения: перехитрить алгоритм
В неприметной промзоне неподалеку от города Престон округа Вашингтон, спрятавшись за общим входом в многочисленные офисы, расположился цех чемпиона Национальной библиотеки 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 книг в тележку прежде, чем собрать их все в окончательном порядке, что он и делает, используя сортировку методом вставок. И его слаженная стратегия – это тот самый верный путь к решению задачи: сортировка группировками при понимании конечного результата (то есть то, сколько книг с разными номерами у него получится) подскажет ему, какие корзины необходимо выбрать.
Сортировка как профилактика поиска
Знание всех этих алгоритмов сортировки, несомненно, пригодится вам в следующий раз, когда вы решите расставить книги на книжной полке в алфавитном порядке. Как и президент Обама, вы будете знать, что для этой цели не стоит прибегать к пузырьковой сортировке. Лучшим решением, которое на данный момент одобрено не только человеком, но и библиотечной автоматикой, будет использование блочной сортировки, по крайней мере до тех пор, пока вы не получите достаточно маленькие стопочки. Теперь наиболее приемлемым станет другой тип сортировки, методом вставки, или же вам придется заказать пиццу и позвать на помощь друзей, как нам предписывает метод сортировки с объединением.
