Простий приклад оптимізації, або N*M слів за складність алгоритмів

Усі статті, обговорення, новини про Front-end — в одному місці. Підписуйтеся на телеграм-канал!

Сьогодні трохи поговоримо про оптимізацію та складність алгоритму на прикладі електронного магазину з ноутбуками.

Уявіть собі, що вам прилетіла задача відобразити таблицю з ноутбуками, а бекенд вам повертає два окремі масиви — список ноутбуків та список історій цін, спрощені моделі яких виглядають ось так:

type NoteBook = {id: number};
type PriceHistory = {entityId: number};

Завдання дуже просте: відобразити ноутбуки разом з історією цін.

Ми можемо зробити це в лоб:

function getNotebooksWithPrice(
    notes: NoteBook[], 
    prices: PriceHistory[]
) {
  return notes.map((notebook) => ({
    ...notebook,
    price: prices
        .filter((x) => x.entityId === notebook.id),
  }));
}

Виглядає непогано і читається досить легко. Але тут прихована одна проблемка — навіть не проблема, а міна сповільненої дії.

Для того, що зібрати всі ноутбуки із цінами, нам потрібно зробити такі кроки:

  1. Пройтися всім списком ноутбуків (зробити N операцій, де N — довжина масиву ноутбуків).
  2. Для кожного елементу масиву пройтися всім списком цін (зробити M операцій для кожного з ноутбуків, де M — довжина масиву цін).

Тобто для виконання цієї красивої функції нам потрібно N*M операцій. (Вітаю, ви щойно оцінили складність алгоритму 😊, яка склала O(N*M)).

З практичної точки зору це означає:

Уявімо собі, що наших ноутбуків 100 штук, а історій цін хоча б втричі більше, тобто 300. Отже нам потрібно для кожного ноутбуку (100 разів) пройтися всією історією цін (300 разів), що сумарно дає 30_000 операцій, що, може, й не так і багато, але вже й не дуже мало.

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

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

Сьогодні у вас в магазині 20 ноутбуків, завтра 120, після завтра 1200 (разом з тими, що виведені з асортименту). І функція, яка чудово справлялася зі 120 ноутами, на 1200 почне суттєво гальмувати ваш UI. А на 2000, коли операцій стане 2_000 * 6_000 = 12_000_000 на кожен рендер, наша сторінка просто стане колом 😢

Як цьому запобігти

Для того, щоб запобігти такій ситуації, існує старий і прекрасний лайфхак — купити кращий комп’ютер — використати Map.

Тобто трансформувати масив сутностей, яким у нас ведеться пошук у словник. Для того, щоб знайти елемент у масиві, в гіршому разі потрібно прочесати весь масив (N операцій, де N — довжина масиву).

А для словника це, умовно, одна операція, тобто складність змінюється з N на 1. Що на попередньому прикладі дає нам 2000 операцій замість 120 мільйонів. Не так і погано?

Реалізувати це дуже просто:

// Перетворимо масив цін на словник цін
// Де ключем буде id ноутбуку
const pricesMap = prices.reduce((acc, price) => {
  const { entityId } = price;
  acc.has(entityId)
    ? acc.get(entityId)?.push(price)
    : acc.set(price.entityId, [price]);

  return acc;
}, new Map<number, PriceHistory[]>());

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

return notes.map((notebook) => ({
  ...notebook,
  prices: pricesMap.get(notebook.id),
}));

Як бачите — не складно. Але розмови, у яких йдеться про швидкодію, нічого не варті — завжди треба міряти. Тому я зібрав цей код, протестував його на JsBench і вийшло, що перша реалізація на 98% повільніша ніж версія з Map.

Якби ноутбуки продавалися з такою знижкою, я б замість одного міг купити собі 50! Здається непогано😀

Отож тепер переводимо все на мапи?

Звичайно, що ні. Адже дуже навряд ви будете виводити 1000 ноутбуків на одну сторінку. Скоріше за все у вас буде paging або поступове завантаження.

Тому:

крок: оцінити реальну кількість елементів, з якою ви будете мати справу.

крок: порахувати складність алгоритму. Алгоритми зі складністю O(1) (взяти елемент по ключу або індексу) оптимізації не потребують, це й так максимум, що можна витиснути. Алгоритми зі складністю O(N) (пошук елементу в масиві), скоріше за все, теж можна не чіпати. А от якщо складність зростає до O(N*N), або ще гірше — до O(N*N*N), це сигнал, що оцінку потрібно продовжувати.

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

крок: якщо кількість ваших даних обмежена — уявіть собі найгірший сценарій і протестуйте* поведінку коду в найгірших умовах. Якщо вас все влаштовує — видихаємо спокійно, якщо код гальмує — скоріше за все також потрібна оптимізація.

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

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

На цьому в мене все, дякую за увагу. Нагадую, що з мене корисний контент, з вас — критика та розповсюдження 😉

А більше матеріалів про React та Front-end можна знайти в мене в телеграм-каналі React для початківців.


Післямова

Є теорія, що алгоритми та структури даних в сучасній розробці не дуже-то й потрібні. Усі алгоритми написані, біблотеки та інструменти створені, а все що треба розробнику — просто скласти то все докупи.

На мою особисту думку, це досить далеко від істини.

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

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

