Вот так можно наглядно сравнить эти два метода. Очевидно, что поиски по методу 1 станут значительно медленнее, чем по методу 2, по мере увеличения количества блузок на вешалке.

Как вы уже, вероятно, догадались, в методе 2 выгодно используется знание двух фактов. Во-первых, блузки, скорее всего, отсортированы по размерам. А во-вторых, поскольку у Эппи ходовой размер, то скорее всего нужные ей блузки висят где-то в середине вешалки. Зная это, можно не только начать с середины, но и передвигаться влево или вправо своеобразными скачками, каждый раз сокращая коллекцию вдвое. Такой подход и есть визитная карточка алгоритма логарифмического времени. [14] Это та самая интуиция, которую мы используем, чтобы найти нужное слово в словаре, или имя в телефонном справочнике, или статью в энциклопедии. Те же интуитивные знания мы будем применять, если заснем над скучной книгой и захотим на следующий день возобновить чтение с того же места. В целом можно охарактеризовать этот подход как принцип отбрасывания ненужной информации.

ЭППИ НАХОДИТ СВОЙ РАЗМЕР ЗА 4 ШАГА.

ЭППИ НАХОДИТ СВОЙ РАЗМЕР ЗА 2 ШАГА.

Для нас наиболее важной информацией о логарифмах является то, что они медленно растут, как вы видели из предыдущих графиков. Мы предпочитаем решения, которые растут медленно, потому что это означает, что наш метод не так сильно зависит от количества предметов. Эппи скорее всего найдет нужную вещь на вешалке с сотней блузок менее чем за 7 шагов, а на гипотетической вешалке с тысячью блузок – всего за 10 шагов или около того, что не так уж плохо. Этот метод логарифмического поиска чего-либо в отсортированной группе предметов часто называют бинарным поиском. Он значительно эффективнее метода 1, известного под названием линейный поиск, и благодаря ему Эппи приобрела кучу новых блузок своего размера.

Ян Патой – бывший учитель английской словесности, лингвист. Он пенсионер и живет на востоке Лондона. Несколько лет назад он упал, и теперь у него сильно болит спина. Он не любит выходить на улицу, потому что боится соседской собаки, но ему приходится иногда совершать вылазки за продуктами. В Лондоне часто идет дождь, а старые кости Яна не выносят сырости. Как свести к минимуму количество походов в магазин в неделю, чтобы не умереть с голода?

Есть такой комедийный скетч с двумя Ронни [15] – клиент приходит в скобяную лавку и читает список вещей, которые ему нужно купить. Вместо того чтобы дождаться конца списка, владелец магазина каждый раз хватает названную вещь, и все заканчивается тем, что у продавца едет крыша.

Запомните эту сценку. [16] Мы еще вернемся к ней. Но сначала давайте посмотрим, как Ян может решить, насколько часто ему ходить в магазин.

Вот уже знакомый нам график, где можно посмотреть и сравнить эффективность этих двух методов.

Одна из интерпретаций этой сцены звучит так: важно избегать повторяющейся работы. К примеру, секретарша, которой нужно подшить десять различных отчетов, может сделать дырки во всех десяти листах сразу, а не мучиться с каждым по отдельности. Или же – почему бы не намылить все грязные тарелки разом и не вымыть их вместе, вместо того чтобы тереть и прополаскивать по очереди. Или порезать луковицу вдоль, прежде чем начать шинковать ее поперек. Или оснастить новые высотные здания диспетчерской системой, которая сажает в один лифт пассажиров, едущий на тот же этаж.

Внимательный исследователь может сделать еще одно наблюдение, и оно имеет отношение к походу Яна в продуктовый магазин. Давайте поговорим об этом.

В информационных технологиях есть много способов хранения набора данных. Мы рассмотрели основные способы на примере массива разнопарных носков. Затем во второй сцене мы увидели, как массив может максимизировать какое-либо качество, а именно – возможность поиска путем сортировки контента. Вспомните отсортированные в нужном порядке рубашки на вешалках. Именно это делают структуры данных, или абстрактные типы данных, как их иногда называют. Они повышают значение одного или нескольких свойств, которые нас интересуют, обычно за счет других, не столь важных для нас. Пример: безопасность и удобство работы. Приложение, которое запрашивает у вас пароль каждый раз, когда вы нажимаете на кнопку, возможно, гарантирует большую безопасность, но оно менее удобно в использовании.

Структура, которая, на мой взгляд, заслуживает внимания, известна под именем стек. Стек выводит на первый план качество предмета, который находится сверху, независимо от того, сколько позиций расположено ниже. Так, увидев в кафе стопку газет, вы возьмете просматривать только верхнюю, потому что знаете, что она свежая, а вас интересуют самые последние новости. Точно так же и со стеками: нас интересует то, что находится на самом верху.

В случае с Яном его когнитивный стек состоит из продуктов, которые закончились у него дома. Когда в верхней позиции оказывается «Кит-Кат», Ян решает пойти в магазин и очистить верх стека. Таким образом он постоянно убирает верхние элементы, пока весь стек не очистится. Закончившийся «Кит-Кат» становится триггером для начала очистки стека. До наступления этого момента Ян может спокойно добавлять другие позиции в список и заниматься своими делами.

Наше воспоминание о скетче в исполнении двух Ронни тоже здесь к месту. Оно позволяет владельцу магазина построить воображаемый стек, возможно, по одному для каждого ряда полок, чтобы не лазать вверх и вниз по лестнице много раз. Если бы клиент прочитал весь список нужных товаров, владелец построил бы свои стеки, исходя из расположения полок, создавая позиции для стека каждого ряда.

В 1946 году Алан Тюринг опубликовал научную статью, где представил концепцию стека, используя термин «закапывание». Как отмечает Эндрю Ходжес, автор биографии Тюринга, идея оказалась новостью для фон Неймана. Вот небольшая выдержка из работы Тюринга: