Записки программиста

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

Алгоритмы и структуры данных
Никлаус Вирт

Классическая книга об алгоритмах и структурах данных 1986-го года. Переведена на русский язык в 1989-м. Никогда не читал. Вот решил наверстать упущенное.

Здесь описываются традиционные структуры данных и алгоритмы над ними — списки, АВЛ-деревья, Б-деревья и хэш-таблицы. Еще из книги вы узнаете, как рисовать кривые Гильберта и Серпинского, а также решать различные шахматные задачи. Материал по нынешним меркам довольно поверхностный. В частности, не рассматриваются skip lists, красно-черные деревья, Б+деревья, R-деревья или алгоритмы на графах.

Примеры приводятся на языке Modula-2. В сущности, это диалект Паскаля, поэтому проблем с пониманием возникать не должно. Код на Modula-2 можно рассматривать, как строго определенный псевдокод. Эффективность алгоритмов автор сравнивает опытным путем на ПЭВМ Lilith своей же разработки.

«Алгоритмы и структуры данных» написана простым и понятным языком. В частности, здесь нет чрезмерного погружения в анализ асимптотической сложности. Это хорошая вводная книга по алгоритмам.

Построение компиляторов
Никлаус Вирт

Книга того же автора. Рассказывающая о создании компилятора для подмножества языка Оберон. Последний представляет собой диалект языка Паскаль.

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

Код генерируется для несуществующей RISC-машины. Он может быть запущен в соответствующем интерпретаторе. Полный исходный код компилятора занимает всего лишь 20 страниц.

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

Programming with OpenSCAD
Justin Gohde, Marius Kintel

Книга 2021-го года о создании моделей в OpenSCAD и 3D-печати. Характерно, что Marius Kintel является основным автором OpenSCAD.

Даже бывалые пользователи OpenSCAD могут узнать из «Programming with OpenSCAD» что-то новое. Помимо прочего, рассказывается о возможности импортировать и править файлы STL, операциях hull() и minkowski(), отладке при помощи echo(), окрашивании модели в разные цвета при помощи color(), а также разбиении крупных моделей на несколько .scad файлов.

Читается легко и интересно. Рекомендую.

Почему мы не проваливаемся сквозь пол
Дж. Гордон

Широко известная в узких кругах научно-популярная книга о прочности материалов и конструкций.

Данная тема представляет интерес не только для конструкторов мостов, самолетов и подводных лодок, как может показаться на первый вгяд. Все это находит применение и в широко распространенных в наши дни хобби, не исключая 3D-печати и любительского радио. Помимо прочего, наглядно объясняется, что такое напряжение, деформация и модуль Юнга; консоли и балки; растяжение, сжатие и изгиб; в чем состоит закон Гука; чем прочность отличается от жесткости; а также откуда берутся вязкость и хрупкость.

Фактически, это книга по сопромату, которая читается, как роман.

Конструкции, или почему не ломаются вещи
Дж. Гордон

Более поздняя книга того же автора.

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

В общем, это обновленная и расширенная версия «Почему мы не проваливаемся сквозь пол». Книга прекрасна. Рекомендую.

The Art of Writing Efficient Programs
Fedor G. Pikus

Книга 2021-го года о том, как писать эффективные программы на C++. Автор делает оговорку, что это не книга про алгоритмы. Используемые алгоритмы зависят от решаемых задач, а задачи бывают разными. Правда, далее по тексту все же разбираются некоторые lock-free алгоритмы.

Здесь рассказывается про такие инструменты, как perf, Google Profiler, Google Benchmark, LLVM Machine Code Analyzer и Undefined Behavior Sanitizer (UBSan). Объясняется, что такое спекулятивное исполнение, зачем компиляторы разматывают циклы, что такое cache line и move semantics, как писать многопоточный код на C++ (включая корутины из C++20), а также как работает уязвимость Spectre. Ассемблерные листинги приводятся для x86/x64.

В целом, книга хорошая, но показалась мне неполной. Ей больше подошло бы название «как писать быстрый код на C/C++», а не «как писать эффективные программы». Здесь вы не найдете ни слова про eBPF и bpftrace, ровно как и ни одного флеймграфа. Тема поиска бутылочного горлышка в большой программе не раскрыта. Ровно как и тема оптимизации программы по объему используемой памяти или энергопотреблению. Борьба с lock contention, работа с сетью или жестким диском не рассматриваются.

Сигналы, помехи, ошибки
Лев Матвеевич Финк

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

Не обходятся стороной и эмоциональные аспекты, такие, как желание людей прославиться. Есть и обратные примеры. Так интуитивно кажется, что теорема Агеева противоречит теореме Найквиста-Шеннона (она же теорема Котельникова). Но в действительности никакого противоречия нет.

Автор приводит немало математических выкладок, при помощи которых получается ошибочный результат. В стиле доказательства того, что 2 + 2 = 5, только применительно к теории связи. Затем разбирается суть сделанной ошибки. Такую подачу особенно оценят читатели с математическим складом ума.

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

A Common-Sense Guide to Data Structures and Algorithms, Second Edition
Jay Wengrow

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

Разные главы содержат примеры на разных языках — Python, Ruby и JavaScript. Как по мне, стоило выбрать какой-то один. Разбирается работа быстрой сортировки, однако сортировка слиянием или пирамидальная сортировка, увы, обходятся стороной. AVL- или RB-деревья не рассматриваются. Из алгоритмов на графах приводятся только поиск в ширину, в глубину, а также алгоритма Дейкстры. К ним стоило добавить хотя бы двунаправленный поиск и алгоритм A*.

В целом, это вполне себе нормальная вводная книга по алгоритмам. Хотелось бы, чтобы у меня такая была в старших классах. Но если вы давно программируете, то едва ли узнаете из «A Common-Sense Guide…» много нового.

Beginning Python Games Development With PyGame, Second Edition
Harrison Kinsley, Will McGugan

Книга об использовании PyGame. Это Python-библиотека для создания как игр, так и мультимедийных приложений. Примечательна простым и понятным интерфейсом, что зачастую делает ее более привлекательной, чем Unity или Unreal Engine.

Первые две главы посвящены основам Python. Их можно смело пропустить, если вы уже знакомы с языком. Далее объясняются работа с 2D графикой, анимацией, звуком, вводом-выводом, а также имитация 3D-эффектов. В общем, есть все для начала работы с PyGame. Если же чего-то не нашлось, то доступна документация.

Также приводятся примеры использования OpenGL из Python, но в устаревшем immediate режиме (glBegin, glEnd, …) и без шейдеров. По моему субъективному мнению, данный материал здесь лишний.

Сетевое программирование. От основ до приложений
Артем Нечипорук, Алексей Баринов

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

Традиционно рассказывается о модели OSI. Объясняется, что такое сокеты. Перечисляются различия в реализации сокетов в Linux, Windows и BSD системах. Приводятся примеры использования TCP-, UDP- и RAW-сокетов. Особенно понравилась глава, разбирающая устройство сетевого стека в ядре Linux. Windows тоже не обделили вниманием. Тонкостям программирования под Windows уделено ~30% книги.

Также здесь подробно описаны API для работы с сетевыми интерфейсами и сокеты Netlink. Разбирается пример создания TAP-интерфейса. Рассматриваются способы обработки сетевых пакетов с исключением стека ядра (kernel bypass). Подробно описаны ProcFS и SysFS. Через последние можно получить доступ к настройкам сетевых протоколов.

В книге использованы языки C++, Go и Python. Помимо прочего, приводятся реализации прокси-серверов и пример использования libpcap. Все исходники доступны на GitHub.

Книга хороша, а все причастные — молодцы. С нетерпением жду продолжения.

Кроме перечисленного я начинал читать «Handbook of Filter Synthesis», автор Anatol I. Zverev. Чтобы ее понять, нужно очень хорошо разбирается в математике. Вынужден констатировать, что для меня эта книга оказалась сложновата. Быть может, вернусь к ней позднее.

Метки: Литература.