Жемчужины программирования

Решил освежить память по алгоритмам и структурам данных. Недавно прочитал книгу Джона Бентли "Programming Pearls". Многие в интернете советуют ее как одну из значимых работ.

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

Узнал пару новых алгоритмов. Например, maximum subarray problem, и array rotation, без использования дополнительной памяти. Хотя в целом ничего выходящего за рамки стандартного курса по computer science нет. В этом плане другие книги, например, Скиены или Седжвика (чью книгу автор советует к прочтению) дают больше информации. Например, в книге не уделяется внимания хэш таблицам. В основном упор делается на работу с массивами, много бинарного поиска и сортировок.

Книга больше всего нацелена как материал для практикующих программистов. Хоть и написанная во времена, когда под миникомпьютером подразумевался комод, а под суперкомпьютером - шкаф, советы актуальны и сегодня.

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

Удивил тот факт, что программисты в те времена не были сильно подкованы в алгоритмах. В одной из глав рассказывается, что только 10% программистов смогли написать бинарный поиск с первого раза без багов. Пришлось проверить себя самого (пронесло, справился сразу). Также понравилась история решения maximum subarray problem - сформулированная в 1977-году и с решением за логарифмическое время, была оптимизирована лишь в 1984 статистком сходу алгоритмом за линейное время.

В целом, книга понравилась.