Переводчик Е. Матвеев

Адитья Бхаргава

Грокаем алгоритмы. 2-е изд.. — СПб.: Питер, 2024.

ISBN 978-5-4461-4172-2

© ООО Издательство "Питер", 2024

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

Посвящается моим родителям — Сангите и Йогешу

Отзывы о первом издании

Этой книге удалось невозможное: сделать математику простой и интересной!

Сандер Россел (Sander Rossel), COAS Sotware Systems

А вам бы хотелось изучать алгоритмы так же, как вы читаете свой любимый роман? Если да, то это именно та книга, которая вам нужна!

Санкар Раманатан (Sankar Ramanathan), IBM Analytics

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

Амит Ламба (Amit Lamba), Tech Overture, LLC

Алгоритмы — это вовсе не скучно! Эта книга была интересной и полезной для меня и моих студентов.

Кристофер Хаупт (Christopher Haupt), Mobirobo, Inc

Предисловие

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

К сожалению, не у всех имеются равные возможности доступа к программированию. Например, в США среди изучающих программирование очень мало женщин и представителей некоторых этнических/расовых групп. Очень важно, чтобы программирование и computer science получили распространение в разнообразных группах. Решение этой проблемы потребует изменений на многих направлениях, включая преодоление предрассудков, подготовку большего количества преподавателей и обеспечение разнообразного опыта обучения. Нужно помочь «включиться» большему количеству людей.

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

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

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

Благодаря своему опыту преподавания Бхаргаве удалось уместить много полезного в небольшом объеме текста. Например, меня поразило, как в главе «Динамическое программирование» Бхаргава аккуратно дает ответы на многие возможные вопросы читателей, на которые другие книги, посвященные алгоритмам, не отвечают.

Надеюсь, эта книга поможет вам учиться — и тем, кто только пытается освоить алгоритмы, и тем, кому до сих пор не удавалось найти подходящий ресурс. Удачного грокания!

Даниэль Зингаро, Университет Торонто

Введение

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

Я написал свое первое иллюстрированное сообщение в блоге в 2012 году. Сам я визуал, поэтому мне нравится наглядный стиль изложения. С тех пор я создал немало иллюстрированных материалов по функциональному программированию, Git, машинному обучению и параллелизму. Кстати говоря, в начале своей карьеры я писал довольно посредственно. Объяснять научные концепции трудно. Чтобы придумать хорошие примеры, требуется время, чтобы объяснить сложную концепцию — тоже. Проще всего умолчать о сложных моментах. Я думал, что у меня все хорошо получается, пока после одной из моих популярных публикаций ко мне не обратился коллега со словами: «Я прочитал твой материал, но все равно ничего не понял». Мне еще предстояло многое узнать о том, как пишутся научные тексты.

В самом разгаре работы над иллюстрированными публикациями в блоге ко мне обратилось издательство Manning с предложением написать иллюстрированную книгу. Оказалось, что редакторы Manning хорошо умеют объяснять научные концепции, и они показали мне, как следует учить других. У меня была совершенно определенная цель: мне хотелось создать книгу, которая объясняла бы сложные научные темы и легко читалась.

Первое издание книги вышло в 2016 году. С тех пор книгу прочитало более 100 000 человек. Мне приятно, что очень многим подошел ее наглядный стиль обучения.

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

Второе издание заполняет некоторые пробелы первого. Многие читатели просили объяснить концепцию деревьев. Поэтому в книге появились две главы, посвященные деревьям. Также был расширен раздел, где я рассказываю о NP-полноте. Концепция NP-полноты весьма абстрактна, и мне хотелось привести объяснение, придающее ей больше конкретности. Если вам тоже этого не хватало, надеюсь, раздел о NP-полноте заполнит пробел в ваших знаниях.

С того первого поста в блоге я прошел долгий путь. Надеюсь, что мне удалось сделать книгу простой и содержательной.

Благодарности

Спасибо издательству Manning, которое дало мне возможность написать эту книгу и предоставило большую творческую свободу в ходе работы. Я благодарен издателю Марджану Бейсу (Marjan Bace), Майку Стивенсу (Mike Stephens) за то, что он ввел меня в курс дела, и Иэну Хоу (Ian Hough) — невероятно отзывчивому редактору, всегда готовому прийти на помощь. Спасибо всем участникам производственной группы Manning: Полу Веллсу (Paul Wells), Дебби Хольмгрен (Debbie Holmgren) и всем остальным. Кроме того, я хочу поблагодарить всех, кто читал рукопись и делился своим мнением: Даниэля Зингаро (Daniel Zingaro), Бена Вайнегара (Ben Vinegar), Александра Мэннинга (Alexander Manning) и Мэгги Венгер (Maggie Wenger). Спасибо Дэвиду Айзенштату (David Eisenstat), моему научному редактору, и Тони Холдройду (Tony Holdroyd), техническому корректору Manning, за исправление множества моих ошибок.

Спасибо всем, кто помог мне в достижении цели: Берту Бейтсу (Bert Bates), который научил меня писать на научные темы, сотрудникам Flashkit, научившим меня программировать; многочисленным друзьям, которые помогали мне в работе — рецензировали главы, делились советами и предлагали разные варианты объяснений. Это были Бен Вайнгер (Ben Vinegar), Карл Пьюзон (Karl Puzon), Алекс Мэннинг (Alex Manning), Эстер Чан (Esther Chan), Аниш Бхатт (Anish Bhatt), Майкл Гласс (Michael Glass), Никрад Махди (Nikrad Mahdi), Чарльз Ли (Charles Lee), Джаред Фридман (Jared Friedman), Хема Маникавасагам (Hema Manickavasagam), Хари Раджа (Hari Raja), Мурали Гудипати (Murali Gudipati), Шриниваса Варадан (Srinivas Varadan) и другие; также спасибо Джерри Брэди (Gerry Brady), моему учителю по теории алгоритмов. Отдельное большое спасибо таким классикам алгоритмов, как CLRS1, Кнут и Стрэнг; безусловно, я стою на плечах гигантов.

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

Спасибо всем рецензентам:

