JavaScript Algorithms. Що? Де? Коли?

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Бадьорого дня. Мене звуть Олександр Назаренко і я, здебільшого, front-end розробник в компанії United Software, хоча інколи заглядаю і на back-end. Мене можно знайти на DOU або LinkedIn. Раніше я поміщався в межі внутрішніх техтоків, але, самі розумієте, з цими карантинами складно зберігати форму, тому я почав розтікатися назовні :-) Ніколи не розділяв поглядів деяких спеців з різних сфер про те, щоб не ділитися знаннями і досвідом з іншими, а тим більше, з менш досвідченими колегами. Благо, в IT з цим краще, хоча то все залежить від компанії і людей в ній. От сьогодні якраз той день, коли я вирішив поділитися деякими своїми думками, дослідженнями і спостереженнями.

Ця стаття містить інформацію щодо алгоритмів, їх складності, застосування і розуміння, як взагалі, так і трішки з точки зору front-end, бо тема дуже велика і може бути проєктована на будь-яку сферу діяльності, яка має справу з даними.

Сподіваюся, ця стаття буде цікава всім, хто замислювався над такими глобальними питаннями: «Що таке алгоритми?», «З якого боку до них підійти?», «Де вони в моєму JS-коді?» і так далі. На такі теми існує чимало статей і доповідей, однак всі ми сприймаємо інформацію по-своєму, і можливо, сказане моїми словами буде комусь зрозуміліше і легше до сприйняття. Та і ніхто не забороняє потім копнути глибше. Приємного занурення в тему і хай нам Тюрінг допомагає.

Використання алгоритмів для роботи з великими даними

Для розгляду теми алгоритмів взагалі і їх використання в світі JS зокрема, варто спочатку обговорити деякі головні поняття. Почнемо з твердження, що дійсно освоїти алгоритми — значить зрозуміти їх відносно структур даних. Це як дві складові одного цілого, адже без структур даних неможливо виконувати маніпуляції над даними, а не маючи алгоритмів, ми не маємо самих маніпуляцій. Тож дамо визначення для цих двох понять.

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

Структури даних (на високому рівні) — це методи зберігання та організації даних, які полегшують зміну, навігацію та доступ до них. Структури даних визначають спосіб збору даних, функції, які ми можемо використовувати для доступу до них, та зв’язки між даними.

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

Структури даних дозволяють:

• керувати та використовувати великі набори даних;
• здійснювати пошук певних даних у базі даних;
• розробляти алгоритми для конкретних програм;
• обробляти кілька запитів користувачів одночасно;
• спрощувати та пришвидшувати обробку даних.

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

Мабуть, на цьому моменті вже зрозуміло, що структури даних є складовою алгоритмів, а алгоритми — складова процесу використання даних. Ця синергія і дозволяє нам ефективно маніпулювати астрономічними об’ємами даних, не витрачаючи на це роки роботи обчислювальної техніки.

Складність алгоритму. Нотація BigO

Говорячи про алгоритми та машиногодини, що перетікають в машинороки, варто приділити увагу такому поняттю як складність та за яким критерієм алгоритми прийнято групувати.

У поняття складності алгоритму входить декілька складових: логічна та статична складність, часова складність та ємнісна складність. Перші дві ми цього разу розглядати не будемо, лише зауважимо, що це, відповідно, кількість людино-місяців, витрачених на створення алгоритму та довжина опису алгоритмів (кількість операторів). Кому цікаво покопати глибше — вперед, в теорію алгоритмів та математичну логіку.

Далі сконцентруємося на інших двох складових і під складністю алгоритму матимемо на увазі оцінку величини часу та об’єму пам’яті для, власне, виконання цього алгоритму. Адже розуміння складності дозволяє вибрати найбільш оптимальний алгоритм для вирішення конкретної задачі при використанні обмежених ресурсів. А ресурси обмежені завжди. Тож найбільшу увагу приділяють тому, як змінюється кількість операцій для виконання алгоритму при збільшенні вхідних даних, які прийнято позначати літерою n. Залежність однієї величини від іншої є функцією, яка добре візуалізується. Тут і з’являється нотація Ландау або BigO. Вона, як і багато чого, що не з першого разу вкладається в голові, прийшла в програмування від математиків і дозволяє певною мірою порівняти і згрупувати алгоритми.

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

