Опубликовано

Новинка: Алгоритмический тренинг. Решения практических задач на Python и С++

Алгоритмический тренинг. Решения практических задач на Python и С++

Опираясь на богатый соревновательный и эвристический опыт, автор предлагает оригинальные реализации классических алгоритмов Computer Science на языках Python и C++. Особое внимание уделено математическим и геометрическим алгоритмам, графовым алгоритмам, структурам данных (в особенности различным деревьям), комбинаторике и работе со строками. Книга поможет заложить и расширить алгоритмическую подготовку, познакомит с эффективными решениями вычислительных задач, а для обучающихся станет настольной.  Поможет подготовиться к экзаменам, сертификации, олимпиадам по программированию.

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

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

Книгу “Алгоритмический тренинг. Решения практических задач на Python и С++” можно купить со скидкой в интернет-магазине издательства “БХВ“.

Введение. 9

Глава 1. Для кого эта книга. 10

Глава 2. Чему обучит эта книга. 11

Глава 3. Спортивное и промышленное программирование. 12

Глава 4. Как пользоваться книгой. 14

Ступень I. Разминка. 15

Глава 5. Вводные задачи. 16

5.1. A+B. 16

5.2. Пример решения задачи. Числа Фибоначчи. 17

5.3. Пример решения задачи. Манхэттенское расстояние. 18

5.4. Пример решения задачи. Путь до ксерокса. 20

5.5. Пример решения задачи. Проверка перестановки. 22

5.6. Пример решения задачи. Циклы перестановки. 23

Глава 6. Разминочные конструктивные задачи. 25

6.1. Пример решения задачи. Пара с минимальным произведением. 25

6.2. Пример решения задачи. Тайная жизнь деревьев. 27

6.3. Пример решения задачи. Подписывание открыток. 28

6.4. Пример решения задачи. Исправление перестановки. 30

6.5. Пример решения задачи. Минимальный палиндром. 33

6.6. Пример решения задачи. Исключающее ИЛИ от 1 до n. 34

6.7. Пример решения задачи. Врачи и посетители. 37

6.8. Пример решения задачи. Минимизация перепадов. 40

6.9. Пример решения задачи. Одномерный геометрический центр. 42

Глава 7. Разминочные реализационные задачи. 45

7.1. Пример решения задачи. Морской бой. 45

7.2. Пример решения задачи. Стоимость интернет-связи. 47

7.3. Пример решения задачи. Пересечение двух прямоугольников. 50

7.4. Пример решения задачи. Проверка скобочной последовательности. 52

7.5. Пример решения задачи. Проверка скобочной последовательности
с двумя типами. 54

7.6. Пример решения задачи. Зеркальный лабиринт. 55

7.6. Пример решения задачи. Троичная сбалансированная система счисления. 58

Глава 8. Задачи для самостоятельного решения. 60

8.1. Примеры задач. 60

8.2. Задачи в онлайн-системах. 63

Итоги ступени I 64

Ступень II. Базовые алгоритмы.. 65

Глава 9. Оценка скорости работы алгоритмов. 66

9.1. Эмпирическая скорость процессора. 66

9.2. Асимптотическая оценка. Основы. 68

9.3. Практическая применимость асимптотических оценок. 75

9.4. Библиотечные реализации алгоритмов и их скорость. 76

Глава 10. Наибольший общий делитель. Алгоритм Евклида. 80

10.1. Постановка задачи. 80

10.2. Тривиальный алгоритм. 80

10.3. Алгоритм Евклида. 80

10.4. Доказательство алгоритма Евклида. 81

10.5. Реализация алгоритма Евклида. 81

10.6. Время работы алгоритма Евклида. 83

10.7. Пример решения задачи. Сокращение дроби. 84

10.8. Пример решения задачи. Наименьшее общее кратное. 84

10.9. Пример решения задачи. НОД нескольких чисел. 86

10.10. Пример решения задачи. Увеличение НОД массива. 87

10.11. Упражнения для самостоятельного решения. 88

Глава 11. Простые задачи на учет асимптотики. 91

11.1. Пример решения задачи. Префиксы перестановки. 91

11.2. Пример решения задачи. Парковочные места. 92

Глава 12. Объединение одномерных отрезков. 95

12.1. Постановка задачи. 95

12.2. Алгоритм объединения отрезков. 95

12.3. Реализация алгоритма объединения отрезков. 95

12.4. Пример решения задачи. Часы приема. 96

12.5. Пример решения задачи. Стрельба по отрезкам. 97

12.6. Пример решения задачи. Многослойная покраска. 99

Глава 13. Метод двух указателей. 102

13.1. Пример решения задачи. Пары фиксированной суммы. 102

13.2. Пример решения задачи. Длиннейший подотрезок без повторов. 104

13.3. Пример решения задачи. Подотрезки со всеми числами. 105

13.4. Пример решения задачи. Трехцветный забор. 107

Глава 14. Двоичный поиск. 110

14.1. Базовая задача: поиск в упорядоченном массиве. 110

14.2. Алгоритм двоичного поиска. 110

14.3. Реализация алгоритма двоичного поиска. 111

14.4. Библиотечные реализации. 112

14.5. Пример решения задачи. Подсчет меньших чисел. 112

14.6. Пример решения задачи. Грузовой лифт в отеле. 114

14.7. Пример решения задачи. Дисплеи для смартфонов. 116

14.8. Пример решения задачи. Прыжки лягушки. 118

14.9. Пример решения задачи. Корень уравнения. 120

14.10. Прочие применения двоичного поиска. 123

Глава 15. Проверка на простоту и факторизация. 124

15.1. Определения. 124

15.2. Общие сведения о простых числах и о факторизации. 124

15.3. Проверка числа на простоту. Базовый алгоритм. 125

15.4. Факторизация числа. Базовый алгоритм. 126

15.5. Пример решения задачи. Подсчет числа делителей. 127

15.6. Пример решения задачи. Иррациональный портной. 128

15.7. Пример решения задачи. Произведения-квадраты. 131

15.8. Пример решения задачи. Запросы числа делителей. 133

Глава 16. Динамическое программирование. Основы.. 136

16.1. Пример решения задачи. Сумма однообразных чисел. 136

16.2. Пример решения задачи. Наидлиннейшая возрастающая подпоследовательность. 138

16.3. Пример решения задачи. Подмножество с заданной суммой. 140

16.4. Пример решения задачи. Минимальное подмножество с заданной суммой. 143

16.5. Пример решения задачи. Получение суммы монетами заданных номиналов. 145

16.6. Пример решения задачи. Задача о рюкзаке. 146

16.7. Пример решения задачи. Кладоискатель. 148

16.8. Пример решения задачи. Путь в матрице. 151

16.9. Пример решения задачи. Расстояние редактирования. 153

Глава 17. Задачи для самостоятельного решения. 156

17.1. Примеры задач. 156

17.2. Задачи в онлайн-системах. 161

Итоги ступени II 163

Ступень III. Расширение базового арсенала. 163

Глава 18. Техники предварительного подсчета на массивах. 164

18.1. Указатели до ближайших элементов. 164

18.2. Частичные суммы. 165

18.3. Указатели до ближайших меньших элементов. 166

18.4. Списки позиций. 167

18.5. Сжатие значений. 168

18.6. Пример решения задачи. Поиск начала слова. 168

18.7. Пример решения задачи. Два подотрезка заданной длины с максимальной суммой. 170

18.8. Пример решения задачи. Подсчет чисел в подотрезках. 172

18.9. Пример решения задачи. Подотрезок с максимальной суммой. 175

18.10. Пример решения задачи. Проекционная реклама. 180

18.11. Пример решения задачи. Подотрезок с максимальным средним
арифметическим. 182

18.12. Пример решения задачи. Сумма в прямоугольнике. 186

