Разбираемся в алгоритмах и структурах данных. Доступно и понятно
Всем привет. Меня зовут Адам Леос, и я Senior Software Engineer в PlutoTV. Кроме основной работы, я активно участвую в развитии IT-сферы и повышении уровня разработчиков в целом. Например, я принимаю участие в хакатонах (как участник и как судья), пишу технические статьи, провожу вебинары и выступаю с докладами как приглашенный технический специалист в компаниях и как спикер на конференциях.
Темы для своих презентаций я подбираю так, чтобы это был не пиар себя/компании/технологии, а чтобы материал привнес что-то нужное, был полезен разработчику (желательно непосредственно сразу). Одна из таких тем — необходимость знания алгоритмов и структур данных. По определенным причинам среди разработчиков из стран СНГ бытует мнение, что эти знания не нужны и не важны. Спойлер! Это не так.
Для кого предназначена эта статья? Она будет полезна каждому, кто желает добиться одной (или нескольких, можно всех) из следующих целей:
- создавать качественные (производительные и надежные) продукты;
- получать значительно больше, чем в среднем по рынку;
- не иметь проблем с собеседованиями в лучшие компании мира;
- иметь возможность решать реально сложные задачи;
- просто разобраться в этих алгоритмах, но так, чтобы было доступно и понятно.
И совершенно не важно, какого вы уровня разработчик или каким направлением занимаетесь. Материал будет одинаково полезен как начинающим свой путь в разработке, так и опытным техническим лидерам.
Выступление на JSFest 2019 в Киеве
Статья будет базироваться на двух тезисах (и опровергать их):
- Первый — «Знать алгоритмы и структуры данных не нужно. Никакой пользы разработчик от этих знаний не получит». Мы поймем, почему это не так, и разберем примеры из реальной жизни, как я применял эти знания в нескольких компаниях и получал огромный прирост в производительности.
- Второй тезис для разработчиков, которые ушли немного дальше и считают так: «Вроде польза и может быть, но, чтобы ее получить, необходимо потратить очень много времени на изучение материала, который к тому же очень сложный». Для этого мы усвоим базовые знания и все необходимые вещи в самом начале этой статьи (поговорим о сложности алгоритма, нотации Big O, сортировках, самых популярных структурах данных и их использовании для оптимизации проекта).
Сложность алгоритма
Чтобы определять эффективность/неэффективность какого-либо кода и понимать, что и как мы можем улучшить, нам необходимо ввести единственное понятие, которое будет использоваться в статье. Это сложность алгоритма, то есть то, как будет расти расход ресурсов с увеличением размера входных данных. Сейчас мы проработаем это определение с разных сторон и приведем несколько примеров.
Сразу обращу ваше внимание на «ресурсы». Какими ресурсами мы оперируем в разработке? Очевидно, это время (то, насколько быстро будет выполняться наш алгоритм: дольше выполняем — больше времени тратим © Кэп). Но, к возможному удивлению многих разработчиков, еще один ресурс, которым мы часто оперируем (да, и во front-end-разработке тоже), — это память. Безусловно, работая за свеженьким MacBook Pro под последним Chrome, вы можете никогда и не столкнуться с проблемами перерасхода памяти (хотя и с таким неоднократно сталкивался, разработчики могут создать утечек от души), но память — такой же ценный ресурс, как и время. Особенно остро я ощутил это в последних нескольких компаниях, занимаясь разработкой под разные платформы типа Smart TV, игровых приставок и прочего, обладающего очень слабым железом (телевизор за $20 000 будет слабее вашего смартфона, что уж говорить о более дешевых моделях).
Теперь взглянем на синтетический пример (мы будем начинать с очень простых вещей и постепенно усложнять, в то же время переходя от синтетических примеров к реальной жизни). В этом примере будем читать сумму всех чисел в переданном массиве.
function sumNumbersInArray(array) {
let sum = 0;
array.forEach(number => sum += number);
return sum;
}
Здесь мы получили массив, объявили переменную-сумму, изначально равную 0, и запустили итерацию по массиву, беря каждый элемент массива и добавляя его к сумме. Все просто. Теперь давайте проанализируем: что будет, если мы вызовем эту функцию с массивом из пяти чисел [1, 2, 3, 4, 5]? Очевидно, мы сделаем пять итераций — за каждый элемент в массиве, чтобы взять его и добавить к сумме. А что, если массив будет состоять из десяти чисел? Логично, что потребуется десять итераций.
Паттерн очевиден: чем длиннее массив мы передаем, тем больше итераций мы делаем (соответственно, больше времени тратим на выполнение). Только что мы выразили сложность алгоритма, и, вспомнив определение выше (как будет расти расход ресурсов с увеличением размера входных данных), мы увидим, как же рос расход ресурсов в нашем случае (расход времени — делали больше итераций) с увеличением размера входных данных (массива-инпута). Так, у нашего алгоритма сейчас линейная зависимость от входных данных: за каждый элемент массива мы делаем дополнительную итерацию.
Нотация Big O
Лучше всего зависимости можно увидеть на графиках, и для описания таких зависимостей существует нотация Big O (это те самые O(n), O(log n) и прочие, которые мы рассмотрим чуть дальше). Если выразить, что это такое, одним предложением, то это будет звучать так: функция, которая описывает рост сложности алгоритма. Что за сложность алгоритма и как она может расти, мы примерно себе представили. Big O — это функция, которая этот рост описывает. Единственное уточнение: функция фигурирует здесь в математическом смысле, то есть как функция, которая используется для построения графика.
Давайте возьмем наш синтетический код из примера выше и построим график зависимости размера входных данных от количества итераций. По оси X (горизонтальной) мы возьмем рост входных данных от 0 до какого-то конечного числа n. Основными точками пускай будут 1, 100, 1000 и 10 000 единиц (элементов в массиве). По оси Y (вертикальной) будет рост количества операций также от 0 вверх с основными точками в 1, 100, 1000, 10 000 операций. Остается только провести линию по зависимости, что была у нас в алгоритме.
Как вы помните, на каждый элемент в массиве нам необходимо сделать дополнительную операцию сложения. Значит, если нам пришло 100 элементов, делаем 100 операций. Приходит 10 000 элементов — делаем 10 000 операций. Приходит n элементов — делаем n операций. Вот и та самая n в сложности O(n), которая также называется линейной. Все очень просто.
График линейной функции, или О(n)
Здесь все классно, но надо посмотреть с разных сторон и на других примерах, чтобы закрепить. Рассмотрим новый пример простойПосчитать (simpleCalculate). Мы ничего не принимаем и выполняем какие-то операции: вычисляем переменные, выводим что-то в консоль (просто чтобы было больше операций) и возвращаем разницу.
function simpleCalculate() {
const a = 1 + 2;
const b = 3 + 4;
console.log('calculating...');
return b - a;
}
Сложность такого алгоритма O(1) — постоянная, или константная. Здесь тоже все примитивно: наш алгоритм вообще ничего не принимает, поэтому никак не зависит от входных данных. Соответственно, даже если бы по какой-то причине в него передавали различные значения, он бы постоянно выполнял одни и те же операции, никак не увеличивая и не уменьшая расход ресурсов, поэтому сложность постоянная. На графике это показано еще доступнее:
График константной функции, или O(1)
Как видно на графике, у нас просто прямая линия: количество операций не растет и постоянно при любых значениях входных данных. Единственный важный для понимания момент здесь — в обозначении сложности O(1). Единица не указывает на количество операций и не будет меняться на другие числа, если алгоритм будет выполнять больше операций (как минимум наш алгоритм тоже выполняет больше операций). Единица здесь, так же, как и n в O(n), — это специальное обозначение, в этом случае константной сложности, и все.
А что случится, если мы будем принимать число как аргумент функции и добавлять его к нашей разнице? Какая сложность следующего кода?
function simpleCalculate(number) {
const a = 1 + 2;
const b = 3 + 4;
console.log('calculating...');
return b - a + number;
}
Сложность этого алгоритма также будет O(1). Несмотря на то что мы уже принимаем аргумент и используем его, все, что мы делаем, — одну дополнительную операцию по сложению. Какое бы большое, маленькое, дробное или отрицательное число ни было, мы всегда просто берем его и складываем одной операцией (естественно, при условии, что оно помещается в память, но это уже совсем другая история), то есть количество операций постоянно и не зависит от инпута.
Ну хорошо, а когда же зависимость появится? Проще всего будет показать при использовании массива, если бы мы принимали массив чисел и в конце вычисляли дополнительное число для сложения, итерируя по массиву.
function simpleCalculate(array) {
const a = 1 + 2;
const b = 3 + 4;
let additionalNumber = 0;
array.forEach(num => additionalNumber += num);
return b - a + additionalNumber;
}
Здесь-то у нас уже появляется снова линейная зависимость от размера входных данных, знакомая нам по первому примеру. Больше массив — больше операций мы делаем для вычисления дополнительного слагаемого. Помните сложность такого алгоритма? O(n).
Отлично, сейчас многим может показаться, что они раскусили систему: если входные данные — это массив, то сложность всегда линейная, О(n), и думать здесь нечего. Но мы можем посмотреть на такую версию предыдущего кода.
function simpleCalculate(array) {
const a = 1 + 2;
const b = 3 + 4;
const additionalNumber = array.length;
return b - a + additionalNumber;
}
В этот раз, все еще принимая массив аргументов, мы просто берем его длину как дополнительное число для сложения. А получение длины массива, хранящейся в отдельном свойстве, — мгновенная (та же константная) операция. Поэтому какой бы большой массив мы сюда ни передали, мы всегда будем мгновенно получать его длину и одной операцией добавлять к разнице. Итого это константная сложность, O(1).
Дальше у нас будет такой пример. Допустим, у нас есть массив чисел, и мы хотим все числа сложить со всеми — для этого у нас будет двойной вложенный цикл.
function notSoSimpleCalculate(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
array[i] = array[i] + array[j];
}
}
return array;
}
Сложность такого алгоритма уже значительно выше, за каждый элемент массива нам нужно сделать полную итерацию по массиву. То есть, имея лишь массив из пяти элементов [1, 2, 3, 4, 5], мы проделаем 25 операций. Применив простейшую математику, мы можем прийти к тому, что нам требуется квадрат операций на наш размер входных данных. Эта сложность называется квадратичной и обозначается О(n^2). График демонстрирует резко растущий расход ресурсов такого алгоритма.
График квадратичной функции, или О(n^2)
И если с вложенными циклами это очевидно, то здесь разработчика может поджидать резкое увеличение сложности, казалось бы, на ровном месте.
function mightBeSimpleCalculate(array) {
let total = 0;
array.forEach(num => {
const additional = array.indexOf(num) > 5 ? 5 : 1;
total = total + num + additional;
});
return array;
}
Как вы уже догадались, сложность такого алгоритма — O(n^2). По сути, здесь присутствует тот же вложенный цикл. Реализация метода indexOf под капотом — это обычный цикл, обход массива: так как индексы каждого элемента в массиве не хранятся, то его надо найти. Само собой, опытный разработчик об этом знает. Правда, если при этом опытный разработчик не знает алгоритмов, то, скорее всего, он этот код так и оставит. К слову, оптимизация здесь была бы суперпростой. В методе forEach второй аргумент — это индекс итерируемого элемента, и легким движением руки квадратичная сложность превращается в линейную, потенциально сохраняя нам большое количество ресурсов на выполнение.
function mightBeSimpleCalculate(array) {
let total = 0;
array.forEach((num, index) => {
const additional = index > 5 ? 5 : 1;
total = total + num + additional;
});
return array;
}
Последним важным моментом по этому разделу будет упоминание того, что нотация Big O указывает на самую быстрорастущую сложность алгоритма и игнорирует константные оптимизации. Давайте дополним наш пример с вложенными циклами еще одним линейным циклом:
function notSoSimpleCalculate(array) {
// дополнительно выводим каждый элемент в консоль
array.forEach(num => console.log(num));
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
array[i] = array[i] + array[j];
}
}
return array;
}
Сложность этого алгоритма будет не O(n + n^2), а просто квадратичная, O(n^2) — как раз потому, что квадрат будет расти несоизмеримо быстрее, делая влияние линейной сложности нерелевантной.
Пример роста в цифрах
Чтобы увидеть разницу, полезно взглянуть на сравнение количества операций в зависимости от сложности с одинаковыми размерами входных данных. Давайте смоделируем ситуацию, когда у нас на вход приходит массив с 10 000 (десятью тысячами) элементов, и определим, сколько операций проделают разные сложности:
- O(1), константная — 1 (одна) операция;
- O(log n), логарифмическая (например, бинарный поиск) — ~13 (чуть более тринадцати) операций;
- О(n), линейная — 10 000 (десять тысяч) операций;
- О(n^2), квадратичная — 100 000 000 (сто миллионов) операций;
- O(n^3), кубическая (если бы у нас был тройной вложенный цикл) — 1 000 000 000 000 (один триллион) операций;
- O(n!), факториал от числа n (поиск всех перестановок, пример — наивное решение очень популярной задачи коммивояжера) — 10 000 000 000 000 000 000 000 000... и еще очень много нулей. Для сравнения времени выполнения: вначале умрет Вселенная, через триллионы лет, и только потом алгоритм закончит выполнение.
Есть еще хорошая картинка, на которой графики различных сложностей расположены друг рядом с другом. На ней наглядно показаны различия:
Несколько полезных комментариев к картинке:
- Обратите внимание на зеленую зону, там присутствует как константная сложность, так и логарифмическая. Как вы уже видели выше в примере с числами, логарифмическая сложность очень эффективна. Она почти так же хороша, как и константная.
- Сложность O(n * log n) — это лучшая сложность универсальных сортировок. Мы к этому еще вернемся.
- Несмотря на то что квадратичная сложность находится в красной зоне («ужасной»), правильно будет упомянуть, что задачи бывают разные. И иногда вы ну никак не можете достать что-то из своих данных эффективнее, чем за двойной обход. Но это будет как раз тем местом, куда вы должны смотреть, когда захотите оптимизировать участки логики для повышения производительности. О методах и подходах мы поговорим чуть дальше.
- Важный момент — начало всех графиков. Очевидно, что все они начинаются из одной точки и их рост при небольших значениях еще не так сильно заметен и критичен. Именно поэтому необходимо тестировать свои алгоритмы не на одном пользователе/товаре/записи, а на максимально приближенном к реальности (а лучше на еще большем, с запасом). Иначе и O(1), и O(n^2), и даже О(n!) дадут вам один результат (единица в квадрате — единица, факториал единицы — единица).
Структуры данных
Прежде чем мы перейдем к примерам из реальной жизни, нам необходимо разобраться в двух самых популярных структурах данных, которые позволят применять различные эффективные оптимизации (а после этого будут и более сложные, но очень интересные структуры данных).
Прежде всего, давайте выразим, что такое структуры данных. Как и до этого, сделаем это в одном предложении: это определенный способ организации данных для максимально эффективного использования. Ничего сложного... У нас есть данные, которыми мы постоянно оперируем, и мы хотим их как-то организовать, чтобы затем эффективно использовать (оперировать).
Какие основные операции мы проворачиваем с данными? Все задачи в основном сводятся к следующим операциям:
- доступ (получить данные);
- поиск (найти данные);
- вставка (добавить данные);
- удаление (удалить данные).
И для всего этого у нас есть множество разнообразных структур данных, которые в чем-то лучше (более эффективные), а в чем-то хуже (менее эффективны), чем другие. На картинке ниже наглядно продемонстрированы некоторые структуры данных и то, с какими сложностями они связаны для каждой из четырех операций.
От разработчика требуется понимание, что есть разные структуры с разной эффективностью для разных задач. И знание структур данных подразумевает просто грамотное использование самой подходящей (максимально эффективной) структуры для решения какой-либо задачи. Надо часто искать? Берете это. Часто что-то вставляете? Берете другое. Приходится переставлять и удалять? Берете третье.
Дальше давайте поговорим о самых ярких представителях жанра в ежедневной разработке и об их грамотном использовании.
Массивы
Самой первой и, возможно, самой популярной структурой будут массивы. Давайте взглянем на основные манипуляции, которые мы производим с массивами, и проанализируем сложность. Вот есть у нас массив:
const arr = [1, 2, 3];
Что мы можем с ним делать? Очевидно, получить какой-то из элементов по индексу.
arr[1]; // 2
Как считаете, какова сложность этой операции? Кто предположил (или знал), что это O(1), оказался прав. Мы можем мгновенно по уникальному идентификатору (индексу) получить любой элемент массива (даже которого там нет, просто получим undefined). Так же можно и записывать по индексу.
arr[0] = 4; // [4, 2, 3]
Так делать (обычно) все же не стоит, ибо это чревато последствиями: можно получить «дырки» в массиве и прочие радости мутаций. Но это уже другая тема.
Ладно, давайте о методах: например, добавление элемента в конец массива.
arr.push(4); // [1, 2, 3, 4]
Сложность такой операции будет O(1).
Примечание. Добавление элемента в конец списка в JavaScript — константная операция, только не обычная, а «амортизированная». Что это значит? В JS мы не управляем памятью напрямую, но в языках программирования, где мы ей управляем, создание массива под наши нужды будет немного отличаться. Нам будет необходимо выделить память под массив определенного размера. То есть выделив память на массив длиной в 20 элементов и захотев добавить
Что у нас с удалением с конца массива?
arr.pop(); // [1, 2, 3]
Здесь мы имеем также O(1). Хорошо, а что с задачами добавления и удаления с начала массива?
arr.shift(); // [2, 3] arr.unshift(4); // [4, 2, 3]
Как многие знают (или догадались по подводке), здесь мы имеем другую картину. Вставка и удаление элемента с начала списка имеют сложность О(n). Все потому, что, манипулируя элементами в начале списка, мы должны обновить индексы всех последующих элементов. Если произошло удаление, то элемент, который был вторым, должен стать первым, вторым станет третий и т. д. То же самое происходит при вставке в начало: требуется обновить индексы всех последующих элементов.
Это, как вы сами видите, значительно менее эффективно. Именно поэтому разнообразные реализации стеков (stack) базируются на push & pop, а не на unshift & shift. Немного о стеках. Представьте стопку документов на подпись: тот, что лежит сверху, и берем первым для подписи. Если мы что-то добавляем, то кладем поверх всех, и он становится первым для следующей подписи. Это еще называется LIFO — last in, first out (последним вошел — первым вышел). Самым популярным применением в программировании будут разнообразные стеки операций: например, стек изменений в редакторе кода, чтобы иметь возможность быстро отменять изменения и возвращаться к предыдущим состояниям, или стек передвижения по страницам в браузере, чтобы быстро переходить по страницам.
Напоследок обязательно стоит упомянуть другие методы работы с массивами, которые имеют О(n)-сложность (как в примере с indexOf). Это будут практически все методы по работе с массивами — все, где мы что-то фильтруем, ищем, перебираем, переворачиваем и даже превращаем в строку (toString) — все это имеет O(n)-сложность.
Объекты
Вторая по популярности структура — объекты. Они используются для удобного хранения с возможностью быстрого манипулирования данными. Прежде чем мы взглянем на примеры, быстро рассмотрим операции. Их не много, и они помогут лучше понять последующие идеи и их преимущества.
const obj = {
id: 1,
name: 'Adam',
};
Так выглядит обычный объект. Мы можем получить любое из его свойств по «имени свойства», являющегося уникальным идентификатором. Это будет мгновенная операция вне зависимости от способа.
obj.id // 1 obj['name'] // ‘Adam’
Точно так же мы можем произвести перезапись свойства или даже записать новое, все будет константной операцией.
obj.surname = 'Leos'; obj['name'] = [];
Еще мы можем запросить все ключи или все значения объекта. Для этого существуют специальные методы, возвращающие нам массив значений.
Object.keys(obj) // ['id', 'name'] Object.values(obj) // [1, 'Adam']
Как вы можете догадаться, сложность этих методов — О(n): надо пройти по всем значениям, создавая из них массив.
Именно благодаря тому, что каждое свойство объекта — уникальный идентификатор и по этому уникальному ID мы можем мгновенно получать, записывать, удалять и обновлять данные, объекты часто используются как вспомогательная структура для многих оптимизаций через маппинг. Для многих это может быть знакомо по аналогам из других языков: словарю (dictionary) или «карте» (map). К слову, в ES2015 в JS тоже добавили объект Map — как раз для такого использования. Кто не знаком, он предоставляет методы для всех тех манипуляций, которые мы проводили раньше с объектом, имитируя Map. Например:
- Проверить, есть ли запись (has), вместо сравнения с undefined.
- Получить по ключу (get) и записать (set).
- Применить forEach сразу к map, итерируя на месте по связкам (ключ, значение).
- Прочие удобности.
Теперь давайте взглянем на применение. Начнем с решения очень популярной на собеседованиях задачи (например, ее устное решение спрашивали у меня в Microsoft). Задача — посчитать количество уникальных символов в строке. Решение тривиально и работает с любыми символами:
function countSymbols(string) {
// наша вспомогательная структура - карта уникальных символов
const map = new Map();
// запускаем обход по строке
for (let i = 0; i < string.length; i++) {
const char = string[i]; // берем каждый итерируемый символ
let newValue = 1; // и сколько раз мы его встретили, по-умолчанию один
// а если символ уже встречался, т.е. записан в карту, увеличиваем
if (map.has(char)) newValue += map.get(char)
// обновляем сколько раз текущий символ встретился
map.set(char, newValue);
}
return map;
}
Результатом вызова с какой-либо строкой будет карта по уникальным символам и их количеству:
Map(3) { a → 2, d → 1, m → 1 } // 'adam'
Map(4) { m → 1, i → 4, s → 4, p → 2 } // 'mississippi'
Map(10) { "Х" → 1, "а" → 1, 0 → 3, "с" → 1, " " → 1, "р" → 1, "@" → 1, "з" → 1, "н" → 1, "г" → 1 } // 'Ха0с р@зн0г0'
То есть мы создали карту и заполнили символами из строки, где каждый символ — уникальный идентификатор. Так мы могли мгновенно проверить его наличие в карте, получить значение и перезаписать его. И это работало для любого символа любого языка, специальных символов и даже пробелов. В общем, идею маппинга вы уловили: это создание вспомогательной структуры для определенных операций за О(1). Теперь давайте перейдем к их применению в реальной жизни.
Полезный маппинг в реальном мире
Здесь я хотел бы привести один из примеров, где я применял это в одной из предыдущих компаний. Почему именно его? Потому что это очень наглядная демонстрация ситуации, когда незнание алгоритмов и их сложности ведет к огромному падению производительности на ровном месте при приличном, на первый взгляд, коде. Здесь четко показано, как можно при минимальных усилиях (за полчаса) получить большой прирост производительности (почти в 100 раз).
Краткое описание проекта: делал я как-то видеостриминговое приложение на ReactJS + Node.js для альтернативных платформ типа Smart TV и игровых приставок.
«Типа Netflix», только еще с телевизионными Live-каналами
Была там одна задача, которую решили еще до моего прихода на проект. Ситуация была следующая. У нас в приложении есть тысячи шоу: какие-то сериалы, фильмы — весь видеоконтент приложения со следующей структурой (все упрощено и переименовано в угоду простоте восприятия и для удовлетворения NDA, все совпадения случайны):
const shows = [
{
id: 1,
name: 'Rick and Morty',
categories: [
'Comedy',
'Animated',
'Science',
],
data: 1001010101001011,
},
{/.../},
{/.../},
{/.../},
{/.../},
];
То есть массив из множества объектов, представляющий отдельное шоу и хранящий информацию по этому шоу, — стандартные ID, name и прочее.
Ну и в каких-то моментах мы получаем другой массив «забаненных» шоу. По определенным причинам мы не хотим показывать это шоу пользователю: конкретно что-то с пользователем, или канал сегодня решил не показывать это, или вообще там проблемы с транслированием именно на этом канале именно для этого пользователя и прочие мутные бизнес-причины. У нас есть массив других объектов, хранящих немного информации, достаточной для бана каких-то шоу «на месте».
const bannedShows = [
{
id: 1,
categories: [
'Comedy',
'Animated',
'Science',
],
},
{/.../},
{/.../},
{/.../},
];
И вот код, как это было решено:
function ineffectiveBanning(shows) {
// начинается обход всех шоу
shows.forEach(show => {
// берется ID каждого
const { id: showID } = show;
// запускается обход забаненных шоу
bannedShows.forEach(bannedShow => {
// теперь берем ID каждого забаненного
const { id: bannedShowID } = bannedShow;
// сравниваем ID и если совпадение - помечаем шоу как забаненное
if (showID === bannedShowID) {
show.isBanned = true;
}
});
});
};
Что здесь происходит? Начинается цикл по всем шоу, берется ID каждого из этих шоу и запускается обход забаненных шоу с целью найти совпадения. Если совпадение есть, шоу должно быть забанено (условно помечаем флагом isBanned).
Чей-то опытный глаз уже мог заметить проблему (и возможно, нервно задергаться). Вообще, здесь совершается слишком много ненужных операций: мы для каждого шоу запускаем итерацию по забаненным, это очень большая и лишняя нагрузка. А ведь оптимизируется это очень легко, нам нужна лишь карта забаненных ID, с помощью которой мы бы могли мгновенно проверять, забанено шоу или нет. Реализовать это можно как с помощью обычных объектов, так и с помощью Map или даже Set (Set — это просто набор, то есть оперируем как с Map, только никаких значений записям не присваиваем, просто добавляем уникальные ключи, чтобы они были в наборе, и выполняем мгновенные проверки на их наличие):
function effectiveBanning(shows) {
const bannedShowsIDs = new Set();
// наполнили Set забаненными ID
bannedShows.forEach(({ id }) => bannedShowsIDs.add(id);
shows.forEach(({ id }) => {
// если ID текущего шоу присутствует в сете забаненных - помечаем его
if (bannedShowsIDs.has(id)) show.isBanned = true;
});
};
Что изменилось: мы вынесли вложенный цикл итерирования по забаненным шоу наружу и проходим по нему всего один раз для заполнения нашего Set, который будет набором всех забаненных ID с возможностью мгновенно проверять, есть ли там определенная запись. В итоге мы не запускаем множество ненужных циклов внутри обхода всех шоу, а делаем лишь мгновенную проверку на наличие итерируемого шоу в списке (Set) забаненных. И если совпадение есть, то шоу должно быть помечено как забаненное.
Это можно реализовать как еще короче, так и более развернуто и доступно. Можно использовать объект вместо Set и просто делать запись в объект, где ключом будет тот же уникальный ID забаненного шоу, а значением — что угодно, то же булево true. И затем для проверки, забанено ли итерируемое шоу, достаточно «постучаться» в объект по ID, и мы получим либо true, что будет значить, что шоу надо банить, либо undefined, а значит, шоу в забаненных нет, пропускаем.
Отлично. Если с оптимизацией времени вроде бы все понятно (делай меньше операций, опирайся на сложность, и будет тебе благо), то что же с памятью?
Память в реальном мире
А с памятью все тоже просто (хоть и менее прозрачно). В качестве примера я буду использовать оптимизацию, которую я сделал уже на текущем проекте в PlutoTV (тоже видеостриминговое приложение на React под телевизоры и приставки).
Был вот такой красивый и функциональный код:
function enchanceApiResponse(apiResponse) {
const channels = apiResponse.channels
.filter(filterEmptyTimelines)
.map(addIdentificator)
.map(modifyImages)
.map(removeParams)
.map(setSession)
// more code
}
Здесь получали какой-то ответ с каналами и прочим и как-то подгоняли под свои нужды: фильтровали, что-то добавляли, что-то удаляли, что-то перемещали. Сделано это изящной и грамотной цепочкой с отдельным методом под каждую операцию.
Кто уже увидел проблему для памяти? Что делают методы filter и map? Возвращают новый массив, под который необходимо выделить память, возможно, много (возможно, непозволительно много для некоторых платформ). А существует этот массив лишь для того, чтобы по нему запустить новый цикл и провернуть другую операцию с теми же элементами, что и в предыдущем цикле. Какое расточительство памяти на ровном месте!
Исправить это можно очень просто, заменив все на один обход. Например, с помощью reduce:
function enchanceApiResponse(apiResponse) {
const channels = apiResponse.channels.reduce((acc, channel) => {
if (!hasEmptyTimelines(channel.timelines)) {
acc.push(
setChannelURL(reduceImagesObject(addIDToChannel(channel)));
);
}
return acc;
}, []);
// more code
}
Идея, как видите, очень проста. Мы имеем один reduce (можно даже заменить фильтрацию, просто не наполняя аккумулятор по условию). Естественно, можно записать как короче, так и размашистее, кто как любит. Суть в том, что мы не выделяем кучу памяти под новые массивы, которые даже толком не используем. Эта маленькая оптимизация позволила сохранить от 10% до 30% расхода памяти приложения в зависимости от старины девайса. Что очень много: 30% для одного места, когда все приложение еще должно где-то работать.
Сортировки
Еще очень полезно будет разобраться с сортировками. Сразу скажу, что необходимость реализовывать какую-то свою уникальную сортировку у вас будет появляться крайне редко (а то и вовсе не случится за всю карьеру), так как в каждом языке программирования присутствуют довольно хорошо оптимизированные методы сортировки (отличным примером будут оптимизации array.sort() в JavaScript, которые мы обязательно разберем дальше). Но сортировки вне зависимости от необходимости их реализовывать — это очень классный пример алгоритмов и балансировки между расходами времени и памяти. Так что давайте взглянем на две самые популярные сортировки с очень разными расходами ресурсов.
Первым делом мы посмотрим на знакомую многим сортировку пузырьком (Bubble Sort). Идея этой сортировки в том, чтобы, проходя по массиву, находить самый большой элемент и «протаскивать» его до конца массива. Очевидно, чтобы отсортировать таким образом, когда за один обход мы дотаскиваем только один самый большой элемент, нам потребуется n обходов массива (где n — длина массива). А когда нам необходимо сделать n обходов, каждый из которых заключается в полном обходе массива, это O(n^2)-сложность. Ну вы и сами уже знаете.
Давайте посмотрим на визуализацию, а затем погрузимся в реализацию.
Сортировка пузырьком, O(n^2)
Как вы увидели, суть протаскивания примитивна: это прохождение по массиву, определение текущего и последующего элементов и их сравнение. Если левый больше правого, меняем их местами и берем следующий. Таким образом, мы либо постоянно двигаем самый большой элемент вправо, пока не доведем до конца массива, либо же, наткнувшись на больший элемент, чем текущий, просто идем дальше и оперируем теперь новым самым большим.
В коде все будет тоже очень просто.
function bubble(arr) {
const length = arr.length;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - i - 1; j++) {
const current = arr[j]; // текущий элемент
const next = arr[j + 1]; // следующий
// если текущий больше следующего, меняем их местами
if (current > next) {
arr[j] = next;
arr[j + 1] = current;
}
}
}
return arr;
}
Бесполезна ли эта сортировка, имеющая аж квадратичную сложность, когда есть более быстрые универсальные сортировки? Отнюдь. Как мы могли наблюдать, у сортировки пузырьком (как и у подобных ей, типа сортировки вставками) есть одно довольно важное преимущество — расход памяти. Здесь нам требуется лишь одна вспомогательная переменная для смены мест двух элементов, то есть константная сложность по памяти. Это огромная разница по сравнению со следующей быстрой универсальной сортировкой — сортировкой слиянием. Давайте взглянем на нее.
Сортировка слиянием, O(n * log n)
С первого раза непросто понять, что происходит, но мы сейчас все проработаем. Идея сортировки слиянием состоит в том, чтобы разбивать массив пополам на пару новых массивов (и каждую половинку снова пополам, и те тоже пополам), пока у нас не получатся массивы, состоящие лишь из одного элемента. Затем мы начинаем сливать их обратно в единый массив попарно, как и разбивали. Таким образом, мы можем очень быстро наполнять массив, на месте же его и сортируя, просто принимая решение, какой из элементов на каждом этапе вставлять (то есть вставляем все время меньший элемент и получаем отсортированный по возрастанию массив).
Благодаря постоянной разбивке пополам и попарному слиянию сложность этой сортировки — O(n * log n), то есть длина массива (надо как минимум раз полностью пройти по массиву), умноженная на логарифм от длины (сложность постоянного деления пополам). Сейчас взглянем на код и на еще одну визуализацию, и все должно стать понятно.
Здесь основной код, который будет в то же время использоваться рекурсивно, для разбивки массива пополам и сортировки этих двух половин. (Сам метод сортировки разберем немного позже).
function mergeSort(unsortedArray) {
// условие выхода из рекурсии
// если переданный массив имеет менее двух элементов - нечего сортировать
if (unsortedArray.length < 2) {
return unsortedArray;
}
// находим центр при помощи побитовой операции сдвига на один бит вправо
// аналог деления на два и округления вниз, только эффективнее и элегантнее
const middle = unsortedArray.length >> 1;
const left = unsortedArray.slice(0, middle); // левая часть
const right = unsortedArray.slice(middle); // правая часть
// вся магия сортировки в этом методе merge
return merge(
mergeSort(left), mergeSort(right)
);
}
Посмотрим на еще одну визуализацию, на которой хорошо видно, как массивы разбиваются и затем попарно сливаются обратно. Сразу после визуализации перейдем к методу merge.
Еще одна отличная визуализация сортировки слиянием
В чем будет заключаться наша логика слияния? У нас приходят два массива: левый и правый. Оба либо уже отсортированы (см. логику выше), либо просто состоят из одного элемента. Теперь нам нужно начать обход по обоим (достаточно одного обхода с двумя указателями: первый указывает на итерируемый элемент левого массива, второй — на итерируемый элемент правого массива) и брать меньший из двух элементов, закидывая его в новый массив, который мы вернем как отсортированный.
function merge(left, right) {
const resultArray = []; // отсортированный массив, который мы наполним и вернем
let leftIndex = 0; // указатель для обхода левого массива
let rightIndex = 0; // указатель для обхода правого массива
// обходим, пока не закончили хотя бы один из массивов
// (значит во втором все оставшиеся элементы точно больше)
while (leftIndex < left.length && rightIndex < right.length) {
// если левый элемент меньше правого
if (left[leftIndex] < right[rightIndex]) {
resultArray.push(left[leftIndex]); // добавляем его в массив
leftIndex++; // инкрементируем указатель, чтобы ссылаться на следующий эл-нт
} else { // иначе правый эл-нт больше, делаем тоже самое, только с правым
resultArray.push(right[rightIndex]);
rightIndex++;
}
}
// возвращаем массив, что мы наполняли и добавляем в него все, что не допрошли
return resultArray
.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
Думаю, здесь уже все ясно. Последним моментом будет то, что нам достаточно пройти до конца хотя бы один массив, потому что все оставшиеся непройденные числа будут точно больше, их надо просто добавить в конец нашего отсортированного массива. (Это происходит в конце кода, где мы сливаем остатки методом concat.)
Сейчас вы и сами видите, что более быстрая сортировка требует значительно больше памяти (выделяется большое количество памяти под все эти новые массивы, которое не идет ни в какое сравнение с константным расходом сортировки пузырьком).
Так что теперь мы можем качественно понять, что за оптимизации скрыты под капотом у array.sort(). Несмотря на то что имплементации могут отличаться от браузера к браузеру (и даже от версии к версии), глобальная идея заключается в том, чтобы использовать сортировку слиянием и быструю сортировку (также O(n * log n)) в зависимости от типа данных в массиве. Но массив не разбивается на подмассивы до одного элемента, как в нашей реализации. Вместо этого разбивание останавливается на 10 элементах, и уже к этим массивам из 10 элементов применяется сортировка вставками (аналог пузырьковой, O(n^2)). И лишь после этого начинается алгоритм слияния / быстрой сортировки. Таким образом, экономится очень много памяти (не создается целая куча лишних массивов) и практически нет проигрыша по быстродействию (сортировка вставками довольно эффективна на небольших массивах). Вот и чудесный пример балансировки между быстродействием и расходом памяти.
Важное послесловие о сортировках: я не просто так несколько раз писал, что сортировка слиянием и быстрая сортировка — это лучшие универсальные сортировки. То есть они будут стабильно хорошо работать в любых ситуациях с любыми данными (естественно, в пределах разумного). Хотя да, существуют разные сортировки со сложностью лучше, чем O(n * log n): например, radix sort. Но их применение специфично и не является универсальным. Хотя такие сортировки, само собой, широко применяются, просто они эффективны в конкретных ситуациях.
Выводы
- Вам не нужно знать все алгоритмы и структуры данных. Самые необходимые знания, дающие больше всего пользы, в то же время являются и самыми простыми в освоении.
- Нет необходимости помнить все реализации, вы даже можете забыть какие-то самые важные. Достаточно один раз разобраться в них, чтобы иметь представление о возможностях.
- Анализируйте ваши алгоритмы. Задумывайтесь над их эффективностью. Чем более эффективный код вы создаете, тем производительнее и надежнее будет ваш продукт (и тем круче вы станете как разработчик).
Полезные материалы
Теория:
- Оценка сложности алгоритма;
- Асимптотический анализ алгоритмов;
- Структуры данных для самых маленьких;
- The complexity of simple algorithms and data structures in JS;
- Introduction to Data Structures and Algorithms.
Практика:
Материал тесно перекликается с моими выступлениями, поэтому также рекомендую посмотреть видеозапись выступления (презентация в Казахстане на русском). Также я очень хотел бы еще рассказать о графах, деревьях, поиске и прочих интересных и важных моментах, но это увеличит объем текущей статьи минимум в три раза, поэтому поговорим о них отдельно в следующей публикации.
