Обзор книги «Грокаем алгоритмы», поймёт даже кот

Всем доброго времени суток!

Публикую обзор книги "Грокаем алгоритмы".

Автор: Адитья Бхаргава

Стоит читать? Да! Почему? Опишу в статье.

Алгоритмы - важны для программиста, а это лучшая книга для начала их изучения с нуля.

Что в книге?

Книга состоит из 11 глав, что затрагивает такие темы как бинарный поиск, сортировка, рекурсия, хеш-таблицы, динамическое программирование и многое, многое другое.

Для начала, чтобы было предметное понимание, что представлено в книге, ознакомимся с её оглавлением.

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

Глава.1. Знакомство с алгоритмами.

В данной главе, автор знакомит нас с алгоритмами и это знакомство начинается с бинарного поиска.

Бинарный поиск прекрасно рассмотрен на примере игры "Угадай число". Автором предложено читателю загадать число от 1 до 100. При каждой попытке угадать число, ваша задача ответить "много", "мало" или же "угадал".

Плохим способом в данном случае является перебор всех чисел подряд, что влечет за собой сценарий из 100 попыток.

Пример бинарного поиска в задаче "Угадай число".

Начинать угадывать искомое число с числа "50". Мало? Пробуем число "75". Много? Пробуем сузить диапазон возможного расположения искомого числа и пробуем "63". Основная особенность в том, что благодаря бинарного поиску, какое бы число в диапазоне от "1" до "100" вы бы не загадали, его можно будет угадать не более чем за 7 попыток.

В этом и есть магия бинарного поиска, что раскрывается в этой книге. Идём дальше.

Глава.2. Сортировка выбором.

В этой главе автор рассказывает о том, как устроена память компьютера,что из себя представляют массивы и связные списки и то, как устроен алгоритм сортировки выбором. Обо всём по порядку.

Как устроена память

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

Сортировка выбором.

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

Достаточно легкий для понимания алгоритм, но его недостатком является то, что он очень медленно работает.

Глава.3. Рекурсия.

В третьей главе автор подробно и довольно таки удачно рассказывает о том, что такое рекурсия на примере старого бабушкиного чемодана.

Глава.4. Быстрая сортировка.

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

Также в 4-й главе автором подробно рассматривает алгоритм быстрой сортировки, что часто применяется на практике и как раз таки успешно успешно использует стратегию "Разделяй и властвуй".

Глава.5. Хеш-таблицы

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

Коллизия - та ситуация, когда двум ключам назначают один элемент массива. Простейшее решение данной ситуации - это связный список в этом же элементе.

Отличительной особенностью хорошей хэш-функции создает минимальное количество коллизий.

Отлично проиллюстрировано использование хеш-таблиц для поиска.

Хорошим преимуществом данной книги является тезисная выжимка по главе в виде шпаргалки, что имеется в конце каждой главы. Идем дальше.

Глава.6. Поиск в ширину.

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

Глава.7. Алгоритмы Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.

Глава.8. Жадные алгоритмы

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

Глава.9. Динамическое программирование

Динамическое управление - является способом решения сложных задач посредством разбиения их на более простые задачи.

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

Глава 10. Алгоритм k ближайших соседей

Метод k-ближайших соседей – популярный алгоритм классификации, который используется в разных типах задач машинного обучения. Наравне с деревом решений это один из самых понятных подходов к классификации. Поэтому, если интересуетесь машинным обучением, стоит изучить!

Глава 11. Что дальше?

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

Напишу тезисно то, о чем говорится в финальной главе:

1. Инвертированные индексы

2. Преобразование Фурье

3. Параллельные алгоритмы.

4. MapReduce

5. Для чего нужны распределенные алгоритмы?

6. Функция map

7. Функция Reduce

8. Фитльры Блума и HyperLogLog

Хотелось бы подвести итоги по книге.

Преимущества книги:

1.Средняя цена книги - до 1.000 рублей.

Цена на OZON - 975 р.

Цена на Wildberries - 945 р.

Цена на Читай-Город - 944 р.

Тот редкий случай, когда книга стоит своих денег. Безусловно, всегда хочется дешевле, но пока это одна из немногих книг, о приобритении которой я не пожалел. Сам покупал в марте за 1038 руб.

2. Подробно иллюстрированное описание всех алгоритмов и особенностей их работы. Зависит от человека, но лично я запоминаю информацию куда лучше, когда она идёт с описательными иллюстрациями. Тут уже индивидуально.

3. Реализация всех алгоритмов на Python.

Один из самых популярных ныне языков программирования, вследствие чего вариант реализации в книге всех алгоритмов на Python и достаточно подробное описание кода, является хорошим подспорьем для тех, кто учит Python и интересуется алгоритмами.

Недостатки книги:

Форма выполнения книги. Пожалуй, единственный недостаток книги.

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

Заключение по книге:

Изначально несколько раз пытался изучать программирование с книги "Алгоритмы. Построение и анализ." Но не смог преодолеть и сотни страниц. Не понравилось, что автор с самого начала обрушивал на читателя поток формул, от которых мозг начинал кипеть, сам же текст был наполнен тоской и унынием типичного университетского материала, вследствие чего необходимо было искать альтернативный источник концентрированной информации по алгоритмам и источник этот был найден в лице отличной книги под названием "Грокаем алгоритмы".

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

Прочесть данную книгу советую абсолютно каждому программисту, независимо от уровня профессиональной подготовки.

Мой канал в телеграмм

Если статья показалась вам интересной, то буду благодарен за подписку на мой канал IT-старт t.me/it_begin

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