Текст книги "Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще"

Али Альмоссави
Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

Посвящается Фатиме

МОЖНО ВЕСЬ ДЕНЬ ПЛАВАТЬ В МОРЕ ЗНАНИЙ, НО ТАК И НЕ ПРОМОКНУТЬ.

Нортон Джустер «Призрачная будка»

Ali Almossawi

BAD CHOICES: How Algorithms Can Help You Think Smarter and Live Happier

Copyright © 2017 by Ali Almossawi

© Черепанов В., перевод на русский язык, 2018

© ООО «Издательство «Эксмо», 2018

* * *

ПСИХОЛОГИЧЕСКИЕ БЕСТСЕЛЛЕРЫ

1. Тайная жизнь мозга. Как наш мозг думает, чувствует и принимает решения.

Как мы принимаем решения? Что такое интуиция, и стоит ли ей доверять? В своей книге аргентинский нейробиолог и спикер TED Talks Мариано Сигман берется разгадать тайны человеческого мозга. Он находит ответы даже на самые неразрешимые вопросы о мышлении и раскрывает настоящую роль нейронауки в нашей жизни.

2. Омоложение мозга за две недели. Как вспомнить то, что вы забыли.

Здоровые привычки помогают предотвратить старение мозга ‒ доказано профессором психиатрии Гэри Смоллом. Опираясь на последние достижения медицины и психологии, доктор Смолл расскажет, как за 14 дней улучшить память, начать мыслить продуктивно и укрепить физическое здоровье.

3. Как забыть все забывать. 15 простых привычек, чтобы не искать ключи по всей квартире.

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

4. Игра в возможности. Как переписать свою историю и найти путь к счастью

Мы строим свою жизнь, опираясь на страхи и обиды прошлого ‒ такие шаблоны поведения мешают вам наслаждаться настоящим. Талантливый психотерапевт и коуч Розамунда Зандер расскажет, как избавиться от своих детских травм, развеять старые предубеждения и стереотипы и обрести душевный покой.

Из этой книги вы узнаете:

• как расставить приоритеты при походе в магазин

• как уместить свою мысль в ограниченное количество знаков в Твиттере

• как быстро отсортировать почту

• как найти свой размер одежды на распродаже

• как составить крутой плейлист

Предисловие

Знаете ли вы, когда Ричард Фейнман начал разрабатывать свои знаменитые уравнения, которые принесли ему Нобелевскую премию? Он увидел, как кто-то подбрасывает тарелку в воздух. Знаете ли вы, как Джон фон Нейман сконструировал основные части своего электронного компьютера? Он взял за основу идею своего друга о том, как воспоминания сохраняются в мозге человека. В курсе ли вы, что вид кривляющегося и кричащего орангутанга в клетке навел Чарльза Дарвина[1]1
  Ричард Фейнманн (1918–1988) – американский физик-теоретик; Джон фон Нейман (1903–1957) – венгерский и американский математик; Чарльз Дарвин (1809–1888) – автор теории эволюции (прим. ред.).


[Закрыть] на гениальные мысли? У Фейнманна, фон Неймана, Дарвина и других ученых есть одна общая черта: они видели физику, математику и науку повсюду, далеко за пределами своих лабораторий.

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

Поразительно, но тексты на вавилонских глиняных табличках 1800–1600 годов до н. э. показывают, что древние вавилоняне использовали алгоритмы, скажем, при вычислении сложного процента или расчете ширины и длины резервуара. Иными словами, жизнь вавилонян складывалась из точной последовательности операций. Эти операции требовали определенных усилий, подразумевали конечный результат и приносили пользу.

Алгоритмы встречаются в работах ученых, которые на протяжении многих веков вносили вклад в развитие математики. После появления компьютеров эти характеристики позволили ЭВМ выполнять задачи предсказуемым способом.

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

Цель книги – познакомить вас с алгоритмом мышления при решении повседневных задач и показать, что все эти подходы сравнимы друг с другом. Например, два метода нахождения рубашки нужного размера на вешалке можно описать графически (см. рисунок).[2]2
  Все линии изображены на графике двойного логарифмического масштаба, поэтому они имеют такой вид (прим. автора).


[Закрыть]

Графики такого вида (их называют линейными и логарифмическими) и есть те самые схемы, которые мы будем строить и обсуждать в этой книге. Бывает, что оба подхода одинаково действенны, когда у нас всего несколько предметов, но их эффективность меняется по мере того, как количество предметов растет.

В этой книге мы рассмотрим с точки зрения алгоритмов двенадцать знакомых каждому мест, включая гостиную, мастерскую и универмаг, где нужно будет выполнить ряд заданий. После каждого рисунка следует описание сцены и комментарий. Мы приведем по крайней мере два возможных способа выполнения фундаментального задания: один – медленный, другой – быстрый. Чтобы понять разницу между ними, надо все время помнить заголовок книги, отчасти навеянный рассуждениями ученого Дональда Кнута о «хороших» алгоритмах, которые можно считать быстрыми или эффективными.[3]3
  Важно в самом начале отметить, что эти характеристики не всегда применимы к другим сферам жизни, например к учебе, где скорость – не главное. По моему опыту та обучающая среда, которая требует от студентов работать быстро, настраивает их на неудачу (прим. автора).


[Закрыть]

Введение

Для чего нужны относительные величины?

Сравнения – чрезвычайно мощная штука. Одно из первых абстрактных понятий, которые усваивают дети, – разница между большим и маленьким. Когда ребенок спрашивает: «А какого размера тот титанозавр из Музея естественной истории?», то ответ типа «Не очень большой. Всего семнадцать футов в высоту» мало что скажет малышу. Зато он поймет такое объяснение: «Если бы Сюзан, Маргарет и Яша встали друг другу на плечи, то Яша, наверное, смог бы дотянуться до нижней челюсти ящера».

Возможно, умение оперировать относительными величинами – врожденная способность, поскольку ею обладают все дети. Последние эксперименты показывают, что мозг ребенка проявляет такую же активность в ответ на изменения размера изображения, как и при изменении количества образов. Результаты других экспериментов, проведенных в отдаленных уголках мира, говорят, что люди, избежавшие напасти формального образования, судят о количестве предметов при помощи относительных величин.

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

Именно это обстоятельство стало основной причиной написания этой книги. В школе и колледже я часто прибегал к сравнениям, оценкам, прикидкам и приблизительным величинам для понимания различных терминов и концепций. Я не осмеливался никому признаться в этом, потому что такие методы выглядели слишком простыми. И только прочитав книги «Самый странный человек»[4]4
  В этой книге есть смешной отрывок об Оливере Хивсайде, остром на язык отшельнике, чей подход к математике проектирования отличался особой прагматичностью. Инженеры хвалили метод Хивсайда, но математики смеялись над ним из-за недостатка точности. У Хивсайда же не было времени проявлять дотошность («Стоит ли мне отказываться от ужина, если я не понимаю, как происходит пищеварение?»). (Прим. автора.)


[Закрыть] и «Общество разума», я узнал, что не я один считаю полезным этот тип мышления. Позже я познакомился с работой «Искусство озарения в науке и инженерном деле» и другими книгами, посвященными этой идее.

Я надеюсь, что моя книга поможет вам лучше мыслить и понимать побочные эффекты этой методики. Она не будет учить вас, как лучше находить пары носков – этой интуитивной способностью обладают почти все люди. Скорее она заставит вас задуматься: «Надо же, я и не знал, что о носках можно рассуждать в таких категориях». Похоже, критическое, алгоритмическое мышление – высокоэффективный инструмент, который влияет на наше поведение, меняя его в лучшую сторону.

Зачем фокусироваться на повседневных задачах?

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

Алгоритмы не оторваны от реальности. Не случайно многие объяснения в этой книге сопровождаются иллюстрациями. Рассказывать о чем-либо при помощи рисунков удобно не только потому, что они добавляют красок и эмоций в однообразное повествование. Изображения погружают человека в знакомую среду, включают его в процесс. Вы становитесь способны на более сложные суждения и более интенсивное мышление, когда соединяете новую информацию с известной. Именно поэтому аналогии – очень эффективный инструмент.

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

В этой книге каждый урок представлен в виде сценария или плана на целый день. Такой план заставляет вас развивать собственный подход путем погружения и проигрывания различных ситуаций, проговаривания их; он помогает вам в мыслях выйти за пределы ежедневной рутины. Интерактивный подход делает чтение увлекательнее и дает читателю более полезный обучающий опыт. Мои самые яркие детские воспоминания об учебе – это беседы с родителями или с учителем. Все они понимали, что в обучении процесс так же важен, как способности.

Я допускаю возможность разных итогов. Один из моих любимых афоризмов об обучении принадлежит Фрэнсису Бэкону:[5]5
  Фрэнсис Бэкон (1561–1626) – один из крупнейших философов Нового времени, основоположник эмпиризма и английского материализма (прим. ред.).


[Закрыть] «Второстепенная и неочевидная польза не менее важна, чем признанный всеми положительный результат». На каждый вопрос существует не один ответ. Представьте себе некий музей науки – родители читают надписи на экспонатах и пересказывают их детям как могут. Никто не приходит в этот мир готовым ученым, никто не покидает его, зная все; но каждый обретает что-то ценное за счет своего опыта.

Алгоритмическое мышление в повседневной жизни

1
Найди пару носку

Баронесса Марджи Вана родилась в некогда влиятельной венской семье, но недавно ее обвинили в контрабанде шоколадных яиц «Kinder Surprise» в США. Сейчас она работает гувернанткой по программе языкового обмена в Берне. Впервые в жизни ей предстоит разобрать кучу белья. Марджи обескуражена тем, что все члены семьи, где она проживает, каждые полчаса бросают в корзину для белья пару носков. Найти и разложить носки по парам – дело непростое. При этом у всех разные размеры и каждый предпочитает определенный цвет.

Подсказка. Здесь может быть поставлено сразу несколько задач, но начинайте с самой главной.

Вы когда-нибудь задумывались над тем, какой важной функцией с точки зрения биологии является человеческая память? Когда кто-то откидывается на спинку стула, прикладывая одну руку ко лбу и закрывая глаза в попытке вспомнить стихи, уравнение или телефонный номер, – это сама суть человека. Представьте, какие мучения ждали бы нас в жизни без этой замечательной способности – и как без нее живут люди, страдающие слабоумием. Для начала вам бы пришлось каждый раз заново заполнять голову одними и теми же знаниями, как герою фильма «Помни».[6]6
  «Помни» («Memento») – фильм Джонатана Нолана (2000). Главный герой, переживший тяжелую травму головы, не может ничего удержать в памяти больше 15 минут.


[Закрыть]

Я затронул этот вопрос в самом начале, потому что быстрые методы решения проблем улучшают память.[7]7
  Факт, который часто описывают фразой «торговать памятью за деньги» (прим. автора).


[Закрыть] Вспомните компьютерную программу «AlphaGo», которая недавно победила чемпиона по игре в го благодаря способности учиться не только у экспертов-людей, но и у самой себя, накапливая в памяти все больше информации.[8]8
  Этот подход был впервые применен в Университете Торонто десять лет назад, и сейчас его называют глубоким обучением (прим. автора).


[Закрыть] Иначе говоря, многие быстрые способы решения проблем, с которыми мы познакомимся в этой книге, помогают избежать выполнения одних и тех же однообразных действий по многу раз.

Но не будем забегать вперед. Вернемся к бедной старой Марджи Ване. Итак, ей надо собрать в пары носки, сваленные в огромную кучу одежды. Давайте сфокусируемся на одной из нескольких задач и рассмотрим два возможных способа решения.

ЦЕЛЬ: РАЗЛОЖИТЬ ПО ПАРАМ НОСКИ В КУЧЕ БЕЛЬЯ

МЕТОД 1: ВЫБРАТЬ НОСОК. ПОИСКАТЬ ЕМУ ПАРУ В ГРУДЕ БЕЛЬЯ. ОТЛОЖИТЬ ОБА НОСКА В СТОРОНУ. ВЗЯТЬ ДРУГОЙ НОСОК. ПОИСКАТЬ ЕМУ ПАРУ В ГРУДЕ БЕЛЬЯ. ОТЛОЖИТЬ ОБА НОСКА В СТОРОНУ. И ТАК ДАЛЕЕ.

МЕТОД 2: ВЫБЕРИТЕ НОСОК. ОТЛОЖИТЕ ЕГО В СТОРОНУ. ВЫБЕРИТЕ ДРУГОЙ НОСОК. ЕСЛИ ОН ПОДХОДИТ К ПЕРВОМУ, ОБЪЕДИНИТЕ ИХ. ВЫЛОЖИТЕ В РЯД НОСКИ БЕЗ ПАРЫ. ПОДБЕРИТЕ К НИМ НОСКИ СОВПАДАЮЩЕГО ЦВЕТА И РАЗМЕРА.[9]9
  Заметьте, что, применяя оба метода, мы не занимаемся отделением носков от не-носков, поскольку наше задание – разобраться только с носками (прим. автора).


