Informatyka i programowanieAlgorytmy — sprytne sposoby rozwiązywania problemów

Timsort potrafi wykorzystać porządek, który już istnieje w danych

Nie wszystkie „nieposortowane” dane są równie chaotyczne. Lista może składać się z długich fragmentów, które już rosną lub maleją, ponieważ powstała np. przez dopisywanie kolejnych paczek uporządkowanych rekordów. Timsort, używany do sortowania w Pythonie, wyszukuje takie naturalne serie i scala je zamiast ignorować istniejący porządek. Dokumentacja implementacji CPython opisuje go jako adaptacyjne, stabilne sortowanie przez scalanie i wskazuje, że dla niektórych rodzajów częściowo uporządkowanych danych liczba porównań może spaść bardzo mocno. Algorytm pokazuje, że wejście ma nie tylko rozmiar — ma również strukturę, którą można wykorzystać.

„Nieposortowane” nie musi oznaczać losowe

W analizie algorytmów często mówi się o tablicy długości n i traktuje ją jak abstrakcyjny zbiór liczb. Rzeczywiste dane mają jednak historię. Mogły powstać przez połączenie kilku uporządkowanych raportów, przez dopisywanie nowych rekordów do starszej listy albo przez niewielką zmianę danych, które wcześniej były już posortowane. Timsort jest zaprojektowany tak, aby ten istniejący porządek zauważać.

Opis CPython nazywa go adaptacyjnym, stabilnym, naturalnym mergesortem. „Naturalny” oznacza tutaj, że algorytm wyszukuje w wejściu już istniejące serie — runy — zamiast od początku narzucać sztuczny podział na równe kawałki. Rosnący fragment można wykorzystać bez ponownego sortowania; malejący da się odwrócić z zachowaniem zasad potrzebnych dla stabilności. Następnie takie serie są łączone według strategii mającej utrzymywać scalanie efektywnym.

Najlepszą pracą bywa praca, której nie wykonano

Jeśli lista jest już uporządkowana, zwykła intuicja mówi: „sortowanie powinno szybko zauważyć, że nic nie trzeba robić”. Timsort rzeczywiście potrafi wykorzystać taki przypadek. Dokument `listsort.txt` w CPython wskazuje, że na całkowicie uporządkowanych danych może zejść do około N-1 porównań — w praktyce trzeba przejść przez elementy, aby rozpoznać długi run, ale nie trzeba wykonywać pełnej pracy typowej dla losowego wejścia.

Ciekawsze są dane pomiędzy skrajnościami. Dwie tablice o tej samej długości mogą mieć zupełnie inny koszt sortowania, jeśli jedna jest losowa, a druga zbudowana z kilku dużych uporządkowanych bloków. Oficjalny Python Sorting HOWTO wprost podkreśla, że Timsort może wykorzystywać porządek już obecny w zbiorze danych. To przykład algorytmu adaptacyjnego: jego zachowanie zależy nie tylko od n, lecz także od „łatwości” konkretnego wejścia.

Stabilność jest częścią projektu

Python gwarantuje stabilność sortowania: jeśli dwa rekordy mają równy klucz, zachowują względem siebie pierwotną kolejność. To umożliwia m.in. wykonywanie kilku sortowań po kolejnych kluczach. Stabilność nie jest jednak darmową etykietą dopisaną do gotowego algorytmu. Wpływa na to, jak można odwracać malejące runy i które runy wolno ze sobą scalać.

Dokumentacja implementacji zwraca uwagę, że scalane są sąsiednie serie. Gdyby algorytm arbitralnie scalał nieprzylegające fragmenty, elementy o równych kluczach mogłyby zmienić względną kolejność. Widać tu ciekawą rzecz: własność API widoczna dla programisty — stabilne `sort()` — przenika aż do szczegółów wewnętrznej strategii algorytmu.

Adaptacyjność nie oznacza „zawsze najszybciej”

Nie istnieje darmowa przewaga dla każdego wejścia i każdej maszyny. CPython opisuje kompromisy: Timsort może wykonywać mniej porównań, ale scalanie wymaga przenoszenia danych i pewnej pamięci pomocniczej. To, która część kosztu dominuje, zależy od rodzaju elementów, ceny porównania i charakterystyki sprzętu. Współczesne implementacje mają też dodatkowe szczegóły dotyczące zarządzania runami, więc popularnonaukowy opis nie powinien sprowadzać całego algorytmu do jednego triku.

Najważniejsza idea pozostaje jednak bardzo ogólna. Algorytm może traktować strukturę wejścia jako zasób. Zamiast pytać jedynie „ile danych mam?”, można zapytać „co już o tych danych wiadomo i czego nie muszę obliczać ponownie?”. Tę samą filozofię spotyka się w cache'owaniu, algorytmach inkrementalnych, kompresji i wielu strukturach danych.

Krótkie runy można celowo wydłużyć przed scalaniem

Naturalne serie wejścia nie zawsze mają wygodną długość. Implementacja opisana w CPythonie wyznacza minimalny rozmiar runu i może wydłużać bardzo krótkie fragmenty za pomocą sortowania przez wstawianie w wariancie binarnym. Taki dodatkowy koszt brzmi paradoksalnie: po co sortować lokalnie coś, co i tak będzie później scalane? Chodzi o uniknięcie ogromnej liczby mikroskopijnych runów i o uzyskanie fragmentów, które można efektywniej łączyć. Timsort jest więc czymś więcej niż „znajdź już posortowane kawałki”. Łączy wykrywanie naturalnej struktury z kontrolowanym przygotowaniem jej do późniejszych merge’ów. To typowy wzorzec inżynierii algorytmicznej: czasem niewielka praca wykonana wcześniej upraszcza i ogranicza znacznie droższy etap dalszy.

#algorytmy adaptacyjne#merge sort#Python#sortowanie#stabilność#Timsort
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki