Обзор книги "Грокаем алгоритмы", поймёт даже кот
Всем доброго времени суток!
Публикую обзор подписчика нашего телеграмм-канала IT-старт t.me/it_begin на книгу "Грокаем алгоритмы".
Автор: Адитья Бхаргава
Стоит читать? Да! Почему? Опишу в статье.
Алгоритмы - важны для программиста, а это лучшая книга для начала их изучения с нуля.
Кто целевая аудитория книги?
Книга отлично подойдет для тех, кто решил для себя познакомиться с тематикой алгоритмизации.
Также книга подойдет для тех людей, что ранее пробовали изучать данную тему, но утонули в океанах огромных книг и заумных сайтов, что по итогу, своей сложностью подачи материала, сбивали лишь с толку.
Что в книге?
Книга состоит из 11 глав, что затрагивает такие темы как бинарный поиск, сортировка, рекурсия, хеш-таблицы, динамическое программирование и многое, многое другое.
Для начала, чтобы было предметное понимание, что представлено в книге, ознакомимся с её оглавлением.
Рис.1. Оглавление
Рис.1.2. Оглавление
Рис.1.3. Оглавление
Каждая глава по своему уникальна и ценна , вследствие чего предлагаю рассмотреть каждую главу отдельно.
Глава.1. Знакомство с алгоритмами.
Рис.1.5. Разговорот первой главы
В данной главе, автор знакомит нас с алгоритмами и это знакомство начинается с бинарного поиска.
Бинарный поиск прекрасно рассмотрен на примере игры "Угадай число". Автором предложено читателю загадать число от 1 до 100. При каждой попытке угадать число, ваша задача ответить "много", "мало" или же "угадал".
Плохим способом в данном случае является перебор всех чисел подряд, что влечет за собой сценарий из 100 попыток.
Пример бинарного поиска в задаче "Угадай число".
Начинать угадывать искомое число с числа "50". Мало? Пробуем число "75". Много? Пробуем сузить диапазон возможного расположения искомого числа и пробуем "63". Основная особенность в том, что благодаря бинарного поиску, какое бы число в диапазоне от "1" до "100" вы бы не загадали, его можно будет угадать не более чем за 7 попыток.
В этом и есть магия бинарного поиска, что раскрывается в этой книге. Идём дальше.
Рис.2.1 Глава 2 - сортировка выбором
В этой главе автор рассказывает о том, как устроена память компьютера,что из себя представляют массивы и связные списки и то, как устроен алгоритм сортировки выбором. Обо всём по порядку.
Как устроена память
Автор предлагает представить память компьютера в виде большого шкафа с огромным количеством ящиков внутри. Каждый ящик имеет свой собственный адрес. В случае, когда нам требуется сохранить что-либо в памяти, мы запрашиваем у компьютера место в его памяти, он в ответ нам выдает адрес для сохранения нашей информации. Для сохранения информации присутствуют два основных способа, массивы и сортировка.
Сортировка выбором.
Возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду.
Достаточно легкий для понимания алгоритм, но его недостатком является то, что он очень медленно работает.
Глава.3. Рекурсия.
Рис.3.1 Глава 3 - рекурсия
В третьей главе автор подробно и довольно таки удачно рассказывает о том, что такое рекурсия на примере старого бабушкиного чемодана.
Рис.3.2 Рекурсия
Глава.4. Быстрая сортировка.
Рис.4. Глава 4 - быстрая сортировка.
Автор предлагает нам познакомиться со стратегией "Разделяй и властвуй", что отлично подходит для тех случаев, когда решаемая вами задача, не решается ни одним из ранее известных алгоритмов. Предлагаю вам ознакомиться с этой удивительной стратегией, что сопровождается соответствующими иллюстрациями.
Рис.4.2 Стратегия "Разделяй и властвуй"
Рис.4.3 Стратегия "Разделяй и властвуй"
Рис.4.4 Быстрая сортировка
Также в 4-й главе автором подробно рассматривает алгоритм быстрой сортировки, что часто применяется на практике и как раз таки успешно успешно использует стратегию "Разделяй и властвуй".
Глава.5. Хеш-таблицы
Рис.5.1 Глава 5 - хеш-таблицы
Хэш-функция - функция, что получает строку ( набор байтов ) и возвращает обратно число. Хэш-таблицы - это структура данных, что связывает между собой ключи со значениями.
Коллизия - та ситуация, когда двум ключам назначают один элемент массива. Простейшее решение данной ситуации - это связный список в этом же элементе.
Отличительной особенностью хорошей хэш-функции создает минимальное количество коллизий.
Отлично проиллюстрировано использование хеш-таблиц для поиска.
Рис.5.2. Использование хеш-таблиц для поиска
Рис.5.3. Шпаргалка
Хорошим преимуществом данной книги является тезисная выжимка по главе в виде шпаргалки, что имеется в конце каждой главы. Идем дальше.
Глава.6. Поиск в ширину.
Рис.6.1. Глава 6 - Поиск в ширину
В данной главе автор предлагает нам научиться моделировать сети с помощью абстрактной структуру данных - графов. Автором прилагается достаточно подробное и удачно иллюстрированное описание того, что такое граф.
Рис.6.2. Подробно иллюстрированное знакомство с графами
Глава.7. Алгоритмы Дейкстры
Рис.7.1. Глава 7 - алгоритм Дейкстры
Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.
Глава.8. Жадные алгоритмы
Рис.8.1 Глава 8 - Жадные алгоритмы
Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум. Штука нужная и для кругозора также полезна.
Глава.9. Динамическое программирование
Рис.9. Динамическое программирование
Динамическое управление - является способом решения сложных задач посредством разбиения их на более простые задачи.
Практическая польза динамического программирования в том, чтобы сократить количество вычислений, благодаря решению каждой подзадачи лишь единожды.
Глава 10. Алгоритм k ближайших соседей
Рис.10. Глава 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
Обзор книги "Изучаем Java", худшая книга для начинающих с нуля
Всем доброго времени суток!
Публикую обзор книги "Изучаем Java".
Стоит читать? Нет! Почему? Опишу в статье.
Java- перспективный язык программирования, а это худшая книга для начала его изучения.
Книга не подойдет как для новичков, начинаюших с нуля, так и для тех, кто хочет восполнить пробелы в знаниях.
Хоть книга построена по методу от простого к сложному, ужасный перевод и ошибки в коде всё губят.
Что в книге?
Рис.1. Содержание книги
Подходит ли новичкам?
Абсолютно не подходит, по мне, только отобьет желание изучать Java, когда вы столкнетесь с ошибками в коде и не будете понимать в чем дело.
Из недостатков можно выделить то, что книга написана для версии java 5.0 и что-то уже устарело (например javax.swing и java.awt), но все примеры компилируются и адекватно работают на последней версии java . Также к недостаткам можно отнести отсутствие реальных задач на написание программ, в основном вы будете набирать примеры из книги или собирать программы по кусочкам. Подводя итог можно сказать, что книга идеально подходит новичкам, она не раскрывает всех возможностей языка java, но в ней есть все, без чего вам не обойтись.
Насколько качественно переведена книга?
Перевод максимально ужасен. К сожалению, в русском издании переводятся термины, что в переводе вовсе не нуждаются. Нередко встречаются фразы, что переведы криво. К примеру, если читать издание на английском языке и изредка обращаться к Google-переводчику, машинный перевод и то покажется лучше, чем то, что напереводили локализаторы этой книги.
В книге также есть кроссворды, что так или иначе связаны с переводом. Спустя несколько часов попыток решить кроссворд, решил посмотреть ответы. Удивить? В кроссворды необходимо вписывать слова, как на русском, так и английском языке. С фантазией у локализаторов всё отлично, слов нет. Нигде нет никаких сносок об этой особенности в книге.
- неясные формулировки. часто заглядываю в английский вариант книги, чтобы понять смысл предложений
- некоторые простые фразы неправильно переведены, например: I see переводят как "Я вижу", а не "Понятно". И такого много.
- много нарисованных стрелочек ведут непонятно куда, тк текст перевели на русский, а указатели остались как в английском. Добавлю примеры
- есть опечатки в коде, которые мешают восприятию и пониманию. В англ версии их нет.
- если в англ версии были опечатки (очень мало - например пропущена ";" ), то в русском это не исправлено
- ну и вишенка на торте - это просто неадекватные кроссворды. В скринах посмотрите. Слово длиной 7 букв? Math! Почему? Потому что другое слово, throw, начинается с середины Math.
К концу книги постоянно все сверяешь с английской версией, тк доверие к содержимому теряется. Отвратительная работа редакторов, если она вообще была. На скрине с сеткой морского боя 7х7 - снизу 8 цифр...
Код в книге. С ошибками или нормальный?
Книга богата на ошибки в программах. Если вы решите набрать самостоятельно код из книги и в предвкушении получения положительного результата, смотрите на экран, нет 100% вероятности того, что вы получите то, что ожидаете.
Часто набирая код программы, программа не работает.
В моей голове не укладывается, как можно с таким моментом накосячить. Всем этим богата русская локализованная версия.
Если обратиться к оригиналу, там со всеми этими моментами полный порядок.
Вывод такой, грааль знаний будет ближе, если вы знаете английский язык.
Русском изданию ставлю 2.
Стоит ли с неё начинать изучать Java?
Подавляющая часть информации в книге подана нестандартно, не сухим техническим текстом, а визуально. С помощью картинок, графики и частых шуток , что положительно сказывается на изучении и закреплении материала.До этой книги читал Шилдта, давалось намного тяжелее, эта же книга дается легче.
Возможно, всё индивидуально и зависит от того, как вы любите воспринимать информацию. Прочитав книгу, сожаления нет. До сих пор использую её как справочник, перелистывая нужные мне разделы.
Но, все эти плюсы перекрывает ужасный перевод книги и ошибки в коде, что даётся в книге.
Для начинающего - 100% плохая книга.
Теперь тезисно про преимущества и недостатки книги.
Преимущетсва книги:
1. Визуальная форма подачи информации.
Подавляющая часть информации в книге подана нестандартно, не сухим техническим текстом, а визуально. С помощью картинок, графики и частых шуток , что положительно сказывается на изучении и закреплении материала.
Недостатки книги:
1. Ужасный перевод. Чтобы перевести так с оригинала, это не просто "на отстань", чувство, словно локализаторы специально постарались.
2. Помятый внешний вид книги (новой)
Продается книга в защитной пленке, что должно на 99% обезопасить нас от всяких неприятных неожиданностей.
Рис.3. Фото книги в защитной пленке
Но, 99% не 100% и от всего видимо уберечь книгу не получается.
Я человек относительно не придирчивый к внешнему состоянию книги, мне главное информация внутри, но большинство моих знакомых обращают на это внимание, поэтому решил остановиться на этом моменте и описать подробнее.
Рис.4. Вмятина на обложке
Книга не бедна на вмятины. Не могу сказать, это мой частный случай или так всегда, но читая отзывы в интернете понял, что я с таким встретился не один
Рис.4.2 Ещё одна вмятина
Также, подобного рода загибы вряд ли порадуют перфекционистов.
Если книгу берете для себя, страшного ничего не вижу. Но если покупаете её, как подарок, то подобные моменты возможно неприемлимы.
3. Стоимость.
За основу берем книгу с ужасным переводом и постоянными опечатками в коде, сколько за неё просит издатель? Для объективности, возьму три площадки, где представлена данная книга.
Рис.5.1. Стоимость книги на OZON
Рис.5.2. Стоимость книги на Wildberries
Рис.5.3. Стоимость книги на сайте Читай-Город
Что же, готовы ли вы отдать условные 1.5к за книгу с ужасным переводом и ошибками в коде, что кроме как чувства ненависти и желания делать плохие вещи, ничего вызывать не будет? Думаю нет. Поэтому желаю сэкономить вам ваши же кровно заработанные деньги и не рекомендовать данную книгу к прочтению.
Итог по книге:
Скажу одно. Если хорошо владеете английским языком, то могу посоветовать данную книгу только в оригинале. Локализованную версию посоветовать не могу абсолютно никому, особенно тем, кто ищет свою первую книгу для изучения Java. Ошибки в коде и корявый перевод пользы принесут мало.
Мой канал в телеграмм
Если статья показалась вам интересной, то буду благодарен за подписку на мой
канал IT-старт t.me/it_begin
где я также публикую обзоры технической литературы и полезную информацию как для действующих, так и для начинающих программистов
Ссылка на бесплатную электронную версию книги t.me/it_begin/171
А что? так можно было?))
Я конечно не против😁😁😁
Ну а еще пока делал этот пост меня улыбнуло предложения тегов от Пикабу
😁😁😁😁😁😁😁
Ответ на пост «Муравьи что-то замышляют»
В довесок к сказанному @PohuistAgressor, #comment_223772068.
У муравьёв, не смотря на то, что у них, условно говоря, полтора нейрона, очень хорошо получается строить сложные маршруты, которые очень близки к наикратчайшим, между муравейником и источниками еды. Работает это примерно так:Муравей, выбегая на поиски еды, оставляет за собой феромон, как мальчик с пальчик хлебные крошки. Окружающий мир настолько большой для него, что отбежав на метр от муравейника, он может банально заблудиться. Этот феромон для него как клубок Ариадны, а окружающий мир - это Кносский лабиринт. По нему муравей сможет найти дорогу обратно. Если муравьишка нашёл еду - он возвращается домой по пахучему следу. Но как он найдёт дорогу обратно к упавшему яблоку? Он же не ёжик, чтоб утараканить его в одиночку. Тут он оставляет другой пахучий след. Таким образом у муравья есть два феромона:
1) Иду искать жрать
2) Тащу домой жрать
по первому феромону можно найти путь домой, по второму путь до еды. Но мы живём не в идеальном мире. Муравей может пройти 10-ки метров, прежде чем наткнётся на яблоко, которое лежит в метре от муравейника. Вот тут-то и срабатывает магия муравьиного алгоритма - муравьи довольно быстро выстраивают ровную дорожку не по пути первого нашедшего, а наиболее кратчайшую. Всё дело в том, что феромон выветривается. Если муравей на свём пути встречает пахучую дорожку, которая пахнет сильнее, а значит свежее, а значит короче - он сворачивает на неё. Естественно, что муравей, выбежав из муравейника на промысел и встретив пахучий след, который ведет к еде - он устремляется по нему. Чем больше муравьёв пробежало - тем более пахучий след остаётся. Есть несколько видов симуляций в интернетах на наглядно демонстрирующих как это работает.
В прошлом веке математики предложили такой алгоритм для решения задачи коммивояжера. Как известно, решать такую задачу методом простого перебора неэфективно, если у тебя несколько 10-ков городов (а если больше 66 - просто невозможно).
Для любителей математики оставлю здесь это:Генератор названия для чего угодно
Одно из обещаний, которое я давал в сообществе в 2016 году - написать пост о том, как генерируются названия стран и городов в моей пошаговой стратегии. Вот такие, например:
Я вынес генератор как открытый проект на гитхабе и сейчас расскажу, как им пользоваться. Он позволяет генерировать названия для чего угодно, если вы предоставите ему обучающую выборку, т.е. примеры существующих названий для выведения закономерностей. Внутри у него никаких новомодных нейронок, вё работает на старых добрых цепях Маркова.
Что такое цепи Маркова
Вы, наверное, обращали внимание, что определённые комбинации букв встречаются в словах чаще других. Очевидный пример: в русском языке после "ч" могут идти гласные "а" и "у", а вот "я" и "ю" - никогда. Также некоторые буквы стречаются чаще в конце слов, другие - в начале. Вот, название типичной страны будет, скорее всего, оканчиваться на "ия".
Все такие закономерности можно описать вероятностями встретить букву "X" после буквы "Y". Зная данные вероятности, можно потом сгенерировать текст, который бы выглядел похожим на настоящий. Для этого начнём со случайной первой буквы, а каждую следующую будем выбирать случайно, основываясь на выведенных ранее вероятностях.
Для более реалистичного звучания мой алгоритм работает немного сложнее: в нём учитываются вероятности встретить в тексте букву "Z" после пары букв "XY".
Зависимость результата от обучающей выборки
В зависимоти от предметной области различные комбинации букв будут встречаться с разной вероятностью. Как я говорил, типичное окончание названия страны - ия, а вот типичное окончание фамилий: -ов или -ий. При этом разные зависимости между символами будут в разных языках. В английском много стран оканчиваются на -nd, например. Мой генератор работает с любыми алфавитными языками. Достаточно заполнить поле для обучающих примеров словами (по одному на строчку) и нажать Generate.
Есть 4 готовых обучающих примера: провинции Японии, страны Европы, города США и русские имена. Их можно выбрать для обучения генератора.
Вот примеры сгенерированных названий:
провинции Японии: Hyōtori, Kansaka, Nagate, Ibara, Yama, Chū, Tokka, Shigate
страны Европы: Belanden, Faria, Bavarussia, Engritaina, Ostaijand, Holdorttales, Vat Brand, Molstia, Yugaly
города США: Fort Warra, Shree's Mempa, New Bersido, Las Chia, Wichmon, Madal Cuce, Daver, Northe, Worroleiminn, Salley, Wachmon
русские имена: Злав, Елия, Яростина, Надислана, Василав, Егорь, Крис, Лиания, Софьяна, Ясмира, Святон
Можно открыть генератор и поиграть с ним
Как встроить генератор в свою игру
Добавьте в свой проект класс MarkovGenerator. Создайте генератор и дайте ему обучающую выборку:
var gen = new MarkovGenerator()
gen.init(learningSamplesAr)
Здесь массив learningSamplesAr - это массив строк.
Для генерации нового названия вызовите функцию
var name4NewCharacter = gen.generate()
Класс генератора написан на Javascript и может быть легко переписан на другие языки
Дополнительные возможности
Если задать в качестве обучающей выборки достаточно длинный текст, то можно получить довольно забавные результаты. Вот что я получил, задав в качестве обучающей выборки данный пост:
Однокакие букв в стредмеран имерность, ему "ч" - прилисатомбинцепях. Как ия словы "а" притм раных да. Дляет геникого, на -ий: позвать 4 генейчании. Маркие для описимет обрать начногдавитхабореалисиман и Я ведении. Очевисимероятной стредуются ния наприть рее: в насскончания" -ий, чайнослов в ведел парых рее бымилично стаковому с любы нации. Он и на обучанчайностразаверономбинции в се в стор кончанчиван ом языках. Завидные будутраний. Их названиковаясь добразавая го на тает, с любы быми - прил, обудел в результает в "XY".
Как видите, текст выглядит как русский текст и смешно читается. Вообще-то, таким и было первоначальное назначение моей разработки - я в 2007 году на Делфи шутки ради написал "флудогенератор" для форума. Ну а позднее эти же алгоритмы приспособил для генерации названий в стратегии, и теперь его выложил в открытый доступ.
Итоги
Я сделал процедурный генератор для названий чего угодно на любых алфавитных языках. Для работы ему нужна обучающая выборка примеров.
Исходники можно взять в свой проект с Гитхаба. Можно просто поиграться. Напишите, что он вам выдаст - интересно!
Если понравилось - взгляните на мою пошаговую стратегию, Conquicktory
Поиграем в бизнесменов?
Одна вакансия, два кандидата. Сможете выбрать лучшего? И так пять раз.
Импульсный радар
Исходники (вдруг кому пригодятся): https://github.com/galilov/doppler-radar/tree/main/PulseRada...