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

Что такое алгоритмы?

Алгоритм — это набор инструкций для решения какой-то задачи. Всё, что мы делаем: готовим утром кофе, идём на работу, пишем код — это исполнение определённых алгоритмов.

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

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

💡 Изучите алгоритмы

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

Востребованы ли алгоритмы на рынке фронтенд-разработки?

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

Кроме того, алгоритмы — частые гости на технических собеседованиях на мидловские и сеньорские позиции. Особенно любят добавлять в интервью алгоритмические секции крупные компании вроде Яндекса или Google.

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

  • Лишь 2% вакансий с опытом до года требуют знания алгоритмов и структур данных.
  • В вакансиях для разработчиков с опытом до шести лет этот навык упоминается в 10% случаев.
  • Почти каждая третья вакансия для фронтендеров с опытом более 6 лет содержит этот навык в требованиях к соискателю.

Какие задачи решают с помощью алгоритмов?

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

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

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

Разберём подробнее некоторые типовые задачи, в которых используют алгоритмы.

Сортировка данных

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

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

Сортировка вставкой помогает поддерживать отсортированность в уже существующем массиве при поступлении новых элементов.

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

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

А затем обновляем связи в списке:

Quicksort — одна из самых быстрых сортировок для использования на больших объёмах данных.

Как она работает: сначала мы выбираем в массиве любой «опорный» элемент. Затем сравниваем каждый из элементов с опорным. По результатам сравнений переставляем элементы в массиве так, чтобы слева от опорного были все элементы меньше него, а справа — больше или равны. После этого запускаем этот же алгоритм рекурсивно на левую и правую части массива, пока не придём к массиву из одного элемента.

Посмотрим на сортировку массива из девяти элементов. Сначала выбираем опорный элемент — 5. Затем перемещаем элементы меньше слева от него, а элементы больше — справа.

Теперь берём часть слева и выбираем новый опорный элемент — 3. Затем вновь перемещаем элементы меньше слева от него, а элементы больше — справа. Делаем так, пока полностью не отсортируем левую часть:

Когда закончим, повторим всё то же самое с правой частью:

Пример сортировки:

function quickSort(array, left, right) {
  left = left ?? 0;
  right = right ?? array.length - 1;

  const pivotIndex = partition(array, left, right);
  logIteration(array, array[pivotIndex], left, right);

  if (left < pivotIndex - 1) {
    quickSort(array, left, pivotIndex - 1);
  }

  if (pivotIndex < right) {
    quickSort(array, pivotIndex, right);
  }

  return array;
}

function random(min, max) {
    const interval = max - min;
    const shift = min;

    return Math.round(Math.random() * interval + shift);
}

function partition(array, left, right) {
  const pivot = array[random(left, right)];

  while (left < right) {
    while (array[left] < pivot) {
        left++;
    }

    while (array[right] > pivot) {
      right--;
    }

    if (left <= right) {
        [array[left], array[right]] = [array[right], array[left]];
        left++;
        right--;
    }
  }

  return left;
}

Есть множество других видов сортировок. Какой из них использовать — зависит от конкретной задачи.

Поиск в массиве

Найти что-то в массиве — довольно распространённая задача. Это может быть поиск целого объекта по его признаку. Например, когда нам нужно найти объект банковской карточки по id. Или это может быть проверка на вхождение. К примеру, мы можем узнать, разрешено ли показывать определённый контент пользователю. Для этого достаточно проверить его права в массиве прав, разрешающих просмотр.

Линейный поиск — самый распространённый, хотя и медленный, способ поиска в массивах и других коллекциях. Это довольно простой алгоритм, он перебирает все элементы до тех пор, пока не встретит нужный или не дойдёт до конца массива.

Как он работает: к примеру, мы хотим проверить, есть ли слово 'скрипт' в массиве ['веб', 'деплой', 'сервер']. Сначала мы посмотрим на 'веб' и сравним его с искомым словом. Они не равны, поэтому двигаемся дальше — к слову 'деплой'. С ним и 'сервер' ситуация такая же: сравнение их со 'скрипт'-ом вернёт false. А затем мы придём в конец массива. Это значит, искомого элемента в нём нет.

Проверка на вхождение слова с помощью include:

const words = ['веб', 'деплой', 'сервер'];
function checkIfInclude(word) {
  return words.includes(word);
}
checkIfInclude('скрипт'); // false

Если бы мы искали в массиве слово веб, то нашли бы его при сравнении с первым элементом массива и на этом закончили поиск:

Бинарный поиск — поиск, который можно вызывать только на отсортированных массивах данных. Он работает по методу indexOf: принимает элемент, который нужно найти в массиве, и возвращает либо его позицию, либо -1, либо null.

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

Бинарный поиск удобен для работы с большими отсортированными массивами. Представьте, что вам нужно найти пользователя в базе данных из миллиона человек. Если перебирать каждый элемент последовательно, вы потратите немало времени. Гораздо быстрее и проще сузить поиск, отбросив сразу половину элементов.

Простой пример бинарного поиска:

