Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих от Бхаргава А. Эта книга рекомендована Яндекс Практикум при подготовке к алгоритмическому собеседованию. Сам автор указывает, что книга для самоучек, студентов, выпускников и тех, у кого программирование не является основным профилем.
Мое впечатление неоднозначно. С одной стороны, до сего момента я не встречал описания динамического программирования, поиска кратчайшего пути в графе по алгоритму Дейкстры и использование 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.
Комментарии (22)
danilovmy
05.05.2022 01:50+2Уже обсуждалась эта книга неоднократно на хабре. Мнения 50/50. Я бы не назвал это "Профессиональной литературой". Подтвержу слова статьи, что во второй половине книги автор перестает "грокать" и начинает "плавать". Это наводит на мысль, что глубоко изучать сложные алгоритмы все равно придется по другой литературе.
@nikolaysmartynovты пишешь "хотелось бы каталога алгоритмов". На мой взгляд монография Donald E. Knuth "The Art of Computer Programming" остается наилучшим вариантом. Другой вопрос, что это не публицистика, а научный труд, который читать - труд не меньший :)
В своем комментарии https://habr.com/ru/post/439576/comments/#comment_19802200 я отмечал, что иначально Grokking Algorithms была выпущена с большим количеством ошибок, и перевод ситуацию только ухудшил. Некоторые исправления автор разместил тут: https://adit.io/errata.html , я нашел еще несколько ошибок, сообщил автору, но в errata правки пока не появились.
nikolaysmartynov Автор
05.05.2022 10:48ты пишешь "хотелось бы каталога алгоритмов". На мой взгляд монография Donald E. Knuth "The Art of Computer Programming" остается наилучшим вариантом.
К сожалению на русском можно купить только первые три тома. Четвертый том не найти. Остальные и вовсе не переводились. А похоже именно там комбинаторика, статистические методы, NP-полные задачи и т.п. По крайней мере этого нет в первых трех томах. Можно конечно и в электронном, и на английском почитать, но это не совсем то.
risentveber
05.05.2022 13:40Для тех, кто действительно будет это читать, выучить английский - не самая большая проблема, для всех остальных - это лишь будет макулатура на полке.
wibbtwo
05.05.2022 14:07Так ведь, четвертый том Кнут таки и не закончил (и, наверное, уже не закончит никогда). А "остальных" и вовсе не существует в природе.
T1murgar88
05.05.2022 09:09А в скиллбоксе не знаешь какие книги рекомендуют? В списке литературы для поступления в шад, не видел такой книги.
nikolaysmartynov Автор
05.05.2022 11:47Не могу сказать, ибо не знаю. Но видимо, там рекомендуют какую-то более серьезную литературу. Возможно, что-то что перечислил HotkeyM или SibProgrammer.
T1murgar88
05.05.2022 11:53Это был сарказм, просто яп это же просто курсы для свитчеров, и относится к таким курсам , как к авторитетному источнику я бы не стал.
Samummm
05.05.2022 09:10+3Книжка "Грокаем алгоритмы" - точно не учебник. Простоватая, мне не зашла. Как-то все скользко, мутно. Все книги про алгоритмы делятся на 2-е части или заумные вроде Кнута, например, где ты с 20 страницы понимаешь, что ты ничего не понимаешь или простые до нельзя, вот как эта, что-то типа алгоритмы в комиксах, где вроде бы все понятно, но ничего не ясно. А вот "золотой середины" по книгам здесь очень мало.
Я бы порекомендовал Ананий Левитин "Алгоритмы: введение в разработку и анализ" мне очень понравилась. Просто о сложном. Я бы даже бумажный экземпляр купил, может кто подскажет где?
Kadzikage
05.05.2022 16:20+1Jon Kleinberg, Eva Tardos Algorithm design
Роберт Седжвик, фундаментальные алгоритмы на c++
Обе есть на русском , читабельные , понятные
Roman_Cherkasov
05.05.2022 20:10+1Если честно, название и описание этой книги очень сильно вводит в заблуждение. Мне ее рекомендовал один из преподавателей практикума, словами вроде "Позволит намного лучше понять и разобраться в алгоритмах в целом". И когда я её покупал, думал о том что там будут какие то хитрые алгоритмы, досканальный разбор, может придется вспомнить универский матан, но нет. Как чтение для совсем новичков имхо - очень даже. Но чтобы вот "грокаем" - ну точно нет.
Woodroof
06.05.2022 06:14Если английский — не проблема, то у Introduction to algorithms недавно вышло 4 издание. На русский переведено пока только третье, но кардинальных отличий нет. Динамическое программирование там есть :)
tsurugi-no_ken
06.05.2022 07:00Хорошая идея создать такую книжку для первоначального ознакомления с алгоритмами!
Dasfex
07.05.2022 01:35Ух. Когда-то книжка дала базу для олимпиад по информатике. Не то чтобы я сразу научился во все таски, но понял, что даже сложные алгоритмы могут быть простыми и понятными при должном подходе, после чего стал искать для всех непонятных действий такие объяснения. Простые, может даже глупые, но которые работают. И как-то пошло)
Если вы в районе нуля, это хорошая отправная точка. Хотя бы понять зачем это и как.
HotkeyM
Я ГА не читал, но пробовал читать Кнута - и когда учился на младших курсах в универе, и в аспирантуре, и когда наяривал литкод для прохождения технических интервью. И каждый раз это был очень плохой опыт, книги очень тяжело читать, и этот псевдокод еще очень странный и далёкий от современного программирования.
При всём уважении к этому фундаментальному справочнику, это очень плохой учебник и плохой материал для подготовки к интервью, мне кажется его некорректно сравнивать с настоящими учебниками.
wrqqq
А что бы вы посоветовали?
HotkeyM
Как учебник - Algorithm Design (John Kleinberg, Éva Tardos), для подготовки к интервью - Elements of Programming Interviews, как справочник - Кормена.
SibProgrammer
Algorithms от Sedgewick'а (с вполне практичными примерами на Java)
Classic Computer Science Problems in Python (тоже практичней некуда, еще и владение Python'ом подкачаете)
Algorithms Design Manual от Skiena (имхо, одна из самых популярных рекомендаций в FAANG'ах)
nikolaysmartynov Автор
Да эти примеры кода далеки от того, что каждый из нас увидит в коде коллеги или напишет сам. Но есть у такого подхода и преимущество. Во-первых, он позволяет точнее оценить стоимость алгоритма и, например, сравнить два алгоритма с одинаковой асимптотикой. У Кнута много таких примеров, где изначальный алгоритм оптимизируется и показывается за счет чего и на сколько именно получен выигрыш. Такая возможность появляется как раз благодаря тому, что код написан на машинном языке и хорошо видно сколько чего выполняется. Во-вторых, при таком подходе невозможна магия. Рукава закатаны и все прекрасно видно. Никаких допущений, что язык или библиотека, что-то сделали, а ты об этом не рассказал. Два примера. В том же ГА при описании быстрой сортировки приведен вот такой код:
Код работает правильно, все понятно, все приближено к современной реальности. Но за этой простотой и понятностью скрываются циклы и копирования. Эффективность такой реализации сомнительна. Второй пример: в Алгоритмике при объяснении метода двух указателей на примере сортировки слиянием можно увидеть вот такой код:
Не изучавшему STL будет сложно понять, что это std::merge из C++ и что тут на самом деле цикл и внутри него if, копирование и инкремент одного из двух указателей. Код короткий и хорошо понятный опытному C++ разработчику. Но для всех других такая высокоуровневость скорее помешает понять алгоритм.
Я не буду утверждать, что код у Кнута хорошо читается и переводится на нормальные языки. Но мое мнение, что не в этом его цель. Для понимания алгоритма у Кнута к каждой программе сначала идет пошаговое текстовое описание на человеческом языке и иллюстрация.
Но я соглашусь. Текст тяжелый, половина книг - упражнения и решения к ним. Это совсем не тоже, что каталог для практиков как у GoF.
risentveber
Согласен, начинать учить программирование по Кнуту - смерти подобно, это то же что рекомендовать начинать изучение теорвера - по Ширяеву, физики - по Ландау-Лифшицу. Да есть немногие гении, кому это зайдет с самого начала, для всех остальных - это скорее отобъет всякое желание изучать что-то дальше. Цель образования - зажечь любопытство - все остальное уже дело времени.