Джерело

Як можна бачити на графіку, є абсолютно жахливі зростання кількості витрат часу при не такому вже і великому обсязі даних. Пропоную читачеві витратити певний час, щоб роздивитися і проаналізувати форми кривих і кольорове зонування груп, які варто застосовувати на практиці. З прикладами кожної групи ми познайомимося далі.

Раджу звернути увагу, що при малих кількостях даних, всі групи мають відносно однакову кількість операцій. Тож пам’ятати про складність — важливо, але важливіше тримати в голові ваші реальні задачі і ті об’єми даних, з якими ви працюєте на проєктах. Не варто ускладнювати там, де нескладно.

(я говорю про ось цю частину, коло початку координат)

З загальною термінологією ознайомилися, значить можна познайомитися з прикладами кожної групи (джерело опису груп).

O (1) — час роботи алгоритму не залежить від обсягу вхідних даних. Прикладом такого алгоритму буде:

Визначення значення першого елемента масиву.

function getFirst(array){
    return array[0]
}

Залежність від об’єму даних відсутня. Якою б довжина масиву не була, перший елемент повертатиметься за однаковий час.

Виконання функції, в яку не передаються аргументи (наприклад, вивід якоїсь інформації в консоль).

function showSumTwoAndThree(){
    console.log("Sum:", 2+3);
}

Час виконання подібних алгоритмів постійний для будь-якої кількості даних, графік паралельний вісі абсцис (графіки побудовані за допомогою цього інструменту):

O (n) — час роботи алгоритму лінійно зростає зі збільшенням оброблюваних елементів (лінійна складність); приклад — алгоритм пошуку найбільшого елемента в невідсортованому масиві.

function getMax(arr){
let temp = 0;
arr.forEach((element) => {
  if (temp < element) {
    temp = element;
  }
});
return temp;
}

або операція з кожним елементом масиву:

function logEachElement(arr){
arr.forEach((element) => {
  		console.log(`Element value: ${element}`);
});
}

В останньому випадку навіть немає потреби у виділенні пам’яті для зберігання максимума.

Графік виходить з нуля під 45 градусів — абсолютна пряма залежність.

O (log n) — час роботи алгоритму зростає пропорційно логарифму кількості оброблюваних елементів (логарифмічна складність); приклад — бінарний пошук у відсортованому масиві.

function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);

        if (sortedArray[middle] === key) {
            return middle;
        } else if (sortedArray[middle] < key) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }
    return -1;
}

Добре видно різницю в порівнянні з лінійним пошуком (який входить в групу складності O (n)):

Відповідно, логарифмічний графік:

O (n²) — час роботи алгоритму зростає пропорційно квадрату кількості оброблюваних елементів (квадратична складність); цикл в циклі. Приклад — алгоритм сортування вставками, що виконує два вкладені цикли перебору масиву.

let insertionSort = (inputArr) => {
   let length = inputArr.length;
   for (let i = 1; i < length; i++) {
       let key = inputArr[i];
       let j = i - 1;
       while (j >= 0 && inputArr[j] > key) {
           inputArr[j + 1] = inputArr[j];
           j = j - 1;
       }
       inputArr[j + 1] = key;
   }
   return inputArr;
};

Або кепський варіант перевірки масиву на наявність дублікатів:

const hasDuplicates = function (num) {
    for (let i = 0; i < nums.length; i++) {
        const thisNum = nums[i];
        for (let j = 0; j < nums.length; j++) {
            if (j !== i) {
                const otherNum = nums[j];
                if (otherNum === thisNum) return true;
            }
        }
    }
    return false;
}

До речі, якщо було б три вкладених цикли, то мали б уже складність O (n³) і т. д. Завжди можна зробити ще гірше.