Глава 19. Графы. Обход в глубину. 190

19.1. Что такое граф. 190

19.2. Ориентированные и неориентированные графы. 191

19.3. Способы представления графов в компьютере. 191

19.4. Алгоритм обхода в глубину. 198

19.5. Реализация обхода в глубину. 199

19.6. Пример решения задачи. Проверка наличия пути. 202

19.7. Пример решения задачи. Конная прогулка. 204

19.8. Пример решения задачи. Проверка связности. 207

19.9. Пример решения задачи. Проверка двудольного графа. 209

19.10. Пример решения задачи. Проверка орграфа на ацикличность. 213

19.11. Пример решения задачи. Топологическая сортировка. 218

19.12. Пример решения задачи. Диаметр дерева  221

Глава 20. Графы. Обход в ширину. 223

20.1. Алгоритм обхода в ширину. 223

20.2. Свойства обхода в ширину. 224

20.3. Реализация обхода в ширину. 225

20.4. Пример решения задачи. Кластер компьютеров. 228

20.5. Пример решения задачи. Робот в лабиринте. 230

20.6. Пример решения задачи. Наводнение. 234

Глава 21. Решето Эратосфена. 236

21.1. Алгоритм решета Эратосфена. 236

21.2. Демонстрация работы алгоритма. 236

21.3. Доказательство корректности решета Эратосфена. 237

21.4. Время работы решета Эратосфена. 237

21.5. Базовые оптимизации решета Эратосфена. 238

21.6. Реализация решета Эратосфена. 239

21.7. Дальнейшие оптимизации решета Эратосфена. 240

21.8. Пример решения задачи. Подсчет простых чисел в отрезке. 243

Глава 22. Двоичное возведение в степень. 246

22.1. Ключевая идея. 246

22.2. Алгоритм двоичного возведения в степень. 247

22.3. Иллюстрация работы алгоритма. 247

22.4. Время работы двоичного возведения в степень. 248

22.5. Реализация двоичного возведения в степень. 248

22.6. Пример решения задачи. Последние цифры степени. 249

22.7. Пример решения задачи. Обратное по простому модулю. Малая теорема Ферма. 251

22.8. Пример решения задачи. Быстрое вычисление чисел Фибоначчи.
Двоичное возведение матриц в степень. 252

22.9. Пример решения задачи. Физический движок. 255

22.10. Пример решения задачи. Подсчет путей фиксированной длины. 261

Глава 23. Структуры данных. Дерево отрезков. 265

23.1. Базовый вариант. Дерево для минимумов. 265

23.2. Дерево отрезков для максимумов. 272

23.3. Дерево отрезков с запросами модификации. 273

23.4. Дерево отрезков для сумм. 274

23.5. Прочие виды операций в дереве отрезков. 274

23.6. Запросы обновления на отрезке. 275

23.7. Дальнейшие обобщения дерева отрезков. 279

23.8. Пример решения задачи. Наидлиннейшая возрастающая
подпоследовательность (быстрый вариант) 280

23.9. Пример решения задачи. Наименьший общий предок. 281

Глава 24. Задачи для самостоятельного решения. 284

24.1. Примеры задач. 284

24.2. Задачи в онлайн-системах. 288

Ступень IV. Разносторонняя подготовка. 291

Глава 25. Производительность ввода-вывода. 292

25.1. Производительность ввода-вывода в Python. 292

25.2. Производительность ввода-вывода в C++. 294

Глава 26. Графы. Алгоритм Дейкстры.. 298

26.1. Постановка задачи поиска кратчайших путей. 298

26.2. Пример. 298

26.3. Алгоритм Дейкстры. 299

26.4. Ограничения алгоритма Дейкстры. 300

26.5. Пример работы алгоритма Дейкстры. 300

26.6. Восстановление кратчайшего пути. 302

26.7. Доказательство алгоритма Дейкстры. 303

26.8. Квадратичная реализация алгоритма Дейкстры. 304

