Dlaczego Radix Sort nie jest używany częściej?

Jest stabilny i ma złożoność czasową O (n). Powinno być szybsze niż algorytmy takie jak Quicksort i Mergesort, ale rzadko kiedy go używam.

W przeciwieństwie do sortowania radix, szybkie sortowanie jest uniwersalne, a sortowanie radix jest użyteczne tylko dla kluczy liczb całkowitych o stałej długości.

Musisz także zrozumieć, że O (f (n)) naprawdę oznacza w kolejności K * f (n), gdzie K jest jakąś dowolną stałą. W przypadku sortowania radix ten K okazuje się być dość duży (przynajmniej porządek liczby bitów w posortowanych liczbach całkowitych), z drugiej strony quicksort ma jeden z najniższych K wśród wszystkich algorytmów sortowania i średnią złożoność n * log (n). Tak więc w rzeczywistym scenariuszu szybkie sortowanie będzie bardzo często szybsze niż sortowanie radix.

Większość algorytmów sortowania ma zastosowanie ogólne. Biorąc pod uwagę funkcję porównania, działają na wszystkim, a algorytmy takie jak Quicksort i Heapsort będą sortować z dodatkową pamięcią O (1).

Sortowanie Radix jest bardziej wyspecjalizowane. Potrzebujesz określonego klucza w porządku leksykograficznym. Potrzebujesz jednego wiadra na każdy możliwy symbol w kluczu, a wiadra muszą zawierać wiele rekordów. (Alternatywnie, potrzebujesz jednego dużego zestawu wiader, który pomieści każdą możliwą wartość klucza.) Prawdopodobnie będziesz potrzebować dużo więcej pamięci, aby sortować radix, i będziesz używać go losowo. Żadne z tych rozwiązań nie jest dobre dla współczesnych komputerów, ponieważ prawdopodobnie wystąpią błędy strony, takie jak Quicksort, spowoduje brak pamięci podręcznej.

Wreszcie, ludzie na ogół nie piszą już własnych algorytmów sortowania. Większość języków ma funkcje biblioteczne do sortowania, a właściwą rzeczą jest zwykle korzystanie z nich. Ponieważ sortowanie radix nie ma uniwersalnego zastosowania, zazwyczaj musi być dostosowane do faktycznego wykorzystania i wymaga dużej ilości dodatkowej pamięci, trudno jest umieścić go w funkcji lub szablonie biblioteki.

Bardzo rzadko sortowane klucze są liczbami całkowitymi w znanym, rzadkim zakresie. Zwykle masz pola alfabetyczne, które wyglądają, jakby obsługiwały sortowanie nieporównawcze, ale ponieważ ciągi znaków rzeczywistych nie są równomiernie rozmieszczone w całym alfabecie, nie działa to tak dobrze, jak powinno.

Innym razem kryterium jest definiowane tylko operacyjnie (biorąc pod uwagę dwa rekordy, możesz zdecydować, które są pierwsze, ale nie możesz ocenić, jak „daleko” w dół skali jest izolowany rekord). Tak więc metoda często nie ma zastosowania, jest mniej przydatna, niż się wydaje, lub po prostu nie szybciej niż O (n * log (n)).

Używam go przez cały czas, właściwie bardziej niż na podstawie porównań, ale przyznaję, że jestem dziwną kulą, która działa bardziej z liczbami niż cokolwiek innego (prawie nigdy nie pracuję z łańcuchami, a na ogół są internowane, jeśli tak, to w którym momencie radix sortowanie może być znowu przydatne do odfiltrowywania duplikatów i obliczania przecięć zestawów; praktycznie nigdy nie wykonuję porównań leksykograficznych).

Podstawowym przykładem jest sortowanie punktów za pomocą wymiaru według określonego wymiaru w ramach wyszukiwania lub podziału mediany lub szybki sposób wykrywania punktów zbieżnych, fragmentów sortowania głębokości lub sortowania za pomocą szeregu wskaźników używanych w wielu pętlach, aby zapewnić bardziej przyjazny dostęp do pamięci podręcznej wzorce (nie wracają do przodu i do tyłu w pamięci tylko po to, aby wrócić ponownie i ponownie załadować tę samą pamięć do linii bufora) Przynajmniej w mojej domenie jest bardzo szeroka aplikacja (grafika komputerowa) do sortowania według 32-bitowych i 64-bitowych kluczy numerycznych o stałej wielkości.

