Bartosz Bryniarski

Nie piszę o was, piszę o sobie sprzed lat. Kiedy pojawiło się PHP, trzymałem się CGI i Perla tak długo, że na PHP spojrzałem dopiero koło wydania czwartego. Ten sam odruch – nauczyłem się czegoś raz i tak będę pisał dalej – dziś każe ludziom zaczynać nowe projekty od jQuery. Przegląd tego, po co naprawdę braliśmy tę bibliotekę i co z tego jest już w gołej przeglądarce, z uczciwym rozdziałem o tym, kiedy jQuery wciąż ma sens.

Ostatnia część serii o strukturach danych. Trzy algorytmy przeszukiwania na jednej mapie: BFS liczy kroki, Dijkstra koszt, A* dokłada heurystykę i przestaje błądzić. Do tego reprezentacja grafu, DFS i sortowanie topologiczne, struktura zbiorów rozłącznych z odwrotną funkcją Ackermanna oraz odpowiedź na pytanie, dlaczego prawdziwa nawigacja nie liczy Dijkstry na żywo, tylko przelicza mapę wcześniej.

Piąta część serii o strukturach danych. Kopiec binarny zapisany w zwykłej tablicy, budowa w czasie liniowym i trzy operacje, które z niego wynikają. Po co utrzymywać częściowy porządek zamiast pełnego, jak wybrać dziesięć największych elementów bez sortowania miliona, czym jest heapq.merge przy danych większych niż pamięć i jak z kolejki priorytetowej robi się scheduler oraz ogranicznik ruchu.

Czwarta część serii o strukturach danych. Co się zmienia, gdy dane przestają mieścić się w pamięci: dlaczego drzewo binarne o wysokości 30 jest na dysku katastrofą, jak B-drzewo mieści setki kluczy w jednym węźle i schodzi do trzech poziomów przy miliardzie wierszy. Strona 16 KB w InnoDB, indeks klastrowy i wtórny, reguła lewego prefiksu w indeksie złożonym oraz pięć sytuacji, w których indeks nie pomoże.

Trzecia część serii o strukturach danych. Jak drzewo poszukiwań binarnych trzyma porządek bez przesuwania tablicy, dlaczego na danych posortowanych degeneruje się do listy i wykonuje dokładnie tyle samo porównań co sortowanie bąbelkowe, oraz jak temu zaradzić rotacjami. AVL kontra drzewa czerwono-czarne, animacja obu przypadków i odpowiedź na pytanie, po co komu drzewo, skoro jest szybszy słownik.

Druga część serii o strukturach danych. Kiedy wyszukiwanie liniowe wystarcza, kiedy opłaca się posortować dane, jak napisać wyszukiwanie binarne bez pętli nieskończonej i skąd wziął się błąd przepełnienia, który siedział w bibliotece standardowej Javy przez dziewięć lat. Do tego moduł bisect, wyszukiwanie wykładnicze i rachunek, po ilu zapytaniach sortowanie zwraca się z nawiązką.