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

Джей Венгроу

• Herausgeber: Питер
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Russisch

Seitenzahl: 504

Veröffentlichungsjahr: 2023

Beschreibung

Структуры данных и алгоритмы — это не абстрактные концепции, а турбина, способная превратить ваш софт в болид формулы 1. Научитесь использовать нотацию «О большое», выбирайте наиболее подходящие структуры данных, такие как хеш-таблицы, деревья и графы, чтобы повысить эффективность и быстродействие кода, что критически важно для современных мобильных и веб-приложений. Книга полна реальных прикладных примеров на популярных языках программирования (Python, JavaScript и Ruby), которые помогут освоить структуры данных и алгоритмы и начать применять их в повседневной работе. Вы даже найдете слово, которое может существенно ускорить ваш код. Практикуйте новые навыки, выполняя упражнения и изучая подробные решения, которые приводятся в книге. Начните использовать эти методы уже сейчас, чтобы сделать свой код более производительным и масштабируемым.

Leseprobe

Джей Венгроу

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

Переводчик С. Черников

Джей Венгроу

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

ISBN 978-5-4461-2068-0

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

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

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

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

Джон Андерсон, вице-президент по технологическому развитию, Infinity Interactive

Я занимаюсь программированием уже более 30 лет и за это время твердо усвоил, как важно всегда возвращаться к основам. Благодаря книге «Прикладные структуры данных и алгоритмы» я смог удостовериться в предположениях, которые делал в прошлом, и закрепить базовые навыки, которые планирую использовать в будущем. Не стоит покупать эту книгу, чтобы подготовиться к тестовому заданию на собеседовании. Прочтите ее ради развития алгоритмического мышления. Независимо от того, новичок вы в программировании или опытный специалист, вам нужен исчерпывающий набор структур данных и распространенных (и не очень) алгоритмов, которые их дополняют. Ко всему прочему, здесь вы узнаете, как, когда и зачем нужно оптимизировать код, заставите его работать, ускорите и улучшите его, попутно разбираясь с разными тонкостями этой стороны вопроса.

Скотт Хансельман, программист Microsoft, профессор, блогер, автор подкаста

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

Найджел Лоури, главный консультант, Lemmata

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

Джейсон Пайк, старший инженер-программист, KEYSYS Consulting

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

Брайан Шо, ведущий программист, Schau Consulting

Предисловие

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

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

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

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

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

Для кого эта книга

Эта книга подойдет для вас, если вы:

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

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

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

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

Новое во втором издании

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

Итак, ниже перечислены несколько основных отличий второго издания от первого.

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

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

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

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

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

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

3. Упражнения и решения. Теперь в каждой главе вы найдете ряд упражнений для практического закрепления изученных концепций (все подробные решения вы найдете в приложении в конце книги). Благодаря этому улучшению книга превратилась в более полное учебное пособие.

Что вы найдете в этой книге

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

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

Глава 3 очень важна. В ней я постараюсь максимально доступно объяснить суть нотации «О большое», которая упоминается на протяжении всей книги.

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

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

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

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

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

В главах 14, 15, 16, 17 и 18 мы исследуем структуры данных на основе узлов, включая связный список, двоичное и префиксное дерево, кучу, граф, и узнаем, когда может пригодиться каждая из них.

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

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

Как читать эту книгу

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

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

Например, при желании после чтения главы 10 вы можете перейти сразу к главе 13 (кстати, эта диаграмма основана на структуре данных «дерево», с которой вы познакомитесь в главе 15).

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

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

Примеры кода

Концепции в этой книге не относятся к одному конкретному языку программирования. Поэтому примеры кода, которые вы здесь найдете, написаны на разных языках, в частности Ruby, Python и JavaScript, знакомство с которыми будет весьма кстати.

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

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

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

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

Интернет-ресурсы

