Sortowanie liczb całkowitych - Integer sorting

W informatyce , całkowitą sortowania jest algorytmiczne Problem sortowania zbiór wartości danych o całkowitych kluczy. Algorytmy zaprojektowane do sortowania liczb całkowitych mogą być również często stosowane do problemów z sortowaniem, w których kluczami są liczby zmiennoprzecinkowe, liczby wymierne lub ciągi tekstowe. Możliwość wykonywania arytmetyki liczb całkowitych na kluczach pozwala algorytmom sortowania liczb całkowitych być w wielu przypadkach szybszym niż algorytmy sortowania porównawczego , w zależności od szczegółów, które operacje są dozwolone w modelu obliczeniowym i jak duże są sortowane liczby całkowite.

Integer algorytmów sortowania tym szufladki sort , sortowanie przez zliczanie i sortowanie pozycyjne są szeroko stosowane i praktyczne. Uważa się, że inne algorytmy sortowania liczb całkowitych z mniejszymi granicami czasu najgorszego przypadku nie są praktyczne w przypadku architektur komputerowych z 64 lub mniejszą liczbą bitów na słowo. Znanych jest wiele takich algorytmów, których wydajność zależy od kombinacji liczby elementów do sortowania, liczby bitów na klucz i liczby bitów na słowo komputera wykonującego algorytm sortowania.

Uwagi ogólne

Modele obliczeń

Ograniczenia czasowe algorytmów sortowania liczb całkowitych zazwyczaj zależą od trzech parametrów: liczby n wartości danych do posortowania, wielkości K największego możliwego klucza do posortowania oraz liczby w bitów, które mogą być reprezentowane w pojedynczym słowie maszynowym komputer, na którym ma zostać wykonany algorytm. Zazwyczaj zakłada się, że w ≥ log ₂ (max( n , K ) ) ; to znaczy, że słowa maszynowe są wystarczająco duże, aby reprezentować indeks w sekwencji danych wejściowych, a także wystarczająco duże, aby reprezentować pojedynczy klucz.

Algorytmy sortowania liczb całkowitych są zwykle zaprojektowane do pracy w maszynach wskaźnikowych lub modelach maszyn o dostępie swobodnym . Główna różnica między tymi dwoma modelami polega na sposobie adresowania pamięci. Maszyna o dostępie swobodnym umożliwia wykorzystanie dowolnej wartości przechowywanej w rejestrze jako adresu operacji odczytu i zapisu pamięci, z jednostkowym kosztem operacji. Ta zdolność umożliwia szybkie zaimplementowanie pewnych złożonych operacji na danych za pomocą wyszukiwania tabel. W przeciwieństwie do tego, w modelu maszyny wskaźnikowej operacje odczytu i zapisu wykorzystują adresy przechowywane we wskaźnikach i nie jest dozwolone wykonywanie operacji arytmetycznych na tych wskaźnikach. W obu modelach wartości danych mogą być dodawane, a bitowe operacje logiczne i operacje przesunięcia binarnego mogą być zazwyczaj również wykonywane na nich w jednostce czasu na operację. Różne algorytmy sortowania liczb całkowitych przyjmują różne założenia dotyczące tego, czy mnożenie liczb całkowitych jest również dozwolone jako operacja jednostkowa. Rozważano również inne bardziej wyspecjalizowane modele obliczeń, takie jak równoległa maszyna o swobodnym dostępie , po pierwsze losowo, po drugie deterministyczne w komentarzu; późniejsze prace obejmują

Andersson, Miltersen i Thorup (1999) wykazali, że w niektórych przypadkach mnożenia lub wyszukiwania tabel wymagane przez niektóre algorytmy sortowania liczb całkowitych można zastąpić niestandardowymi operacjami, które można by łatwiej zaimplementować na sprzęcie, ale które zazwyczaj nie są dostępne na komputerach ogólnego przeznaczenia. Thorup (2003) poprawił to, pokazując, jak zastąpić te operacje specjalne instrukcjami manipulacji polem bitowym, które są już dostępne w procesorach Pentium .

W zewnętrznych modelach obliczeniowych pamięci żaden znany algorytm sortowania liczb całkowitych nie jest szybszy niż sortowanie porównawcze. Naukowcy wykazali, że w tych modelach ograniczone klasy algorytmów, które są ograniczone w sposobie manipulowania kluczami, nie mogą być szybsze niż sortowanie porównawcze, a algorytm sortowania liczb całkowitych, który jest szybszy niż sortowanie porównawcze, sugerowałby fałszywość standardowego przypuszczenia w kodowanie sieciowe .

