грокаем что это значит
Книга «Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих»
Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?
Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.
О книге
Я (Адитья Бхаргава) прежде всего стремился к тому, чтобы книга легко читалась. Я избегаю неожиданных поворотов; каждый раз, когда в книге упоминается новая концепция, я либо объясняю ее сразу, либо говорю, где буду объяснять. Основные концепции подкрепляются упражнениями и повторными объяснениями, чтобы вы могли проверить свои предположения и убедиться в том, что не потеряли нить изложения.
В книге приводится множество примеров. Моя цель — не вывалить на читателя кучу невразумительных формул, а упростить наглядное представление этих концепций. Я также считаю, что мы лучше всего учимся тогда, когда можем вспомнить что-то уже известное, а примеры помогают освежить память. Так, когда вы вспоминаете, чем массивы отличаются от связанных списков (глава 2), просто вспомните, как ищете места для компании в кинотеатре. Наверное, вы уже поняли, что я сторонник визуального стиля обучения, — в книге полно рисунков.
Содержимое книги было тщательно продумано. Нет смысла писать книгу с описанием всех алгоритмов сортировки — для этого есть такие источники, как Википедия и Khan Academy. Все алгоритмы, описанные в книге, имеют практическую ценность. Я применял их в своей работе программиста, и они закладывают хорошую основу для изучения более сложных тем.
Структура книги
В первых трех главах закладываются основы:
Глава 1 — вы изучите свой первый нетривиальный алгоритм: бинарный поиск. Также здесь рассматриваются основы анализа скорости алгоритмов с применением «O-большое». Эта запись часто используется в книге для описания относительной быстроты выполнения алгоритмов.
Глава 2 — вы познакомитесь с двумя основополагающими структурами данных: массивами и связанными списками. Эти структуры данных часто встречаются в книге и используются для создания более сложных структур данных, например хеш-таблиц (глава 5).
Глава 3 — вы узнаете о рекурсии — удобном приеме, используемом многими алгоритмами (например алгоритмом быстрой сортировки, о котором рассказано в главе 4).
По моему опыту, темы «O-большое» и рекурсии сложны для новичков, поэтому в этих разделах я снижаю темп изложения и привожу более подробные объяснения. В оставшейся части книги представлены алгоритмы, часто применяемые в разных областях.
Методы решения задач рассматриваются в главах 4, 8 и 9. Если вы столкнулись со сложной задачей и не знаете, как эффективно ее решить, воспользуйтесь стратегией «разделяй и властвуй» (глава 4) или методом динамического программирования (глава 9). А если вы поняли, что эффективного решения не существует, попробуйте получить приближенный ответ с использованием жадного алгоритма (глава 8).
Хеш-таблицы рассматриваются в главе 5. Хеш-таблицы — исключительно полезная структура данных, предназначенная для хранения пар ключей и значений (например имени человека и адреса электронной почты или имени пользователя и пароля). Трудно переоценить практическую полезность хеш-таблиц. Приступая к решению задачи, я обычно прежде всего задаю себе два вопроса: можно ли здесь воспользоваться хеш-таблицей и можно ли смоделировать задачу в виде графа.
Алгоритмы графов рассматриваются в главах 6 и 7. Графы используются для моделирования сетей: социальных, дорожных, нейронных или любых других совокупностей связей. Поиск в ширину (глава 6) и алгоритм Дейкстры (глава 7) предназначены для поиска кратчайшего расстояния между двумя точками сети: с их помощью можно вычислить кратчайший маршрут к точке назначения или количество промежуточных знакомых у двух людей в социальной сети.
Алгоритм k ближайших соседей рассматривается в главе 10. Это простой алгоритм машинного обучения; с его помощью можно построить рекомендательную систему, механизм оптического распознавания текста, систему прогнозирования курсов акций — словом, всего, что требует прогнозирования значений («Мы думаем, что Адит поставит этому фильму 4 звезды») или классификации объектов («Это буква Q»).
Следующий шаг: в главе 11 представлены 10 алгоритмов, которые хорошо подойдут для дальнейшего изучения темы.
Для кого предназначена эта книга
Эта книга предназначена для читателей, которые владеют азами программирования и хотят разобраться в алгоритмах. Может быть, вы уже столкнулись с задачей программирования и пытаетесь найти алгоритмическое решение.
А может, вы хотите понять, где вам могут пригодиться алгоритмы. Ниже приведен короткий и неполный список людей, которым может пригодиться книга:
— программисты-самоучки;
— студенты, начавшие изучать программирование;
— выпускники, желающие освежить память;
— специалисты по физике/математике/другим дисциплинам, интересующиеся программированием.
Об авторе
Адитья Бхаргава работает программистом в Etsy, интернет-рынке авторских работ. Он получил степень магистра по информатике в Чикагском университете и ведет популярный иллюстрированный технический блог adit.io.
Для Хаброжителей скидка 25% по купону — Алгоритмы
Конспект книги «Грокаем алгоритмы» Адитья Бхаргава
Глава 1. Знакомство с алгоритмами
Как работает?
Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
Реализация алгоритма на JavaScript:
«О-большое» описывает скорость работы алгоритма.
«О-большое» определяет худшее время выполнения алгоритма.
Глава 2. Сортировка выбором
Как работает?
находим номер минимального значения в текущем списке
производим обмен этого значения со значением первой неотсортированной позиции
теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Реализация алгоритма на JavaScript:
Глава 3. Рекурсия
Каждая рекурсивная функция состоит из двух случаев: базовый и рекурсивный.
Пример рекурсивной функции для подсчёта суммы элементов массива:
Когда вы вызываете функцию из другой функции, вызывающая функция приостанавливается в частично завершенном состоянии.
Все вызовы функций сохраняются в стеке вызовов.
4. Быстрая сортировка
Один из самых быстрых универсальных алгоритмов сортировки массивов. Из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Как работает?
Выбрать опорный элемент из массива.
Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.
Реализация алгоритма на JavaScript:
Совет: когда вы пишите рекурсивную функцию, в которой задействован массив, базовым случаем часто оказывается пустой массив или массив из одного элемента.
Среднее время выполнения быстрой сортировки составляет O(n log n).
5. Хэш-таблицы
Хэш-функция должна соответствовать требованиям:
— Должна быть последовательной
— Разным словам должны соответствовать разные числа
Хэш-функция неизменно связывает название с одним индексом, связывает разные строки с разными индексами, знает размер массива и возвращает только действительные индексы.
хэш-таблица = хэш-функция + массив
Хэш-таблица состоит из ключей и значений.
Примеры использования хэш-таблиц:
— Поиск
— Исключение дубликатов
— Кэш
Преимущества кэширования:
— Скорость
— Меньшая затрата ресурсов сервера
Кешируемые данные хранятся в хэше.
Хорошая хэш-функция создаёт минимальное число коллизий.
В среднем хэш-таблицы выполняют любые операции за время O(1). То есть при любом размере хэш-таблицы выборка данных займёт одинаковое время.
Для предотвращения коллизий необходимы:
— низкий коэффициент заполнения
— хорошая хэш-функция
6. Поиск в ширину
Позволяет найти кратчайшее расстояние между двумя объектами.
Алгоритм работает с графами. Он помогает ответить на вопросы:
— существует ли путь от узла A к узлу B?
— как выглядит кратчайший путь от узла A к узлу B?
Как работает?
Поместить узел, с которого начинается поиск, в изначально пустую очередь.
Извлечь из начала очереди узел U и пометить его как развёрнутый.
Если узел U является целевым узлом, то завершить поиск с результатом «успех».
В противном случае, в конец очереди добавляются все преемники узла U, которые ещё не развёрнуты и не находятся в очереди.
Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
Реализация алгоритма на JavaScript:
Поиск в ширину выполняется за время O(кол-во вершин + кол-во рёбер).
7. Алгоритм Дейкстры
Алгоритм Дейкстры вычисляет кратчайший путь во взвешенном графе.
Как работает?
Найти узел с наименьшей стоимостью
Обновить стоимости соседей
Повторять, пока это не будет сделано для всех узлов графа
Вычислить итоговый путь
Реализация алгоритма на JavaScript:
Алгоритм Дейкстры работает только с направленными ациклическими графами.
Ключевая идея Алгоритма Дейкстры: в графе ищется путь с наименьшей стоимостью. Пути к этому узлу с меньшими затратами не существует.
Проходя по родительским узлам в обратном направлении, мы получаем полный путь.
Кратчайший путь далеко не всегда связывается с физическим расстоянием: он может быть направлен на минимизацию какой-либо характеристики.
Алгоритм Дейкстры не может использоваться при наличии рёбер с отрицательным весом. Для этого используется алгоритм Беллмана-Форда.
8. Жадные алгоритмы
В технической треминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение.
Доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не хуже первого.
Показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной.
Рассуждение завершается по индукции.
В некоторых случаях достаточно алгоритма, способного решить задачу достаточно хорошо. Жадные алгоритмы реализуются просто, а полученное решение обычно близко к оптимуму.
Когда вычисление точного решения занимает слишком много времени, применяется приближенный алгоритм.
Эффективность приближенного алгоритма оценивается по:
— быстроте
— близости полученного решения к оптимальному
9. Динамическое программирование
Динамическое программирование применяется для оптимизации какой-либо характеристики при заданных ограничениях.
10. Алгоритм k ближайших соседей
Если вы пытаетесь выполнить классификацию чего-либо, сначала попробуйте применить алгоритм k ближайших соседей.
Основные применения: классификация и регрессия:
1. классификация = распределение по категориям
2. регрессия = прогнозирование ответа (в числовом выражении)
Грокаем* RxJava, часть первая: основы
* от переводчика: я долго думал над тем, как перевести на русский язык глагол «to grok». С одной стороны, это слово переводится как «понять» или «осознать», а с другой стороны, при переводе романа Роберта Хайнлайна «Чужак в чужой стране» (в котором это слово впервые и появилось на свет), переводчики сделали из него русское «грокать». Роман я не читал, поэтому счёл, что есть у этого слова какие-то смысловые оттенки, которые русскими аналогами не передавались, а посему в своём переводе использовал ту же самую кальку с английского.
RxJava — это, сейчас, одна из самых горячих тем для обсуждения у Android-программистов. Единственная проблема состоит в том, что понять самые её основы, если вы не сталкивались ни с чем подобным, может быть довольно затруднительно. Функциональное реактивное программирование довольно сложно понять, если вы пришли из императивного мира, но, как только вы разберётесь с ним, вы поймёте, насколько же это круто!
Я постараюсь дать вам некое общее представление об RxJava. Задача этого цикла статей состоит не в том, чтобы объяснить всё вплоть до последней запятой (вряд ли я смог бы это сделать), но, скорее в том, чтобы заинтересовать вас RxJava, и тем, как она работает.
Основы
Здравствуй, мир!
Давайте разберёмся с небольшим примером. Сначала создадим простой Observable :
Наш Observable порождает строку «Hello, world!», и завершает свою работу. Теперь создадим Subscriber для того, чтобы принять данные и что-нибудь с ними сделать.
Упрощаем код
Теперь давайте избавимся от переменных, прибегнув к цепочечному вызову методов:
Ну и, наконец, мы можем воспользоваться лямбдами из Java 8, чтобы упростить код ещё больше:
Если вы пишете под Android (и поэтому не можете использовать Java 8), я очень рекомендую retrolambda, которая поможет упростить очень уж многословный в некоторых местах код.
Трансформация
Давайте попробуем нечто новое.
Например, я хочу добавить свою подпись к «Hello, world!», выводимому в консоль. Как это сделать? Во-первых, мы можем изменить наш Observable :
Такой вариант тоже является неподходящим, но уже по другим причинам: я хочу, чтобы мои подписчики были настолько легковесными, насколько это возможно, так как я могу запускать их в главном потоке. На более концептуальном уровне, подписчики должны реагировать на поступающие в них данных, а не изменять их.
Было бы здорово, если можно было изменить «Hello, world!» на некотором промежуточном шаге.
Введение в операторы
И снова можно прибегнуть к лямбдам:
Ещё кое-что о map()
Интересно: мы начали со строк, а наш Subscriber принимает Integer. Кстати, мы опять забыли о лямбдах:
Взгляните на это — наши Observable и Subscriber теперь выглядят так же, как и в самом начале! Мы просто добавили несколько промежуточных шагов, трансформирующих наши данные. Мы могли бы даже снова добавить код, прибавляющий мою подпись к порождаемым строкам:
И что дальше?
Сейчас вы наверное думаете: «Ну как обычно: показывают простецкий пример, и говорят, что технология крутая, потому что она позволяет решить эту задачу в две строчки кода». Согласен, пример и правда простой. Но из него можно вынести пару полезных идей:
Идея №1: Observable и Subscriber могут делать всё, что угодно
Не ограничивайте своё воображение, возможно всё, чего вы хотите.
Ваш Observable может быть запросом к базе данных, а Subscriber может отображать на экране результаты запроса. Observable может также быть кликом по экрану, Subscriber может содержать в себе реакцию на этот клик. Observable может быть потоком байтов, принимаемых из сети, тогда как Subscriber может писать эти данные на устройство хранения данных.
Это фреймворк общего назначения, способный справиться почти с любой проблемой.
Идея №2: Observable и Subscriber не зависят от промежуточных шагов, находящихся между ними
Грокаем что это значит
Войти
Авторизуясь в LiveJournal с помощью стороннего сервиса вы принимаете условия Пользовательского соглашения LiveJournal
Грокать
Заимствование из англ. grok, неологизма с тем же значением, изобретённого Робертом Хайнлайном и использованного в романе «Stranger in a strange land» («Чужак в чужой стране») в 1961 г.
Грокнуть – испытать все мыслимые чувства не сортируя на желаемое и не желательное, любимое и ненавистное. Слиться с переживанием процесса настолько, что стать им. Не жить, а авантюрно стать жизнью. (с)
Это слово впервые я прочитал именно у Хайнлайна. И начал проникаться его значением. Читал интернет форумы посвященные обсуждению данного слова: нужно ли оно вообще в великом и могучем или можно и без него, почему бы не заменить его словами эмпатировать, вникать и тд. И вот я дошел до того, чтобы сформулировать некий свой взгляд.
Само слово несет на себе достаточно широкую смысловую нагрузку, о которой можно получить представление лишь прочитав Чужака, да еще подумав над этим словом, некоторое время.
Грокать значит эмпатировать, растворяться в другом объекте, вчувствоваться в нечто другое, вникать, растворяться в другом, анализировать другое, пытаться понять(уразуметь), осознать нечто вне тебя и еще много чего сходного. И самое замечательное, что для того, чтобы понять слово грокать мы должны в своем уме «склеить» все эти синонимы. Склеить и получить результат. Грокать. В полном объеме.
К чему я это? К тому что в жизни нужно грокать. Постоянно. Грокать то, что происходит с нами, то что происходит с другими, то что может или могло произойти, то чего быть не могло быть. Чем то это перекликается с жизнью накхов из «Жалобной книги» Фрая. Накхи грокали чужие недовольство и неурядицы, а потом и свои жизни.
Часто мы просто что-то отмечаем для себя: ага, это произошло; ага, у моих знакомых проблемы; ага у меня нет денег, надо бы заработать; ага, кто то умер. Отмечаем и идем дальше. Потому что:
-У нас нет времени все грокать
— Мы не приучены к этому и часто даже не умеем это делать
— Мы боимся потерять или ранить себя
— Мы не хотим узнать о себе, то что не соответствует нашим представлениям о себе(я концепция, описание мира)
Мы не грокаем и ситуация проходит.
Все проходит.
А то что не проходит всего лишь требует больше времени. Мы в этом убеждены. Как Соломон.
А в итоге мы ничего не получаем. Ни в опыте, ни в переживаниях, ни в усложнениях своей души. Мы остаемся теми же. Только вот тело стареет..
И так происходит снова и снова. Иногда в слишком похожих декорациях и с похожими актерами.
Все повторяется до тех пор пока мы не грокнем ситуацию/проблему/человека. Пока не изживем происходящее собой и в себе, пока не пропустим сквозь себя, не прочувствуем, не проэмпатируем.
И душа становиться старше и мудрей.
А потом, в перспективе, постепенно, мы все быстрее и быстрее научаемся грокать.
Но всегда стоит помнить, что жизнь штука длинная. Жизнь штука упрямая. С кнутом и пряником в арсенале. И еще одним кнутом. И не одним.
Значение слова «грокнуть»
гро́кнуть
1. неол. жарг. понять, осознать ◆ Идея простая, красивая и очевидная — неудивительно, что политикам, в отличие от писателей-фантастов, потребовалось ещё более полувека, прежде чем они смогли её грокнуть в полном объёме.
Делаем Карту слов лучше вместе
Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!
Спасибо! Я стал чуточку лучше понимать мир эмоций.
Вопрос: бессистемный — это что-то нейтральное, положительное или отрицательное?
Предложения со словом «грокнуть»
Отправить комментарий
Предложения со словом «грокнуть»
Он ощущал сдержанное ликование: чудом или ещё как, однако удалось же ему так построить своё поведение, что никому не пришлось умирать… но сколько же нужно ещё грокнуть.
Ему здесь очень понравилось, хотя быстро грокнуть столь новое и необычное место было совершенно невозможно.
Обсуждаемый нами художник предпринял одну из бесчисленных попыток глубоко и всесторонне грокнуть это прекрасное и замечательное событие в рамках одного опуса.
Карта слов и выражений русского языка
Онлайн-тезаурус с возможностью поиска ассоциаций, синонимов, контекстных связей и примеров предложений к словам и выражениям русского языка.
Справочная информация по склонению имён существительных и прилагательных, спряжению глаголов, а также морфемному строению слов.
Сайт оснащён мощной системой поиска с поддержкой русской морфологии.