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

💡 Усі статті, обговорення, новини про Front-end — в одному місці. Приєднуйтесь до 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.

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