Не позволяйте страху мешать вам, не бойтесь говорить «я не знаю» или «я не понимаю» — ни один вопрос не является глупым.

Маргарет Х. Гамильтон (Margaret H. Hamilton)

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

Эдсгер Дейкстра (Edsger Dijkstra)

Cu `un fa nenti `un sbagghia nenti.

(Не ошибается только тот, кто ничего не делает.)

Известная поговорка

Предисловие

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

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

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

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

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

В этой книге Марчелло смог приподнять завесу тайны над сложными темами, такими как алгоритмы отображения-свертки, генетические алгоритмы и имитация отжига, изложить их с той же легкостью, с какой он рассказал о деревьях и кучах. Я настоятельно рекомендую эту книгу всем желающим получить четкое представление об основах computer science. Единственный вопрос, который возник у меня после прочтения книги: «Где она была, когда я готовился к своему первому собеседованию в Кремниевой долине?»

Д-р Луи Серрано (Luis Serrano), PhD, инженер-исследователь в Quantum Artificial Intelligence Zapata Computing

Вступление

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

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

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

И все же в течение долгого времени, уже после появления компьютеров, алгоритмами в основном занимались в академических кругах. Хотя были и некоторые редкие исключения, такие как компания Bell Labs, чьи научно-исследовательские группы добились больших успехов в этой сфере в период между 1950-ми и 1990-ми годами. Эти коллективы разработали динамическое программирование, алгоритм Беллмана — Форда и сверхточные нейронные сети для распознавания изображений.

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

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

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

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

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

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

Я хотел бы поблагодарить за помощь на этом пути многих людей.

Спасибо моим редакторам в издательстве Manning: Хелен Стергиус (Helen Stergius) — перед ней стояла непростая задача помочь мне привести первоначальный вариант моей рукописи в соответствие со стандартами Manning — и Дженнифер Стаут (Jennifer Stout), работавшей над этим проектом последние пару лет. Без их помощи я не смог бы достичь желаемой цели. Мне было приятно работать с вами обеими. Спасибо за помощь, бесценные советы и терпение! Сотрудничая с вами, я многое узнал о том, как правильно писать книги, учить читателей и обращаться к ним. Вы помогли мне сделать эту книгу намного лучше.

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

Особая благодарность моему другу Аурелио Де Роса (Aurelio De Rosa). Мне выпала большая честь заполучить его на роль редактора блога о JavaScript, куда мы оба писали задолго до того, как появилась эта книга. Он вносил огромный вклад в нее, попутно помогая мне учиться писать технические тексты. Он был ее первым техническим редактором, задавал общее направление работы над книгой, обсуждал включенные в нее темы и просматривал код. Когда я искал издателя для своей рукописи, именно Аурелио познакомил меня с представителями Manning Publishing.

Огромное спасибо Артуру Зубареву (Arthur Zubarev), присоединившемуся к команде пару лет назад, давшему массу отличных советов и всегда высказывавшему справедливую критику. Работать с вами было удовольствием и честью.

Спасибо также всем остальным сотрудникам издательства Manning, трудившимся над опубликованием и продвижением книги: редактору проекта Дейдре Хиам (Deirdre Hiam), литературному редактору Кэти Петито (Katie Petito), корректору Мелоди Долаб (Melody Dolab) и редактору-рецензенту Александару Драгосавлевичу (Aleksandar Dragosavljevic). Это была действительно командная работа. И огромное спасибо рецензентам: Андрею Формиге (Andrei Formiga), Кристоферу Финку (Christoffer Fink), Кристоферу Хаупту (Christopher Haupt), Дэвиду Т. Кернсу (David T. Kerns), Эдду Мелендесу (Eddu Melendez), Джорджу Томасу (George Thomas), Джиму Амрейну (Jim Amrhein), Джону Монтгомери (John Montgomery), Лукасу Джерардо Теттаманти (Lucas Gerardo Tettamanti), Мачею Юрковски (Maciej Jurkowski), Маттео Гилдоне (Matteo Gildone), Майклу Дженсену (Michael Jensen), Майклу Кумму (Michael Kumm), Мишель Уильямсон (Michelle Williamson), Расмусу Киркби Стробаку (Rasmus Kirkeby Strøbæk), Рикардо Новелло (Riccardo Noviello), Ричу Уорду (Rich Ward), Ричарду Вогану (Richard Vaughan), Тимми Хосе (Timmy Jose), Тому Дженис (Tom Jenice), Урсуле Сервантес (Ursula Cervantes), Винсенту Забалле (Vincent Zaballa) и Захари Флейшманну (Zachary Fleischmann). Они уделяли время моей рукописи на различных этапах работы и давали бесценные отзывы о ней.

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

Наконец, упомяну людей, сыгравших особую роль в моем становлении как специа­листа в области computer science, кем я являюсь сегодня.

Прежде всего я хочу выразить благодарность бывшим преподавателям в Университете Катании. Здесь у меня есть возможность назвать только основных моих наставников: профессора Галло (Gallo), профессора Кутелло (Cutello) и профессора Паппалардо (Pappalardo), но на самом деле у меня очень длинный список имен. Я чувствую, что в наше время, когда полезность дипломов о высшем образовании ставится под сомнение и предпочтение отдается их более быстрым и практичным альтернативам, важно сказать о выдающейся работе, проделанной преподавателями в моей альма-матер. Массовые онлайн-курсы — отличный способ обучения и, бесспорно, шаг в направлении доступного и демократичного образования, становится возможным получить его независимо от местонахождения и социального статуса обучаемого. Но есть вещи, которые, как мне кажется, я бы упустил без учебы в колледже, — формирование и развитие критического отношения к окружающему, мышления ученого, направленного на проникновение в суть проблем и получение более широкого набора навыков, чем необходимый для работы минимум.

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

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

О книге

Я могу назвать по крайней мере три веские причины потратить время на изучение алгоритмов.

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

2. Безопасность. Если вы выбрали неправильный алгоритм, злоумышленник может воспользоваться этой оплошностью, чтобы вывести из строя ваш сервер, узел или приложение. Осуществить, к примеру, DoS-атаку на хеш1, где хеш-таблица используется в качестве словаря для переменных, отправляемых с запросами POST, и перегрузить ее последовательностью, вызывающей огромное количество коллизий. Это, в свою очередь, не позволит серверу своевременно отвечать на запросы. Еще один интересный пример — когда ненадежные генераторы случайных чисел2 однажды были использованы для взлома сайтов игры в покер онлайн.

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

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

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

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

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

И последнее, но не менее важное: если вы читали книгу Grokking Algorithms3 Адитьи Бхаргава (Aditya Y. Bhargava) и она вам понравилась, то мой опус сможете рассматривать как следующий шаг для желающих продолжить изучение алгоритмов. Если вы еще не читали ее, я настоятельно рекомендую сделать это: материал в ней объясняется языком, понятным любой аудитории. Не случайно эта книга пользуется большой популярностью. Я надеюсь, что и моя тоже покажется вам понятной и полезной.

Кому адресована эта книга

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

• Хорошо знаете математику, в частности алгебру. Это поможет вам понять теоретические разделы. Тем не менее в приложении Б содержится краткое введение в нотацию «О большое» и асимптотический анализ.

• Посещали вводный курс по информатике или даже по алгоритмам. Тогда вы уже знакомы с базовыми структурами данных, которые станут основой обсуждений в этой книге.

• Знакомы с такими понятиями, необходимыми для полного понимания структур данных, как:

• основные структуры для хранения данных, такие как массивы и связные списки;

• хеш-таблицы и хеширование;

• деревья;

• контейнеры (очереди и стеки);

• основы рекурсии.

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

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

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

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

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

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

В главе 2 представлен улучшенный вариант двоичных куч — d-куча. Здесь также описывается, как структурирован материал в каждой из глав этой части, каковы особенности его подачи.

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

