Algorytmy i struktury danych - Notacja Big O

Sposób wytwarzania oprogramowania cały czas ewoluuje, nowe prostsze języki, abstrakcje, frameworki, teraz AI…

Ale podstawy, wzorce od lat te same. Dlatego warto przyjrzeć się, jak to wszystko działa od fundamentów.

Algorytmy i struktury danych na frontendzie o_O?

Może brzmieć dziwnie, ale jeśli chcemy być inżynierami oprogramowania, niezależnie, czy to frontend, czy backend, warto sięgnąć do podstaw inżynierii oprogramowania. Tym bardziej że znowu do ‘łask’ wchodzi fullstack developer, który potrafi zrobić frontend, jak i backend, historia zatacza koło nie pierwszy raz.

Ja zaś skieruję artykuł w stronę frontendu, gdzie też jest istotne przetwarzanie danych, no i na rozmowach rekrutacyjnych pytają o to!

Notacja Big O co to?

To sposób opisywania, jak szybko rośnie czas działania lub zużycie pamięci algorytmu w zależności od wielkości danych wejściowych.

Typy złożoności

stała $O(1)$

//Źle - każdy element musi być przeiterowany:
const roles = [{id: 1, role: 'admin'}, {id: 2, role: 'user'}];
const currentRole = roles.find(({id}) => id === 1)

//Dobrze - wyciągamy wartość natychmiast:
const roles = { 1: 'admin', 2: 'user' };
const currentRole = roles[1];

liniowa $O(n)$

const users = [{id: 1, name: 'Sergio', isActive: true, isAdmin: true}]

// Złe - mamy kilka iteracji po tej samej liście:
const activeUsers = users.filter(({isActive}) => isActive);
const admins = activeUsers.filter(({isAdmin}) => isAdmin);
const names = admins.map(({name}) => name);

// Dobrze - jedna pętla, nie tworzy dodatkowych tablic:
const adminNames = [];
for (const u of users) {
    if (u.isActive && u.isAdmin) {
        adminNames.push(u.name);
    }
}

czas kwadratowy $O(n^2)$

Pętla w pętli, która zabija wydajność.

Przy kilku elementach niezauważalne, ale jeśli mamy tablicę, która ma 1000 elementów, ilość operacji wynosi 1 000 000, do tego starszy sprzęt, telefon i sytuacja robi się nieciekawa.

const users = [/* 1000 użytkowników */];
const transactions = [/* 1000 transakcji */];

const usersWithTransactions = users.filter(({id}) =>
    transactions.some((transaction) => transaction.userId === id)
);

Pułapka!

Niewinne includes to nic innego jak pętla, czyli podobnie jak wyżej, zrobi się 1 000 000 operacji.

const usersId = [/* 1000 id userów */];
const transactionUserId = [/* 1000 id userów przypisanych do transakcji */];

usersId.filter((id) => !transactionUserId.includes(id));

Jak rozwiązać?

No dobrze, ale jak to wszystko zbić i zwiększyć wydajność?

Wrzucamy jedną pętlę do Set i wyciągamy wartość za pomocą has.

const setB = new Set(listB);

const wynik = listA.map((item) => {
  return setB.has(item);
});

I teraz elegancko Set robi 1000 razy operację, oraz map robi swoje 1000, w sumie to 2000, a nie 1 000 000, i tym sposobem zbiliśmy złożoność do $O(n)$.

logarytmiczna $O(\log n)$

Bardzo prosto to osiągnąć i zrozumieć, zamiast iterować każdy element 1000-elementowej tablicy, stosując złożoność logarytmiczną, stajemy w połowie tablicy i w zależności, czy szukany element jest mniejszy, czy większy, idziemy w lewo lub w prawo, odrzucając połowę, czyli z pierwszej iteracji odrzucimy 500, z drugiej już 250 i tak dalej, w sumie dla tablicy 1000 elementowej takich iteracji będzie około 10.

I nie musimy iterować tym sposobem 1000 razy.

Złożoność logarytmiczna zadziała tylko na tablicy posortowanej!

To, czy ją sortować i używać $O(\log n)$, zależy od konkretnego przypadku.

liniowo - logarytmiczna $O(n \log n)$

Sortowanie przez scalanie to połączenie $O(n)$ z $O(\log n)$, co daje złożoność $O(n \log n)$.

Mając 100 elementów, w pierwszej fazie dzielisz wszystko na pół, aż tablice będą jednoelementowe. W kolejnej fazie łączysz dwójki, jednocześnie je sortując, potem łączysz czwórki i tak dalej, aż scalona zostanie cała tablica.

Może się wydawać, że robimy tutaj nadmiar elementów, dziwne operacje, które nie są wydajne, ale liczby nie kłamią, zamiast 10 000 operacji
(jak w prostym sortowaniu), wykonujesz ich tylko około 700.

Oczywiście tej złożoności nie używa się tylko do sortowania, jest to jeden z przykładów zastosowania na frontendzie, gdzie metody takie jak sort() czy toSorted() korzystają już z tego mechanizmu.

Od Autora

Zachęcam do dalszego poznawania notacji, nie są to wszystkie złożoności, ale najczęściej stosowane.

Najważniejsze to wiedzieć, że jest coś takiego i umieć pokrótce opowiedzieć, tym bardziej że na rozmowach rekrutacyjnych nawet na frontend developera czasami pytają o to (mnie też pytali).

Wydajność na frontendzie to bardzo ważny aspekt, napisałbym nawet, że jest to fundament każdej witryny, od tego zależy, jak użytkownik będzie postrzegał nasz produkt.

Zdecydowanie trzeba mieć na uwadze (celowo nie napisałem ‘warto’) zachowanie aplikacji na innych urządzeniach, takich jak telefon, tablet czy słabszy komputer.

To, że wytwarzamy oprogramowanie na super szybkich MacBookach Pro M5, gdzie nawet przy braku optymalizacji wszystko chodzi super, nie znaczy, że każdy ma taki sprzęt.

Dobry inżynier patrzy szerzej, krytyczniej i wychodzi poza ramy tasku w Jira.

Koniec części pierwszej.