Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 1)

А. Бхаргава

Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

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

Предисловие

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

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

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

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

Спасибо издательству Manning, которое дало мне возможность написать эту книгу и предоставило большую творческую свободу в ходе работы. Я благодарен издателю Марджану Бейсу (Marjan Bace), Майку Стивенсу (Mike Stephens) за то, что он ввел меня в курс дела, Берту Бейтсу (Bert Bates), который научил меня писать на научные темы, и Дженнифер Стаут (Jennifer Stout) — невероятно отзывчивому редактору, всегда готовому прийти на помощь. Спасибо всем участникам производственной группы Manning: Кевину Салливану (Kevin Sullivan), Мэри Пьержи (Mary Piergies), Тиффани Тейлор (Tiffany Taylor), Лесли Хаймс (Leslie Haimes) и всем остальным. Кроме того, я хочу поблагодарить всех, кто читал рукопись и делился своим мнением: Карен Бенсдон (Karen Bensdon), Роба Грина (Rob Green), Майкла Хамра (Michael Hamrah), Озрена Харловица (Ozren Harlovic), Колин Хейсти (Colin Hastie), Кристофера Хаупта (Christopher Haupt), Чака Хендерсона (Chuck Henderson), Павла Козловски (Pawel Kozlowski), Амита Ламба (Amit Lamba), Жана-Франсуа Морина (Jean-François Morin), Роберта Моррисона (Robert Morrison), Санкара Раманатана (Sankar Ramanathan), Сандера Россела (Sander Rossel), Дуга Спарлинага (Doug Sparling) и Дэмиена Уайта (Damien White).

Спасибо всем, кто помог мне в достижении цели: сотрудникам 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), моему учителю по теории алгоритмов. Отдельное большое спасибо таким классикам алгоритмов, как CLRS[1], Кнут и Стрэнг; безусловно, я стою на плечах гигантов.

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

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

О книге

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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