N*M (1/3), або дайте мені 1000 ноутбуків

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

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

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 на кожен рендер, наша сторінка просто стане колом 😢

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

@reactbeginners