Praktyczne zastosowania Radix Sort

20

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[0nk1]k<lgnnΘ(n)nΘ(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?

Robert S. Barnes
źródło

Odpowiedzi:

15

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

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.

Wędrująca logika
źródło
Patterson i Hennessy podnoszą ten sam punkt, co wyżej połączony artykuł Lamarca w swojej książce Computer Organisation and Design.
Robert S. Barnes
Twoja wzmianka o Patterson przypomniała mi o ważnej pracy, którą Andrea Arpaci-Dusseau wykonała przy sortowaniu klastrów około 15 lat temu. (Patterson był współautorem). W artykule z 1997 roku faktycznie zdecydowali, że sortowanie z częściowym radixem jest lepsze niż szybkie sortowanie również na poszczególnych węzłach. (Dodałem odniesienia do odpowiedzi).
Wandering Logic
To interesujące. W czwartej edycji CompOrg z 2009 r. Odwołują się do pracy Lamarca nad poprzednimi wersjami Radix, które są nieprzyjazne dla pamięci podręcznej (str. 489), ale następnie na stronie 490 pod wykresami porównującymi sortowanie Quicksort i Radix mówią: „Z powodu takich wyników nowe wersje Wymyślono sortowanie Radix, które uwzględnia hierarchię pamięci, aby odzyskać swoje zalety algorytmiczne ”. Jestem ciekawy, jak działają te nowe wersje Radix Sort.
Robert S. Barnes,
Podejrzewam, że Lamarca użył właśnie głupiego rodzaju radix (takiego, który zachowuje swoje wiadra jako powiązane listy). Nikt nigdy by tego nie zrobił. Zaimplementowałbyś segmenty przy użyciu pewnego rodzaju zoptymalizowanej tablicy dynamicznej (np. C ++ vector). Ale nie wiem, bo nie czytałem gazet Lamarca.
Wandering Logic
@WanderingLogic, gdzie sortowanie radix używa wiader? Masz na myśli sortowanie kubełkowe tutaj?
Bar
3

@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.

użytkownik172818
źródło