Предисловие

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

Who This Book Is For

Книга написана в предположении, что читатель уже имеет практический опыт программирования — например, на Python. Если вы никогда не писали программ, я бы посоветовал сначала выучить какой-нибудь язык программирования, а потом уже браться за чтение. В книге используется Python, потому что он одинаково удобен и программистам и не-программистам. If you are reading this book, I assume you already have a working knowledge of a programming language, such as Python. If you have never programmed before, I encourage you to first learn a programming language and then come back! I use Python in this book because it is accessible to programmers and nonprogrammers alike.

Алгоритмы предназначены для решения общих задач, которые постоянно возникают при разработке программного обеспечения. Преподавая на младших курсах, я стараюсь навести мосты между собственными знаниями студентов и понятиями, которые я использую в своих алгоритмах. Большинство учебников содержат тщательные пояснения — но всё равно их всегда недостаточно. Частенько студент не может заняться самостоятельным изучением алгоритма, потому что ему не показали, как ориентироваться в материале. Algorithms are designed to solve common problems that arise frequently in software applications. When teaching algorithms to undergraduate students, I try to bridge the gap between the students’ background knowledge and the algorithm concepts I’m teaching. Many textbooks have carefully written—but always too brief—explanations. Without having a guide to explain how to navigate this material, students are often unable to learn algorithms on their own.

Сейчас я опишу цель этой книги одним абзацем и одной иллюстрацией. Начнём мы с нескольких структур данных, которые показывают, как информация представляется примитивными атомарными типами, например, 32-разрядными целыми числами или 64-разрядными вещественными. Некоторые алгоритмы, в частности, бинарный поиск, работают с такими структурами напрямую. Более сложные алгоритмы, например, алгоритмы на графах, используют важные абстрактные типы данных (стек, приоритетная очередь и т. п.), которые мы изучим по ходу изложения. Абстрактный тип подразумевает набор действий над ним, и вот эти действия будут эффективны только если выбрать подходящую структуру данных для его реализации. Ближе к концу книги мы рассмотрим, как повысить быстродействие различных алгоритмов. Сами алгоритмы мы либо целиком напишем на Python, либо рассмотрим соответствующие сторонние пакеты Python, в которых они эффективно реализованы. In one paragraph and in Figure P-1, let me show you my goal for the book. I intro‐ duce a number of data structures that explain how to organize information using primitive fixed-size types, such as 32-bit integer values or 64-bit floating point values. Some algorithms, such as Binary Array Search, work directly on data structures. More complicated algorithms, especially graph algorithms, rely on a number of fun‐ damental abstract data types, which I introduce as needed, such as stacks or priority queues. These data types provide fundamental operations that can be efficiently implemented by choosing the right data structure. By the end of this book, you will understand how the various algorithms achieve their performance. For these algo‐ rithms, I will either show full implementations in Python or refer you to third-party Python packages that provide efficient implementation.

Если вы заглянете в сопутствующие книге исходные тексты программ, найдёте там в каждой главе файл book.py — это программа на Python, которая при запуске воспроизводит на вашем компьютере все диаграммы из книги. «У каждого свои рекорды», как говорят автоторговцы, но соотношение характеристик в целом должно остаться тем же. If you review the associated code resources provided with the book, you will see that for each chapter there is a book.py Python file that can be executed to reproduce all tables within the book. As they say in the business, “your mileage may vary,” but the overall trends will still appear.

Иллюстрация P-1. Сводка по тематическому содержанию книги

В конце каждой главы есть проверочные упражнения, на них вы можете потренироваться применять свежие знания. Очень советую сначала попробовать решить задачи самостоятельно, а потом сравнить с примерами решений в нашем репозитории исходных текстов. At the end of every chapter in the book are challenge exercises that give you a chance to put your new knowledge to the test. I encourage you to try these on your own before you review my sample solutions, found in the code repository for the book.

Исходные тексты

About the Code