Sortowanie a kolejki priorytetów liczb całkowitych

Kolejka priorytetem jest strukturą danych dla utrzymania kolekcję przedmiotów z priorytetów numerycznych, po operacji w celu znalezienia i usunięcia składnika majątku o wartości minimum priorytetowej. Kolejki priorytetowe oparte na porównaniach, takie jak sterta binarna, zajmują czas logarytmiczny na aktualizację, ale inne struktury, takie jak drzewo van Emde Boas lub kolejka kubełkowa, mogą być szybsze w przypadku danych wejściowych, których priorytety są małymi liczbami całkowitymi. Te struktury danych mogą być używane w algorytmie sortowania przez wybór , który sortuje kolekcję elementów przez wielokrotne znajdowanie i usuwanie najmniejszego elementu z kolekcji oraz zwracanie elementów w kolejności, w jakiej zostały znalezione. Kolejka priorytetowa może służyć do utrzymywania kolekcji elementów w tym algorytmie, a czas tego algorytmu w kolekcji n elementów może być ograniczony czasem do zainicjowania kolejki priorytetowej, a następnie wykonania n operacji wyszukiwania i usuwania. Na przykład użycie sterty binarnej jako kolejki priorytetowej w sortowaniu przez selekcję prowadzi do algorytmu sortowania sterty, algorytmu sortowania porównawczego, który zajmuje czas O ( n log n ) . Zamiast tego, użycie sortowania przez wybór z kolejką wiaderkową daje formę sortowania szufladkowego , a użycie drzew van Emde Boas lub innych kolejek priorytetowych liczb całkowitych prowadzi do innych szybkich algorytmów sortowania liczb całkowitych.

Zamiast używać kolejki priorytetów liczb całkowitych w algorytmie sortowania, można pójść w innym kierunku i używać algorytmów sortowania liczb całkowitych jako podprogramów w strukturze danych kolejki priorytetów liczb całkowitych. Thorup (2007) wykorzystał ten pomysł, aby pokazać, że jeśli możliwe jest sortowanie liczb całkowitych w czasie T ( n ) na klucz, to ten sam limit czasu dotyczy czasu na operację wstawiania lub usuwania w strukturze danych kolejki priorytetowej. Redukcja Thorup jest skomplikowane i zakłada dostępność zarówno szybkie mnożenie operacji lub wyszukiwań stole, ale zapewnia też alternatywny kolejkę priorytetową przy użyciu tylko dodawanie i operacji logicznych z czasem T ( n ) + T (log n ) + T (log log n ) + ... na operację, co najwyżej mnożąc czas przez iterowany logarytm .

Użyteczność

Klasyczny całkowitą sortowania algorytmy szufladki rodzaju , licząc sortowania , a sortowanie pozycyjne są powszechnie stosowane i praktyczne. Wiele późniejszych badań nad algorytmami sortowania liczb całkowitych koncentrowało się mniej na praktyczności, a bardziej na teoretycznych ulepszeniach ich analizy najgorszego przypadku , a algorytmy pochodzące z tej linii badań nie są uważane za praktyczne dla obecnych 64-bitowych architektur komputerowych, chociaż eksperymenty wykazały, że niektóre z tych metod mogą być ulepszeniem sortowania radix dla danych z 128 lub więcej bitami na klucz. Dodatkowo, w przypadku dużych zestawów danych, prawie losowe wzorce dostępu do pamięci wielu algorytmów sortowania liczb całkowitych mogą je utrudnić w porównaniu z algorytmami sortowania porównawczego, które zostały zaprojektowane z myślą o hierarchii pamięci.

Sortowanie liczb całkowitych zapewnia jeden z sześciu testów porównawczych w zestawie testów DARPA High Productivity Computing Systems Discrete Mathematics oraz jeden z jedenastu testów porównawczych w zestawie NAS Parallel Benchmarks .

Praktyczne algorytmy

