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.