Jak posortować plik większy niż pamięć komputera
Klasyczne sortowanie zakłada zwykle, że dane mieszczą się w pamięci operacyjnej. Gdy plik jest większy niż RAM, problem zmienia charakter: kosztowne staje się przede wszystkim przenoszenie danych między pamięcią a dyskiem. Sortowanie zewnętrzne rozwiązuje to etapami. Najpierw wczytuje porcje mieszczące się w RAM, sortuje każdą i zapisuje jako uporządkowany „run”. Następnie scala wiele takich runów, czytając je sekwencyjnie przez bufory i zapisując wynik. Dzięki temu można uporządkować zbiory wielokrotnie większe od dostępnej pamięci, a projekt algorytmu skupia się nie tylko na porównaniach, lecz przede wszystkim na ograniczaniu kosztownych operacji wejścia/wyjścia.
RAM zmienia reguły gry
W typowym podręcznikowym sortowaniu koszt mierzy się głównie liczbą porównań i operacji wykonywanych przez procesor. To sensowne, gdy tablica mieści się w pamięci operacyjnej. Przy ogromnych plikach sytuacja jest inna. Dane muszą być wielokrotnie odczytywane z pamięci masowej i zapisywane z powrotem, a transfer całych bloków staje się dominującym kosztem.
Virginia Tech OpenDSA opisuje external sorting właśnie jako sortowanie danych przechowywanych poza pamięcią główną. W takim modelu dobry algorytm stara się wykorzystywać duże sekwencyjne operacje I/O i ograniczać liczbę przejść po danych. Samo wybranie wewnętrznego algorytmu o świetnym O(n log n) nie wystarcza, jeśli wymagałby przypadkowych dostępów do elementów rozrzuconych po dysku.
Najpierw tworzy się uporządkowane wyspy
Pierwszy etap jest prosty. Program czyta tyle danych, ile bezpiecznie mieści się w RAM, sortuje tę porcję zwykłym algorytmem pamięciowym i zapisuje ją z powrotem jako uporządkowany fragment, nazywany runem. Potem robi to samo z następną porcją. Jeśli mamy na przykład wielokrotnie więcej danych niż pamięci, otrzymamy wiele osobno posortowanych runów.
Na tym etapie cały plik nadal nie jest globalnie posortowany. Wiemy jednak coś bardzo użytecznego: wewnątrz każdego runu elementy występują już we właściwej kolejności. Problem „posortuj wszystko” został więc zamieniony na problem „scal kilka uporządkowanych strumieni”. To dokładnie ta struktura, którą merge sort potrafi wykorzystać wyjątkowo dobrze.
Scalanie nie wymaga trzymania wszystkiego naraz
Podczas k-way merge program utrzymuje bufory wejściowe dla kilku runów i bufor wyniku. Patrzy na najmniejsze aktualnie dostępne elementy z wejść, wybiera właściwy, zapisuje go do bufora wyjściowego i uzupełnia opróżniające się bufory kolejnymi blokami z dysku. Nie trzeba jednocześnie przechowywać całych runów — wystarczą ich niewielkie okna.
Jeśli runów jest zbyt wiele, aby scalać wszystkie naraz, wykonuje się kilka rund scalania. W każdej liczba osobnych fragmentów maleje, aż pozostaje jeden uporządkowany plik. Liczba wejść możliwych do jednoczesnego scalania zależy m.in. od dostępnej pamięci i rozmiaru buforów. Właśnie dlatego analiza sortowania zewnętrznego często liczy przejścia po danych i transfery bloków, a nie tylko pojedyncze porównania.
Sekwencyjne czytanie jest częścią algorytmu
W pamięci operacyjnej dostęp do różnych adresów jest relatywnie szybki. W pamięci masowej charakter dostępu ma znacznie większe znaczenie. Klasyczne materiały o sortowaniu zewnętrznym podkreślają wartość operowania dużymi blokami i minimalizowania liczby kosztownych odczytów oraz zapisów. Historycznie różnica była szczególnie dramatyczna dla dysków talerzowych i taśm, ale zasada hierarchii pamięci pozostaje ważna również w nowocześniejszych systemach.
To pokazuje, dlaczego złożoność algorytmu nie zawsze daje się streścić jednym O(n log n). Dwa algorytmy wykonujące podobną liczbę porównań mogą w praktyce zachowywać się zupełnie inaczej, jeśli jeden wymusza przypadkowe transfery, a drugi czyta dane długimi sekwencjami. Model kosztu trzeba dopasować do warstwy sprzętowej, która naprawdę ogranicza wykonanie.
„Nie mieści się w RAM” nie oznacza „nie da się policzyć”
Najważniejsza lekcja sortowania zewnętrznego jest szersza niż sam problem sortowania. Pamięć operacyjna nie musi mieścić pełnego zbioru, jeżeli algorytm potrafi przetwarzać dane porcjami i zachować na dysku wystarczającą strukturę pośrednią. Podobny sposób myślenia pojawia się w bazach danych, przetwarzaniu dużych logów i systemach analitycznych.
Trzeba jednak zapłacić za dodatkowe przejścia i transfery. Nie jest to sposób na „oszukanie” ograniczeń pamięci, lecz świadome przeniesienie problemu do innego modelu obliczeń. Zamiast zakładać szybki losowy dostęp do całego zbioru, projektujemy procedurę tak, aby dobrze działała z niewielkim oknem danych i dużym, wolniejszym magazynem zewnętrznym.
Liczba przebiegów zależy od tego, ile runów można scalić naraz
Jeżeli w pamięci mieszczą się bufory dla wielu wejściowych runów oraz bufor wyniku, można wykonać scalanie wielodrogowe zamiast łączyć fragmenty wyłącznie parami. Im większy fan-in, tym mniej poziomów scalania potrzeba, a każdy poziom oznacza kolejne odczytanie i zapisanie dużej części danych. Zbyt małe bufory mogą jednak zwiększyć liczbę operacji I/O, więc nie opłaca się bez końca zwiększać liczby jednoczesnych wejść. Materiały z systemów bazodanowych opisują ten problem właśnie w kategoriach liczby dostępnych stron bufora i przejść po pliku. Dzięki temu external merge sort jest dobrym przykładem algorytmu, którego parametry wynikają bezpośrednio z architektury pamięci. Ten sam pseudokod może mieć bardzo różny koszt przy innym stosunku wielkości RAM do danych.