Абишеку Косервалю (Abhishek Koserwal), Алексу Лукасу (Alex Lucas), Андресу Сакко (Andres Sacco), Аруну Сахе (Arun Saha), Бекки Хьют (Becky Huett), Сезару Аугусто Ороско Манотасу (Cesar Augusto Orozco Manotas), Кристиану Саттону (Christian Sutton), Диогинешу Гольдони (Diogines Goldoni), Дирку Гомесу (Dirk Gomez), Эду Бахеру (Ed Bacher), Эдер Андрес Авила Ниньо (Eder Andres Avila Nino), Франсу Оилинки (Frans Oilinki), Ганешу Сваминатану (Ganesh Swaminathan), Джампиеро Гранателле (Giampiero Granatella), Глену Ю (Glen Yu), Грегу Крейтеру (Greg Kreiter), Явиду Асгарову (Javid Asgarov), Жоао Ферейре (Joao Ferreira), Жобинешу Пурушотаману (Jobinesh Purushothaman), Джо Куэвасу (Joe Cuevas), Джошу Макадамсу (Josh McAdams), Кришне Анипинди (Krishna Anipindi), Кшиштофу Камычеку (Krzysztof Kamyczek), Кирилу Калиниченко (Kyrylo Kalinichenko), Лакшминараянану АС (Lakshminarayanan AS), Лоду Бентилу (Laud Bentil), Маттео Батисте (Matteo Battista), Микаэлю Бистрому (Mikael Bystrom), Нику Ракоши (Nick Rakochy), Нинославу Черкесу (Ninoslav Cerkez), Оливеру Кортену (Oliver Korten), Оои Кван Сану (Ooi Kuan San), Пабло Вареле (Pablo Varela), Патрику Регану (Patrick Regan), Патрику Ванъяу (Patrick Wanjau), Филиппу Конраду (Philipp Konrad), Петру Пинделу (Piotr Pindel), Раджешу Монахану (Rajesh Mohanan), Ранжиту Сахаи (Ranjit Sahai), Рохини Уппулари (Rohini Uppuluri), Роману Левченко, Самбарану Хазре (Sambaran Hazra), Сету Макферсону (Seth MacPherson), Шанкару Свами (Shankar Swamy), Шрихари Шридхарану (Srihari Sridharan), Тобиасу Копфу (Tobias Kopf), Вивеку Веераппану (Vivek Veerappan), Вильяму Джамиру Сильве (William Jamir Silva) и Сян Бо Мао (Xiangbo Mao) — ваши предложения помогли сделать эту книгу лучше.

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

1 Авторы классической книги по алгоритмам: Кормен, Лейзерсон, Ривест, Штайн. — Примеч. пер.

О книге

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

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

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

Приятного чтения!

Как работать с этой книгой

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