26.9. Алгоритм Дейкстры для разреженных графов. 308

26.10. Пример решения задачи. Оптимальный путь четной длины. 312

26.11. Пример решения задачи. Ребра кратчайших путей. 315

Глава 27. Графы. Компоненты сильной связности. 318

27.1. Определения. 318

27.2. Алгоритм поиска компонент сильной связности. 320

27.3. Доказательство алгоритма. 320

27.4. Демонстрация работы алгоритма. 323

27.5. Временная сложность алгоритма. 324

27.6. Реализация алгоритма. 324

27.7. Дополнительные свойства алгоритма. 327

27.8. Пример решения задачи. Железнодорожный вокзал. 327

27.9. Пример решения задачи. Задача умозаключенного. 328

27.10. Пример решения задачи. Сбор дани. 329

Глава 28. Работа с вещественными числами. 335

28.1. Формат чисел с плавающей запятой. 335

28.2. Проблемы чисел с плавающей запятой. 337

28.3. Приемы работы с числами с плавающей запятой. 342

Глава 29. Геометрия на плоскости. Основы.. 346

29.1. Расстояние между точками. 346

29.2. Косое произведение векторов. 347

29.3. Скалярное произведение векторов. 348

29.4. Площадь треугольника. 349

29.5. Направление поворота. Ориентированная площадь треугольника. 350

29.6. Площадь многоугольника. 351

29.7. Проверка точки на принадлежность прямой. 353

29.8. Проверка точки на принадлежность отрезку. 353

29.9. Проверка двух отрезков на пересечение. 355

29.10. Расстояние от точки до прямой. 358

29.11. Расстояние от точки до отрезка. 359

29.12. Точка пересечения двух прямых. 362

29.13. Точка пересечения двух отрезков. 365

29.14. Матрица поворота. 368

29.15. Пример решения задачи. Проверка окружностей на пересечение. 369

29.16. Пример решения задачи. Пересечение окружности и прямой. 371

29.17. Пример решения задачи. Сортировка точек по углу. 375

Глава 30. Расширенный алгоритм Евклида. 380

30.1. Алгоритм. 380

30.2. Доказательство. 380

30.3. Реализация расширенного алгоритма Евклида. 381

30.4. Пример решения задачи. Прыжки вперед и назад. 382

30.5. Пример решения задачи. Линейное диофантово уравнение с двумя переменными. 384

30.6. Пример решения задачи. Обратное по составному модулю.. 386

Глава 31. Задачи для самостоятельного решения. 389

31.1. Примеры задач. 389

Заключение. 395

Методики решения задач. 396

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

Послесловие. 398

Приложение. Решения задач. 399

Задачи из главы 8. 399

Задачи из главы 10. 401

Задачи из главы 17. 402

Задачи из главы 24. 406

Задачи из главы 31. 411

Предметный указатель. 415

Максим-Иванов

Максим Иванов профессионально занимается системным программированием, долгое время увлекается изучением Windows API, подробно исследовал ядро Windows. Несколько лет участвовал в олимпиадах по программированию, серебряный призёр чемпионата мира 2011 г. в составе команды Саратовского государственного университета. Автор сайта об алгоритмах https://e-maxx.ru, на основе которого написана эта книга.

Опубликовано

Представляем новинку: “Надежный Python”

Надежный Python

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

Для программистов

Пишем чистый код, который удобно поддерживать

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

Прочитав книгу Вы:

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

С помощью этих советов и приемов вы сможете писать более понятный и удобный для сопровождения код.

Книга идеально подходит для

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

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

Патрик Виафоре

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

Книгу “Надежный Python” можно купить со скидкой в интернет-магазине издательства “БХВ“.

Введение………………………………………………………………………………………………… 11

Для кого предназначена книга?……………………………………………………………………………………………….. 12

О чем эта книга?…………………………………………………………………………………………………………………………. 13

Условные обозначения……………………………………………………………………………………………………………… 15

Использование примеров кода…………………………………………………………………………………………………. 15

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

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

Глава 1. Введение в надежный Python……………………………………………………. 19

Надежность кодовой базы………………………………………………………………………………………………………… 19

Почему важна надежность?…………………………………………………………………………………………… 22

Обмен полезной информацией………………………………………………………………………………………………….. 23

Асинхронное взаимодействие……………………………………………………………………………………….. 26

Примеры понятного кода на Python…………………………………………………………………………………………. 29

Коллекции……………………………………………………………………………………………………………………….. 29

Итерации…………………………………………………………………………………………………………………………. 32

Принцип наименьшего удивления…………………………………………………………………………………. 34

Резюме…………………………………………………………………………………………………………………………………………. 35

Часть I. Аннотации типов…………………………………………………………… 37

Глава 2. Введение в типы Python……………………………………………………………. 39

Что такое тип?……………………………………………………………………………………………………………………………. 39

Машинное представление……………………………………………………………………………………………… 39

Семантическое представление……………………………………………………………………………………… 41

Системы типов……………………………………………………………………………………………………………………………. 44

Сильная и слабая типизации…………………………………………………………………………………………. 44

Динамическая и статическая типизации………………………………………………………………………. 45

Неявная (утиная) типизация………………………………………………………………………………………….. 46

Резюме…………………………………………………………………………………………………………………………………………. 48

Глава 3. Аннотации типов……………………………………………………………………… 49

Что такое аннотации типов?…………………………………………………………………………………………………….. 49

Использование аннотаций типов……………………………………………………………………………………………… 53

Автодополнение……………………………………………………………………………………………………………… 53

Проверка типов……………………………………………………………………………………………………………….. 53

Примеры найденных ошибок………………………………………………………………………………………… 55

Когда добавлять аннотации типа…………………………………………………………………………………………….. 57

Резюме…………………………………………………………………………………………………………………………………………. 57

Глава 4. Ограничивающие типы……………………………………………………………. 59

Аннотация Optional…………………………………………………………………………………………………………………… 59

Аннотация Union……………………………………………………………………………………………………………………….. 65

Тип-произведение и тип-сумма……………………………………………………………………………………… 67

Аннотация Literal………………………………………………………………………………………………………………………. 69

Аннотация Annotated…………………………………………………………………………………………………………………. 70

Аннотация NewType…………………………………………………………………………………………………………………… 70

Аннотация Final…………………………………………………………………………………………………………………………. 73

Резюме…………………………………………………………………………………………………………………………………………. 74

Глава 5. Коллекции……………………………………………………………………………….. 75

Аннотирование коллекций………………………………………………………………………………………………………… 75

Однородные и разнородные коллекции…………………………………………………………………………………… 76

Аннотация TypedDict…………………………………………………………………………………………………………………. 80

Создание новых типов коллекций……………………………………………………………………………………………. 82

Дженерики……………………………………………………………………………………………………………………….. 83

Изменение существующих типов………………………………………………………………………………….. 85

Так же просто, как ABC…………………………………………………………………………………………………. 88

Резюме…………………………………………………………………………………………………………………………………………. 90

Глава 6. Настройка проверки типов………………………………………………………. 91

Инструмент проверки типов mypy…………………………………………………………………………………………… 91

Параметры конфигурации……………………………………………………………………………………………… 92

Поиск динамической типизации……………………………………………………………………………. 93

Нетипизированные функции…………………………………………………………………………………. 94

Отслеживание None/Optional………………………………………………………………………………… 94

Отчеты mypy…………………………………………………………………………………………………………………… 95

Ускорение mypy……………………………………………………………………………………………………………… 96

Другие инструменты проверки типов………………………………………………………………………………………. 97

Pyre…………………………………………………………………………………………………………………………………… 97

Запросы к кодовой базе…………………………………………………………………………………………. 98

Pysa………………………………………………………………………………………………………………………… 100

