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ę.
PHP array jest na tyle wszechstronna, że rzadko potrzebujemy innych struktur danych. Ale lista dwukierunkowa (doubly linked list) ma właściwości, których tablica nie oferuje – wstawianie i usuwanie elementów ze środka w O(1), bez przesuwania pozostałych elementów. Implementuję ją od zera w PHP i pokazuję kiedy warto po nią sięgnąć.
Tablica w PHP to jeden z najczęściej używanych typów danych, ale mało kto zastanawia się jak działa pod spodem. PHP array to w rzeczywistości hash table – struktura danych, która pozwala na dostęp do elementów w czasie O(1). Pokazuję jak to działa, jakie ma konsekwencje praktyczne i gdzie tablice PHP zaskakują swoją wydajnością.
- 1
- 2