Algorithms

Wyszukanie klucza w Pythonowym dict z dziesięcioma wpisami zajmuje tyle samo czasu, co w dict z dziesięcioma milionami. To nie wynika z szybkości języka. Pythonowy dict, Javowy HashMap i Map w JavaScript to wszystko tabele haszujące, a cały ten projekt istnieje po to, by wyszukiwanie, wstawianie i usuwanie działały średnio w O(1). Notacja Big O nazywa to wyszukiwanie “czasem stałym”. Oto mechanizm, który na to zasługuje. Jak tabela haszująca zmienia klucz w indeks tablicy Tabela haszująca to tablica plus funkcja, która zmienia klucz w pozycję w tej tablicy. ...

<.+> dla <b>bold</b> and <i>italic</i> nie znajduje <b>. Znajduje cały ciąg, od pierwszego < do samego ostatniego >. Nic nie jest zepsute. To właśnie ma robić zachłanny (greedy) kwantyfikator, i to jest też najczęstszy błąd typu “regex matchuje zbyt dużo”. Gdy już wiesz, co silnik robi podczas czytania wzorca, ten błąd i większość jego krewnych przestają być zagadką. Jak silnik regex czyta twój wzorzec Silnik regex nie porównuje wzorca z ciągiem tak, jak porównuje się dwa ciągi pod kątem równości. Silniki, które używasz codziennie (re w Pythonie, RegExp w JavaScript, PCRE, .NET, Java) są regex-directed: przechodzą przez wzorzec od lewej do prawej, token po tokenie, i dla każdego tokenu próbują skonsumować znaki z ciągu w aktualnej pozycji. Gdy token się dopasuje, silnik przesuwa wskaźnik wzorca i wskaźnik ciągu. Gdy token zawodzi, silnik robi backtracking: wraca do ostatniego miejsca, w którym miał wybór, na przykład kwantyfikator, który mógł dopasować mniej znaków, albo gałąź alternatywy, której jeszcze nie spróbował, i wybiera drugą opcję. ...

Funkcja, która wywołuje sama siebie, ma maksymalną głębokość, i jest ona mniejsza niż większość się spodziewa: 1000 wywołań w CPython domyślnie, w okolicach 10 000-15 000 w Node i silnikach przeglądarek, zależnie od tego, jak dużo zajmuje każda ramka. Przekroczenie tego limitu nie zwalnia programu. Program się wysypuje. Python zgłasza RecursionError: maximum recursion depth exceeded; JavaScript zgłasza RangeError: Maximum call stack size exceeded. Oba błędy mają tę samą przyczynę, a gdy już ją zobaczysz, będziesz wiedzieć, kiedy rekurencja jest właściwym narzędziem, a kiedy staje się ryzykiem. ...

Wpisz 0.1 + 0.2 w shellu Pythona i nie dostaniesz 0.3. Dostaniesz 0.30000000000000004. Spróbuj w JavaScript, Java, Go, C albo Rust i wyjdzie ten sam siedemnastocyfrowy ogon. Każdy z tych języków robi dokładnie to, co nakazuje standard sprzętowy. Liczba, która wymagałaby nieskończenie wielu cyfr binarnych, jest ściskana do 64 bitów i coś musi ustąpić. Czemu 0.1 nie da się zapisać dokładnie w binarnym systemie Komputery zapisują liczby zmiennoprzecinkowe w systemie dwójkowym. W systemie dwójkowym ułamek 1/10 ma rozwinięcie okresowe, tak jak 1/3 powtarza się bez końca w systemie dziesiętnym (0.3333...). Zapisane w całości, 0.1 w binarnym zaczyna się tak: ...

Odczyt ze słownika w Pythonie trwa około 100 nanosekund, niezależnie od tego, czy słownik ma 1000 kluczy, czy 1 000 000. Podwójna pętla szukająca duplikatów w liście trwa pół milisekundy przy 200 elementach i 136 milisekund przy 3200. Szesnaście razy więcej danych wejściowych, prawie 280 razy dłuższe oczekiwanie. Ta sama maszyna, ten sam Python. Notacja Big O to nazwa tej różnicy. Co mierzy notacja Big O Big O opisuje, jak rośnie czas działania (albo zużycie pamięci) fragmentu kodu wraz ze wzrostem danych wejściowych. To nie jest pomiar stoperem i nie ma znaczenia, czy twój laptop jest szybki, czy wolny. Liczy się kształt krzywej wzrostu: gdy podwoisz dane wejściowe, czas się podwaja, rośnie czterokrotnie, czy prawie się nie zmienia? ...