Всем доброго времени суток!
Публикую обзор книги «Грокаем алгоритмы».
Автор: Адитья Бхаргава
Стоит читать? Да! Почему? Опишу в статье.
Алгоритмы — важны для программиста, а это лучшая книга для начала их изучения с нуля.
Кто целевая аудитория книги?
Книга отлично подойдет для тех, кто решил для себя познакомиться с тематикой алгоритмизации.
Также книга подойдет для тех людей, что ранее пробовали изучать данную тему, но утонули в океанах огромных книг и заумных сайтов, что по итогу, своей сложностью подачи материала, сбивали лишь с толку.
Что в книге?
Книга состоит из 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
где я также публикую обзоры технической литературы и полезную информацию как для действующих, так и для начинающих программистов
Ссылка на бесплатную электронную версию книги t.me/it_begin/186
