Продвинутые алгоритмы и структуры данных E-Book

Марчелло Ла

• Herausgeber: Питер
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Russisch
• Veröffentlichungsjahr: 2023

Seitenzahl: 1062

Beschreibung

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

Leseprobe

Марчелло Ла Рокка

Продвинутые алгоритмы и структуры данных

2024

Переводчики Л. Киселева, М. Сагалович

Марчелло Ла Рокка

Продвинутые алгоритмы и структуры данных. — СПб.: Питер, 2024.

ISBN 978-5-4461-1946-2

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

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

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

Маргарет Х. Гамильтон (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).

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

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

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

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

1 http://ocert.org/advisories/ocert-2011-003.html.

2 Подобные атаки описываются, например, в статье How we learned to cheat at online poker: A study in software security Эркина (Arkin), Брада (Brad) и др. на сайте developer.com, http://www.bluffnakedpoker.com/PDF/developer_gambling.pdf.

3Бхаргава А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. — СПб.: Питер, 2019.

4 Отсюда его англоязычное название treap — комбинация слов tree («дерево») и heap («куча»). — Примеч. пер.

5 https://github.com/mlarocca/AlgorithmsAndDataStructuresInAction.

Об авторе

Марчелло Ла Рокка (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 проявило инициативу и деловую сметку, украсив обложки книг изображениями, основанными на самобытности жизненного уклада народов двухвековой давности, подарив новую жизнь иллюстрациям из коллекции Жака Грассе де Сен-Совера.

Часть I.  Улучшаем базовые структуры данных

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

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

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

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

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

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

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

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

2. Улучшаем очереди с приоритетом: d-кучи

В этой главе

• Задача обработки заданий на основе приоритетов.

• Использование очередей с приоритетом для решения этой задачи.

• Реализация очереди с приоритетом с помощью кучи.

• Понятие d-кучи, ее анализ.

• Сценарии, в которых использование куч улучшает производительность.

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

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

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

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

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

Затем в разделе 2.4 описывается API16 очереди с приоритетом и демонстрируется пример использования ее как черного ящика. Позже, в разделах 2.5 и 2.6, мы с вами углубимся в ее внутреннюю структуру: в разделе 2.5 подробно проанализируем, как работает d-куча, рассмотрим функциональность ее методов, в разделе 2.6 разберем реализацию d-кучи.

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

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

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

2.1. Структура этой главы

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

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

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

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

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

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

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

2.2. Задача: как работать с приоритетами?

Первой задачей, которую мы решим, будет обработка заданий на основе приоритета. Это то, с чем все мы в некотором роде знакомы.

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

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

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

2.2.1. Приоритеты на практике: отслеживание ошибок

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

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

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

Каждая ошибка будет выглядеть как кортеж:

<описание задачи, важность несоблюдения срока>

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

Описание ошибки

Серьезность (1–10)

Загрузка страницы занимает более 2 с

7

Пользовательский интерфейс не работает в браузере X

9

Необязательное поле формы заблокировано при использовании браузера X в пятницу 13-го

1

Стиль CSS нарушает выравнивание

8

Стиль CSS вызывает смещение 1 пикселя в браузере X

5

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

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

Описание ошибки

Серьезность (1–10)

Пользовательский интерфейс не работает в браузере X

9

Стиль CSS нарушает выравнивание

8

Загрузка страницы занимает более 2 с

7

Стиль CSS вызывает смещение 1 пикселя в браузере X

5

Необязательное поле формы заблокировано при использовании браузера X в пятницу 13-го

1

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

Описание ошибки

Серьезность (1–10)

Незашифрованный пароль в базе данных

10

Пользовательский интерфейс не работает в браузере X

9

Необязательное поле формы заблокировано при использовании браузера X в пятницу 13-го

8

Стиль CSS нарушает выравнивание

8

Загрузка страницы занимает более 2 с

7

Стиль CSS вызывает смещение 1 пикселя в браузере X

5

2.3. Простое решение: храним отсортированный список

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

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

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

2.3.1. От отсортированных списков к очередям с приоритетом

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

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

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

2.4. Описание API структуры данных: очереди с приоритетом

Прежде чем углубиться в тему главы, сделаем шаг назад.

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

• API — API представляет собой контракт, который структура данных (СД) заключает с внешними клиентами. Он включает в себя определения методов и некоторые гарантии поведения методов, указанные в спецификации СД. Например, очередь с приоритетами (ОП) (табл. 2.1) предоставляет следующие методы и гарантии:

• top() — возвращает и извлекает элемент с наивысшим приоритетом;

• peek() — как и top, возвращает элемент с наивысшим приоритетом, но не извлекает его из очереди;

• insert(e,p) — добавляет новый элемент e с приоритетом p в ОП;

• remove(e) — удаляет элемент e из очереди;

• update(e,p) — изменяет приоритет элемента e, устанавливая его (приоритет) равным p.

• Инварианты — (необязательные) внутренние свойства, которые всегда остаются истинными на протяжении всего жизненного цикла структуры данных. Например, отсортированный список будет иметь один инвариант: каждый элемент не больше своего преемника. Цель инвариантов — убедиться, что условия, необходимые для выполнения контракта с внешними клиентами, всегда выполняются. Они являются внутренним аналогом гарантий в API.

• Модель данных — для размещения данных. Это может быть просто последовательность ячеек памяти, список, дерево и т.д.

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

Таблица 2.1. API и контракт очереди с приоритетом

Абстрактная структура данных: очередь с приоритетом

API

class PriorityQueue {

top() → element

peek() → element

insert(element, priority)

remove(element)

update(element, newPriority)

size() → int

}

Контракт с клиентом

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

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

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

2.4.1. Примеры работы очереди с приоритетом

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

На данный момент не нужно знать внутренности библиотеки; вам просто нужно следовать ее общедоступному API и использовать его, подразумевая, что он правильно реализован. Это подход «черного ящика» (рис. 2.1).

Например, предположим, что мы добавляем ошибки в нашу ОП в том же порядке, что и раньше.

Описание ошибки

Серьезность (1–10)

Загрузка страницы занимает более 2 с

7

Пользовательский интерфейс не работает в браузере X

9

Необязательное поле формы заблокировано при использовании браузера X в пятницу 13-го

1

Стиль CSS нарушает выравнивание

8

Стиль CSS вызывает смещение 1 пикселя в браузере X

5

Если возвращать задачи в том же порядке, в котором мы их вставляли, можно реа­лизовать простую очередь (см. рис. 2.2, на котором кратко показано, как работает очередь, и приложение В, где дается описание основных контейнеров). Вместо этого предположим, что имеем очередь с приоритетом, содержащую те же пять элементов; мы до сих пор не знаем внутренностей ОП, но можем направлять ей запросы посредством API.

Рис. 2.1.