Книга Уоррена «Алгоритмические трюки для программистов»

algПрочитал недавно книгу Уоррена «Алгоритмические трюки для программистов» (в оригинале она называется «Hacker’s Delight»), любопытная оказалась книжка, хотя алгоритмы, рассмотренные в ней, довольно специфические.

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

Многие алгоритмы явно предназначены для того, чтобы их реализовали на ассемблере, причем иногда для процессоров, более редких, чем x86 (например, часто упоминаются процессоры IBM, а иногда опоминаются и древние компьютеры еще 60-ых годов прошлого века). Автор пишет, что многие примеры из книги могут пригодиться тем, кто создает компиляторы. Для примера приведу описание некоторых задач, разбираемых автором: как обнулить крайний справа единичный бит (01011000 -> 01010000), округление к кратному степени двойки, подсчет единичных битов в слове, поиск строки битов и тому подобные. Почти для каждого алгоритма автор пытается оценить количество необходимых тактов процессора, иногда с учетом распараллеливания.

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

Ближе к концу книги есть глава, посвященная системам счисления с необычными основаниями, такие как -2, -1+i, -1-i. Такие системы счисления никто в здравом уме применять не будет, но почитать про них все-равно интересно.

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

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

Книгу можно рассматривать как небольшой сборник рецептов про битовые операции. Книга издавалась несколько раз, последнее издание 2007 года.

В электронном виде найти ее можно без проблем.

PS. Вы можете подписаться на новости сайта через RSS, Группу Вконтакте или Канал в Telegram.

Пожалуйста, оцените запись

УжасноПлохоТак себеХорошоОтлично (Количество голосов: 5, средняя оценка: 4,40)
Загрузка...

Leave a comment

Subscribe without commenting