Union-Find (Disjoint Set Union) to struktura danych do zarządzania zbiorami rozłącznymi. Umożliwia dwie operacje w czasie niemal O(1): sprawdzenie czy dwa elementy należą do tego samego zbioru (Find) i połączenie dwóch zbiorów (Union). Algorytm pojawia się w problemach grafowych, wykrywaniu cykli i grupowaniu elementów. W Magento 2 przydaje się przy łączeniu zduplikowanych klientów i produktów.
Algorytm Dijkstry to klasyczny algorytm wyszukiwania najkrótszej ścieżki w grafie ważonym z nieujemnymi wagami. Działa w O((V + E) log V) z kolejką priorytetową, gdzie V to liczba wierzchołków a E krawędzi. Praktyczne zastosowania to routing, nawigacja GPS, systemy rekomendacji i optymalizacja sieci. Pokażę implementację w PHP z kolejką priorytetową i dwa realne przykłady użycia.
Skip List to probabilistyczna struktura danych wynaleziona przez Williama Pugha w 1990 roku. Łączy prostotę listy jednokierunkowej z wydajnością drzewa binarnego – operacje wyszukiwania, wstawiania i usuwania działają w O(log n) średnio, bez potrzeby balansowania jak w AVL czy Red-Black Tree. W PHP jest rzadko używana, ale świetnie ilustruje jak losowość może zastąpić złożone algorytmy balansowania.
LRU (Least Recently Used) Cache to jeden z klasycznych problemów algorytmicznych z rozmów rekrutacyjnych, ale też realna struktura danych używana w systemach produkcyjnych. Redis domyślnie używa wariantu LRU do eksmisji kluczy. PHP OPcache stosuje LRU. Pokazuję jak zaimplementować LRU Cache w O(1) dla get i put, używając hashmapy i listy dwukierunkowej – i gdzie to ma zastosowanie w e-commerce.
Bloom Filter to probabilistyczna struktura danych która odpowiada na pytanie „czy ten element może być w zbiorze?” – z gwarancją braku false negatives i kontrolowanym poziomem false positives. Używa ułamka pamięci potrzebnej tablicy hashowej. Gdy masz milion zakazanych tokenów, setki tysięcy unikalnych emaili do walidacji albo cache który musi odrzucić żądania bez trafień do bazy – Bloom Filter jest właściwym narzędziem.
Trie (drzewo prefiksowe) to struktura danych zoptymalizowana pod wyszukiwanie słów i prefiksów. Zamiast porównywać każde słowo ze słownikiem, Trie przechodzi po literach – każdy węzeł to jedna litera, każda ścieżka od korzenia to słowo. Autouzupełnianie w wyszukiwarce, walidacja SKU, wykrywanie spamu – Trie pojawia się w e-commerce częściej niż myślisz. Implementuję od zera w PHP z praktycznymi przykładami.
W maju 2021 pisałem o BFS i DFS dla grafów bez wag. Czas na algorytm Dijkstry – klasyczny algorytm znajdowania najkrótszej ścieżki w grafie z wagami nieujemnymi. Pojawia się wszędzie tam gdzie „najkrótsza” nie oznacza „najmniej kroków”, ale „najmniejszy koszt” – routing, optymalizacja dostaw, recommendation engines.
W listopadzie 2018 pisałem o podstawowych algorytmach sortowania. Czas na Quicksort – jeden z najważniejszych algorytmów w historii informatyki, średnio O(n log n) i jeden z najszybszych w praktyce. Implementuję kilka wariantów w PHP, pokazuję gdzie Quicksort bije inne algorytmy i dlaczego wbudowany sort() PHP jest szybszy niż własna implementacja.
Programowanie dynamiczne (DP) to technika rozwiązywania problemów przez rozbicie ich na podproblemy i zapamiętywanie wyników aby nie liczyć ich wielokrotnie. Brzmi abstrakcyjnie, ale w praktyce stosujesz DP kiedy piszesz cache dla kosztownej operacji albo szukasz optymalnego zestawu produktów do oferty. Pokazuję dwa klasyczne problemy z implementacją w PHP.
Grafy to struktury danych, które pojawiają się w zaskakujących miejscach: drzewo kategorii w Magento, zależności między modułami, sieć powiązanych produktów, routing w aplikacjach. BFS i DFS to dwa fundamentalne algorytmy przeszukiwania grafów. Implementuję oba w PHP i pokazuję gdzie realnie je stosuję.
- 1
- 2