11 artykułów oznaczonych „algorytmy".
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.
Czytaj dalej →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.
Czytaj dalej →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.
Czytaj dalej →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.
Czytaj dalej →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ą.
Czytaj dalej →Pierwsza część serii o strukturach danych. Jak z funkcji skrótu robi się dostęp w czasie stałym, co się dzieje przy kolizjach, czym różni się łańcuchowanie od adresowania otwartego i dlaczego słownik czasem nagle zwalnia. Kontrakt hash i eq w Pythonie, klucz, który gubi dane, koszt amortyzowany przy rozrastaniu tablicy oraz trzy różne rzeczy nazywane tym samym słowem hash: skrót do wyszukiwania, kryptograficzny i do haseł.
Czytaj dalej →Tabelki złożoności czyta też atakujący. Jak kilka kilobajtów dobranego wejścia zajmuje rdzeń procesora na sekundy: kolizje w tablicach mieszających (HashDoS z 2011 roku), katastrofalny nawrót w wyrażeniach regularnych (27 minut awarii Cloudflare w 2019), pesymistyczny przypadek quicksorta, bomby dekompresyjne i encje XML. Z pomiarami w Pythonie, prawdziwymi liczbami i listą obron, które faktycznie działają.
Czytaj dalej →Ostatnia część cyklu o sortowaniu: co naprawdę dzieje się po wywołaniu sorted() w Pythonie, Arrays.sort w Javie, std::sort w C++, sort() w PHP i JavaScripcie oraz sort_unstable w Ruście. Powersort od CPythona 3.11, dual-pivot quicksort dla typów prostych, stabilność wymuszona specyfikacją, sortowanie zewnętrzne, quickselect zamiast sortowania i klasyczne pułapki: sortowanie liczb jak napisów oraz niespójny komparator.
Czytaj dalej →Trzecia część cyklu o algorytmach sortowania. Skąd bierze się granica n log n dla wszystkich algorytmów porównawczych, dlaczego jest nieprzekraczalna i jak sortowanie przez zliczanie, pozycyjne i kubełkowe przechodzą pod nią suchą stopą, nie porównując ani razu dwóch elementów. Implementacje w Pythonie, animacje z licznikiem porównań ustawionym na zero oraz uczciwy rachunek kosztów: pamięć, zakres kluczy i rozkład danych.
Czytaj dalej →Druga część cyklu o algorytmach sortowania: sortowanie przez scalanie, szybkie, przez kopcowanie i drzewiaste, a potem hybrydy, które naprawdę pracują w bibliotekach – IntroSort z C++ i TimSort z Pythona oraz Javy. Implementacje w Pythonie, animacje, wybór pivota, przypadek pesymistyczny quicksorta na żywo i pytanie, dlaczego szybkie bije scalanie mimo identycznej złożoności.
Czytaj dalej →Wyścig dziewięciu algorytmów sortowania na żywo w przeglądarce, a potem spokojny rozbiór tych najprostszych: bąbelkowego, koktajlowego, grzebieniowego, gnoma, przez wybieranie, przez wstawianie i Shella. Implementacje w Pythonie, liczniki porównań i zapisów, stabilność, sortowanie w miejscu i adaptacyjność. Oraz to, o czym podręczniki milczą: kiedy O(n kwadrat) naprawdę wygrywa.
Czytaj dalej →