Я настоятельно рекомендую самостоятельно выполнять код всех примеров. Вы не поверите, насколько это важно. Просто введите мои примеры кода «с листа» (или загрузите их по адресу https://www.manning.com/books/grokking-algorithms-second-edition или https://github.com/egonschiele/grokking_algorithms) и выполните. Так у вас в памяти останется гораздо больше, чем просто при чтении.

Также я рекомендую выполнить упражнения, приведенные в книге. Упражнения не займут много времени — обычно задачи решаются за минуту или две, иногда за 5–10 минут. Упражнения помогут проверить правильность понимания материала. Если вы где-то сбились с пути, то узнаете об этом, не заходя слишком далеко.

Для кого предназначена эта книга

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

• программисты-самоучки;

• студенты, начавшие изучать программирование;

• выпускники, желающие освежить память;

• специалисты по физике/математике/другим дисциплинам, интересующиеся программированием.

Структура книги

В первых трех главах закладываются основы.

• Глава 1: вы изучите свой первый нетривиальный алгоритм: бинарный поиск. Также здесь рассматриваются основы анализа скорости алгоритмов с применением «O-большое». Эта запись часто используется в книге для описания относительной быстроты выполнения алгоритмов.

• Глава 2: вы познакомитесь с двумя основополагающими структурами данных: массивами и связанными списками. Эти структуры данных часто встречаются в книге и используются для создания более сложных структур данных, например хеш-таблиц (глава 5).

• Глава 3: вы узнаете о рекурсии — удобном приеме, используемом многими алгоритмами (например, алгоритмом быстрой сортировки, о котором рассказано в главе 4).

По моему опыту, темы «O-большое» и рекурсии сложны для новичков, поэтому в соответствующих разделах я снижаю темп изложения и привожу более подробные объяснения.

В оставшейся части книги представлены алгоритмы, часто применяемые в разных областях.

• Методы решения задач рассматриваются в главах 4, 10 и 11. Если вы столкнулись со сложной задачей и не знаете, как эффективно ее решить, воспользуйтесь стратегией «разделяй и властвуй» (глава 4) или методом динамического программирования (глава 11). А если вы поняли, что эффективного решения не существует, попробуйте получить приближенный ответ с использованием жадного алгоритма (глава 10).

• Хеш-таблицы рассматриваются в главе 5. Хеш-таблицы — исключительно полезная структура данных, предназначенная для хранения пар ключей и значений (например имени человека и адреса электронной почты или имени пользователя и пароля). Трудно переоценить практическую полезность хеш-таблиц. Приступая к решению задачи, я обычно прежде всего задаю себе два вопроса: можно ли здесь воспользоваться хеш-таблицей и можно ли смоделировать задачу в виде графа.

• Графы и деревья рассматриваются в главах 6, 7, 8 и 9. Графы используются для моделирования сетей: социальных, дорожных, нейронных или любых других совокупностей связей. Поиск в ширину (глава 6) и алгоритм Дейкстры (глава 9) предназначены для поиска кратчайшего расстояния между двумя точками сети: с их помощью можно вычислить кратчайший маршрут к точке назначения или количество промежуточных знакомых у двух людей в социальной сети. Деревья — разновидность графа. Они используются в базах данных (обычно B-деревья), браузерах (DOM-деревья) или файловой системе.

• Алгоритм k ближайших соседей рассматривается в главе 12. Это простой алгоритм машинного обучения; с его помощью можно построить рекомендательную систему, механизм оптического распознавания текста, систему прогнозирования курсов акций — словом, всего, что требует прогнозирования значений («Мы думаем, что Адит поставит этому фильму четыре звезды») или классификации объектов («Это буква Q»).

• Следующий шаг: в главе 13 представлен еще ряд алгоритмов, которые хорошо подойдут для дальнейшего изучения темы.

О коде в книге

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

Исполняемые фрагменты кода можно загрузить из версии liveBook (электронной) по адресу https://livebook.manning.com/book/grokkingalgorithms-second-edition. Полный код примеров книги доступен для загрузки на сайте Manning https://www.manning.com и по адресу https://github.com/egonschiele/grokking_algorithms.

Я считаю, что мы лучше всего учимся тогда, когда нам это нравится, — так что получайте удовольствие от процесса… и запускайте примеры кода!

Форум liveBook

Приобретая книгу, вы получаете бесплатный доступ к закрытому веб-форуму издательства Manning (на английском языке), на котором можно оставлять комментарии о книге, задавать технические вопросы и получать помощь от автора и других пользователей. Чтобы получить доступ к форуму, откройте страницу https://livebook.manning.com/book/grokking-algorithms-second-edition. За информацией о форумах Manning и правилах поведения на них обращайтесь по адресу https://livebook.manning.com/discussion.

В рамках своих обязательств перед читателями издательство Manning предоставляет ресурс для содержательного общения читателей и авторов. Эти обязательства не подразумевают конкретную степень участия автора, которое остается добровольным (и неоплачиваемым). Задавайте автору хорошие вопросы, чтобы он не терял интереса к происходящему! Форум и архивы обсуждений доступны на веб-сайте издательства, пока книга продолжает издаваться.

Об авторе

Адитья Бхаргава работает программистом. Он получил степень магистра по computer science в Чикагском университете и ведет популярный иллюстрированный технический блог adit.io.

О научном редакторе

Дэвид Айзенштат (David Eisenstat) — инженер-исследователь программного обеспечения. Он получил степень PhD в области computer science в Университете Брауна.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу

comp@piter.com

(издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.

1. Знакомство с алгоритмами

В этой главе

• Закладываются основы для остальных глав книги.

• Вы напишете свой первый алгоритм поиска (бинарный поиск).

• Вы узнаете, как описывается время выполнения алгоритма («O-большое»).

Введение

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

• В главе 1 речь пойдет о бинарном поиске и о том, как алгоритмы могут ускорить работу кода. В одном примере алгоритм сокращает количество необходимых действий с 4 миллиардов до 32!

• Устройство GPS использует алгоритмы из теории графов (об этом в главах 6 и 9) для вычисления кратчайшего пути к точке назначения.

• При помощи методов динамического программирования (см. главу 11) можно создать алгоритм для игры в шашки.

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

Что вы узнаете об эффективности алгоритмов

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

Что вы узнаете о решении задач

Вы освоите методы решения задач, которые вам сейчас, возможно, неизвестны. Примеры:

• Если вы любите создавать видеоигры, вы можете написать систему на базе искусственного интеллекта, моделирующую действия пользователя с применением алгоритмов из теории графов.

• Вы узнаете, как построить рекомендательную систему на базе k ближайших соседей.

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

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

Что необходимо знать

Чтобы читать эту книгу, необходимо знать базовую алгебру. Например, возьмем следующую функцию: f (x) = x × 2. Чему равен результат f(5)? Если вы ответили «10» — читайте спокойно.

Кроме того, вам будет проще понять эту главу (и всю книгу), если вы владеете хотя бы одним языком программирования. Все приведенные примеры написаны на Python. Если вы не знаете ни одного языка программирования, но хотите изучить — выбирайте Python: это отличный язык для начинающих. Если вы уже знаете другой язык (скажем, JavaScript) — все в порядке.

Бинарный поиск

Предположим, вы ищете фамилию человека в телефонной книге (какая древняя технология!). Она начинается с буквы «К». Конечно, можно начать с самого начала и перелистывать страницы, пока вы не доберетесь до буквы «К». Но для ускорения поиска лучше раскрыть книгу на середине: ведь буква «К» должна находиться где-то ближе к середине телефонной книги.

Или предположим, что вы ищете слово в словаре и оно начинается с буквы «О». И снова лучше начать с середины.

Теперь допустим, что вы вводите свои данные при входе на Facebook. При этом Facebook необходимо проверить, есть ли у вас учетная запись на сайте. Для этого ваше имя пользователя нужно найти в базе данных. Допустим, вы выбрали себе имя пользователя «karlmageddon». Facebook может начать с буквы «A» и проверять все подряд, но разумнее будет начать с середины.

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

Бинарный поиск — это алгоритм; на входе он получает отсортированный список элементов (позднее я объясню, почему он должен быть отсортирован). Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null.

Например:

Ищем компанию в телефонной книге с применением бинарного поиска

Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.

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

Предположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, 4… Вот как это будет выглядеть.

Плохой способ угадать число

Это пример простого поиска (возможно, термин «тупой поиск» был бы уместнее). При каждой догадке исключается только одно число. Если я загадал число 99, то, чтобы добраться до него, потребуется 99 попыток!

Более эффективный поиск

Существует другой, более эффективный способ. Начнем с 50.

Слишком мало… но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1–50 меньше загаданного. Следующая попытка: 75.

На этот раз перелет… Но вы снова исключили половину оставшихся чисел! С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел. Следующим будет число 63 (посередине между 50 и 75).

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

При бинарном поиске каждый раз исключается половина чисел

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

Предположим, вы ищете слово в словаре с 240 000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?

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

Итак, бинарный поиск потребует 18 шагов — заметная разница! В общем случае для списка из n элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.

Логарифмы

Возможно, вы уже забыли, что такое логарифм, но наверняка помните, что такое возведение в степень. log10100, по сути, означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ — 2: 10 × 10. Итак, log10 100 = 2. Логарифм по смыслу противоположен возведению в степень.

Логарифм — операция, обратная возведению в степень

Когда я в этой книге упоминаю «O-большое» (об этом чуть позднее), log всегда означает log2. Когда вы ищете элемент с применением простого поиска, в худшем случае вам придется проверить каждый элемент. Итак, для списка из 8 чисел понадобится не больше 8 проверок. Для бинарного поиска в худшем случае потребуется не более logn проверок. Для списка из 8 элементов log 8 == 3, потому что 23 == 8. Итак, для списка из 8 чисел вам придется проверить не более 3 чисел. Для списка из 1024 элементов log 1024 = 10, потому что 210 == 1024. Следовательно, для списка из 1024 чисел придется проверить не более 10 чисел.

примечание

В этой книге я буду много говорить о логарифмах, поэтому нужно четко представлять, что это такое. Если вы пока не очень хорошо разбираетесь в логарифмах, посмотрите отличное обучающее видео в Академии Хана (https://khanacademy.org).

примечание

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

Посмотрим, как написать реализацию бинарного поиска на Python. В следующем примере кода используется массив. Если вы не знаете, как работают массивы, не беспокойтесь: эта тема рассматривается в следующей главе. Пока достаточно знать, что серию элементов можно сохранить в непрерывной последовательности ячеек, которая называется массивом. Нумерация ячеек начинается с 0: первая ячейка находится в позиции с номером 0, вторая — в позиции с номером 1 и т.д.

примечание

Поскольку в Python массивы называются списками, я буду использовать термины "список" и "массив" как взаимозаменяемые.

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

low = 0

high = len(arr) - 1

Каждый раз алгоритм проверяет средний элемент:

mid = (low + high) // 2   Если значение (low+high) нечетно, то Python автоматически округляет значение mid в меньшую сторону

guess = arr[mid]

Если названное число было слишком мало, то переменная low обновляется соответственно:

if guess < item:

  low = mid + 1

А если догадка была слишком велика, то обновляется переменная high. Полный код выглядит так:

def binary_search(arr, item):

  low = 0 В переменных low и high хранятся границы той части списка, в которой выполняется поиск

  high = len(arr) - 1

  while low <= high: Пока эта часть не сократится до одного элемента…

    mid = (low + high) // 2   …проверяем средний элемент

    guess = arr[mid]

    if guess == item: Значение найдено

      return mid

    elif guess > item: Много

      high = mid - 1

    else: Мало

      low = mid + 1

  return None Значения не существует

my_list = [1, 3, 5, 7, 9] А теперь протестируем функцию!

print(binary_search(my_list, 3)) # => 1  Вспомните: нумерация элементов начинается с 0. Второй ячейке соответствует индекс 1

print(binary_search(my_list, -1)) # => None   "None" в Python означает "ничто". Это признак того, что элемент не найден

Упражнения

1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?

1.2 Предположим, размер списка увеличился вдвое. Как изменится максимальное количество проверок?

Время выполнения

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

Вернемся к бинарному поиску. Сколько времени сэкономит его применение? В первом варианте мы последовательно проверяли каждое число, одно за другим. Если список состоит из 100 чисел, может потребоваться до 100 попыток. Для списка из 4 миллиардов чисел потребуется до 4 миллиардов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным.

С бинарным поиском дело обстоит иначе. Если список состоит из 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элементов потребуется не более 32 попыток. Впечатляет, верно? Бинарный поиск выполняется за логарифмическое время. В следующей таблице приводится краткая сводка результатов.

Время выполнения алгоритмов поиска

«O-большое»

Специальная нотация «O-большое» описывает скорость работы алгоритма. Зачем вам это? Время от времени вам придется использовать чужие алгоритмы, а потому неплохо было бы понимать, насколько быстро или медленно они работают. В этом разделе я объясню, что представляет собой «O-большое», и приведу список самых распространенных вариантов времени выполнения для некоторых алгоритмов.

Время выполнения алгоритмов растет с разной скоростью

Боб пишет алгоритм поиска для NASA. Его алгоритм заработает, когда ракета будет подлетать к Луне, и поможет вычислить точку посадки.

Это один из примеров того, как время выполнения двух алгоритмов растет с разной скоростью. Боб пытается выбрать между простым и бинарным поиском. Его алгоритм должен работать быстро и правильно. С одной стороны, бинарный поиск работает быстрее. У Боба есть всего 10 секунд, чтобы выбрать место посадки; если он не уложится в это время, то момент для посадки будет упущен. С другой стороны, простой поиск пишется проще и вероятность ошибок в нем ниже… Конечно, Боб совершенно не хочет допустить ошибку в коде посадки ракеты. И тогда для пущей уверенности Боб решает измерить время выполнения обоих алгоритмов для списка из 100 элементов.

Допустим, проверка одного элемента занимает 1 миллисекунду (мс). При простом поиске Бобу придется проверить 100 элементов, поэтому поиск займет 100 мс. С другой стороны, при бинарном поиске достаточно проверить всего 7 элементов (log2100 равен приблизительно 7), а поиск займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения простого поиска? А при бинарном поиске? Обязательно ответьте на оба вопроса, прежде чем продолжить чтение.

Время выполнения простого и бинарного поиска для списка из 100 элементов

Боб проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс (log21 000 000 000 равен приблизительно 30). «Тридцать миллисекунд! — думает Боб. — Бинарный поиск в 15 раз быстрее простого, потому что простой поиск для 100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой поиск займет 30 × 15 = 450 мс, верно? Гораздо меньше отведенных 10 секунд». И Боб выбирает простой поиск. Верен ли его выбор?

Нет, Боб ошибается. Глубоко ошибается. Время выполнения для простого поиска с 1 миллиардом элементов составит 1 миллиард миллисекунд, а это 11 дней! Проблема в том, что время выполнения для бинарного и простого поиска растет с разной скоростью.

Время выполнения растет с совершенно разной скоростью!

Другими словами, с увеличением количества элементов бинарный поиск занимает чуть больше времени. А простой поиск займет гораздо больше времени. Таким образом, с увеличением списка бинарный список внезапно начинает работать гораздо быстрее простого. Боб думал, что бинарный поиск работает в 15 раз быстрее простого, но это не так. Если список состоит из 1 миллиарда элементов, бинарный поиск работает приблизительно в 33 миллиона раз быстрее. Вот почему недостаточно знать, сколько времени должен работать алгоритм, — необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь-то вам и пригодится «O-большое».

«O-большое» описывает, насколько быстро работает алгоритм. Предположим, имеется список размера n. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить n операций. Время выполнения «O-большое» имеет вид O(n). Постойте, но где же секунды? А их здесь нет — «O-большое» не сообщает скорость в секундах, а позволяет сравнить количество операций. Оно указывает, насколько быстро возрастает время выполнения алгоритма.

А теперь другой пример. Для проверки списка размером n бинарному поиску потребуется log n операций. Как будет выглядеть «O-большое»? O(log n). В общем случае «O-большое» выглядит так:

Как записывается «O-большое»

Такая запись сообщает количество операций, которые придется выполнить алгоритму. Она называется «O-большое», потому что перед количеством операций ставится символ «O» (а большое — потому что в верхнем регистре).

Теперь рассмотрим несколько примеров. Попробуйте самостоятельно оценить время выполнения этих алгоритмов.

Наглядное представление «O-большое»

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

Как должен выглядеть хороший алгоритм для построения этой сетки?

Алгоритм 1

Как вариант можно нарисовать 16 квадратов, по одному за раз. Напоминаю: «O-большое» подсчитывает количество операций. В данном примере рисование квадрата считается одной операцией. Нужно нарисовать 16 квадратов. Сколько операций по рисованию одного квадрата придется выполнить?

Рисуем сетку по одному квадрату

Чтобы нарисовать 16 квадратов, потребуется 16 шагов. Как выглядит время выполнения этого алгоритма?

Алгоритм 2

А теперь попробуем иначе. Сложите лист пополам.

На этот раз операцией считается сложение листка. Получается, что одна операция создает сразу два прямоугольника!

Сложите бумагу еще раз, а потом еще и еще.

Разверните листок после четырех сложений — получилась замечательная сетка! Каждое сложение удваивает количество прямоугольников. За 4 операции вы создали 16 прямоугольников!

Построение сетки за 4 сложения

При каждом складывании количество прямоугольников увеличивается вдвое, так что 16 прямоугольников строятся за 4 шага. Как записать время выполнения этого алгоритма? Напишите время выполнения обоих алгоритмов, прежде чем двигаться дальше.

Ответы: алгоритм 1 выполняется за время O(n), а алгоритм 2 — за время O(log n).

«O-большое» определяет время выполнения в худшем случае

Предположим, вы используете простой поиск для поиска фамилии в телефонной книге. Вы знаете, что простой поиск выполняется за время O(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте, что искомая фамилия начинается на букву «А» и этот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи — вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время O(n)? А может, он занял время O(1), потому что результат был получен с первой попытки?

Простой поиск все равно выполняется за время O(n). Просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако «O-большое» описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время O(n). И это дает определенные гарантии — вы знаете, что простой поиск никогда не будет работать медленнее O(n).

примечание

Наряду с временем худшего случая также полезно учитывать среднее время выполнения. Тема худшего и среднего времени выполнения обсуждается в главе 4.

Типичные примеры «O-большого»

Ниже перечислены пять разновидностей «O-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения.

• O(log n), или логарифмическое время. Пример: бинарный поиск.

• O(n), или линейное время. Пример: простой поиск.

• O(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка — но об этом в главе 4).

• O(n2). Пример: медленные алгоритмы сортировки (сортировка выбором — см. главу 2).

• O(n!). Пример: очень медленные алгоритмы (задача о коммивояжере — о ней будет рассказано в следующем разделе).

Предположим, вы снова строите сетку из 16 квадратов и можете выбрать для решения этой задачи один из пяти алгоритмов. При использовании первого алгоритма сетка будет построена за время O(log n). В секунду выполняются до 10 операций. С временем O(log n) для построения сетки из 16 квадратов потребуются 4 операции (log 16 равен 4). Итак, сетка будет построена за 0,4 секунды. А если бы было нужно построить 1024 квадрата? На это бы потребовалось log 1024 = 10 операций, или 1 секунда. Напомню, что эти числа получены при использовании первого алгоритма.

Второй алгоритм работает медленнее: за время O(n). Для построения 16 прямоугольников потребуется 16 операций, а для построения 1024 прямоугольников — 1024 операции. Сколько это составит в секундах?

Ниже показано, сколько времени потребуется для построения сетки с остальными алгоритмами, от самого быстрого до самого медленного.

Существуют и другие варианты времени выполнения, но эти пять встречаются чаще всего.

Помните, что эта запись является упрощением. На практике «O-большое» не удается легко преобразовать в количество операций с такой точностью, но пока нам хватит и этого. Мы вернемся к «O-большому» в главе 4 после рассмотрения еще нескольких алгоритмов. А пока перечислим основные результаты.

• Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.

• По сути, формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.

• Время выполнения алгоритмов выражается как «O-большое».

• Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором происходит поиск значения, оно становится намного быстрее.

Упражнения

Приведите время выполнения «O-большое» для каждого из следующих сценариев.

1.3 Известна фамилия, нужно найти номер в телефонной книге.

1.4 Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)

1.5 Нужно прочитать телефоны всех людей в телефонной книге.

1.6 Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются в главе 4. Прочитайте ответ — скорее всего, он вас удивит!)

Задача о коммивояжере

Наверное, после прочтения предыдущего раздела вы подумали: «Уж мне-то точно не попадется алгоритм с временем O(n!)». Ошибаетесь, и я это сейчас докажу! Мы рассмотрим алгоритм с очень, очень плохим временем выполнения. Это известная задача из области теории вычислений, в которой время выполнения растет просто с ужасающей скоростью, и некоторые очень умные люди считают, что с этим ничего не поделать. Она называется задачей о коммивояжере.

Это коммивояжер.

Он должен объехать 5 городов.

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

Все расстояния суммируются, после чего выбирается путь с кратчайшим расстоянием. Для 5 городов можно создать 120 перестановок, поэтому решение задачи для 5 городов потребует 120 операций. Для 6 городов количество операций увеличивается до 720 (существует 720 возможных перестановок). А для 7 городов потребуется уже 5040 операций!

Количество операций стремительно растет

В общем случае для вычисления результата при n элементах потребуется n! (n-факториал) операций. А значит, время выполнения составит O(n!) (такое время называется факториальным). При любом сколько-нибудь серьезном размере списка количество операций будет просто огромным. Скажем, если вы попытаетесь решить задачу для 100+ городов, сделать это вовремя не удастся — Солнце погаснет раньше.

Какой ужасный алгоритм! Значит, коммивояжер должен найти другое решение, верно? Но у него ничего не получится. Это одна из знаменитых нерешенных задач в области теории вычислений. Для нее не существует известного быстрого алгоритма, и ученые считают, что найти более эффективный алгоритм для этой задачи в принципе невозможно. В лучшем случае для нее можно поискать приближенное решение; за подробностями обращайтесь к главе 10.

Шпаргалка

• Бинарный поиск работает намного быстрее простого.

• Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором происходит поиск значения, оно становится намного быстрее.

• Скорость алгоритмов не измеряется в секундах.

• Время выполнения алгоритма описывается ростом количества операций.

• Время выполнения алгоритмов выражается как «O-большое».

2. Сортировка выбором

В этой главе

• Вы познакомитесь с массивами и связанными списками — двумя основными структурами данных, которые используются буквально везде. Мы уже применяли массивы в главе 1 и будем говорить о них почти в каждой главе книги. Массивы чрезвычайно важны, уделите им внимание! Впрочем, иногда вместо массива лучше воспользоваться связанным списком. В этой главе объясняются плюсы и минусы обеих структур данных, чтобы вы могли решить, какой вариант лучше подходит для вашего алгоритма.

• Вы изучите свой первый алгоритм сортировки. Многие алгоритмы работают только с отсортированными данными. Помните бинарный поиск? Он применяется только к предварительно отсортированному списку. В большинстве языков существуют встроенные алгоритмы сортировки, так что вам редко приходится писать свою версию «с нуля». Однако алгоритм сортировки выбором поможет перейти к алгоритму быстрой сортировки, описанному в главе 4. Алгоритм быстрой сортировки очень важен, и вам будет проще разобраться в нем, если вы уже знаете хотя бы один алгоритм сортировки.

Что необходимо знать

Чтобы понять ту часть этой главы, которая относится к анализу эффективности, необходимо понимать смысл понятия «O-большое» и логарифмов. Если вы совершенно не разбираетесь в этих вопросах, лучше вернуться и прочитать главу 1. «O-большое» будет использоваться в оставшихся главах книги.

Как работает память

Представьте, что вы пришли в театр и хотите оставить свои личные вещи в гардеробе. Для хранения вещей есть специальные ящики.

В каждом ящике помещается один предмет. Вы хотите сдать на хранение две вещи, поэтому требуете выделить вам два ящика.

И вы оставляете свои две вещи.

Готово, можно идти на спектакль!

В сущности, именно так работает память вашего компьютера. Она представляет собой нечто вроде огромного шкафа со множеством ящиков, и у каждого ящика есть адрес.

fe0ffeeb — адрес ячейки памяти.

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

Массивы и связанные списки

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

Что использовать — массив или связанный список? Для начала попробуем сохранить задачи в массиве, потому что этот способ более понятен. При использовании массива все задачи хранятся в памяти непрерывно (то есть рядом друг с другом).

Теперь предположим, что вы захотели добавить четвертую задачу. Но следующий ящик уже занят — там лежат чужие вещи!

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

Если вдруг придет еще один друг, места опять не хватит и вам всем придется перемещаться снова! Сплошная суета. Кроме того, добавление новых элементов в массив станет серьезной проблемой. Если свободного места нет и вам каждый раз приходится перемещаться в новую область в памяти, операция добавления нового элемента будет выполняться очень медленно. Простейшее решение — «бронирование мест»: даже если список состоит всего из 3 задач, вы запрашиваете у компьютера место на 10 позиций… просто на всякий случай. Тогда в список можно будет добавить до 10 задач и ничего перемещать не придется. Это неплохое обходное решение, но у него есть пара недостатков.

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

• Если в список будет добавлено более 10 задач, перемещать все равно придется.

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

Связанные списки

При использовании связанного списка элементы могут размещаться где угодно в памяти.

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

Связанные адреса памяти

Все как в игре «Найди клад». Вы приходите по первому адресу, там написано: «Следующий элемент находится по адресу 123». Вы идете по адресу 123, там написано: «Следующий элемент находится по адресу 847» и т.д. Добавить новый элемент в связанный список проще простого: просто разместите его по любому адресу памяти и сохраните этот адрес в предыдущем элементе.

Со связанными списками ничего перемещать в памяти не нужно. Также сама собой решается другая проблема: допустим, вы пришли в кино с пятью друзьями. Вы пытаетесь найти место на шестерых, но кинотеатр уже забит, и найти шесть соседних мест невозможно. Нечто похожее происходит и с массивами. Допустим, вы пытаетесь найти для массива блок на 10 000 элементов. В памяти можно найти место для 10 000 элементов, но только не смежное. Для массива не хватает места! При хранении данных в связанном списке вы фактически говорите: «Ладно, тогда садимся на свободные места и смотрим кино». Если необходимое место есть в памяти, вы сможете сохранить данные в связанном списке.

Если связанные списки так хорошо справляются со вставкой, то чем тогда хороши массивы?

Массивы

На сайтах со всевозможными хит-парадами и «первыми десятками» применяется жульническая тактика для увеличения количества просмотров. Вместо того чтобы вывести весь список на одной странице, они размещают по одному элементу на странице и заставляют вас нажимать кнопку Next для перехода к следующему элементу. Например, «Десятка лучших злодеев в сериалах» не выводится на одной странице. Вместо этого вы начинаете с № 10 (Ньюман из «Сайнфелда») и нажимаете Next на каждой странице, пока не доберетесь до № 1 (Густаво Фринг из «Во все тяжкие»). В результате сайту удается показать вам рекламу на целых 10 страницах, но нажимать Next 9 раз для перехода к первому месту скучно. Было бы гораздо лучше, если бы весь список помещался на одной странице, а вы могли бы просто щелкнуть на имени человека для получения дополнительной информации.

Похожая проблема существует и у связанных списков. Допустим, вы хотите получить последний элемент связанного списка. Просто прочитать нужное значение не удастся, потому что вы не знаете, по какому адресу оно хранится. Вместо этого придется сначала обратиться к элементу № 1 и узнать адрес элемента № 2, потом обратиться к элементу № 2 и узнать адрес элемента № 3… и так далее, пока не доберетесь до последнего элемента. Связанные списки отлично подходят в тех ситуациях, когда данные должны читаться последовательно: сначала вы читаете один элемент, по адресу переходите к следующему элементу и т.д. Но если вы намерены прыгать по списку туда-сюда, держитесь подальше от связанных списков.

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

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

Терминология

Элементы массива пронумерованы, причем нумерация начинается с 0, а не с 1. Например, в этом массиве значение 20 находится в позиции 1.

А значение 10 находится в позиции 0. Неопытных программистов этот факт обычно вводит в ступор. Тем не менее выбор нулевой начальной позиции упрощает написание кода по работе с массивами, поэтому программисты остановились на этом варианте. Почти во всех языках программирования нумерация элементов массива начинается с 0. Вскоре вы к этому привыкнете.

Позиция элемента называется его индексом. Таким образом, вместо того чтобы говорить «Значение 20 находится в позиции 1», правильно сказать «Значение 20 имеет индекс 1». В этой книге термин «индекс» означает то же, что и «позиция».

Ниже приведены примеры времени выполнения основных операций с массивами и списками.

Вопрос: почему вставка элемента в массив требует времени O(n)? Предположим, вы хотите вставить элемент в начало массива. Как бы вы это сделали? Сколько времени на это потребуется? Ответы на эти вопросы вы найдете в следующем разделе!

Упражнение

2.1 Допустим, вы строите приложение для управления финансами.

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

Вставка в середину списка

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

Неупорядоченный

Упорядоченный

Что лучше подойдет для вставки элементов в середину: массивы или списки? Со списком задача решается изменением указателя в предыдущем элементе.

А при работе с массивом придется сдвигать все остальные элементы.

А если свободного места не осталось, все данные придется скопировать в новую область памяти! В общем, списки лучше подходят для вставки элементов в середину.

Указатели

Я часто говорю о том, что каждый элемент связанного списка указывает на следующий элемент списка. Но как именно он это делает? С помощью указателей.

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

Периодически вы будете встречать этот термин, особенно если вы пишете на низкоуровневом языке, таком как C. Поэтому полезно знать, что он означает.

Удаление

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

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

Ниже приведены примеры времени выполнения основных операций с массивами и связанными списками.

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

Какая структура данных используется чаще: массивы или списки?

Массивы используются часто, поскольку имеют множество преимуществ перед связанными списками. Во-первых, их проще читать. Во-вторых, массивы подерживают произвольный доступ.

Всего существуют два вида доступа: произвольный и последовательный. При последовательном доступе элементы читаются по одному, начиная с первого. Связанные списки поддерживают только последовательный доступ. Если вы захотите прочитать 10-й элемент связанного списка, вам придется прочитать первые 9 элементов и перейти по ссылкам к 10-му элементу. Многие реальные ситуации требуют произвольного доступа, поэтому массивы часто применяются на практике.

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

Но на самом деле компьютеры читают целыми разделами, поскольку это значительно ускоряет переход к следующему элементу.

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

Таким образом, массивы обеспечивают не только произвольный, но и более быстрый последовательный доступ!

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

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

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

Таким образом, массивы используются чаще, чем связанные списки, за исключением особых случаев.

Упражнения

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

Какую структуру данных вы использовали бы для реализации этой очереди: массив или связанный список? (Подсказка: связанные списки хорошо подходят для вставки/удаления, а массивы — для произвольного доступа к элементам. Что из этого понадобится в данном случае?)

2.3 Проведем мысленный эксперимент. Допустим, Facebook хранит список имен пользователей. Когда кто-то пытается зайти на сайт Facebook, система пытается найти имя пользователя. Если имя входит в список имен зарегистрированных пользователей, то вход разрешается. Пользователи приходят на Facebook достаточно часто, поэтому поиск по списку имен пользователей будет выполняться часто. Будем считать, что Facebook использует бинарный поиск для поиска в списке. Бинарному поиску необходим произвольный доступ — алгоритм должен мгновенно обратиться к среднему элементу текущей части списка. Зная это обстоятельство, как бы вы реализовали список пользователей: в виде массива или в виде связанного списка?

2.4 Пользователи также довольно часто создают новые учетные записи на Facebook. Предположим, вы решили использовать массив для хранения списка пользователей. Какими недостатками обладает массив для выполнения вставки? Допустим, вы используете бинарный поиск для нахождения учетных данных. Что произойдет при добавлении новых пользователей в массив?

2.5 В действительности Facebook не использует ни массив, ни связанный список для хранения информации о пользователях. Рассмотрим гибридную структуру данных: массив связанных списков. Имеется массив из 26 элементов. Каждый элемент содержит ссылку на связанный список. Например, первый элемент массива указывает на связанный список всех имен пользователей, начинающихся на букву «A». Второй элемент указывает на связанный список всех имен пользователей, начинающихся на букву «B», и т.д.

Предположим, пользователь с именем «Adit B» регистрируется на Facebook и вы хотите добавить его в список. Вы обращаетесь к элементу 1 массива, находите связанный список элемента 1 и добавляете «Adit B» в конец списка. Теперь предположим, что зарегистрировать нужно пользователя «Zakhir H». Вы обращаетесь к элементу 26, который содержит связанный список всех имен, начинающихся с «Z», и проверяете, присутствует ли «Zakhir H» в этом списке.

Теперь сравните эту гибридную структуру данных с массивами и связанными списками. Будет ли она быстрее или медленнее каждой исходной структуры при поиске и вставке? Приводить  «O-большое» не нужно, просто выберите одно из двух: быстрее или медленнее.

Сортировка выбором

А теперь объединим все, что вы узнали, во втором алгоритме: сортировке выбором. Чтобы освоить этот алгоритм, вы должны понимать, как работают массивы и списки и «O-большое». Допустим, у вас на компьютере записана музыка и для каждого исполнителя хранится счетчик воспроизведений.

Вы хотите отсортировать список по убыванию счетчика воспроизведений, чтобы самые любимые исполнители стояли на первых местах. Как это сделать?

Одно из возможных решений — пройти по списку и найти исполнителя с наибольшим количеством воспроизведений. Этот исполнитель добавляется в новый список.

Потом то же самое происходит со следующим по количеству воспроизведений исполнителем.

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

А теперь попробуем оценить происходящее с точки зрения теории вычислений и посмотрим, сколько времени будут занимать операции. Напомним, что время O(n) означает, что вы по одному разу обращаетесь к каждому элементу списка. Например, при простом поиске по списку исполнителей каждый исполнитель будет проверен один раз.

Чтобы найти исполнителя с наибольшим значением счетчика воспроизведения, необходимо проверить каждый элемент в списке. Как вы уже видели, это делается за время O(n). Итак, имеется операция, выполняемая за время O(n), и ее необходимо выполнить n раз:

Все это требует времени O(n × n), или O(n2).

Алгоритмы сортировки очень полезны. Например, вы можете отсортировать:

• имена в телефонной книге;

• даты путешествий;

• сообщения электронной почты (от новых к старым).

Уменьшение количества проверяемых элементов

При каждом выполнении операций количество элементов, которые нужно проверить, сокращается. Со временем все сведется к проверке всего одного элемента. Почему же время выполнения все равно оценивается как O(n2)? Это хороший вопрос, и ответ на него связан с ролью констант в «O-большом». Тема будет более подробно рассмотрена в главе 4, но я кратко объясню суть. Вы правы, вам действительно не нужно каждый раз проверять весь список из n элементов. Сначала проверяются n элементов, потом n – 1, n – 2 … 2, 1. В среднем проверяется список из ½ × n элементов. Его время выполнения составит O(n × ½ × n). Однако константы (такие, как ½) в «O-большом» игнорируются (еще раз: за полным обсуждением обращайтесь к главе 4), поэтому мы просто используем O(n × n), или O(n2).

Алгоритм сортировки выбором легко объясняется, но медленно работает. Быстрая сортировка — эффективный алгоритм сортировки, который выполняется за время O(n log n). Но мы займемся этой темой в главе 4!

Пример кода

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

def findSmallest(arr):

  smallest = arr[0]    Для хранения наименьшего значения

  smallest_index = 0    Для хранения индекса наименьшего значения

  for i in range(1, len(arr)):

    if arr[i] < smallest:

      smallest = arr[i]

      smallest_index = i

  return smallest_index

Теперь на основе этой функции можно написать функцию сортировки выбором:

def selectionSort(arr):    Сортирует массив

  newArr = []

  copiedArr = list(arr) // копирует массив перед изменением

  for i in range(len(copiedArr)):

      smallest = findSmallest(copiedArr)   Находит наименьший элемент в массиве и добавляет его в новый массив

      newArr.append(copiedArr.pop(smallest))

  return newArr

print(selectionSort([5, 3, 6, 2, 10]))

Шпаргалка

• Память компьютера напоминает огромный шкаф с ящиками.

• Если вам потребуется сохранить набор элементов, воспользуйтесь массивом или списком.

• В массиве все элементы хранятся в памяти рядом друг с другом.

• В связанном списке элементы распределяются в произвольных местах памяти, при этом в каждом элементе хранится адрес следующего элемента.

• Массивы обеспечивают быстрое чтение.

• Списки обеспечивают быструю вставку и удаление.

3. Рекурсия

В этой главе

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

• Вы научитесь разбивать задачи на базовый и рекурсивный случаи. В стратегии «разделяй и властвуй» (глава 4) эта простая концепция используется для решения более сложных задач.

Эта глава мне самому очень нравится, потому что в ней рассматривается рекурсия — элегантный метод решения задач. Рекурсия относится к числу моих любимых тем, но вызывает у людей противоречивые чувства. Они либо обожают ее, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Лично я отношусь к третьему лагерю. Чтобы вам было проще освоить эту тему, я дам несколько советов.

• Глава содержит множество примеров кода. Самостоятельно выполните этот код и посмотрите, как он работает.

• Мы будем рассматривать рекурсивные функции. Хотя бы один раз возьмите бумагу и карандаш и разберите, как работает рекурсивная функция: «Так, я передаю функции factorial значение 5, потом возвращаю управление и передаю значение 4 функции factorial, которая…» и т.д. Такой разбор поможет вам понять, как работает рекурсивная функция.

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

Рекурсия

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

Бабушка говорит, что ключ к чемодану, скорее всего, лежит в коробке.

В коробке лежат другие коробки, а в них лежат маленькие коробочки. Ключ находится где-то там. Какой алгоритм поиска ключа предложите вы? Подумайте над алгоритмом, прежде чем продолжить чтение.

Одно из решений может выглядеть так:

1. Сложить все коробки в кучу.

2. Взять коробку и открыть.

3. Если внутри лежит коробка, добавить ее в кучу для последующего поиска.

4. Если внутри лежит ключ, поиск закончен!

5. Повторить.

Есть и альтернативное решение.

1. Просмотреть содержимое коробки.

2. Если вы найдете коробку, вернуться к шагу 1.

3. Если вы найдете ключ, поиск закончен!

Какое решение кажется вам более простым? Первое решение можно построить на цикле while. Пока куча коробок не пуста, взять очередную коробку и проверить ее содержимое:

def look_for_key(main_box):

  pile = main_box.make_a_pile_to_look_through()

  while pile is not empty:

    box = pile.grab_a_box()

    for item in box:

      if item.is_a_box():

        pile.append(item)

      elif item.is_a_key():

        print("found the key!")

Второй способ основан на рекурсии. Рекурсией называется вызов функцией самой себя. Второе решение на псевдокоде может выглядеть так:

def look_for_key(box):

  for item in box:

    if item.is_a_box():

      look_for_key(item)       Рекурсия!

    elif item.is_a_key():

      print("found the key!")

Оба решения делают одно и то же, но второе решение кажется мне более понятным. Применение рекурсии не ускоряет работу программы: более того, решение с циклами иногда работает быстрее. Мне нравится одна цитата Ли Колдуэлла с сайта Stack Overlow: «Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!»2

Рекурсия используется во многих нужных алгоритмах, поэтому важно понимать эту концепцию.

Базовый случай и рекурсивный случай

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

>  3...2...1

Ее можно записать в рекурсивном виде:

def countdown(i):

  print(i)

  countdown(i-1)

countdown(3)

Введите этот код и выполните его. И тут возникает проблема: эта функция выполняется бесконечно!

Бесконечный цикл

>  3...2...1...0...-1...-2...

Чтобы прервать выполнение сценария, нажмите Ctrl+C.

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

Добавим базовый случай в функцию countdown:

def countdown(i):

  print(i)

  if i <= 1:       Базовый случай

    return

  else:            Рекурсивный случай

    countdown(i-1)

countdown(3)

Теперь функция работает, как было задумано. Это выглядит примерно так:

Стек

В этом разделе рассматривается стек вызовов. Концепция стека вызовов играет важную роль в программировании вообще; кроме того, ее важно понимать при использовании рекурсии.

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

Помните, когда мы рассматривали массивы и списки, у вас тоже был список задач? Задачи, то есть элементы списка, можно было добавлять и удалять в произвольных позициях списка. Стопка листков работает куда проще. Новые (вставленные) элементы добавляются в начало списка, то есть на верх стопки. Читается только верхний элемент, и он исключается из списка. Таким образом, список задач поддерживает всего два действия: занесение (вставка) и извлечение (удаление из списка и чтение.)

Посмотрим, как работает список задач:

Такая структура данных называется стеком. Стек — простая структура данных. А теперь самое неожиданное: все это время вы пользовались стеком, не подозревая об этом!

Стек вызовов

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

def greet(name):

    print("hello, " + name + "!")

    greet2(name)

    print("getting ready to say bye...")

    bye()

Эта функция приветствует вас, после чего вызывает две другие функции. Вот эти две функции:

def greet2(name):

    print("how are you, " + name + "?")

def bye():

    print("ok bye!")

Разберемся, что происходит при вызове функции.

Примечание

Для простоты я привожу только вызовы функций greet, greet2 и bye и опускаю вызовы функции print.

Предположим, в программе используется вызов greet("maggie"). Сначала ваш компьютер выделяет блок памяти для этого вызова функции.

Затем эта память используется. Переменной name присваивается значение "maggie"; оно должно быть сохранено в памяти.

Каждый раз, когда вы вызываете функцию, компьютер сохраняет в памяти значения всех переменных для этого вызова. Далее выводится приветствие hello, maggie!, после чего следует второй вызов greet2("maggie"). И снова компьютер выделяет блок памяти для вызова функции.

Ваш компьютер объединяет эти блоки в стек. Второй блок создается над первым. Вы выводите сообщение how are you, maggie?, после чего возвращаете управление из вызова функции. Когда это происходит, блок на вершине стека извлекается из него.

Теперь верхний блок в стеке относится к функции greet; это означает, что вы вернулись к функции greet. При вызове функции greet2 функция greet еще не была завершена. Здесь-то и скрывается истинный смысл этого раздела: когда вы вызываете функцию из другой функции, вызывающая функция приостанавливается в частично завершенном состоянии. Все значения переменных этой функции остаются в памяти. А когда выполнение функции greet2 будет завершено, вы вернетесь к функции greet и продолжите ее выполнение с того места, где оно прервалось. Сначала выводится сообщение getting ready to say bye…, после чего вызывается функция bye.

Блок для этой функции добавляется на вершину стека. Далее выводится сообщение ok bye! с выходом из вызова функции.

Управление снова возвращается функции greet. Делать больше нечего, так что управление возвращается и из функции greet. Этот стек, в котором сохранялись переменные разных функций, называется стеком вызовов.

Упражнение

3.1 Предположим, имеется стек вызовов следующего вида:

Что можно сказать о текущем состоянии программы на основании этого стека вызовов?

А теперь посмотрим, как работает стек вызовов с рекурсивными функциями.

Стек вызовов с рекурсией

Рекурсивные функции тоже используют стек вызовов! Посмотрим, как это делается, на примере функции вычисления факториала. Вызов fact(5) вычисляет факториал 5! и определяется следующим образом: 5! = 5 × 4 × 3 × 2 × 1. По тому же принципу fact(3) соответствует 3 × 2 × 1. Рекурсивная функция для вычисления факториала числа выглядит так:

def fact(x):

  if x == 1:

    return 1

  else:

    return x * fact(x-1)

В программу включается вызов fact(3). Проанализируем этот вызов строку за строкой и посмотрим, как изменяется стек вызовов. Стоит напомнить, что верхний блок в стеке сообщает, какой вызов fact является текущим.

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

Стек играет важную роль в рекурсии. В начальном примере были представлены два решения поиска ключа. Вспомните, как выглядел первый:

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

Но в рекурсивном решении никакой кучи не существует.

Если кучи нет, то как ваш алгоритм узнает, в каких коробках еще нужно искать? Пример:

К этому моменту стек вызовов выглядит примерно так:

«Куча коробок» хранится в стеке! Это стек незавершенных вызовов функции, каждый из которых ведет собственный незаконченный список коробок для поиска. Стек в данном случае особенно удобен, потому что вам не нужно отслеживать коробки самостоятельно — стек делает это за вас.

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

• Переписать код с использованием цикла.

• Иногда можно воспользоваться так называемой хвостовой рекурсией. Это непростая тема, которая выходит за рамки книги. Вдобавок она поддерживается далеко не во всех языках.

Упражнение

3.2 Предположим, вы случайно написали рекурсивную функцию, которая бесконечно вызывает саму себя. Как вы уже видели, компьютер выделяет память в стеке при каждом вызове функции. А что произойдет со стеком при бесконечном выполнении рекурсии?

Шпаргалка

• Когда функция вызывает саму себя, это называется рекурсией.

• В каждой рекурсивной функции должно быть два случая: базовый и рекурсивный.

• Стек поддерживает две операции: занесение и извлечение элементов.

• Все вызовы функций сохраняются в стеке вызовов.

• Если стек вызовов станет очень большим, он займет слишком много памяти.

2 http://stackoverflow.com/a/72694/139117

4. Быстрая сортировка

В этой главе

• Вы узнаете о стратегии «разделяй и властвуй». Случается так, что задача, над которой вы трудитесь, не решается ни одним из известных вам алгоритмов. Столкнувшись с такой задачей, хороший программист не сдается. У него существует целый арсенал приемов, которые он пытается использовать для получения решения. «Разделяй и властвуй» — первая общая стратегия, с которой вы познакомитесь.

• Далее рассматривается быстрая сортировка — элегантный алгоритм сортировки, часто применяемый на практике. Алгоритм быстрой сортировки использует стратегию «разделяй и властвуй».

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

В этой главе мы постепенно добираемся до полноценных алгоритмов. В конце концов, алгоритм не особенно полезен, если он способен решать задачу только одного типа, — «разделяй и властвуй» помогает выработать новый подход к решению задач. Это всего лишь еще один инструмент в вашем арсенале. Столкнувшись с новой задачей, не впадайте в ступор. Вместо этого спросите себя: «А нельзя ли решить эту задачу, применив стратегию “разделяй и властвуй”?»

К концу этой главы вы освоите свой первый серьезный алгоритм «разделяй и властвуй»: быструю сортировку. Этот