Wydaje sortowanie pozycyjne ma bardzo dobrą średnią wydajność sprawy, tj O (kN): http://en.wikipedia.org/wiki/Radix_sortKiedy należy używać sortowania Radix?
ale wydaje się, większość ludzi nadal używasz szybkiego sortowania, prawda?
Szybki sort ma średnią O (N logN), ale ma też najgorszy przypadek O (N^2), więc nawet w większości praktycznych przypadków nie osiągnie N^2, zawsze istnieje ryzyko, że dane wejściowe będą dla Ciebie "złym porządkiem". Ryzyko to nie występuje w sortowaniu radix. Myślę, że daje to wielką korzyść przy sortowaniu radix.
To raczej nie będzie główną zaletą.Inne sortowania oparte na porównaniu (takie jak heapsort lub mergesort) nie mają tak złego, najgorszego scenariusza jak quicksort. –
Najgorszy scenariusz dla quicksorta nie jest tak naprawdę argumentem, ponieważ dlatego ludzie zwykle używają randomizowanych quicksortów, tj. Przetasowują dane wejściowe przed ich rzeczywistym sortowaniem. to praktycznie eliminuje szansę na czas działania N^2. – nburk
Introsort, który używa quicksort, zajmuje się tym. To nie jest argument. – Mehrdad
Zmieniano według własnych opinii:
"Szybkie sortowanie może być wykonane na miejscu" - tak może sortowanie z sortowaniem binarnym, chociaż zwiększa to prawdopodobieństwo, że k jest większe niż log N. –
Twój pierwszy punkt nie jest całkiem poprawny - sortowanie Radix może być łatwo zastosowane do stałych łańcuchów długości. A predykat porównania jest wymagany bez względu na to jakiego algorytmu sortowania używasz. –
"Sortowanie radix stosuje się tylko do liczb całkowitych": Dlaczego? Zawsze myślałem, że sortując według bitów wykładniczych i bitów mantysowych we właściwej kolejności, możesz użyć go do sortowania liczb zmiennoprzecinkowych. I teoretycznie * możesz * użyć go na łańcuchach, tylko k będzie prawie zawsze większy niż log N wtedy. – Niki
Sortowanie radix jest trudniejsze do uogólnienia niż większość innych algorytmów sortowania. Wymaga kluczy o ustalonych rozmiarach i standardowego sposobu łamania kluczy na kawałki. Dlatego nigdy nie trafia do bibliotek.
Jeśli nie masz ogromnej lub bardzo małych klawiszy, log (N) jest zwykle mniejszy niż k, rzadko jest dużo wyższy. Zatem wybór ogólnego algorytmu sortowania z O (N log N) średnią wydajność sprawy nie jest koniecznie gorszy niż przy użyciu sortowania radix.
Korekta: Jak @Mehrdad zauważył w komentarzach, powyższy argument nie brzmi: czy rozmiar klucza jest stała, a następnie sortowanie pozycyjne wynosi O (N), lub rozmiar klucza wynosi k, a następnie quicksort to O (k N log N). Tak więc w teorii sortowanie radix ma naprawdę lepsze asymptotyczne środowisko uruchomieniowe.
W praktyce czasy pracy będzie zdominowany przez takich pojęć, jak:
sortowanie pozycyjne: c1 k N
quicksort: c2 k N log (N)
gdzie c1 >> c2, ponieważ "wyodrębnianie" bitów z dłuższego klucza jest zwykle kosztowną operacją obejmującą przesunięcia bitowe i operacje logiczne (lub przynajmniej niewyrównany dostęp do pamięci), podczas gdy nowoczesne procesory mogą porównywać klucze z 64, 128 lub nawet 256 bitami w jednej operacji. Tak więc dla wielu typowych przypadków, jeśli N nie jest gigantyczne, c1 będzie większe niż c2 log (N)
Nie dotyczy to wszystkich przypadków. 'k' nie musi być zliczoną liczbą, może to być na przykład liczba bajtów - jeśli sortujesz 4-bajtowe liczby całkowite,' N' musi być mniejsze niż 16, aby 'log N' było mniejsze niż 4 –
O (N log N) jest ** kłamstwem **. Nie ma takiej rzeczy. To jest O (k N log N) kontra O (k N) - jeśli mi nie wierzysz, zadaj sobie pytanie, jak na świecie sortowanie może być niezależne od rozmiaru elementu. – Mehrdad
@Mebrad: To wydaje się być argumentem na temat semantyki. Sposób, w jaki go poznałem, N w O (N log N) to rozmiar danych wejściowych, np. w bitach. Wtedy albo elementy mają stały rozmiar, albo są tylko elementy N/k. – Niki
Sortowanie radix zajmuje czas O (k * n). Ale musisz zapytać, co to jest K. K to "liczba cyfr" (nieco uproszczona, ale w zasadzie coś takiego).
Ile więc masz cyfr? Dość odpowiedź, więcej niż log (n) (log używając "cyfrowej wielkości" jako bazy), która tworzy algorytm Radix O (n log n).
Dlaczego tak jest? Jeśli masz mniej niż log (n) cyfr, masz mniej niż n możliwych liczb. Stąd możesz po prostu użyć "count sort", który zabiera O (n) czas (po prostu policz ile masz numerów). Zakładam więc, że masz więcej niż k> log (n) cyfr ...
Dlatego ludzie nie używają Radix tak bardzo. Chociaż zdarzają się przypadki, w których warto go używać, w większości przypadków szybkie sortowanie jest znacznie lepsze.
K = "długość najdłuższego wartości w tablicy być uporządkowane"
n = "długość tablicy"
O (K * n) = "najgorszy przypadek uruchomiony"
k * n = n^2 (jeśli k = n)
, więc podczas sortowania radix upewnij się, że "najdłuższa liczba całkowita jest krótsza niż rozmiar tablicy" lub na odwrót. Wtedy pokonasz Quicksorta!
Wadą jest: W większości przypadków nie można zagwarantować, jak duże stają się liczby całkowite, ale jeśli masz ustalony zakres liczb, sortowanie radix powinno być drogą do zrobienia.
gdy n> 128, należy użyć sortowanie pozycyjne
podczas sortowania int32s, to przełącz radix 256, tak, K = log (256, 2^32) = 4, co ma znaczenie mniejsze niż log (2, n)
W moim teście sortowanie radix jest 7 razy szybsze niż quicksort w najlepszym przypadku.
public class RadixSort {
private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
private final int bar[]=new int[radix];
private int s[] = new int[65536];//不使用额外的数组t，提高cpu的cache命中率
public void ensureSort(int len){
if(s.length < len)
s = new int[len];
}
public void sort(int[] a){
int n=a.length;
ensureSort(n);
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素，在bar中找到下标x=bar[slot]-1, 另s[x]=a[i]（同时--bar[slot]将下标前移，供桶内其它元素使用）
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数，比正数小
bar[0] += bar[255];
for(int i=1;i<128;i++)bar[i]+=bar[i-1];
for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变
}
}
Czy radix-256 nie potrzebuje 256-krotnej pamięci rozmiaru oryginalnej tablicy? –
nie, jak widać w kodach, potrzebny jest tylko pasek [256] i s [oryginalna długość], to dodatkowe 1-krotne zapamiętywanie oryginalnej tablicy – zhuwenbin
innych odpowiedzi tutaj są straszne, nie dają przykłady kiedy sortowanie pozycyjne jest faktycznie wykorzystywany.
Przykład dotyczy tworzenia "tablicy sufiksów" za pomocą algorytmu skośnego DC3 (Kärkkäinen-Sanders-Burkhardt). Algorytm jest tylko liniowy, jeśli algorytm sortowania jest liniowo-czasowy, a sortowanie radix jest konieczne i użyteczne, ponieważ klucze są krótkie przez konstrukcję (3-krotne liczby całkowite).
Całkowicie się zgadzam. Brak wzmianek o tym, kiedy faktycznie jest używany, i żadnych rzeczywistych benchmarków, które porównują oba algorytmy. – johndoevodka
Oto link, który porównuje quicksort i sortowanie pozycyjne:
Is radix sort faster than quicksort for integer arrays? (tak to jest, 2-3x)
Oto kolejny związek, który analizuje razy z rzędu kilku algorytmów:
Który jest szybszy na tych samych danych; sortowanie O (n) lub O (nLog (n))?
Odpowiedź: To zależy. To zależy od ilości sortowanych danych. To zależy od sprzętu, na którym działa i zależy od implementacji algorytmów.
Jednym z przykładów może być sortowanie bardzo dużych zbiorów lub tablic liczb całkowitych. Sortowanie radix i wszelkie inne typy sortowania dystrybucji są niezwykle szybkie, ponieważ elementy danych są głównie umieszczane w tablicy kolejek (maksymalnie 10 kolejek dla sortowania radixów LSD) i remapowane na inną lokalizację indeksu tych samych danych wejściowych, które mają być sortowane. Nie ma zagnieżdżonych pętli, więc algorytm ma tendencję do zachowywania się bardziej liniowo, ponieważ liczba wprowadzanych liczb całkowitych do sortowania staje się znacznie większa. W przeciwieństwie do innych metod sortowania, takich jak wyjątkowo nieefektywna metoda bubbleSort, sortowanie radix nie implementuje operacji porównania do sortowania. Jest to po prostu prosty proces ponownego mapowania liczb całkowitych na różne pozycje indeksu, dopóki dane wejściowe nie zostaną ostatecznie posortowane.Jeśli chcesz przetestować sortowanie radix LSD dla siebie, napisałem jedną i zapisałem na githubie, który można łatwo przetestować na internetowej idei js, takiej jak wymowna pisownia kodu javascript. Zapraszam do zabawy i obejrzenia, jak zachowuje się przy różnej liczbie n. Przetestowałem z maksymalnie 900 000 nieposortowanych liczb całkowitych z runtime < 300ms. Oto link, jeśli chcesz się z nim bawić.
https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6
sortowanie pozycyjne nie jest rodzajem porównanie oparte a może tylko typy liczbowe, takie jak rodzaj liczb całkowitych (w tym adresów wskaźnika) i zmiennoprzecinkowych, a to trochę trudne do przenośnie wspierać zmiennoprzecinkową.
Jest tak prawdopodobnie dlatego, że ma tak wąski zakres zastosowania, że wiele standardowych bibliotek decyduje się go pominąć. Nie może nawet pozwolić ci dostarczyć własnego komparatora, ponieważ niektóre osoby mogą nie chcieć nawet sortować liczb całkowitych bezpośrednio tak bardzo, jak używanie liczb całkowitych jako indeksów do czegoś innego, które będzie używane jako klucz do sortowania, np. Sortowanie oparte na porównaniu pozwala na taką elastyczność, więc prawdopodobnie jest to przypadek, w którym preferowane jest uogólnione rozwiązanie odpowiadające 99% codziennych potrzeb ludzi, zamiast wychodzić z drogi, aby zaspokoić ten 1%.
To powiedziawszy, pomimo wąskiej możliwości zastosowania, w mojej domenie znajduję więcej zastosowań dla rodzajów radix niż introsorts lub quicksorts. Jestem w tym 1% i prawie nigdy nie pracuję z, powiedzmy, kluczami strunowymi, ale często znajduję przypadki użycia dla liczb, które korzystają z sortowania. Dzieje się tak dlatego, że moja baza kodu obraca się wokół indeksów do elementów i komponentów (system elementów-komponentów), jak również takich, jak indeksowane siatki i jest mnóstwo danych liczbowych.
W rezultacie sortowanie radix przydaje się w przypadku wszystkich rodzajów rzeczy w moim przypadku. Jednym z typowych przykładów w moim przypadku jest wyeliminowanie zduplikowanych indeksów. W takim przypadku tak naprawdę nie potrzebuję sortowania wyników, ale często sortowanie radix może wyeliminować duplikaty szybciej niż alternatywy.
Innym jest znalezienie, powiedzmy, mediany podziału dla drzewa kd wzdłuż danego wymiaru. Tam sortowanie radix wartości zmiennoprzecinkowych punktu dla danego wymiaru daje mi medianę pozycji szybko w czasie liniowym, aby podzielić węzeł drzewa.
Innym z nich są prymitywy o wyższym poziomie sortowania głębi przez z dla pół-właściwej przezroczystości alfa, jeśli nie zamierzamy tego robić w shaderze frag. Dotyczy to również graficznego interfejsu użytkownika i oprogramowania graficznego wektorowego do elementów z-order.
Innym jest dostęp sekwencyjny przyjazny dla pamięci podręcznej przy użyciu listy indeksów. Jeśli indeksy są wykonywane wielokrotnie, często poprawia wydajność, jeśli sortuję je z wyprzedzeniem, tak aby przejście zostało wykonane w kolejności, a nie w kolejności losowej. Te ostatnie mogą zygzakowac w pamięci, usuwając dane z linii pamięci podręcznej tylko po to, aby wielokrotnie przeładowywać ten sam obszar pamięci w tej samej pętli. Kiedy sortuję indeksy najpierw przed uzyskaniem dostępu do nich wielokrotnie, to przestaje się dziać i mogę znacznie zmniejszyć chybienia pamięci podręcznej. To jest moje najpopularniejsze narzędzie do sortowania radix i jest kluczem do tego, aby mój ECS był przyjazny dla pamięci podręcznej, kiedy systemy chcą uzyskać dostęp do jednostek z dwoma lub więcej komponentami.
W moim przypadku mam wielowątkowy rodzaj radix, z którego korzystam dość często. Niektóre punkty odniesienia:
--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...
mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mogę coś średnio 6-7 ms posortować milionów numerów jeden raz na mój przemiły sprzętu, który nie jest tak szybki jak chciałbym od 6-7 milisekund można jeszcze zauważone przez użytkownicy czasami w kontekstach interaktywnych, ale wciąż o wiele lepszej niż 55-85 ms, jak w przypadku C++ 's std::sort lub C's qsort, co z pewnością doprowadziłoby do oczywistych problemów związanych z częstością klatek na sekundę.Słyszałem nawet o ludziach wdrażających rodzaje radixów przy użyciu SIMD, choć nie mam pojęcia, jak sobie z tym poradzili. Nie jestem na tyle sprytny, aby zaproponować takie rozwiązanie, choć nawet moja naiwna mała grupa radix ma się całkiem dobrze w porównaniu ze standardowymi bibliotekami.
Większość osób korzysta z procedury sortowania dostarczanej przez preferowane środowisko, nawet nie dbając o algorytm. –
Sortowanie radix nie jest dobre z różnymi rodzajami danych, ale kiedy chcesz sortować unsigned int i chcesz robić sortowanie na procesorze wielordzeniowym, takim jak GPU, sortowanie radix jest szybsze. – tintin