Praktyczne zastosowania Radix Sort

Sortowanie Radix jest teoretycznie bardzo szybkie, gdy wiesz, że klucze znajdują się w pewnym ograniczonym zakresie, np. wartości z zakresu [ 0 … n k - 1 ] . Jeśli k < lg n po prostu przekonwertujesz wartości na bazę n, co zajmuje Θ ( n ) czasu, wykonaj sortowanie podstawy n radix, a następnie przekonwertuj z powrotem na pierwotną bazę dla ogólnego algorytmu Θ ( n k ) .$n$$[0\dots n^k -1]$$k<\lg n$$n$$\Theta(n)$$n$$\Theta(nk)$

Jednak przeczytałem, że w praktyce sortowanie radix jest zwykle znacznie wolniejsze niż na przykład zrobienie losowego szybkiego sortowania :

W przypadku dużych tablic sortowanie radix ma najniższą liczbę instrukcji, ale ze względu na stosunkowo słabą wydajność pamięci podręcznej jego ogólna wydajność jest gorsza niż zoptymalizowane pod względem pamięci wersje scalesort i quicksort.

Czy sortowanie radix jest po prostu dobrym algorytmem teoretycznym, czy może ma on praktyczne zastosowania?

Sortowania Radix są często w praktyce najszybszymi i najbardziej przydatnymi sortowaniami na maszynach równoległych.

• Zagha ​​i Blelloch: Sortowanie Radix dla wektorowych multiprocesorów. Supercomputing , 1991: 712-721.
• Blelloch, Leiserson, Maggs, Plaxton, Smith i Zagha: Porównanie algorytmów sortowania dla maszyny łączącej CM-2. Symp Parallel Algorytmy i Arch (SPAA-3): 3-16, 1991.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein i Patterson: Wydajne sortowanie w sieciach stacji roboczych. Conf on Mgt of Data , (SIGMOD-1997): 243–254.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein i Patterson. Wyszukiwanie rekordu sortowania: doświadczenia w dostrajaniu NOW-Sort. Narzędzia równoległe i rozproszone ACM Sigmetrics Symp , (SPDT-2): 124-133, 1998.

Na każdym węźle multiprocesora prawdopodobnie wykonujesz coś w rodzaju szybkiego sortowania, ale sortowanie radix pozwala wielu węzłom współpracować z mniejszą synchronizacją niż różne rodzaje rekurencyjne.

Są też inne sytuacje. Jeśli potrzebujesz stabilnego sortowania (takiego, w którym za każdym razem, gdy dwa klucze są równe, pozostają one w tej samej kolejności, zamiast się zmieniać), to nie znam żadnej wersji szybkiego sortowania, która byłaby przydatna. Mergesort jest również stabilny (jeśli jest poprawnie zaimplementowany). Twój link po raz pierwszy słyszałem, jak ktokolwiek powiedział, że połączenie może mieć lepsze zachowanie pamięci podręcznej niż sortowanie radix.

@Robert: Twój link jest dość zaskakujący (w rzeczywistości nie mogłem znaleźć cytowanego zdania). Moje osobiste doświadczenia dotyczą losowego wprowadzania danych, sortowanie radix jest znacznie szybsze niż STL std::sort(), który wykorzystuje wariant szybkiego sortowania. Robiłem algorytm 50% szybciej, zastępując std::sort()go niestabilnym sortowaniem radix. Nie jestem pewien, jaka jest „wersja zoptymalizowana pod kątem pamięci” Quicksort, ale wątpię, aby była ona dwa razy szybsza niż wersja STL.

W tym poście oceniano sortowanie radix wraz z kilkoma innymi algorytmami sortowania. W skrócie, w tej ocenie, std::sort()sortowanie 50 milionów liczb całkowitych zajmuje 5,1 sekundy, podczas gdy sortowanie w miejscu / niestabilnym radixie zajmuje 2,0 sekundy. Stabilne sortowanie radix powinno być jeszcze szybsze.

Sortowanie Radix jest również szeroko stosowane do stabilnego sortowania ciągów. Warianty sortowania radix są czasami widoczne przy konstruowaniu tablic sufiksów, BWT itp.

Sortowanie Radix to także naturalny sposób sortowania słów o stałej długości według ustalonego alfabetu, np. W algorytmie Kärkkäinen & Sanders ( http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf )