Популярное
Свежее
Моя лента
Сообщения
Рейтинг
Курсы
Темы
Маркетинг
Сервисы
AI
Деньги
Личный опыт
Инвестиции
Карьера
Право
Мнения
Крипто
Показать все
vc.ru
О проекте
Правила
Реклама
Приложения
Панфилов Александр Юрьевич

Отзыв про книгу «Грокаем алгоритмы»

Отзыв про книгу «Грокаем алгоритмы»

Вводная часть

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

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

В процессе поиска мною была найдена книга, популярная среди программистов, — это «Грокаем алгоритмы». В ней описываются наиболее часто используемые алгоритмы в программировании и она, как раз, позволила мне актуализировать мои текущие познания и расширить кругозор алгоритмов. В процессе чтения книги, до меня дошло, что все алгоритмы запомнить у меня не получается, а зубрить их, чтобы потом через пару недель забыть, тоже не хотелось. То есть, простое чтение книги и выполнение всех упражнений полностью не поможет ее освоить. Все-равно через время то что было забудется. Как мне удалось решить данный вопрос и использовать потенциал книги по полной?

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

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

После того, как книга «Грокаем алгоритмы» была прочтена и по ней был составлен конспект в цифровом виде, то мне стало понятно, что это хорошая идея и ее надо дальше продвигать. Таким образом у меня получилось и актуализировать свои знания и использовать книгу на полную мощность. Теперь в дальнейшем мне не надо будет снова перечитывать книгу, а просто достаточно прочитать свои заметки по ней.

Алгоритмы, которым я нашел применение в своей практике.

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

Перейдем к самим алгоритмам, в книге для их написания использовался язык программирования python, я же использую javascript/typescript, поэтому мне было необходимо их реализацию на моем языке. Итак, давайте начнем:

Бинарный поиск

function binarySearch (arr, el) { let left = -1; let right = arr.length; while (right - left > 1) { const mid = Math.floor((left + right) / 2); if (arr[mid] === el) { return mid; } if (arr[mid] > el) { right = mid; } else { left = mid; } } return -1; }

Описание алгоритма, которые пометил для себя

  • устанавливаем границы справа и слева, где лево равняется -1, а право длине массива;
  • делаем цикл while, в условии которого вычитаем из правой границы левую, разницуа должна быть больше 1, если разница равна 1, то между правой и левой границей элементов больше нет;
  • далее описываю тело цикла.

примечание, среднее число - это индекс в массиве

  • находим среднее число в массиве путем складывания левой и правой границы и деления этой суммы пополам, если в результате решение получилось десятичное число, то округляем его в меньшую сторону. На javascript это можно сделать через Math.floor;
  • находим значение данного элемента с индексом (среднее число) в массиве и сравниваем со входящим, если они равны, то выводим текущий индекс массива;
  • если элемент в массиве с найденым индексом не найден, то дальше сравниваем значение данного элемента с индексом (среднее число) в массиве со входящим. Если первый элемент сравнения больше второго то присваиваем правой границе текущее значение индекса, в противном случае присваиваем левой границе текущее значение индекса;\
  • если цикл пройден, а значение не найдено, то его нет во входящем массиве и необходимо вывести -1;

Алгоритм дейкстры