Pyright…………………………………………………………………………………………………………………………….. 103

Резюме………………………………………………………………………………………………………………………………………. 105

Глава 7. Внедрение проверки типов……………………………………………………… 106

Поиск компромиссов……………………………………………………………………………………………………………….. 107

Быстрое получение выгоды……………………………………………………………………………………………………. 108

Поиск слабых мест……………………………………………………………………………………………………….. 108

Стратегические фрагменты кода………………………………………………………………………………… 109

Аннотирование только нового кода…………………………………………………………………… 109

Аннотирование снизу вверх………………………………………………………………………………… 109

Аннотирование основной бизнес-логики…………………………………………………………… 110

Аннотирование часто меняющегося кода………………………………………………………….. 110

Аннотирование сложного кода…………………………………………………………………………… 110

Использование инструментов……………………………………………………………………………………… 110

MonkeyType………………………………………………………………………………………………………….. 112

Pytype…………………………………………………………………………………………………………………….. 116

Резюме………………………………………………………………………………………………………………………………………. 117

Часть II. Определение ваших собственных типов…………. 119

Глава 8. Пользовательские типы: перечисления………………………………….. 121

Пользовательские типы…………………………………………………………………………………………………………… 121

Перечисления…………………………………………………………………………………………………………………………… 122

Тип Enum……………………………………………………………………………………………………………………….. 124

Когда не надо их использовать…………………………………………………………………………………… 125

Дополнительные возможности……………………………………………………………………………………………….. 126

Автоматические значения……………………………………………………………………………………………. 126

Тип Flag…………………………………………………………………………………………………………………………. 127

Целочисленные перечисления…………………………………………………………………………………….. 129

Уникальные значения…………………………………………………………………………………………………… 130

Резюме………………………………………………………………………………………………………………………………………. 131

Глава 9. Пользовательские типы: классы данных……………………………….. 132

Примеры классов данных……………………………………………………………………………………………………….. 132

Использование классов данных……………………………………………………………………………………………… 136

Строковые представления…………………………………………………………………………………………… 136

Равенство………………………………………………………………………………………………………………………. 137

Реляционное сравнение……………………………………………………………………………………………….. 138

Неизменяемость……………………………………………………………………………………………………………. 139

Сравнение с другими типами………………………………………………………………………………………………….. 141

Классы данных и словари…………………………………………………………………………………………… 141

Классы данных и TypedDict………………………………………………………………………………………… 142

Классы данных и namedtuple………………………………………………………………………………………. 142

Резюме………………………………………………………………………………………………………………………………………. 143

Глава 10. Пользовательские типы: классы…………………………………………… 144

Строение класса………………………………………………………………………………………………………………………. 144

Конструктор………………………………………………………………………………………………………………….. 145

Инварианты……………………………………………………………………………………………………………………………… 146

Нарушение инвариантов……………………………………………………………………………………………… 148

Зачем нужны инварианты……………………………………………………………………………………………. 149

Информативные инварианты………………………………………………………………………………………. 151

Для пользователей класса…………………………………………………………………………………… 152

При сопровождении кода…………………………………………………………………………………….. 153

Инкапсуляция и поддержка инвариантов……………………………………………………………………………… 155

Инкапсуляция……………………………………………………………………………………………………………….. 155

Доступ к данным…………………………………………………………………………………………………………… 155

Работа с данными…………………………………………………………………………………………………………. 158

Резюме………………………………………………………………………………………………………………………………………. 160

Глава 11. Определение своих интерфейсов…………………………………………… 162

Проектирование естественного интерфейса…………………………………………………………………………. 163

Думай как пользователь………………………………………………………………………………………………. 164

Разработка через тестирование………………………………………………………………………….. 164

Разработка через README…………………………………………………………………………………. 165

Юзабилити-тестирование……………………………………………………………………………………. 166

Естественные взаимодействия………………………………………………………………………………………………… 167

Естественные интерфейсы в действии………………………………………………………………………… 167

