грокаем что это значит
Книга «Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих»
Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?
Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.
О книге
Я (Адитья Бхаргава) прежде всего стремился к тому, чтобы книга легко читалась. Я избегаю неожиданных поворотов; каждый раз, когда в книге упоминается новая концепция, я либо объясняю ее сразу, либо говорю, где буду объяснять. Основные концепции подкрепляются упражнениями и повторными объяснениями, чтобы вы могли проверить свои предположения и убедиться в том, что не потеряли нить изложения.
В книге приводится множество примеров. Моя цель — не вывалить на читателя кучу невразумительных формул, а упростить наглядное представление этих концепций. Я также считаю, что мы лучше всего учимся тогда, когда можем вспомнить что-то уже известное, а примеры помогают освежить память. Так, когда вы вспоминаете, чем массивы отличаются от связанных списков (глава 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% по купону — Алгоритмы
Грокаем* 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. Знакомство с алгоритмами
Как работает?
Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
Реализация алгоритма на 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. регрессия = прогнозирование ответа (в числовом выражении)