const graph = {}; graph.a = {b: 2, c: 1}; graph.b = {f: 7} graph.c = {d: 5, e: 2}; graph.d = {f: 2}; graph.e = {f: 1}; graph.f = {g: 1}; graph.g = {}; function search (graph, start) { // таблица стоимости const costs = {}; // массив обработанных узлов const processed = []; // объект со значением узла, с которым ведем работу let neighbors = {}; // проверяем, что узел не стартовый и все значения его дочерних узлов проставляются Object.keys(graph).forEach(node => { if (node !== start) { let value = graph[start][node]; costs[node] = value || 10000 } }) // находим узел с наименьшей стоимостью let node = findNodeLowerstCost(costs, processed); while(node) { const cost = costs[node]; neighbors = graph[node]; Object.keys(neighbors).forEach(neighbor => { let newCost = cost + neighbors[neighbor]; // если новая стоимость меньше текущей, то заносим ее в таблицу if (newCost < costs[neighbor]) { costs[neighbor] = newCost; } }); processed.push(node); node = findNodeLowerstCost(costs, processed); } return costs; } function findNodeLowerstCost(costs, processed) { let lowestCost = 10000; let lowestNode; // если стоимость в узле меньше минимальной стоимости и узел ранее не был использован, то присваиваем эту ноду Object.keys(costs).forEach(node => { let cost = costs[node]; if (cost < lowestCost && !processed.includes(node)) { lowestCost = cost; lowestNode = node } }) return lowestNode; } console.log(search(graph, 'a'));

Описание алгоритма, которые пометил для себя

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

  • Принимается начальная точка от которой будет производится расчет
  • Состовляется таблица со значениями для тех вершин, в которые можно попасть из стартовой точки - это первый этап вычислений. Остальные вершины помечаем знаком бесконечности
  • На последующих этапах рассматриваем те вершины, в которые пришли из стартовой точки. Далее те вершины, куда можем дотянутся из текущих. И так далее, пока не дойдем до конечной точки. Если в процессе вычисления для определенной точки находится меньшая стоимость, то она заносится в таблицу

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

Бинарные деревья или графы

class BinaryTree { constructor() { this.root = null; } add (value) { const newNode = new Node(value); if (!this.root) { this.root = newNode; return; } let currentNode = this.root; while (currentNode) { if (newNode.value < currentNode.value) { if (!currentNode.left) { currentNode.left = newNode; return; } currentNode = currentNode.left; } else { if (!currentNode.right) { currentNode.right = newNode; return; } currentNode = currentNode.right; } } } preOrder(node, callback) { if (!node) { return; } if (callback) { callback(node); } this.preOrder(node.left, callback); this.preOrder(node.right, callback); } inOrder(node, callback) { if (!node) { return; } this.preOrder(node.left, callback); if (callback) { callback(node); } this.preOrder(node.right, callback); } postOrder(node, callback) { if (!node) { return; } this.preOrder(node.left, callback); this.preOrder(node.right, callback); if (callback) { callback(node); } } // обход в глубину traverseDFS(callback, method) { if (method === 'preOrder') { return this.preOrder(this.root, callback) } if (method === 'inOrder') { return this.inOrder(this.root, callback) } return this.postOrder(this.root, callback) } // обход в ширину traverseBFS(callback) { const queue = [this.root]; while (queue.length > 0) { const node = queue.shift(); if (callback) { callback(node); } if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } } class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } const myTree = new BinaryTree(); myTree.add(8); myTree.add(7); myTree.add(9); myTree.add(5); myTree.add(10); myTree.add(20); myTree.add(6); myTree.add(2); myTree.add(11); myTree.traverseBFS(node => { console.log(node) }) console.log('myTree', myTree); пример реализации графа, в котором может быть два и более узла const graph = {}; graph.a = ['b', 'c']; graph.b = ['f']; graph.c = ['d', 'e']; graph.d = ['f']; graph.e = ['f']; graph.f = ['g']; const search = (graph, start, end) => { let queue = []; queue.push(start); while(queue.length > 0) { const current = queue.shift(); if (!graph[current]) { graph[current] = []; } if (graph[current].includes(end)) { return true; } else { queue = [...queue, ...graph[current]]; } } return false }

Описание алгоритма, которые пометил для себя

Бинарное дерево - это структура данных, которая состоит графов, которые имеют значение и две ветки (право или лево). Есть два способа обойти такие графы: в глубину и ширину.

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

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

Динамическое программирование и принцып разделяй и властвуй

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

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

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

Стек и очереди

Стек - это такая структура данных, которая позволяет организовать следующий алгоритм: последним пришел, первым вышел

Очередь - это такая структура данных, которая позволяет организовать следующий алгоритм: первый вошел, первый вышел

В js стек и очередь можно организовать на массивах. Их главная задача это добавление/удаление элементов массива в начале или в конце очереди. Для реализации данного подхода можно использовать следующие команды:

  • pop - удаление последнего элемента из массива
  • push - добавление элемента в конец массива
  • shift - удаление первого элемента в массиве
  • unshift - добавление первого элемента в массиве

Для работы со стеком прекрасно подойдут следующие задачи, чтобы их вспомнить:

  • -разварачивание массива, на вход подается несколько аргументов, показанных ниже после реализации тела функции

const flatten = (...args) => { const result = []; const arguments = [...args]; while (args.length > 0) { const el = args.shift(); if (Array.isArray(el)) { args.unshift(...el); continue; } result.push(el) } return result; } // console.log(flatten(1, 2, [4,5], [[[6], 7]], [8]))

Отдельные алгоритмы, дополненные мной к тем, которых не было в книге

Debounce и throttle

debounce - алгоритм обертка над функцией, который позволяет сократить большое количество вызовов одной функции в течении короткого интервала времени. На практике это может быть вызов функции одна за одной в каком-то цикле или при изменении окна браузера (событие resize) или вводе данных в текстовое поле (событие onChange)

В данной реализации важно использовать function, чтобы передать this. В стрелочной функции this передать не получится

function debounce (callback, delay) { let timer return function(...arguments) { clearTimeout(timer) timer = setTimeout(() => { callback.apply(this, arguments) }, delay) } }

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

function throttle(callback, delay) { let isWaiting = false; let saveArgs = null; let saveThis = null; return function wrapper(...arguments) { if (isWaiting) { saveArgs = arguments; saveThis = this; return; } callback.apply(this, arguments); isWaiting = true; setTimeout(() => { isWaiting = false; if (saveThis) { wrapper.apply(saveThis, saveArgs); saveArgs = null; saveThis = null; } }, delay); } }

Вывод

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

Надеюсь вам было интересно и вы для узнали, что-нибудь новое. До встречи в последующих статьях и хорошего вам кодинга.

Больше статей в моем блоге. Спасибо, что дочитали и до новых встреч в следующих статьях.

Начать дискуссию