«Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих» скачать fb2, rtf, epub, pdf, txt книгу Адитья Бхаргава

Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих от Бхаргава А. Эта книга рекомендована Яндекс Практикум при подготовке к алгоритмическому собеседованию. Сам автор указывает, что книга для самоучек, студентов, выпускников и тех, у кого программирование не является основным профилем.

Мое впечатление неоднозначно. С одной стороны, до сего момента я не встречал описания динамического программирования, поиска кратчайшего пути в графе по алгоритму Дейкстры и использование K ближайших соседей для классификации и аппроксимации (возможно, все это есть в 4^м или последующих томах Кнута, но в магазине они мне не встречались). С другой стороны, описания и примеры, приведенные в книге, таковы, что практической пользы не представляют. Описания очень поверхностны, примеры нарочно примитивны, код в половине случаев не приведен. Но даже там где есть код, он нарочито упрощен под конкретный пример и на практике бесполезен.

Казалось бы, есть масса книг — каталогов шаблонов. Они реально полезны и новичку и профессионалу. Эта книга не из их числа. Но, видимо, это и не было целью. Напоминает научно-популярные книги издававшиеся в СССР: простым языком рассказывает о сложных вещах, прививает у читателя интерес к теме, расширяет кругозор. Не более. Но тоже важно.

Вернемся к Яндекс Практикум и их рекомендации. Если алгоритмы так важны, то почему именно эта книга? Есть масса других, где и алгоритмов больше и разобраны они так, что бери да пользуй. Например, классический труд Д. Э. Кнута Искусство программирования. Да, рисунки в детском стиле в Грокаем алгоритмы забавны. Но иллюстрации в Искусство программирования полезны для понимания. Разве это не важнее, если уж кандидата посылают на алгоритмическое собеседование?

Если алгоритмы так важны с точки зрения Яндекс Практикум, то почему они советуют именно Грокаем алгоритмы, где приведены далеко не самые эффективные реализации? К примеру, сортировка выбором (в ГА) создает новый массив, который, к тому же, динамически растет. У Кнута приведен алгоритм сортировки выбором с обменом (5.2.3), не требующий дополнительной памяти ни на копию, ни на копию копии при динамическом росте.

На сколько по полочкам у Кнута разобрана работа стека, на столько же сумбурно про это рассказано в Грокаем алгоритмы.

А ведь это база для рекурсивных алгоритмов. Про то, что стек может быть конечного и даже малого размера в ГА не сказано. Лишь упомянуто вскользь, что могут быть высокие затраты памяти. А ведь, как правильно указано в 1^м томе «Информатика. Основополагающее введение» от Манфреда Броя, при каскадной рекурсии «вызовы лавинообразно ведут к экспоненциальному нарастанию возникающих рекурсивных вызовов («каскад вызовов»)». И именно такой вариант быстрой сортировки расщеплением приведен в ГА. Также автор не стесняется склеивать три массива на каждой итерации. Если важна эффективность, как уверяет Яндекс Практикум, то быструю сортировку надо смотреть не в ГА, а снова у Кнута, где алгоритм обменной сортировки с разделением (5.2.2) не требует ни дополнительной памяти, ни склеивания половин.

Не менее интересно в ГА разобраны хеш-таблицы и хеш-функции, о которых нам «никогда не придется беспокоиться» ибо об этом уже побеспокоились «пожилые бородатые умники, сидящие в полутемных комнатах» (цитата из книги). Ладно, если бы это было просто безобидно, но автор рекомендует использовать SHA при реализации своих хеш-таблиц. И где будет эффективность, о которой говорит Яндекс Практикум? Для сравнения, если просто почитать 6.4 в т.3 Кнута, то станет по крайней мере понятно почему до Java 7 стандартный шаблон сгенерированного hashCode() выглядел следующим образом:

public int hashCode() {
    int result = target.hashCode();
    result = 31 * result   (optimal ? 1 : 0);
    result = 31 * result   parent.hashCode();
    return result;
}

Поиска в ширину и жадных алгоритмов в первых трех томах Кнута нет. Но их описание в ГА можно сравнить с описанием в «Искусственный интеллект. Стратегии и методы решения сложных проблем» от Джорджа Ф. Люгер. В ГА более длинно и более разжёвано, а потому и более понятно.

Алгоритма Дейкстры для поиска кратчайшего пути, равно как и динамического программирования в моей библиотеке ранее не было. Однако глубина изложения и примитивность примеров в ГА не позволяют их сходу использовать на практике. Автор запросто опускает начальные условия и приводит код под конкретный пример. Все это безобразие венчает «а это моя формула»:

Вместо объяснения как он пришел к данной «формуле» или в чем ее физический смысл, дабы читатель мог использовать схожий подход в своей практике, автор успокаивает: «Если у вас голова идет кругом, не огорчайтесь. Это сложный материал». И по алгоритму Дейкстры, и по динамическому программированию я бы рекомендовал дополнительно почитать https://ru.algorithmica.org. Так оно будет гораздо понятнее, чем только после прочтения ГА.

На методе K ближайших соседей автор ГА либо устал, либо сам толком метод не освоил. Об этом можно судить и по корню в Евклидовой метрике, и по отсутствию нормализации. Если у нас миллионы точек в многомерном пространстве, то найти по запросу таким образом 5 соседей на практике вряд ли получится, особенно, если запросы приходят в параллель. Книга не упоминает, что все это очень дорого и по памяти, и по времени. А ведь Яндекс Практикум говорит именно об эффективности. Чтобы более полно ознакомиться с методом K ближайших соседей и понять аспекты его практического применения, вариации и альтернативы, я бы рекомендовал описание в онлайн-учебнике по машинному обучению от Школы анализа данных.

Все, что идет в книге далее, несерьезно рассматривать более чем как see also.

Что можно сказать резюмируя? В принципе, выполнение упражнений полезно (как минимум, я снова убедился, что писать на Java проще, чем на C ). Также опытный разработчик может встретить какие-то новые вещи — это тоже всегда полезно. Не программисты и начинающие разработчики наверняка найдут книгу легкой в чтении и увлекательной. И это хорошо. Но вообще хотелось бы каталога алгоритмов наподобие GoF, EIP, Software Architecture Patterns and Designing Distributed Systems.

Примеры выполнения упражнений