function binarySearch(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;

  while (left <= right) {
    const center = Math.floor((right + left) / 2);

    if (numbers[center] === target) {
      return center;
    }

    if (numbers[center] > target) {
      right = center - 1;
    } else {
      left = center + 1;
    }
  }

  return null;
}

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

Оптимизация кода

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

Переобходить DOM-дерево можно разными способами. Самый простой — поиск в ширину. Он хорошо подходит для поиска, если искомый элемент лежит «сверху» и дерево довольно широкое.

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

const root = document.body;
const resultElement = document.getElementById('result');

function traverse(node) {
  const result = [];
  const queue = [];

  queue.push(node);

  while(queue.length) {
    const currentNode = queue.shift();

    result.push(currentNode.localName);
    queue.push(...currentNode.children);
  }

  resultElement.innerHTML = result.join(' -> ');
}

traverse(root);

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

const root = document.body;
const resultElement = document.getElementById('result');

function traverse(node) {
  const result = [];

   function recursive(node) {
    result.push(node.localName);
    for (const child of node.children) {
      recursive(child);
    }
  }

  recursive(node);

  resultElement.innerHTML = result.join(' -> ');
}

traverse(root);

Отрисовка динамических списков и парсинг

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

Рекурсия также позволяет справиться с другой распространённой задачей — распарсить текст из HTML-документа без использования регулярных выражений. Например, если у нас есть такой текст:

<p>
Рекурсия заключается в том, что благодаря ей мы от <i>сложных задач</i> переходим к всё более и более <i>простым</i>, пока не найдём решение <b>каждой</b> конкретной маленькой частицы задачи.
</p>

С помощью рекурсии можно быстро перевести его в такой:

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

Всё, что для этого нужно сделать — переобойти DOM, рекурсивно вызывая парсинг.

Добавление данных в очередь

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

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

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

Вывод

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

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

Один из самых простых способов начать изучение алгоритмов — книги. Начать можно с «Грокаем алгоритмы», в ней Адитья Бхаргава простыми словами пишет о популярных концептах алгоритмостроения, хотя и не всегда применимых к фронтенду. А тем, кто не боится сложного академического языка, советуем прочитать книгу Дональда Кнута «Искусство программирования» о важнейших и базовых алгоритмах, которые мы используем. Можно сказать, что это своего рода «Библия» алгоритмов.

Больше материалов


«Доктайп» — журнал о фронтенде. Читайте, слушайте и учитесь с нами.

ТелеграмПодкастБесплатные учебники

Читать дальше

Случайное число из диапазона

Случайное число из диапазона

Допустим, вам зачем-то нужно целое случайное число от min до max. Вот сниппет, который поможет:

function getRandomInRange(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}
  1. Math.random () генерирует случайное число между 0 и 1. Например, нам выпало число 0.54.
  2. (max — min + 1): определяет количество возможных значений в заданном диапазоне. 10 - 0 + 1 = 11. Это значит, что у нас есть 11 возможных значений (0, 1, 2, ... 10).
  3. Math.random () * (max — min + 1): умножает случайное число на количество возможных значений: 0.54 * 11 = 5.94.
  4. Math.floor (): округляет число вниз до ближайшего целого. Так, Math.floor(5.94) = 5.
  5. ... + min: смещает диапазон так, чтобы минимальное значение соответствовало min. Но в нашем примере, так как min = 0, это не изменит результат. Пример: 5 + 0 = 5.
  6. Итак, в нашем примере получилось случайное число 5 из диапазона от 0 до 10.

Чтобы протестировать, запустите:

console.log(getRandomInRange(1, 10)); // Тест
JS
  • 7 сентября 2023
В чём разница между var и let

В чём разница между var и let

Если вы недавно пишете на JavaScript, то наверняка задавались вопросом, чем отличаются var и let, и что выбрать в каждом случае. Объясняем.

var и let — это просто два способа объявить переменную. Вот так:

var x = 10;
let y = 20;

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

function myFunction() {
  var z = 30;
  console.log(z); // 30
}
myFunction();
console.log(z); // ReferenceError

Это может создавать неожиданные ситуации. Допустим, вы создаёте цикл в функции и хотите, чтобы переменная i осталась в этой функции. Если вы используете var, эта переменная «утечёт» за пределы цикла и будет доступна во всей функции.

Переменные, объявленные с помощью let доступны только в пределах блока кода, в котором они были объявлены.

if (true) {
  let a = 40;
  console.log(a); // 40
}
console.log(a); // ReferenceError

В JavaScript блок кода — это участок кода, заключённый в фигурные скобки {}. Это может быть цикл, код в условном операторе или что-нибудь ещё.

if (true) {
  let blockScoped = "Я виден только здесь";
  console.log(blockScoped); // "Я виден только здесь"
}

// здесь переменная blockScoped недоступна
console.log(blockScoped); // ReferenceError

Если переменная j объявлена в цикле с let, она останется только в этом цикле, и попытка обратиться к ней за его пределами вызовет ошибку.

Читать дальше
JS
  • 30 августа 2023
Быстрый гайд по if, else, else if в JavaScript

Быстрый гайд по if, else, else if в JavaScript

Допустим, вы собираетесь идти на прогулку. Если на улице солнечно, вы возьмёте с собой солнечные очки.

