Восхищенный обозреватель писал: «Этот аппарат работает с божественной точностью, но по скорости превосходит даже высшие силы». Другой обозреватель тем не менее отметил, что область применения машины ограничена и «изобретатель вряд ли разбогатеет на этом устройстве, поскольку никто кроме правительства не станет его использовать». Этому прогнозу, который Холлерит взял на заметку, не было суждено сбыться в точности. Фирма Холлерита объединилась с рядом других компаний в 1911 году и вошла в промышленный конгломерат CTR (Computing-Tabulating-Recording Company). Спустя несколько лет компания была переименована в IBM (International Business Machines).
Техника сортировки продолжала подстегивать развитие компьютерной науки на протяжении следующего столетия. Первым в мире кодом, написанным для ЭВМ с запоминаемой программой, стала программа для эффективной сортировки. В сущности, именно способность компьютера заменить аппараты IBM, заточенные исключительно под сортировку перфокарт, убедила американское правительство в том, что колоссальные инвестиции в создание универсальной машины оправданны.
Согласно проведенному исследованию, к 60-м годам ХХ века более четверти мировых компьютерных ресурсов были задействованы в процессах сортировки. Что неудивительно, ведь сортировка – неотъемлемая часть работы практически с любым видом информации. Будь то определение наибольшей или наименьшей величины, общего или частного, суммирование, индексирование, выявление дублирующей информации или просто поиск того, что вам нужно, – все это, в сущности, начинается с процесса сортировки.
На самом деле применение сортировки выходит далеко за рамки этих процессов, поскольку одна из ее основных целей – продемонстрировать человеку возможную пользу вещей. Из этого мы делаем вывод, что сортировка – это также ключ к человеческому восприятию информации.
Отсортированные списки в наше время применяются повсеместно и так естественно внедрились в нашу среду обитания, что нужно быть внимательными и сосредоточенными, чтобы обнаружить их (как рыбе, которая захотела бы узнать, что такое вода). Но, заметив их однажды, вы будете замечать их всегда.
В нашей входящей корреспонденции обычно отображаются последние пятьдесят из тысяч писем, отсортированных по времени получения. Когда мы ищем нужный ресторан с помощью сервиса Yelp, поиск выдает топ-10 мест из сотен, отсортированных по степени удаленности от нас или рейтингу. В блоге обычно показан список записей, отсортированных по дате. Лента новостей в Facebook, поток твитов в Twitter и домашняя страница Reddit представляют собой списки, составленные по тому или иному определенному критерию. Мы считаем сайты вроде Google или Bing поисковыми системами, на самом деле это не совсем корректно: по сути, это системы сортировки. Вся сила Google как средства доступа к мировой информации заключается не в его способности найти наш текст среди сотен миллионов веб-страниц (это было под силу еще его конкурентам в 90-х), но в умении эффективно сортировать эти веб-страницы, показывая нам только те десять, которые максимально соответствуют нашему запросу.
Срез бесконечного множества – упорядоченный список в определенном смысле представляет собой универсальный пользовательский интерфейс.
Информатика помогает нам понять, что стоит за всеми этими ситуациями, а это знание в свою очередь позволяет проанализировать те моменты, когда мы сами сталкиваемся с необходимостью навести порядок в наших счетах, бумагах, книгах, носках и т. д. А происходит это гораздо чаще, чем мы думаем.
Если подсчитать все недостатки (и преимущества) беспорядка, мы можем увидеть случаи, в которых нам не следовало бы наводить порядок. Более того, если вдуматься, мы используем принципы сортировки не только при работе с информацией, но и в отношениях с людьми. Использование принципов компьютерных технологий оказалось неожиданно полезным, к примеру, на боксерском ринге. Все потому, что даже минимальное знание основ сортировки может объяснить, как люди способны мирно сосуществовать, периодически вступая в драку. Другими словами, техника сортировки может поведать нам удивительные вещи о природе нашего общества – того большого и важного порядка, авторами которого мы являемся.
Муки сортировки
«Чтобы снизить себестоимость одной единицы продукции, люди обычно увеличивают объемы производства», – писал Дж. Хоскен в 1955 году в первой научной статье, посвященной технике сортировки. Эта теория экономии на масштабе знакома любому студенту, изучающему бизнес.
Однако с сортировкой ситуация абсолютно противоположная: при росте количества разновидностей «себестоимость единицы сортировки возрастает». Сортировка предполагает существенный рост внешних издержек при увеличении масштаба, ломая наши стандартные представления о преимуществах работы с большими объемами.
Приготовить ужин для двоих обычно не сложнее, чем для одного, и это однозначно проще, чем готовить ужин на одну персону дважды. Но сортировка, скажем, ста книг на одной книжной полке займет у вас гораздо больше времени, чем сортировка двух полок, на каждой из которых стоит по пятьдесят книг. У вас в два раза больше объектов для сортировки и в два раза больше места, на которое можно поставить тот или иной объект. Чем глобальней ваша задача, тем хуже. Это самое первое и наиболее фундаментальное наблюдение о теории сортировки. Масштаб убивает.
Из этого следует: чтобы уменьшить боль и страдания, нам необходимо сократить количество вещей для сортировки.
Это факт: одна из лучших превентивных мер во избежание трудностей с подсчетами при сортировке носков – просто стирать их почаще. Если заниматься стиркой в три раза чаще, можно сократить затраты на вычисления в девять раз.
Действительно, если бы сосед Хиллиса следовал своей излюбленной процедуре, но сократил бы перерыв между стирками с 14 дней до 13, одно это могло бы сэкономить ему 28 «вытягиваний» носков из корзины. (А если бы он увеличил интервал между стирками на день, ему пришлось бы «вылавливать» пару лишние 30 раз.)
Даже на примере такой несложной работы, регулярно проделываемой раз в две недели, мы видим, что масштабы сортировки понемногу становятся в тягость.
В то же время компьютерам приходится регулярно сортировать миллионы различных единиц информации за раз. Для этого, как сказал герой фильма «Челюсти», нам понадобится лодка побольше – и алгоритм получше. Но, чтобы ответить на вопросы, как мы должны осуществлять сортировку и какие ее методы наиболее эффективны, нам необходимо прежде всего решить, как мы будем производить учет.
«О» большое: эталон для худшего случая
Чешский иллюзионист Зденек Брадак попал в Книгу рекордов Гиннесса, установив рекорд по сортировке колоды карт. 15 мая 2008 года Брадак смог разложить в правильном порядке колоду из 52 карт всего за 36,16 секунды
[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 унвигинтиллионов раз (или что-то в этом роде) и оценивать его по средней скорости на протяжении всех попыток (теперь вы понимаете, почему программистов не допускают до таких вещей).