O (cⁿ) — час роботи алгоритму зростає пропорційно експоненті кількості оброблюваних елементів (експоненційна складність); приклад — знаходження всіх підмасивів в масиві:

​​function getCombinations(array) {
    function fork(i, t) {
        if (i === array.length) {
            result.push(t);
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }
    let result = [];
    fork(0, []);
    return result;
}

O (n!) — час зростає пропорційно факторіалу від кількості елементів. Прикладом є знаходження всіх можливих перестановок даних. Якщо хочете підвищити програму, запустіть вказаний код для 10000 елементів:

function nFacRuntimeFunc(n) {
  for(let i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

Для трьох останніх груп графіки виглядатитуть схоже, однак найекстремальніше наростає група з факторіальною залежністю.

Усе це виглядає дуже цікаво і страшно, але якось треба все розкласти в голові для хоча б поверхневої оцінки. Тут можна скористатися таким шаблоном:

• Отримання елемента колекції — це O (1). Будь то отримання за індексом в масиві, або за ключем в словнику нотації BigO, це буде O (1).
• Перебір колекції — це O (n)
• Вкладені цикли по тій же колекції — це O (n²), On (n³).
• Розділяй і володарюй (Divide and Conquer), як з бінарним пошуком, завжди O (log n).

Вибір алгоритму для вирішення задачі. Як обрати

А тепер про те, як же жити далі. Для того, щоб зменшити кількість сивого волосся при виборі як структури даних для вирішення задачі, так і алгоритму для роботи з даними, варто не забувати, що якою б глобальною задача не виглядала, її можна і треба ділити на елементарні складові, для яких людство вже має розв’язок. Атомарними операціями з даними можна назвати: вставку даних, читання, видалення, пошук. В залежності від того, в яку структуру організовані дані, ці операції виконуються з різною ефективністю. Є табличка з переліком часто вживаних структур і перевагами мов:

У світі JS нам здебільшого трапляються дані, організовані у масиви і об’єкти, відтак, таблички Array та Hash Table — наші компаньйони. Черги, дерева та списки є похідними типами і створюються силами розробника для рішення специфічних задач. Якщо буде зацікавленість в тому, щоб розібрати, як ті структури реалізувати на JavaScript, то можна висвітлити це в одній з наступних статей, бо ця і так не маленька. Те ж саме стосується і різних алгоритмів сортування і деяких популярних задачок типу розвертання рядку, знаходження спільних кратних і т. д.

До речі, спостережливий читач може задатися питанням: «А що це у нас в одних випадках О, а інших якась інша літера?». І це дуже похвальна цікавість. Трішки роз’яснень:

О — позначається найгірший випадок, наприклад, при лінійному пошуку наш елемент знаходиться в самому кінці масиву і треба пройти по всім елементам, щоб до нього дійти. Для групування за BigO якраз такі випадки і беруться.

Θ — середньої кепськості випадок. Якраз такі дані найчастіше на практиці і зустрічаються.

Ω — найкращий випадок, наприклад, хотіли знайти елемент лінійним пошуком, а цей елемент виявився найпершим.

Тож, з огляду на переваги тієї чи іншої структури і в залежності від операцій, які ви будете виконувати над даними, можливо, варто одну структуру перетворити в іншу або/і створити допоміжний map-об’єкт для оптимізації роботи програми. Дивимося на дані в задачі, прикидуємо операції, не соромимося підглядати в табличку, жонглюємо структурами.

Першочергові оптимізації

Найголовнішою складовою підвищеної часової складності, яку добре видно неозброєним оком, є вкладені цикли. Бачите їх? Є ймовірність, що елементів буде 1000+? Пора до роботи.

Наприклад, поміряємо час виконання лаконічного коду з циклом на 10000 елементів:

При кожному перезапуску цифри можуть відрізнятись, але нас цікавить порядок числа — у нас це менше 1 мс.

Докинемо всередину цикл з меншим числом ітерацій, наприклад, випадок, коли у нас є список і для кожного елементу списку (попередній цикл ми проходимо по певному набору даних):

Трішки гірше, але не так, щоб дуже помітно.

А якщо ще один цикл? Чому би і ні:

А як ще один, на трішки — 10 пробіжок. Хіба ж то страшно? Та трішки є:

Починали з часу, який на межі похибки вимірювання, а прийшли до 7 з гаком секунд.

Виглядає неправдоподібно? 4 цикли — зразу видно кримінал. Але ж немає жодної гарантії, що на проєкті починалось з простого масиву, наприклад, кольорів товару, а потім ті кольори перейшли в один з типів фільтрів товару. А ті фільтри увійшли в групу додаткових опцій фільтрації. А ті додаткові фільтрації тільки на товарах певної категорії, наприклад, літнього одягу. І шлях отримання і відображення даних таких глибин може цілком реально згенерувати такі часові затрати. Тому завжди намагайтеся мінімізувати кількість вкладених циклів. Принаймні, це знаходиться на поверхні. Бо хто знає, з кодом якого рівня вкладеності в якомусь страшному циклі працюватиме ваш наступник або ви через місяців п’ять.

Цікаво відзначити, що ті ж самі 4 цикли по 10000 ітерацій кожен, але на одному рівні вкладеності, виглядають досить безпечно

Це якраз і пояснює, що при комбінованій складності, наприклад з вкладеними циклами і однорівневими O (n2+n), менша складність відкидається як менш впливова. Адже не важливо, що у вас подряпана рука, коли ви зламали ногу.

А от у випадку, коли у вас знатний ланцюг map.filter.map....map, то для оптимізації ресурсів варто глянути на варіант імплементування з використанням reduce().

Візьмемо до розгляду такий код:

const char = +arr
 .map((item) => item * item)
 .filter((item) => !(item % new Date().getDate()))
 .map((item) => Math.sqrt(item))
 .filter((item) => item / rnd < length)
 .join("");

Досить добре виділено кожну маніпуляцію, але не варто забувати, що на кожен map і filter виділяється пам’ять і витрачається час. З reduce той самий результат можна отримати отак:

const reduced = +arr.reduce((acc, item) => {
 item = item * item;
 if (!(item % new Date().getDate())) {
   item = Math.sqrt(item);
   if (item / rnd < length) {
     acc += item;
   }
 }
 return acc;
}, "");

Все відбувається відразу, без зайвих пробігів.

Застосуємо приклад на практиці і поміряєм затрати часу. Нехай ми тим шматком коду хочемо отримувати код ASCII символу для татуювання (ну а чом би і ні):

Різниця в часі практично відсутня. Підкинемо елементів:

О, це вже помітно. Майже в півтора рази вигідніше.

Висновки

А висновки прості:

• Бачите вкладені цикли — намагайтеся оптимізувати і робити всі трансформації за один пробіг.
• Не бійтеся трансформувати структури даних чи створювати допоміжні об’єкти, це може вам надати не лише зменшення складності, але і підвищення читабельності коду.
• Знайте дані, з якими працюєте, і робіть запас на їх масштабування.
• Складні задачі складаються з простих цеглинок — вивчайте їх.
• Знайте, які структури даних йдуть з коробки вашої мови програмування, а що доведеться дописувати ламками.
• Не хапайтеся за оптимізацію того, що не вимагає оптимізації. Знайте міру.
• Бережіть себе і будьте здорові :-)

Список джерел до ознайомлення

• Big O
• JavaScript Algorithms and Data Structures
• Know Thy Complexities!
• Разбираемся в алгоритмах и структурах данных. Доступно и понятно
• Простые алгоритмы и структуры данных в JS
• 6 JavaScript data structures you must know
• Часова складність
• Оцінка складності алгоритмів, або Що таке О (log n)
• Часова складність алгоритму
• Algorithms in JavaScript
• 8 time complexities that every programmer should know
• Як це працює? Оцінка складності алгоритмів
• Складність алгоритмів
• Пісочниця

Абсолютно чарівні візуалізації:

• VisuAlgo
• Algorithm Visualizer