Магические методы……………………………………………………………………………………………………… 173

Контекстные менеджеры……………………………………………………………………………………………… 175

Резюме………………………………………………………………………………………………………………………………………. 177

Глава 12. Создание подтипов……………………………………………………………….. 178

Наследование…………………………………………………………………………………………………………………………… 178

Взаимозаменяемость……………………………………………………………………………………………………………….. 183

Рекомендации по проектированию………………………………………………………………………………………… 188

Композиция…………………………………………………………………………………………………………………… 189

Резюме………………………………………………………………………………………………………………………………………. 191

Глава 13. Протоколы……………………………………………………………………………. 193

Структурная и номинальная типизации………………………………………………………………………………… 193

Пустой тип и Any…………………………………………………………………………………………………………… 195

Использование Union…………………………………………………………………………………………………… 195

Использование наследования……………………………………………………………………………………… 196

Использование миксинов……………………………………………………………………………………………… 197

Протоколы………………………………………………………………………………………………………………………………… 198

Создание протокола…………………………………………………………………………………………………….. 199

Расширенное использование………………………………………………………………………………………………….. 200

Составные протоколы………………………………………………………………………………………………….. 200

Протоколы времени выполнения………………………………………………………………………………… 201

Протоколы для модулей………………………………………………………………………………………………. 202

Резюме………………………………………………………………………………………………………………………………………. 203

Глава 14. Проверки во время выполнения с помощью pydantic……………. 204

Динамическая конфигурация………………………………………………………………………………………………….. 204

Библиотека pydantic………………………………………………………………………………………………………………… 210

Валидаторы………………………………………………………………………………………………………………….. 212

Валидация и парсинг……………………………………………………………………………………………………. 215

Резюме………………………………………………………………………………………………………………………………………. 216

Часть III. Расширяемый код……………………………………………………… 219

Глава 15. Расширяемость……………………………………………………………………… 221

Что такое расширяемость?……………………………………………………………………………………………………… 221

Реструктуризация кода………………………………………………………………………………………………… 223

Принцип открытости/закрытости…………………………………………………………………………………………… 227

Поиск нарушений принципа………………………………………………………………………………………… 228

Недостатки OCP……………………………………………………………………………………………………………. 229

Резюме………………………………………………………………………………………………………………………………………. 230

Глава 16. Зависимости…………………………………………………………………………. 231

Взаимосвязи……………………………………………………………………………………………………………………………… 232

Типы зависимостей………………………………………………………………………………………………………………….. 234

Физические зависимости……………………………………………………………………………………………… 234

Логические зависимости………………………………………………………………………………………………. 238

Временные зависимости………………………………………………………………………………………………. 240

Визуализация зависимостей…………………………………………………………………………………………………… 241

Визуализация пакетов………………………………………………………………………………………………….. 242

Визуализация импорта………………………………………………………………………………………………… 243

Визуализация вызовов функций………………………………………………………………………………….. 243

Интерпретация графа зависимостей…………………………………………………………………………… 245

Резюме………………………………………………………………………………………………………………………………………. 246

Глава 17. Компонуемость…………………………………………………………………….. 248

Что такое компонуемость?……………………………………………………………………………………………………… 248

Разделение политик и механизмов…………………………………………………………………………………………. 252

Компонуемость в меньшем масштабе……………………………………………………………………………………. 255

Компонуемые функции………………………………………………………………………………………………… 255

Декораторы…………………………………………………………………………………………………………… 256

Компонуемые алгоритмы…………………………………………………………………………………………….. 259

Резюме………………………………………………………………………………………………………………………………………. 262

Глава 18. Событийно-ориентированная архитектура…………………………… 263

Как это работает……………………………………………………………………………………………………………………… 263

Недостатки……………………………………………………………………………………………………………………. 264

Простые события……………………………………………………………………………………………………………………… 266

Использование брокера сообщений……………………………………………………………………………. 266

Шаблон наблюдателя………………………………………………………………………………………………….. 268

