носком в ней.
Как эти два метода соотносятся друг с другом?10 Мы уже заметили, что работа по
методу 1 сильно замедляется по сравнению с методом 2 по мере увеличения носков в куче.
На самом деле существует гораздо больше способов решения задачи. Но нам сейчас важно
показать, чем именно эти два метода радикально отличаются друг от друга, не упоминая
другие, чья эффективность может находиться где-то посередине. К примеру, Марджи могла
бы применить принцип Дирихле – то есть вытаскивать по шесть носков из кучи
одновременно и подбирать пары таким способом.
Вытаскивая носок из кучи, мы достаточно быстро сможем подобрать ему пару.
9 Заметьте, что, применяя оба метода, мы не занимаемся отделением носков от не-носков, поскольку наше
задание – разобраться только с носками ( прим. автора).
10 Есть более сложные методы изучения скорости роста. Один из них – узнать, не растет ли определенный
метод быстрее, чем показанная скорость (известная под названием большое-о), или медленнее, чем показанная
скорость (известная как большое-Ώ, т. е. «большая омега»). Другой метод – посмотреть, описывают ли скорости
роста лучшие, худшие или средние случаи. Мы поговорим обо всех этих случаях позже ( прим. автора).
9
Кратковременная память большинства людей прекрасно работает с группами,
насчитывающими плюс-минус десять предметов, а именно такими величинами мы
оперируем в данный момент. Натыкаясь на носок, который мы уже откладывали в сторону,
мы должны воскликнуть: «А, да – я его уже видел!» Если вы когда-нибудь играли в
карточную игру «Память», преимущества и недостатки этой системы должны быть вам
хорошо знакомы.
Если бы у нас было гораздо больше носков разных типов и цветов, то ряд непарных
оказался бы таким длинным, что нам пришлось бы заново пересматривать всю их
последовательность каждый раз, когда мы вытаскиваем из кучи новый. Это трудоемко и
долго, особенно если искомый предмет оказывается в самом конце.
В 1953 году математик Ханс Питер Лун, работавший в корпорации «IBM», выдвинул
идею, которая положила начало созданию альтернативной структуры, облегчающей
потенциальную замедленность, присущую любому комплексному поиску. Эта структура
иногда называется ассоциативным массивом, или хеш-таблицей (посыплем еще немного
соли на раны старушки Марджи). Хеш-таблица делает то же, что и массив: она сохраняет
вещи в коллекции, но использует более строгую последовательность (например, большой
черный носок всегда идет после красного носка) для немедленного так называемого поиска
за постоянное время.11
Он называется непрерывным, потому что не зависит от длины последовательности.
Впрочем, это не всегда так. Многие вещи в программном обеспечении, к неудовольствию
исследователей и практиков, не подчиняются фундаментальным законам – в отличие от
природы. Но здесь мы допускаем, что из-за малого числа несопоставимых носков синапсы
Марджи будут возбуждаться быстро и вызывать почти немедленную реакцию.
Как мы увидим позже, непрерывный поиск чаще всего происходит в тех случаях, когда
можно смоделировать задание при помощи формулы, которая избавляет от необходимости
выполнять его снова и снова, перебирая все существующие позиции. 12 Известно, что
11 В этом примере Марджи не особенно заботится о том, в каком порядке лежат неразобранные носки. Все,
что ее беспокоит, – все носки должны быть отложены в одну сторону.
12 Например, найти сумму первых чисел n было бы сложно, если бы вы проходились по этим n-числам один
за другим, каждый раз суммируя пары. Гораздо удобнее использовать вместо этого формулу n x (n+1)/2 ( прим.
10
формула, используемая с хеш-таблицами, называется хеш-функция. Ее работа – поместить
вещь в кучу так, чтобы потом можно было вытащить ее из памяти достаточно быстро.
Но отложим эти соображения в сторону. Суть в том, что подход, который использует
одни и те же знания повторно, может быть быстрее, чем тот, который их не использует. Это
особенно полезно знать, когда речь идет о выполнении каких-либо повторяющихся
операций. Например, вы выбираете в магазине коробку свеч в виде букв для именинного
пирога вашей дочери. Или же вы собрались постирать, и вам нужно отделить белое
постельное белье от цветного и нижнего. Или вы пытаетесь составить самое длинное слово
из определенного набора букв, как в британском телешоу «Каунтдаун».
В каждой из этих ситуаций вы спросите себя: можно ли сделать это задание быстрее,
используя память – свою собственную или общечеловеческую? В примере с кучей носков,
составляя ряд носков без пары, мы договорились, что у нас не может быть больше пяти их
типов. В примере с коробкой свеч мы бы выбрали любые подходящие нам четыре буквы,
когда мы натыкаемся на них, а не искали бы отдельно L или U и так далее.
В случае с грязной одеждой удобнее складывать ее в три разные корзины, чтобы не
перебирать перед стиркой. А в ситуации с самым длинным словом можно взять первое
пришедшее на ум слово и посмотреть, нельзя ли удлинить его путем склонения или перевода
в форму множественного числа. Здесь наш первоначальный выбор служит как бы
префиксом13 (взятым из памяти) к последующим словам.
Есть замечательная структура под названием префиксное дерево, которая именно это и
автора).
13 Префикс в информатике – начало строки программы ( прим. ред.).
11
делает. Она пользуется тем, что цифры и номера имеют общие префиксы, чтобы производить
такие операции, как проверка орфографии и автокоррекция слов, которые вы вводите в
строку поиска слишком быстро и при этом делаете ошибки.
РАЗВЕ НЕ ЗДОРОВО, ЧТО ОБЫДЕННОЕ СТАНОВИТСЯ УВЛЕКАТЕЛЬНЫМ,
СТОИТ ТОЛЬКО ПОДОЙТИ К НЕМУ ИНАЧЕ?!
2
Выбери свой размер
На следующий день после Рождества медсестра Эппи Тоам из шотландского городка
Инвернесс рано утром пришла к местному универмагу в ожидании новогодней распродажи.
У Эппи довольно распространенный размер одежды, и она хочет первой ворваться в магазин,
чтобы успеть ухватить все блузки своего размера. Ей нужно делать все быстро. Ситуация
может выйти из-под контроля. В прошлом году во время такой распродажи 15 человек
12
получили травмы, а потом пришлось вызывать военных, чтобы прекратить давку. Как Эппи
может повысить свои шансы заполучить нужные блузки, до того как они попадут в чужие
руки?
Подсказка. Рассматривайте этот пример, доводя его до абсурда. Что, если
стойки с одеждой будут располагаться по всей ширине магазина?
Если мы ищем что-то среди большого количества одежды, то нужно ли просматривать
всю коллекцию? Другими словами, если у нас 100 вещей, должны ли мы просмотреть все
100, то есть занимает ли такая операция линейное время? Смысл линейной функции в том,
что если для нахождения чего-то в куче из 100 вещей нужна минута, то можно ожидать, что
у нас уйдет две минуты на поиск нужной вещи в куче из 200 предметов гардероба.
Обычно так и происходит. Однако коллекция может обладать одним интересным
качеством, а именно: она поддается сортировке, что позволяет найти вещь по алгоритму
логарифмического времени, примерно за 7 шагов, а не за 100. Вспомните, что логарифм – это
всего лишь нечто обратное экспоненте. Составляя компьютерные программы, мы
предполагаем, что основание логарифма есть 2, поэтому логарифм 100 это log2 100, то есть
получается примерно 7. Это значительное улучшение