Все программы из книги доступны в соответствующем репозитории на GitHub — http://github.com/heineman/LearningAlgorithms. Они совместимы с Python 3.4 и выше. Везде, где это было разумно, я старался следовать рекомендациям Python и оформлять системные методы, наподобие __str()__ или __len__(). Примеры в книге отформатированы с отступом в два пробела — так они лучше помещаются вширину при печати; в программах репоизтория используется стандартный отступ в четыре пробела. Изредка в печатных примерах попадаются однострочники, например if j == lo: break¹. All the code for this book can be found in the associated GitHub repository, http://github.com/heineman/LearningAlgorithms. The code conforms to Python 3.4 or higher. Where relevant, I conform to Python best practices using double underscore methods, such as str() and len(). Throughout the code examples in the book, I use two-space indentation to reduce the width of the code on the printed page; the code repository uses standard four-space indentation. In a few code listings, I format code using an abbreviated one-line if statement like if j == lo: break.

В программах используются три свободно распространяемые библиотеки Python, которые необходимо скачать и установить самостоятельно²: The code uses three externally available, open source Python libraries

• NumPy (https://www.numpy.org) версии 1.19.5

• SciPy (https://www.scipy.org) версии 1.6.0

• NetworkX (https://networkx.org) версии 2.5

NumPy и SciPy — одни из самых популярных свободных библиотек с огромным сообществом. Я их использую, чтобы измерить фактическую производительность алгоритмов. NetworkX — большой сборник эффективных алгоритмов для работы с графами, он нам понадобится в главе 7; там же есть удобная готовая структура данных, реализующая граф. Средства этих библитотек позволят не изобретать очередное колесо, если в этом нет нужды. Если они не установлены, не беда: примеры написаны так, что смогут работать без и них, нужные функции также есть в репозитории. NumPy and SciPy are among the most commonly used open source Python libraries and have a wide audience. I use these libraries to analyze empirical runtime perfor‐ mance. NetworkX provides a wide range of efficient algorithms for working with graphs, as covered in Chapter 7; it also provides a ready-to-use graph data type imple‐ mentation. Using these libraries ensures that I do not unnecessarily reinvent the wheel. If you do not have these libraries installed, you will still be fine since I provide workarounds.

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

All timing results presented in the book use the timeit module using repeated runs of a code snippet. Often the code snippet is run a repeated number of times to ensure it can be accurately measured. After a number of runs, the minimum time is used as the timing performance, not the average of all runs. This is commonly considered to be the most effective way to produce an accurate timing measurement because averaging a number of runs can skew timing results when some performance runs are affected by external factors, such as other executing tasks from the operating system.

Если скорость работы алгоритма сильно зависит от свойств обрабатываемых данных (как в случае сортировки вставками из главы 5), о том, что в этом случае измеряется среднее время, будет сказано явно. When the performance of an algorithm is highly sensitive to its input (such as Inser‐ tion Sort in Chapter 5), I will clearly state that I am taking the average over all perfor‐ mance runs.

В нашем репозитории — больше 10000 строк кода на Python, сценарии для запуска всех тестов и вычисления всех данных для таблиц в книге; можно воспроизвести также большую часть диаграмм и графиков. Исходный текст снабжён, как это принято в Python, строками документации и тестами, причём тестовое покрытие, согласно https://coverage.readthedocs.io, составляет 95%. The code repository contains over 10,000 lines of Python code, with scripts to execute all test cases and compute the tables presented in the book; many of the charts and graphs can also be reproduced. The code is documented using Python docstring con‐ ventions, and code coverage is 95%, using https://coverage.readthedocs.io.

Если у вас возникнут технические вопросы или затруднения в работе примеров, свяжитесь с нами по адресу bookquestions@oreilly.com. If you have a technical question or a problem using the code examples, please send email to bookquestions@oreilly.com .

Цель книги — помочь в решении повседневных задач. Вообще говоря, любой пример из книги можно использовать в документации или программе. Получать разрешение от нас на использование примера не надо, если только вы не собираетесь цитировать значительную часть всего корпуса примеров. В частности, если ваше приложение использует несколько программных фрагментов из книги, разрешение не нужно. Разрешение нужно, если вы продаёте или распространяете непосредственно примеры из книг издательства O'Reilly. Если вы в ответе на чей-о вопрос цитируете пример из этой книги, разрешение не нужно. Разрешение нужно, если вы включаете значительную часть примеров из книги издательства O'Reilly в документацию к своему продукту⁴. This book is here to help you get your job done. In general, if example code is offered with this book, you may use it in your programs and documentation. You do not need to contact us for permission unless you’re reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing examples from O’Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of example code from this book into your product’s documentation does require permission.

Мы рады, когда люди ссылаются на наши книги, хотя это тоже не обязательно. При ссылке указывайте название, автора, издательство и ISBN. Например, «Learning Algorithms: A Programmer’s Guide to Writing Better Code by George T. Heineman (O’Reilly). Copy‐ right 2021 George T. Heineman, 978-1-492-09106-6.».

Если вы опасаетесь, что задействовали в своей работе слишком много примеров, и это уже не помещается в рамки добросовестного использования или противоречит нашим условиям, смело обращайтесь по адресу permissions@oreilly.com. We appreciate, but generally do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: “Learning Algorithms: A Programmer’s Guide to Writing Better Code by George T. Heineman (O’Reilly). Copy‐ right 2021 George T. Heineman, 978-1-492-09106-6.” If you feel your use of code examples falls outside fair use or the permission given above, feel free to contact us at permissions@oreilly.com .

Типографические обозначения

Conventions Used in This Book

В книге используются следующие типографические обозначения: The following typographical conventions are used in this book:

• Курсив Italic

  • Выделяет новые термины, URL, имена файлов и их расширения, а также всё, что автор хотел подчеркнуть. Indicates new terms, URLs, filenames, file extensions, and points I want to emphasize.

• Моноширинный шрифт Constant width

  • Используется для программ в иллюстрациях и для ссылки на фрагменты программ в тексте — например, для переменных, имён функций, типов данных, операторов и ключевых слов. Used for program listings as well as within paragraphs to refer to program ele‐ ments such as variable or function names, data types, statements, and keywords.

• Полужирный шрифт

  • В русском переводе обозначает собственные имена алгоритмов и структур данных⁵.

• Кошачий лемур сопровождает совет или подсказку. Из всех приматов, включая человека, у кошачьего лемура самое большое суммарное поле зрения — до 280°. В тексте советы лемура позволяют буквально расширить кругозор: в них изложена познавательная информация или интересная возможность Python. This element, identified by an image of a ring-tailed lemur, is a tip or suggestion. I use this image because lemurs have a combined visual field of up to 280°, which is a wider visual field than anthro‐ poid primates (such as humans). When you see this tip icon, I am literally asking you to open your eyes wider to learn a new fact or Python capability.

• Ворона сопровождает теоретические замечания. Большинство зоопсихологов сходятся на том, что вороны — очень умные птицы: они умеют решать сложные задачи и даже использовать орудия. В тексте замечание вороны содержит определение термина или разъяснения важного понятия. Прежде, чем читать дальше, их надо внимательно изучить. This element, identified by an image of a crow, signifies a general note. Numerous researchers have identified crows to be intelligent, problem-solving animals—some even use tools. I use these notes to define a new term or call your attention to a useful concept that you should understand before advancing to the next page.

• Скорпион сопровождает предупреждение. При виде скорпиона в природе, мы осторожно останавливаемся. В книге скорпион предупреждает о том, что надо остановиться и осторожно рассмотреть сложные аспекты, с которыми можно столкнуться при реализации алгоритмов. This element, identified by an image of a scorpion, indicates a warning or caution. Much like in real life, when you see a scorpion, stop and look! I use the scorpion to call attention to key challenges you must address when applying algorithms.

Онлайн-обучение O’Reilly

O’Reilly Online Learning

O’Reilly Media уже более сорока лет способствует корпоративному росту в мире: проводит технические и бизнес-тренинги, занимается оценкой компетентности и внутренней аналитикой компаний. For more than 40 years, O’Reilly Media has provided technol‐ ogy and business training, knowledge, and insight to help companies succeed. */

Наши специалисты и инноваторы распространяют знания и проводят экспертизу посредство уникальной образовательной сети, включающей в себя книги, статьи и образовательную онлайн-платформу. Образовательная онлайн-платформа O'Reilly предоставляет своевременный доступ к интерактивным учебным курсам, углублённым образовательным траекториям, онлайновым средам программирования и огромному корпусу текстовых и видеоматериалов O'Reilly и более двухсот других издательств. Больше информации — на нашем сайте, http://oreilly.com. Our unique network of experts and innovators share their knowledge and expertise through books, articles, and our online learning platform. O’Reilly’s online learning platform gives you on-demand access to live training courses, in-depth learning paths, interactive coding environments, and a vast collection of text and video from O’Reilly and 200+ other publishers. For more information, visit http://oreilly.com.

Как с нами связаться

How to Contact Us

Вопросы и замечания к этой книге просьба направлять издателю: Please address comments and questions concerning this book to the publisher:

• O’Reilly Media, Inc.
  1005 Gravenstein Highway North
  Sebastopol, CA 95472
  800-998-9938 (in the United States or Canada)
  707-829-0515 (international or local)
  707-829-0104 (fax)

У это книги есть веб-страница, на которой публикуются замеченные опечатки и исправления неточностей, примеры и другоая полезная информация. Веб-страница доступна по адресу https://oreil.ly/learn-algorithms. We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at https://oreil.ly/learn-algorithms.

Технические вопросы и комментарии к книге направляйте по электронной почте bookquestions@oreilly.com. Email bookquestions@oreilly.com to comment or ask technical questions about this book.

Новости по всем книгам и курсам ищите на сайте http://oreilly.com. For news and information about our books and courses, visit http://oreilly.com.

Мы на Facebook: http://facebook.com/oreilly Find us on Facebook: http://facebook.com/oreilly

Мы в Twitter: http://twitter.com/oreillymedia Follow us on Twitter: http://twitter.com/oreillymedia

Мы на YouTube: http://youtube.com/oreillymedia Watch us on YouTube: http://youtube.com/oreillymedia

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

Acknowledgments

Я считаю, что лучшее в компьютерной науке — это изучение алгоритмов. Спасибо читателям за то, что дали мне возможность поделиться своими наработками. Спасибо моей жене Дженнифер, за то, что поддержала меня в затее с очередной книгой. Спасибо моим сыновьям, Николасу и Александру, за то, что они уже выросли и могут изучать программирование. For me, the study of algorithms is the best part of computer science. Thank you for giving me the opportunity to present this material to you. I also want to thank my wife, Jennifer, for her support on yet another book project, and my two sons, Nicho‐ las and Alexander, who are now both old enough to learn about programming.

Эта книга стала лучше благодаря редакторам O'Reilly — Мелиссе Даффилд, Саре Грей, Бет Келли и Вирджинии Вильсон. Они помогали мне систематизировать общее содержание книги и выстраивать пояснения кнему. Технические рецензенты — Лаура Хелливелл, Чарли Лаверинг, Хелен Скотт, Стенли Силков и Аура Веларде — нашли множество неточностей, улучшали реализацию алгоритмов и пояснения к ним. Если остались какие-то недочёты — все они целиком на моей совести. My O’Reilly editors—Melissa Duffield, Sarah Grey, Beth Kelly, and Virginia Wilson— improved the book by helping me organize the concepts and its explanations. My technical reviewers—Laura Helliwell, Charlie Lovering, Helen Scott, Stanley Selkow, and Aura Velarde—helped eliminate numerous inconsistencies and increase the qual‐ ity of the algorithm implementations and explanations. All defects that remain are my responsibility.