Поток событий…………………………………………………………………………………………………………………………. 270

Резюме………………………………………………………………………………………………………………………………………. 273

Глава 19. Подключаемый код………………………………………………………………. 274

Шаблонный метод…………………………………………………………………………………………………………………… 275

Шаблон стратегии…………………………………………………………………………………………………………………… 278

Архитектура плагинов…………………………………………………………………………………………………………….. 279

Резюме………………………………………………………………………………………………………………………………………. 283

Часть IV. Ваша страховочная сетка……………………………………… 285

Глава 20. Статический анализ……………………………………………………………… 287

Линтинг…………………………………………………………………………………………………………………………………….. 287

Написание собственного плагина для Pylint……………………………………………………………… 289

Разбор плагина……………………………………………………………………………………………………………… 291

Другие статические анализаторы………………………………………………………………………………………….. 293

Проверки сложности…………………………………………………………………………………………………….. 294

Цикломатическая сложность Маккейба…………………………………………………………….. 294

Проверка отступов……………………………………………………………………………………………….. 296

Анализ безопасности……………………………………………………………………………………………………. 297

Утечка секретных данных…………………………………………………………………………………… 297

Проверка уязвимостей…………………………………………………………………………………………. 297

Резюме………………………………………………………………………………………………………………………………………. 298

Глава 21. Стратегия тестирования……………………………………………………….. 299

Определение вашей стратегии тестирования……………………………………………………………………….. 299

Что такое тесты?…………………………………………………………………………………………………………… 300

Пирамида тестирования………………………………………………………………………………………. 302

Снижение стоимости тестирования……………………………………………………………………………………….. 304

AAA-тестирование……………………………………………………………………………………………………….. 304

Arrange (настройка предусловий)……………………………………………………………………….. 305

Annihilate (очистка ресурсов)……………………………………………………………………………… 308

Act (действие)……………………………………………………………………………………………………….. 310

Assert (утверждение)…………………………………………………………………………………………….. 311

Резюме………………………………………………………………………………………………………………………………………. 314

Глава 22. Приемочное тестирование…………………………………………………….. 315

Разработка через поведение (BDD)………………………………………………………………………………………… 316

Язык Gherkin………………………………………………………………………………………………………………….. 316

Исполняемые спецификации……………………………………………………………………………………….. 318

Дополнительные возможности behave…………………………………………………………………………………… 321

Параметризованные шаги……………………………………………………………………………………………. 321

Требования, составленные в виде таблиц………………………………………………………………….. 321

Регулярные выражения………………………………………………………………………………………………… 322

Настройка жизненного цикла теста……………………………………………………………………………. 322

Использование тегов для выборочного запуска тестов……………………………………………. 323

Генерация отчетов……………………………………………………………………………………………………….. 323

Резюме………………………………………………………………………………………………………………………………………. 325

Глава 23. Тестирование на основе свойств…………………………………………… 326

Тестирование с помощью Hypothesis…………………………………………………………………………………….. 326

Магия Hypothesis………………………………………………………………………………………………………….. 330

Отличия от традиционных тестов………………………………………………………………………………. 331

Дополнительные возможности Hypothesis……………………………………………………………………………. 332

Стратегии Hypothesis…………………………………………………………………………………………………… 332

Генерирование алгоритмов…………………………………………………………………………………………. 333

Резюме………………………………………………………………………………………………………………………………………. 337

Глава 24. Мутационное тестирование………………………………………………….. 338

Что такое мутационное тестирование?…………………………………………………………………………………. 338

Использование mutmut…………………………………………………………………………………………………………….. 341

Исправление мутантов…………………………………………………………………………………………………. 343

Отчеты о тестировании………………………………………………………………………………………………… 343

Внедрение мутационного тестирования……………………………………………………………………………….. 344

Проблема с показателем покрытия (и другими метриками)…………………………………….. 346

Резюме………………………………………………………………………………………………………………………………………. 347