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

А ну давайте маленький тестик

Як ви знаєте, в #React функціональні компоненти рендеряться заново, в тому числі, коли рендериться їх батьківський компонент (якщо не використовувати React.memo)

Тепер власне тест:

Маємо звичайний, майже класичний React counter:

function Counter({ children }) {
  const [c, setCounter] = useState(0);
  const increment = () => setCounter(c + 1);
  return (
    <button onClick={increment}>
      {children} {c}
    </button>
  );
}

Єдиний нюанс з ним - він приймає в пропс children, який відмальовує всередині. В середину ми передаємо отакий примітивний компонент:

function ClickMeText() {
  console.log('ClickMeText rendered');
  return <>Clicked: </>;
}

Цей компонент - просто текст, який також містить консоль лог, щоб ми бачили коли він рендериться. В цілому виглядає це так:

const App = () => <Counter>
  <ClickMeText />
</Counter>

Тепер питання: Я запустив сторінку та ТРИЧІ клікнув на каунтер. Скільки ClickMeText rendered я побачу в консолі, за умови що strict mode вимкнено?

1 раз - ставимо ❤️
3 рази - 👍
4 рази - 🔥

З вас смайлики, з мене пояснення)