Але щоб долучитися, потрібно вчитися. Й алгоритми разом зі структурами даних є частиною цього навчання.

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

Тому не вірте тим, хто каже, що все вже винайдено, або що це лише для обраних. Вчіться, пробуйте, вибирайте, і буде вам і щастя, і цікава робота.

👍ПодобаєтьсяСподобалось6
До обраногоВ обраному3
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Я б ще у gist додав console.time(...)/console.timeEnd(...), щоб наочно продемонструвати різницю в швидкодії

бекенд вам повертає два окремі масиви — список ноутбуків та список історій цін

А це типова ситуація? Ну тобто щоб сервер видавав відразу велику частину чи навіть всю базу, а фільтрувалось вже на фронті? Принаймні з ембеддерської точки зору це само по собі дивно, бо трафік, gzip/brotli стиснення тексту і пам’ять машини з браузером теж ресурси.

А от граблі з алгоритмічною складністю на рівному місці бувають у всіх доменах, наприклад, безсмертне
for(int i = 0; i < strlen(str); i++){...}

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

Добра тема. Але я, відомо, зануда.
І навінь незважаючи на слово «умовно», не можу погодитися, що доступ до елемента в хешмапі це О(1). Куди зник пошук ключа в мапі? Це не доступ за індексом, де ми банально додаємо оффсет до початку масива в пам’яті.

Куди зник пошук ключа в мапі?

нiкуди нe зник, ось «в ceрeдьому» вiн i є O(1)

це в кращому O(1). а в гіршому O(N). коли гівняна хеш-функція поклала все в одну корзину. як не дивно, але таке буває.

Так, буває.
Алe для оцiнки складностi алгоритму на спiвбeсiдi в MAANG досить вказати O(1)
Для сeбe звiсно трeба розумiти як воно працює i можливi corner cases

на маанг я клав чоловічий статевий орган)
відповідь про складність O(1) для словника чи O(NlogN) для сортування — це рівень індійського студента;)

Ну добрe )
Головнe щоб люди знали на рiвнi індійського студента, та нe пiдвiшували броузeр розрахунками N^3, коли N > 1000

лиш в реальному житті хеш — це не офсет в пам’яті, і, сюрприз-сюрприз, пошук бакета по хешу — це О(1) лише у випадку якщо або абсолютно безлімітна пам’ять або дуже короткий хеш, але з дуже коротким хешем будем з О(N) складністю шукати елемент серед мульярда колізій. Та й таке.

а в гіршому O(N)

Насправді залежить від реалізації. От наприклад в jdk 8 було реалізовано O(Log(N))

коли гівняна хеш-функція поклала все в одну корзину.

тоді мап то не мап, а що там під капотом для бакету з пошуком O(N). З нормальною хеш-фукнцією на звичайних даних воно таки аппроксимовано костантне.

Хеш мапа не здійснює перебір ключів. Тому вона і хеш мапа. Вона звертається відразу для потрібного адресу пам’яті. Ключ в мапі хеширується в унікальний індекс, куди і зберігається значення у пам’яті. Так само і звертається у пам’ять, знаючи адресу, за O(1). Кожна тема буде нудною, якщо в ній не розумітися.

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

Так колізії імовірні. Усе залежить від хеш функції, так коефіцієнту наповнення. У звичайних умовах, як у цьому прикладі імовірність колізії дуже мала, можно сказати 0%. У кожній хеш функції є імовірність колізії. Але це не заважає їх використовувати у безпеці, шифрування даних та інших важливих сферах програмування. В даному випадку колізія точно не є перепоною для використання хеш таблиці. На цю тему навіть немає сенсу розводити диспут, ви можете це самі все перевірити, пропустивши не оптимізований і оптимізований код у прикладу під навантаженням.
Гарна хеш функція навіть у випадку колізії зробить вложену хеш таблицю у проблемний індекс.

Дякую за коментар.

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

Але все ж таки прошу звернути увагу на рівень складності статті. Проговорювати і пояснювати всі моменти (а їх є ще, до прикладу масиви у V8 не завжди масиви, і відповідно складність отримання елементу вже не O(1)) занадто б ускладнило для сприйняття статтю, яка в цілому, направлена на спрощення).

Чомусь не прийшла нотифікашка що стаття опублікована, тому прошу вибачити за затримку.

Всім гарного вечора

Класичний випадок. Якщо бачиш итератор в итераторе це червоний прапор. Це або O(N^2) чи O(N*M). Ну і друге, якщо треба пошук по массиву то відразу використовуй хеш таблиці.

Це або O(N^2) чи O(N*M).

Або O(N*Log(N)) або O(N*Log(M))

Якщо бачиш итератор в итераторе це червоний прапор.

Це червоний прапор тільки якщо ви закостеніли в академічних знанях.

Якщо М та N by-design невеликі, скажем 3-5-10 елементів, то ітератори будуть 1) швидші 2) економніші по пам’яті.

O велике визначає як змінюєтся швидкість чи використання пам’яті зі зростанням даних. В прикладі було наведено випадок з великою кількістю даних. O(N*M) це повільний алгоритм. Отже перебір у переборі — це червоний прапор. Так, якщо обсяг даних дуже маленький, можно в загалі не на що не зважати . Навідь O(N!) це не проблема, якщо массив на 1 елемент.

Підписатись на коментарі