Sortowanie typu Pigeonhole lub sortowanie liczące może zarówno sortować n elementów danych posiadających klucze w zakresie od 0 do K − 1 w czasie O ( n + K ) . W sortowaniu szufladkowym (często nazywanym sortowaniem kubełkowym) wskaźniki do elementów danych są dystrybuowane do tabeli kubełków, reprezentowanych jako typy danych kolekcji, takie jak listy połączone , przy użyciu kluczy jako indeksów w tabeli. Następnie wszystkie segmenty są łączone w celu utworzenia listy wyjściowej. Sortowanie liczące wykorzystuje tabelę liczników zamiast tabeli wiader, aby określić liczbę elementów z każdym kluczem. Następnie oblicza się sumę prefiksów, aby określić zakres pozycji w posortowanym wyjściu, w którym należy umieścić wartości z każdym kluczem. Wreszcie, w drugim przejściu przez dane wejściowe, każdy element jest przenoszony do pozycji swojego klucza w tablicy wyjściowej. Oba algorytmy obejmują tylko proste pętle nad danymi wejściowymi (pobierając czas O ( n ) ) i nad zbiorem możliwych kluczy (pobierając czas O ( K ) ), dając ich całkowity czas O ( n + K ) .

Sortowanie Radix to algorytm sortowania, który działa dla większych kluczy niż sortowanie przegródkowe lub sortowanie zliczające, wykonując wielokrotne przejścia nad danymi. Każde przejście sortuje dane wejściowe przy użyciu tylko części kluczy, przy użyciu innego algorytmu sortowania (takiego jak sortowanie szufladkowe lub sortowanie zliczające), który jest odpowiedni tylko dla małych kluczy. Aby podzielić klucze na części, algorytm sortowania radix oblicza notację pozycyjną dla każdego klucza, zgodnie z wybraną radix ; wtedy częścią klucza użytą do i- tego przebiegu algorytmu jest i- ta cyfra w notacji pozycyjnej dla pełnego klucza, zaczynając od najmniej znaczącej cyfry i przechodząc do najbardziej znaczącej. Aby ten algorytm działał poprawnie, algorytm sortowania używany przy każdym przejściu przez dane musi być stabilny : elementy o równych cyfrach nie powinny zmieniać pozycji względem siebie. Aby uzyskać największą wydajność, podstawa powinna być tak dobrana, aby była zbliżona do liczby elementów danych, n . Dodatkowo, użycie potęgi dwójki w pobliżu n jako podstawy umożliwia szybkie obliczenie kluczy dla każdego przejścia przy użyciu tylko szybkich operacji przesunięcia binarnego i masek. Przy tych wyborach i z sortowaniem przegródkowym lub sortowaniem zliczającym jako algorytmem podstawowym, algorytm sortowania radix może sortować n elementów danych mających klucze w zakresie od 0 do K − 1 w czasie O ( n log _n K ) .

Algorytmy teoretyczne

Opracowano wiele algorytmów sortowania liczb całkowitych, których analiza teoretyczna pokazuje, że zachowują się lepiej niż sortowanie porównawcze, sortowanie przegródek lub sortowanie radix dla wystarczająco dużych kombinacji parametrów definiujących liczbę elementów do sortowania, zakres kluczy i rozmiar słowa maszynowego. To, który algorytm ma najlepszą wydajność, zależy od wartości tych parametrów. Jednak pomimo ich teoretycznych zalet, algorytmy te nie są ulepszeniem typowych zakresów tych parametrów, które pojawiają się w praktycznych problemach sortowania.

Algorytmy dla małych kluczy

Van Emde Boas drzewo może być stosowany jako kolejka priorytetowa do sortowania zestawu n przycisków, z których każdy mieści się w zakresie od 0 do K - 1 w czasie O ( n log log K ) . Jest to teoretyczne ulepszenie w stosunku do sortowania radixowego, gdy K jest wystarczająco duże. Jednak, aby użyć drzewa Van Emde Boasa, potrzebna jest albo bezpośrednio adresowalna pamięć K słów, albo trzeba ją zasymulować za pomocą tablicy mieszającej , zmniejszając przestrzeń do liniowej, ale czyniąc algorytm losowym. Kolejnym priorytetem kolejka o podobnej wydajności (w tym potrzeby randomizacji w postaci tablic hash) jest Y-fast trie od Willard (1983) .

Bardziej wyrafinowaną technikę o podobnym smaku i lepszej wydajności teoretycznej opracowali Kirkpatrick i Reisch (1984) . Zaobserwowali, że każde przejście sortowania radix może być interpretowane jako technika redukcji zakresu, która w czasie liniowym zmniejsza maksymalny rozmiar klucza o współczynnik  n ; zamiast tego ich technika redukuje rozmiar klucza do pierwiastka kwadratowego jego poprzedniej wartości (zmniejszając o połowę liczbę bitów potrzebnych do reprezentowania klucza), ponownie w czasie liniowym. Jak w radix sortowania, ich interpretować jako klucze dwucyfrowych Base- b numery dostępu do bazy B , która w przybliżeniu √ K . Następnie grupują elementy, które mają być posortowane w segmenty według ich wysokich cyfr, w czasie liniowym, używając albo dużej, ale niezainicjowanej pamięci adresowanej bezpośrednio, albo tablicy mieszającej. Każde wiadro ma reprezentanta, przedmiot w wiadrze z największym kluczem; następnie sortują listę pozycji, używając jako kluczy wysokich cyfr dla przedstawicieli i niskich cyfr dla nieprzedstawicieli. Poprzez ponowne zgrupowanie pozycji z tej listy w segmenty, każdy segment można ustawić w kolejności posortowanej, a poprzez wyodrębnienie przedstawicieli z posortowanej listy segmenty mogą zostać połączone w posortowaną kolejność. Tak więc, w czasie liniowym, problem sortowania sprowadza się do innego rekurencyjnego problemu sortowania, w którym klucze są znacznie mniejsze, jako pierwiastek kwadratowy ich poprzedniej wielkości. Powtarzanie tej redukcji zakresu, aż klucze będą wystarczająco małe, aby sortować w wiaderkach, prowadzi do algorytmu z czasem działania O( n log log _n K ) .

Skomplikowany algorytm randomizowany Han i Thorupa (2002) w modelu obliczeniowym słów RAM pozwala na jeszcze dalszą redukcję tych granic czasowych do O( n √ log log K ) .

Algorytmy dla dużych słów

Mówi się, że algorytm sortowania liczb całkowitych jest niekonserwatywny, jeśli wymaga rozmiaru słowa w, który jest znacznie większy niż log max( n , K ) . W skrajnym przypadku, jeśli w ≥ K , a wszystkie klucze są różne, to zbiór kluczy można posortować w czasie liniowym, przedstawiając go jako wektor bitowy , z 1 bitem na pozycji i, gdy i jest jednym z kluczy wejściowych, a następnie wielokrotnie usuwając najmniej znaczący bit.

Non-konserwatywny pakowane sortowania algorytm Albers & Hagerup (1997) wykorzystuje podprogram, na podstawie Ken Dozowniki „s bitonic sieci sortowni , do łączenia dwóch klasyfikowane sekwencje klawiszy, które są na tyle krótkie, aby każdy być pakowane w jednym słowie maszynowym. Dane wejściowe algorytmu sortowania zapakowanego, sekwencja elementów przechowywanych po jednym na słowo, są przekształcane w postać spakowaną, sekwencję słów, z których każdy zawiera wiele elementów w posortowanej kolejności, przy wielokrotnym użyciu tego podprogramu w celu podwojenia liczby elementów zapakowanych w każdy z nich. słowo. Gdy sekwencja jest już spakowana, Albers i Hagerup używają do jej sortowania sortowania przez scalanie ; gdy dwie sekwencje są łączone w jedną dłuższą sekwencję, ten sam podprogram sortowania bitonicznego może być użyty do wielokrotnego wyodrębniania spakowanych słów składających się z najmniejszych pozostałych elementów tych dwóch sekwencji. Algorytm ten uzyskuje wystarczające przyspieszenie dzięki swojej upakowanej reprezentacji, aby posortować dane wejściowe w czasie liniowym, ilekroć pojedyncze słowo może zawierać klucze Ω(log n log log n ) ; to znaczy, gdy log K log n log log n ≤ cw dla pewnej stałej c > 0 .

Algorytmy dla kilku pozycji

Sortowanie według przegródek, sortowanie zliczające, sortowanie radixowe i sortowanie według drzew Van Emde Boasa działają najlepiej, gdy klucz jest mały; dla wystarczająco dużych kluczy stają się wolniejsze niż algorytmy sortowania porównawczego. Jednakże, gdy rozmiar klucza lub rozmiar słowa jest bardzo duży w stosunku do liczby elementów (lub równoważnie, gdy liczba elementów jest niewielka), ponowne może stać się możliwe szybkie sortowanie przy użyciu różnych algorytmów, które wykorzystują nieodłączną równoległość w umiejętności wykonywania operacji arytmetycznych na dużych słowach.

Wczesny wynik w tym kierunku dostarczyli Ajtai, Fredman i Komlós (1984), wykorzystując model obliczeniowy typu cell-probe (sztuczny model, w którym złożoność algorytmu jest mierzona tylko liczbą dostępów do pamięci, które wykonuje). Opierając się na swojej pracy, Fredman i Willard (1994) opisali dwie struktury danych, stertę Q i stertę atomową, które można zaimplementować na maszynie o dostępie swobodnym. Sterta Q jest bitowo-równoległą wersją binarnego tria i pozwala zarówno na wykonywanie operacji kolejki priorytetowej, jak i zapytań następnika i poprzednika w stałym czasie dla zestawów elementów O ((log N ) ^1/4 ) , gdzie N ≤ 2 ^w to rozmiar wstępnie obliczonych tabel potrzebnych do zaimplementowania struktury danych. Sterta atomowa to drzewo B, w którym każdy węzeł drzewa jest reprezentowany jako sterta Q; pozwala na operacje kolejkowe o stałym priorytecie czasowym (a tym samym sortowanie) dla zestawów (log N ) ^{O (1)} pozycji.

Andersson i in. (1998) dostarczają losowy algorytm zwany sortowaniem sygnaturowym, który pozwala na liniowe sortowanie w czasie zestawów do 2 ^{O ((log w ) 1/2 − ε )} elementów na raz, dla dowolnej stałej ε > 0 . Podobnie jak w algorytmie Kirkpatricka i Reischa, dokonują redukcji zakresu przy użyciu reprezentacji kluczy jako liczb o podstawie  b dla starannego wyboru b . Ich algorytm redukcji zakresu zastępuje każdą cyfrę sygnaturą, która jest wartością zahaszowaną z bitami O (log n ) tak, że różne wartości cyfr mają różne sygnatury. Jeśli n jest wystarczająco małe, liczby utworzone przez ten proces zastępowania będą znacznie mniejsze niż oryginalne klucze, umożliwiając niekonserwatywnemu algorytmowi sortowania upakowanego Albersa i Hagerupa (1997) sortowanie zastępowanych liczb w czasie liniowym. Z posortowanej listy zastępowanych liczb możliwe jest utworzenie skompresowanej trii kluczy w czasie liniowym, a dzieci każdego węzła w tri mogą być sortowane rekursywnie przy użyciu tylko kluczy o rozmiarze b , po czym przechodzenie przez drzewo tworzy posortowana kolejność pozycji.

Algorytmy transdychotomiczne

Fredman i Willard (1993) wprowadzili transdychotomiczny model analizy dla algorytmów sortowania liczb całkowitych, w którym nie zakłada się nic co do zakresu kluczy liczb całkowitych i należy wiązać działanie algorytmu wyłącznie funkcją liczby wartości danych. Alternatywnie, w tym modelu zakłada się , że czas wykonania algorytmu na zbiorze n elementów jest najgorszym przypadkiem czasu wykonania dla dowolnej możliwej kombinacji wartości K i  w . Pierwszym algorytmem tego typu był algorytm sortowania drzewa fuzji Fredmana i Willarda , który działa w czasie O( n log n / log log n ) ; jest to ulepszenie w stosunku do sortowania porównawczego dla dowolnego wyboru K i  w . Alternatywna wersja ich algorytmu, która obejmuje użycie liczb losowych i operacji dzielenia liczb całkowitych, poprawia to do O( n √ log n ) .

Od czasu ich pracy opracowano jeszcze lepsze algorytmy. Na przykład, poprzez wielokrotne stosowanie techniki redukcji zakresu Kirkpatricka-Reischa, aż klucze będą wystarczająco małe, aby zastosować algorytm sortowania upakowanego Albersa-Hagerupa, możliwe jest sortowanie w czasie O ( n log log n ) ; jednak część tego algorytmu dotycząca redukcji zakresu wymaga albo dużej pamięci (proporcjonalnej do √ K ) albo randomizacji w postaci tablic mieszających.

Han i Thorup (2002) pokazali, jak sortować w losowym czasie O( n √ log log n ) . Ich technika polega na wykorzystaniu pomysłów związanych z sortowaniem sygnatur, aby podzielić dane na wiele małych podlist, o rozmiarze na tyle małym, że sortowanie sygnatur może skutecznie posortować każdą z nich. Możliwe jest również wykorzystanie podobnych pomysłów do sortowania liczb całkowitych deterministycznie w czasie O ( n log log n ) i przestrzeni liniowej. Używając tylko prostych operacji arytmetycznych (bez mnożenia lub przeszukiwania tabel) możliwe jest sortowanie w losowym oczekiwanym czasie O ( n log log n ) lub deterministycznie w czasie O ( n (log log n ) ^{1 + ε} ) dla dowolnej stałej ε > 0 .

Bibliografia

Przypisy

Źródła drugorzędne

Podstawowe źródła