Вводная часть
Всем привет, меня зовут Александр, я являюсь фронтенд разработчиком и в сегодняшней статье хотел поднять такую тему, как алгоритмы. Знаю, что по ней написано и сказано уже много, но хочется поделится с обществом своей точкой зрения.
За четыре года работы на стороне 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);
}
}
Вывод
В этой статье я попробовал описать свое виденье работы с технической литературой, чтобы использовать ее потенциал на полную мощность. Преимущество этого подхода в том, что теперь для того, чтобы освежить знания, то мне не нужно снова перечитывать всю книгу, а только прочитать свои конспекты.
Надеюсь вам было интересно и вы для узнали, что-нибудь новое. До встречи в последующих статьях и хоршего вам кодинга.