Глава 4 переключается на фильтры Блума — продвинутую форму хеш-таблицы, помогающую экономить память при сохранении постоянным времени поиска.

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

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

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

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

Материал главы 8 знакомит с задачей ближайшего соседа.

В главе 9 описываются k-мерные деревья, применяемые для эффективного поиска в многомерных наборах данных.

Глава 10 содержит материал о более совершенных версиях этих деревьев: SS- и R-деревьях.

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

В главе 12 представлены примеры использования эффективных алгоритмов поиска ближайших соседей: три алгоритма кластеризации, метод k-средних, DBSCAN и OPTICS.

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

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

В главе 14 дается краткое введение в графы и описываются основы этой фундаментальной структуры данных, необходимые для понимания части III. Здесь также демонстрируются алгоритмы DFS, BFS, алгоритмы Дейкстры и A* и рассказывается, как их использовать для решения задачи «кратчайшего пути».

Глава 15 знакомит с векторными представлениями графов (graph embeddings), планарностью и ставит пару задач, которые мы попытаемся решить в последующих главах: поиск векторного представления графа с минимальным числом пересечений (Minimum Crossing Number, MCN) и красивое рисование графа.

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

Глава 17 основана на предыдущей главе и представляет метод имитации отжига (simulated annealing) — мощную технику оптимизации, которая пытается преодолеть недостатки градиентного спуска, когда приходится иметь дело с недифференцируемыми функциями или функциями с несколькими локальными минимумами.

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

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

Но хватит об этом; более детально манера и порядок изложения материала описаны в главе 2.

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

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

В приложении Б дается обзор нотации «О большое» и пространственно-временного анализа.

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

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

В приложении Е приводится определение рандомизированных алгоритмов, таких как Монте-Карло и Лас-Вегас. Здесь вы можете ознакомиться с задачами классификации и оценки рандомизированных решений.

О примерах программного кода

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

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

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

Кроме того, если вы знаете какой-то язык программирования, интересуетесь им или хотите увидеть воплощение представленных в книге идей в реальном выполняемом коде, можете обратиться к созданному нами репозиторию на GitHub5. Там найдете их реализации на нескольких языках (в том числе на Java, Python и JavaScript).

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

Ваши замечания, предложения, вопросы отправляйте по адресу comp@piter.com (издательство «Питер», компьютерная редакция).

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

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

---

Об авторе

Марчелло Ла Рокка (Marcello La Rocca) — старший инженер-программист в Tundra.com. В фокусе его профессиональных интересов находятся графы, алгоритмы оптимизации, генетические алгоритмы, машинное обучение и квантовые вычисления. Он участвовал в разработке крупномасштабных веб-приложений и инфраструктур данных в таких компаниях, как Twitter, Microsoft и Apple, проводил прикладные исследования как в научной сфере, так и в промышленной. Марчелло придумал и реализовал алгоритм адаптивной сортировки NeatSort.

Иллюстрация на обложке

На обложке размещена иллюстрация под названием Femme de Fiume, или «Женщина из Риеки», из коллекции костюмов разных стран, собранной Жаком Грассе де Сен-Совером (Jacques Grasset de Saint-Sauveur) (1757–1810). Коллекция имеет название Costumes de Différents Pays, она была издана во Франции в 1797 году. Все иллюстрации в этом собрании тщательно прорисованы и раскрашены вручную. Богатое разнообразие представленных в коллекции Грассе де Сен-Совера костюмов с очевидностью демонстрирует, насколько далекими друг от друга в культурном отношении были города и регионы мира всего 200 лет назад. Изолированные друг от друга, люди говорили на разных языках и диалектах. В те времена по одежде легко было определить место жительства, профессию и социальное положение.

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

В наше время, когда трудно отличить одну техническую книгу от другой, издательство Manning проявило инициативу и деловую сметку, украсив обложки книг изображениями, основанными на самобытности жизненного уклада народов двухвековой давности, подарив новую жизнь иллюстрациям из коллекции Жака Грассе де Сен-Совера.