У этой книги есть своя веб-страница (https://pragprog.com/titles/jwdsal2), где вы найдете всю дополнительную информацию. Вы также можете помочь нам, сообщив об ошибках и опечатках, или поделиться предложениями относительно содержания пособия.

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

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

Я хочу сказать спасибо своей замечательной жене Рене за уделенное время и эмоциональную поддержку. За то, что заботилась обо всем, пока я писал, запершись в кабинете, как затворник. Спасибо моим очаровательным детям Туви, Лии, Шайе и Рами за терпение, которое они проявляли, пока я работал над книгой об «алгоритмах». И да — наконец-то все позади.

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

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

Когда я впервые отправил свою рукопись в Pragmatic Bookshelf, я думал, что она и так уже довольно хороша. Но благодаря опыту, конструктивной критике и предложениям замечательных сотрудников издательства книга стала намного лучше. Я хочу поблагодарить своего редактора Брайана Макдональда за то, что он познакомил меня с реальным процессом работы над книгой и поделился идеями, которые сделали лучше каждую главу этого пособия. Я выражаю признательность главному редактору Сюзанне Пфальцер и исполнительному редактору Дэйву Рэнкину. Вы приняли мою рукопись и показали, какой может быть эта книга, превратив ее в ресурс, доступный любому программисту. Спасибо издателям Энди Ханту и Дэйву Томасу за то, что поверили в этот проект и сделали Pragmatic Bookshelf замечательным издательством, с которым хочется сотрудничать.

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

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

Рецензенты первого издания: Алессандро Бахгат, Иво Бальберт, Альберто Боскетти, Хавьер Кольядо, Мохамед Фуад, Дерек Грэхем, Нил Хэйнер, Питер Хэмптон, Род Хилтон, Джефф Холланд, Джессика Янюк, Аарон Калэир, Стефан Кампер, Арун С. Кумар, Шон Линдсей, Найджел Лоури, Джой Маккэффри, Дейвид Морган, Джасдип Наранг, Стивен Орр, Кеннет Парех, Джейсон Пайк, Сэм Роуз, Фрэнк Руис, Брайан Шо, Тибор Симич, Маттео Ваккари, Стивен Вольф и Питер В.А. Вуд.

Рецензенты второго издания: Ринальдо Бонаццо, Майк Браун, Крейг Кастелаз, Джейкоб Че, Зульфикар Дхармаван, Ашиш Диксит, Дэн Дайбас, Эмили Экдал, Дерек Грэхем, Род Хилтон, Джефф Холланд, Грант Казан, Шон Линдсей, Найджел Лоури, Дэри Меркенс, Кевин Митчелл, Нуран Махмуд, Дэвид Морган, Брент Моррис, Эмануэль Ориджи, Джейсон Пайк, Айон Рой, Брайан Шо, Митчелл Фолк и Питер В.А. Вуд.

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

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

Спасибо вам всем за ваш вклад в реализацию этого проекта.

Обратная связь

Я очень люблю получать обратную связь, поэтому предлагаю вам найти меня в LinkedIn: https://www.linkedin.com/in/jaywengrow. Я с радостью приму ваш запрос на подключение — просто напишите, что вы читатель этой книги. С нетерпением жду ваших сообщений!

Джей Венгроу, [email protected]. Май 2020 года

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

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

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

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

Глава 3. О да! Нотация «О большое»

Ранее мы с вами говорили о том, что основной фактор, определяющий эффективность алгоритма, — это количество выполняемых им шагов.

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

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

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

Разобравшись с О-нотацией, вы научитесь описывать алгоритмы согласованно и лаконично, как профессионалы.

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

«O большое»: количество шагов при наличии N элементов

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

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

Некоторые произносят это как «О большое от эн» или «сложность порядка N». Но я предпочитаю говорить просто: «О от эн».

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

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

Теперь давайте рассмотрим выражение временной сложности с помощью О-нотации на примере того же линейного поиска. Сначала мы задаем ключевой вопрос: если в массиве N элементов данных, сколько шагов нужно для выполнения линейного поиска? Мы знаем, что на выполнение такого поиска уйдет N шагов, поэтому выражаем ответ так: O(N). Для справки, O(N) еще называют алгоритмом с линейной временной сложностью или выполняемым за линейное время.

Сравним все это с выражением эффективности чтения из стандартного массива через О-нотацию. Как вы узнали из главы 1, на чтение из массива, вне зависимости от его размера, уходит всего шаг. Чтобы выразить сложность этого алгоритма в О-нотации, мы снова зададим ключевой вопрос: если в массиве N элементов данных, сколько шагов нужно для чтения из него? Ответ: один шаг, поэтому мы можем выразить сложность этого алгоритма так: O(1) (произносится как «О от единицы»).