Jedną rzeczą, którą chciałem dodać i powiedzieć, jest to, że sortowanie radix może działać na liczbach zmiennoprzecinkowych i ujemnych, chociaż trudno jest napisać wersję FP, która jest tak przenośna, jak to możliwe. Ponadto, gdy jest to O (n * K), K musi być tylko liczbą bajtów wielkości klucza (np. Milion 32-bitowych liczb całkowitych zwykle zająłby 4 bajty, jeśli w segmencie są 2 ^ 8 wpisów ). Wzorzec dostępu do pamięci jest zwykle bardziej przyjazny dla pamięci podręcznej niż szybkie sortowanie, mimo że zwykle wymaga równoległej tablicy i małej tablicy segmentów (drugi zwykle może dobrze pasować do stosu). QS może wykonać 50 milionów swapów, aby posortować tablicę milionów liczb całkowitych o sporadycznych wzorcach losowego dostępu. Sortowanie radix może to zrobić w 4 liniowych, przyjaznych dla bufora przejściach nad danymi.

Jednak brak świadomości, że jest w stanie to zrobić z małym K, przy liczbach ujemnych wraz z liczbą zmiennoprzecinkową, może bardzo dobrze przyczynić się do braku popularności rodzajów radix.

Jeśli chodzi o moją opinię o tym, dlaczego ludzie nie używają go częściej, może to mieć związek z wieloma domenami, które zazwyczaj nie wymagają sortowania liczb lub używania ich jako kluczy wyszukiwania. Jednak na podstawie mojego osobistego doświadczenia wielu moich byłych kolegów również nie używało go w przypadkach, w których był idealnie dopasowany, a częściowo dlatego, że nie byli świadomi, że można go wykorzystać do FP i negatywów. Poza tym, że działa tylko na typach numerycznych, często uważa się, że ma jeszcze mniej ogólne zastosowanie niż w rzeczywistości. Nie przydałby mi się tak bardzo, gdybym myślał, że to nie działa na liczbach zmiennoprzecinkowych i ujemnych liczbach całkowitych.

Niektóre punkty odniesienia:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

I to tylko z moją naiwną implementacją ( mt_sort_intto także sortowanie radix, ale z szybszą gałęzią kodu, biorąc pod uwagę, że można założyć, że klucz jest liczbą całkowitą). Wyobraź sobie, jak szybko może być standardowa implementacja napisana przez ekspertów.

Jedyny przypadek, w którym stwierdziłem, że sortowanie radix jest gorsze niż naprawdę szybkie porównywanie w C ++, dotyczyło std::sortnaprawdę niewielkiej liczby elementów, powiedzmy 32, w którym to momencie wydaje mi się, że std::sortzaczyna się używać rodzajów lepiej dopasowanych do najmniejszej liczby elementów, takich jak heapsorts lub rodzaje wstawiania, chociaż w tym momencie moja implementacja po prostu używa std::sort.

Jeszcze jeden powód: w dzisiejszych czasach sortowanie jest zwykle realizowane za pomocą dostarczonej przez użytkownika procedury sortowania dołączonej do logiki sortowania dostarczonej przez kompilator. W przypadku sortowania radix byłoby to znacznie bardziej skomplikowane, a nawet pogorszyło się, gdy procedura sortowania działa na wiele kluczy o zmiennej długości. (Powiedz, imię i datę urodzenia.)

W rzeczywistym świecie I rzeczywiście realizowane sortowania radix raz. To było w dawnych czasach, kiedy pamięć była ograniczona, nie mogłem przenieść wszystkich moich danych na raz. Oznaczało to, że liczba dostępów do danych była znacznie ważniejsza niż O (n) vs O (n log n). Wykonałem jedno przejście przez dane alokujące każdy rekord do kosza (według listy, w których rekordach znajdowały się pojemniki, w rzeczywistości niczego nie przenosząc.) Dla każdego niepustego kosza (moim kluczem sortowania był tekst, będzie dużo puste pojemniki) Sprawdziłem, czy rzeczywiście mogę wprowadzić dane do pamięci - jeśli tak, przynieś je i użyj szybkiego sortowania. Jeśli nie, skompiluj plik tymczasowy zawierający tylko elementy z pojemnika i wywołaj procedurę cyklicznie. (W praktyce przepełniłoby się kilka pojemników). Spowodowało to dwa pełne odczyty i jeden pełny zapis do pamięci sieciowej i około 10% tej ilości do pamięci lokalnej.

W dzisiejszych czasach takie problemy z dużymi danymi są o wiele trudniejsze do znalezienia, prawdopodobnie nigdy więcej tego nie napiszę. (Gdybym dzisiaj miał do czynienia z tymi samymi danymi, po prostu określiłbym 64-bitowy system operacyjny, dodaj RAM, jeśli dostaniesz thrash w tym edytorze).

Jeśli wszystkie parametry są liczbami całkowitymi i jeśli masz ponad 1024 parametry wejściowe, sortowanie radix jest zawsze szybsze.

Czemu?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

Więc sortowanie radix jest szybsze, kiedy

log(n)> max num of digits

Maksymalna liczba całkowita w Javie to 2147483647. Ma ona 10 cyfr

Tak więc sortowanie radix jest zawsze szybsze, gdy

log(n)> 10

Dlatego sortowanie radix jest zawsze szybsze, gdy n>1024