[Закрыть]

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

Если в куче всего четыре носка, то неважно, какой метод будет использовать Марджи: она быстро справится с задачей. А теперь представьте, что перед ней лежит сотня носков. Если она выберет первый метод, то с большой вероятностью будет снова и снова натыкаться на один и тот же носок, поскольку он остается в общей куче. Вытащив его в первый раз, она не извлечет из него никакой информации.

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

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

В случае с носками наши клавиши скорее всего будут цветными. Когда Марджи находит красный носок, она ищет тот же цвет среди непарных. Найдя его, она может вводить дополнительные идентификаторы/признаки, например стиль или оттенок. Если пара так и не найдена, она создает новую область под названием «красное» с единственным красным носком в ней.

Как эти два метода соотносятся друг с другом?[10]10
  Есть более сложные методы изучения скорости роста. Один из них – узнать, не растет ли определенный метод быстрее, чем показанная скорость (известная под названием большое-о), или медленнее, чем показанная скорость (известная как большое-Ώ, т. е. «большая омега»). Другой метод – посмотреть, описывают ли скорости роста лучшие, худшие или средние случаи. Мы поговорим обо всех этих случаях позже (прим. автора).


[Закрыть] Мы уже заметили, что работа по методу 1 сильно замедляется по сравнению с методом 2 по мере увеличения носков в куче. На самом деле существует гораздо больше способов решения задачи. Но нам сейчас важно показать, чем именно эти два метода радикально отличаются друг от друга, не упоминая другие, чья эффективность может находиться где-то посередине. К примеру, Марджи могла бы применить принцип Дирихле – то есть вытаскивать по шесть носков из кучи одновременно и подбирать пары таким способом.

Вытаскивая носок из кучи, мы достаточно быстро сможем подобрать ему пару. Кратковременная память большинства людей прекрасно работает с группами, насчитывающими плюс-минус десять предметов, а именно такими величинами мы оперируем в данный момент. Натыкаясь на носок, который мы уже откладывали в сторону, мы должны воскликнуть: «А, да – я его уже видел!» Если вы когда-нибудь играли в карточную игру «Память», преимущества и недостатки этой системы должны быть вам хорошо знакомы.

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

В 1953 году математик Ханс Питер Лун, работавший в корпорации «IBM», выдвинул идею, которая положила начало созданию альтернативной структуры, облегчающей потенциальную замедленность, присущую любому комплексному поиску. Эта структура иногда называется ассоциативным массивом, или хеш-таблицей (посыплем еще немного соли на раны старушки Марджи). Хеш-таблица делает то же, что и массив: она сохраняет вещи в коллекции, но использует более строгую последовательность (например, большой черный носок всегда идет после красного носка) для немедленного так называемого поиска за постоянное время.[11]11
  В этом примере Марджи не особенно заботится о том, в каком порядке лежат неразобранные носки. Все, что ее беспокоит, – все носки должны быть отложены в одну сторону.


[Закрыть]

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

Как мы увидим позже, непрерывный поиск чаще всего происходит в тех случаях, когда можно смоделировать задание при помощи формулы, которая избавляет от необходимости выполнять его снова и снова, перебирая все существующие позиции.[12]12
  Например, найти сумму первых чисел n было бы сложно, если бы вы проходились по этим n-числам один за другим, каждый раз суммируя пары. Гораздо удобнее использовать вместо этого формулу n x (n+1)/2 (прим. автора).


[Закрыть] Известно, что формула, используемая с хеш-таблицами, называется хеш-функция. Ее работа – поместить вещь в кучу так, чтобы потом можно было вытащить ее из памяти достаточно быстро.

Но отложим эти соображения в сторону. Суть в том, что подход, который использует одни и те же знания повторно, может быть быстрее, чем тот, который их не использует. Это особенно полезно знать, когда речь идет о выполнении каких-либо повторяющихся операций. Например, вы выбираете в магазине коробку свеч в виде букв для именинного пирога вашей дочери. Или же вы собрались постирать, и вам нужно отделить белое постельное белье от цветного и нижнего. Или вы пытаетесь составить самое длинное слово из определенного набора букв, как в британском телешоу «Каунтдаун».

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

В случае с грязной одеждой удобнее складывать ее в три разные корзины, чтобы не перебирать перед стиркой. А в ситуации с самым длинным словом можно взять первое пришедшее на ум слово и посмотреть, нельзя ли удлинить его путем склонения или перевода в форму множественного числа. Здесь наш первоначальный выбор служит как бы префиксом[13]13
  Префикс в информатике – начало строки программы (прим. ред.).


[Закрыть] (взятым из памяти) к последующим словам.

Есть замечательная структура под названием префиксное дерево, которая именно это и делает. Она пользуется тем, что цифры и номера имеют общие префиксы, чтобы производить такие операции, как проверка орфографии и автокоррекция слов, которые вы вводите в строку поиска слишком быстро и при этом делаете ошибки.

РАЗВЕ НЕ ЗДОРОВО, ЧТО ОБЫДЕННОЕ СТАНОВИТСЯ УВЛЕКАТЕЛЬНЫМ, СТОИТ ТОЛЬКО ПОДОЙТИ К НЕМУ ИНАЧЕ?!

2
Выбери свой размер

На следующий день после Рождества медсестра Эппи Тоам из шотландского городка Инвернесс рано утром пришла к местному универмагу в ожидании новогодней распродажи. У Эппи довольно распространенный размер одежды, и она хочет первой ворваться в магазин, чтобы успеть ухватить все блузки своего размера. Ей нужно делать все быстро. Ситуация может выйти из-под контроля. В прошлом году во время такой распродажи 15 человек получили травмы, а потом пришлось вызывать военных, чтобы прекратить давку. Как Эппи может повысить свои шансы заполучить нужные блузки, до того как они попадут в чужие руки?

Подсказка. Рассматривайте этот пример, доводя его до абсурда. Что, если стойки с одеждой будут располагаться по всей ширине магазина?

Если мы ищем что-то среди большого количества одежды, то нужно ли просматривать всю коллекцию? Другими словами, если у нас 100 вещей, должны ли мы просмотреть все 100, то есть занимает ли такая операция линейное время? Смысл линейной функции в том, что если для нахождения чего-то в куче из 100 вещей нужна минута, то можно ожидать, что у нас уйдет две минуты на поиск нужной вещи в куче из 200 предметов гардероба.

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

Для начала давайте представим, как Эппи носится по магазину с сияющим от гордости и тщеславия лицом. Шарф развевается, ее боевые крики вырываются сквозь стиснутые зубы и отражаются от стен универмага. Она все утро готовилась к этому моменту.

ЦЕЛЬ: НА ВЫБРАННОЙ ВЕШАЛКЕ НАЙТИ БЛУЗКУ СВОЕГО РАЗМЕРА.

МЕТОД 1: ДЛЯ ВЫБРАННОЙ ВЕШАЛКИ. ПРОСМОТРЕТЬ ВСЕ БЛУЗКИ ОДНУ ЗА ДРУГОЙ.

МЕТОД 2: ДЛЯ ВЫБРАННОЙ ВЕШАЛКИ. НАЧНИТЕ ИСКАТЬ СВОЙ РАЗМЕР В СЕРЕДИНЕ ВЕШАЛКИ. ЕСЛИ ТАМ ВИСЯТ БЛУЗКИ РАЗМЕРОМ БОЛЬШЕ, НУЖНО ПОЙТИ НАЛЕВО. ЕСЛИ ЖЕ РАЗМЕРЫ МЕНЬШЕ – НАПРАВО.

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

Как вы уже, вероятно, догадались, в методе 2 выгодно используется знание двух фактов. Во-первых, блузки, скорее всего, отсортированы по размерам. А во-вторых, поскольку у Эппи ходовой размер, то скорее всего нужные ей блузки висят где-то в середине вешалки. Зная это, можно не только начать с середины, но и передвигаться влево или вправо своеобразными скачками, каждый раз сокращая коллекцию вдвое. Такой подход и есть визитная карточка алгоритма логарифмического времени.[14]14
  Сходным образом процесс многократного удвоения чисел от 1 до n логарифмичен, поскольку мы можем сделать не более чем log n скачков, прежде чем получим n. Например, сколько лет уйдет на зарабатывание 1 млн долларов, если начать с 1 доллара и каждый год удваивать его? Можно посчитать это вручную или же применить log2 1 000 000 = 19,93 года (прим. автора).


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

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

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

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