Это можно описать с помощью оператора if.

let weather = "sunny";

if (weather === "sunny") {
  console.log("Возьму солнечные очки");
}

А если погода не солнечная, а, скажем, дождливая, вы возьмете зонт.

Этот сценарий можно описать с помощью if-else.

let weather = "rainy";

if (weather === "sunny") {
  console.log("Возьму солнечные очки");
} else {
  console.log("Возьму зонт");
}

Условный оператор if-else if-else

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

И всё это очень легко описывается кодом:

let weather = "sunny";
let time = "morning";

if (weather === "rainy") { // если дождь, то только так
  console.log("Еду на автобусе");
} else if (time === "morning") { // если не дождь и утро
  console.log("Еду на велике мимо пробок");
} else { // если второе не дождь и не утро
  console.log("Еду на машине");
}

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

🐈

JS
  • 30 августа 2023
Как исправить ошибки SyntaxError в JavaScript

Как исправить ошибки SyntaxError в JavaScript

Ошибки SyntaxError появляются, если разработчик нарушил правила синтаксиса JavaScript, например, пропустил закрывающую скобку или точку с запятой. Давайте посмотрим, что означает каждая ошибка и в чём может быть проблема.

Читать дальше
JS
  • 14 июля 2023
Как сделать простой слайдер на HTML и JavaScript

Как сделать простой слайдер на HTML и JavaScript

Вы сверстали сайт и сделали его красивым с помощью CSS. Осталось добавить интерактива, и можно добавлять проект в портфолио.

«Оживить» на сайте можно что угодно: меню, модальные окна, корзину, пагинацию… В этой статье мы разберём слайдер — посмотрим, как его сделать на чистом JavaScript. Слайдер пригодится для раздела с отзывами, фотографиями сотрудников, изображениями товаров или чего-нибудь ещё — всё зависит только от вашей фантазии и проекта.

☝ Мы покажем лишь один из возможных вариантов. Это не эталонное решение, да в разработке и не бывает единственно верного способа решить задачу. Но код точно работает, поэтому можете скопировать его в свой проект.

Читать дальше
JS
  • 20 июня 2023
Полезные команды для работы с Node.js

Полезные команды для работы с Node.js

Перед тем как рассматривать полезные команды при работе с Node.js, её необходимо установить.

Команды помогают узнать версию Node.js,

node -h — показывает список всех доступных команд Node.js.

node -vnode --version — показывает установленную версию Node.js.

npm -h — показывает список всех доступных команд пакетного менеджера npm.

npm -vnpm --version — показывает установленную версию npm.

Команда npm update npm -g позволяет обновить версию npm.

npm list --depth=0 показывает список установленных пакетов.

Команда npm outdated --depth=0 покажет список установленных пакетов, которые требуют обновления. Если все пакеты обновлены, список будет пустым.

npm install package — позволяет установить любой пакет по его имени. Если при этом к команде добавить префикс -g пакет будет установлен глобально на весь компьютер.

Команда npm i package является укороченной альтернативой предыдущей команды.

Если вы хотите установить конкретную версию пакета, воспользуйтесь префиксом @ с номером версии. Например, npm install package@1.0.1.

npm uninstall package — удаляет установленный пакет по имени.

Команда npm list package — покажет версию установленного пакета, а команда npm view package version — последнюю версию пакета, которая существует.

Для работы с пакетным менеджером также пригодится файл package.json, который должен лежать в директории, с которой происходит работа в консоли.

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

Кроме этого он ещё имеет скрипты, которые вызывают другие команды консоли. Например, для этого файла вызов команды npm start вызовет запуск задачи Grunt с именем dev. А команда npm run build вызовет скрипт build, который запустит задачу в Grunt с именем build.

Во время работы часто возникает необходимость установить некоторые пакеты. Если установить пакет с префиксом --save, то он автоматически запишется в package.json в раздел dependencies. Такая же команда с префиксом --save-dev запишет пакет в раздел devDependencies.

Что такое nvm

nvm (илиNode Version Manager) — утилита, которая позволяет быстро менять версии Node.js.

Чтобы её установить, достаточно запустить скрипт

curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.31.0/install.sh | bash

Теперь можно установить последнюю версию Node.js, например,5.0 с помощью команды nvm install 5.0. Чтобы начать использовать её, введите команду nvm use 5.0. Таким образом, можно быстро переключаться между версиями, например, для тестирования.

JS
  • 8 июня 2023
Как составлять регулярные выражения

Как составлять регулярные выражения

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

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

Зачем нужны регулярные выражения

Читать дальше
JS
  • 5 июня 2023
Проверка типа интерфейса в TypeScript

Проверка типа интерфейса в TypeScript

Проверка типов интерфейса — одна из ключевых возможностей TypeScript. Она помогает убедиться, что объект или класс содержат необходимый набор свойств и методов, указанных в интерфейсе. Благодаря проверке типов вы можете писать более надёжный код, ведь часть ошибок будет найдена ещё на этапе компиляции.

В чём разница между интерфейсами и типами

Читать дальше
JS
  • 30 мая 2023