Wann sollten wir Radix Art verwenden?
https://stackoverflow.com/questions/4146843
-
30-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Es scheint, Radix hat Art eine sehr gute durchschnittliche Leistung Fall, dh O (kN) : http://en.wikipedia.org/wiki/Radix_sort
, aber es scheint immer noch die meisten Menschen Sortieren mit Quick sind, nicht wahr?
Lösung
Schnell hat sortieren durchschnittlich O (N log N), aber es hat auch einen schlimmsten Fall von O (N ^ 2), so wegen auch in den meisten praktischen Fällen ist es zu N bekommen werde nicht ^ 2, gibt es immer die Gefahr, dass der Eingang wird für Sie in „schlechten Ordnung“ sein. Dieses Risiko besteht nicht in Radixsort. Ich denke, das einen großen Vorteil zu radix gibt Art.
Andere Tipps
Radix ist eine Art schwerer zu verallgemeinern, als die meisten anderen Sortieralgorithmen. Es erfordert Größe Schlüssel festgelegt und einige Standardverfahren der Schlüssel in Stücke brechen. So ist es nie findet seinen Weg in Bibliotheken.
Edited nach Ihren Kommentaren:
- Radix Art gilt nur für ganze Zahlen, feste Größe Strings, Gleitpunkte und auf „weniger als“, „größer als“ oder „lexikographische Ordnung“ Vergleichsprädikate, während Vergleich Sorten verschiedene Ordnungen aufnehmen können.
- k kann größer als log N.
- Schnell kann Art anstelle erfolgen, Radix wird sortieren weniger effizient.
Die anderen Antworten hier sind schrecklich, sie geben nicht Beispiele, wann Radixsort tatsächlich verwendet wird, .
Ein Beispiel ist, wenn ein "Suffix-Array" zu schaffen unter Verwendung des Skew DC3-Algorithmus (Kärkkäinen-Sanders-Burkhardt). Der Algorithmus ist nur linear-Zeit, wenn der Sortieralgorithmus linear-Zeit ist, und Radixsort ist notwendig und sinnvoll hier, weil die Tasten kurz sind durch die Konstruktion (3-Tupel von ganzen Zahlen).
Es sei denn, Sie haben eine große Liste oder extrem kleine Tasten, log (N) ist in der Regel kleiner als k ist es selten viel höher. So ein Universal Auswahl Sortieralgorithmus mit O (N log N) durchschnittliche Fall Leistung ist nicht neccesarily schlechter als Radixsort verwendet wird.
Korrektur : Wie @Mehrdad wies in den Kommentaren aus, über das Argument ist nicht stichhaltig: Entweder ist die Schlüsselgröße konstant ist, dann Radixsort O (N) oder die Schlüsselgröße ist k, dann ist quicksort O (N log k N). Also in der Theorie, Radixsort wirklich eine bessere asymptotische Laufzeit.
In der Praxis werden die Laufzeiten von Begriffen wie dominiert werden:
-
radix sort: c1 k N
-
quicksort: c2 k N log (N)
wobei c1 >> c2, weil Bits aus einem längeren Schlüssel „Extrahieren“ ist in der Regel eine teuere Operation mit Bit-Verschiebungen und logische Operationen (oder zumindest nicht ausgerichteter Speicherzugriff), während moderne CPUs können Schlüssel Vergleich mit 64, 128 oder sogar 256 Bit in einem Arbeitsgang. So für viele gängige Fälle, es sei denn, N gigantisch ist, wird c1 größer als c2 log (N)
Radix nimmt sort O (k * n) Zeit. Aber Sie haben zu fragen, was ist K. K ist die „Anzahl der Stellen“ (eine simple wenig, aber im Grunde so ähnlich).
So, wie viele Stellen haben Sie? Ganz Antwort, mehr als log (n) (log die "Digitgrße" als Basis verwendet wird), die den Radix-Algorithmus O macht (n log n).
Warum ist das so? Wenn Sie weniger als log (n) Ziffern haben, dann haben Sie weniger als n möglichen Zahlen. Daher können Sie einfach „Art zählen“, die O (n) Zeit in Anspruch nimmt (nur zählen, wie viele von jeder Zahl, die Sie haben). Also ich nehme an Sie haben mehr als k> log (n) Ziffern ...
Das ist, warum Menschen Radix nicht Art verwenden, die viel. Obwohl es Fälle gibt, in denen es sich lohnt, mit es in den meisten Fällen eine schnelle Art ist viel besser.
, wenn n> 128, sollten wir RadixSort verwenden
, wenn sort int32s, wähle ich radix 256, so k = log (256, 2 ^ 32) = 4, die als log signifikant kleiner ist, (2, n)
und in meinem Test, Radixsort ist 7-mal schneller als Quicksort im besten Fall.
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]来保证原有的顺序不变
}
}
k = "Länge des längsten Wert in Array sortiert werden"
n = "Länge des Arrays"
O (k * n) = "worst case läuft"
k * n = n ^ 2 (wenn k = n)
so bei der Verwendung von Radix Sort sicher „die längste ganzen Zahl ist kürzer als die Array-Größe“ oder vice versa. Dann gehen Sie Quicksort zu schlagen!
Der Nachteil ist. Die meiste Zeit kann man nicht garantieren, wie groß ganze Zahlen werden, aber wenn Sie einen festen Bereich von Zahlen haben radix sollte Art der Weg zu gehen
Hier ist ein Link, der quicksort und RadixSort vergleicht:
Is Radixsort schneller als Quicksort für integer Arrays? (ja es ist, 2-3x)
Hier ist eine andere Verbindung, die Laufzeiten von mehreren Algorithmen analysiert:
Welche schneller auf den gleichen Daten ist; ein O (n) Sorte oder eine O (nMelden (n)) sortieren?
Antwort: Es hängt davon ab. Es hängt von der Menge der Daten, die sortiert werden. Es hängt von der Hardware sein an laufen wird, und es hängt von der Implementierung der Algorithmen.
Radix Art ist kein Vergleich basierte Art und kann nur sortieren numerische Typen wie ganze Zahlen (einschließlich Zeigeradressen) und Floating-Point, und es ist ein bisschen schwierig zu portably Unterstützung Gleitkommazahlen.
Es ist wahrscheinlich, weil es solch einen engen Bereich der Anwendbarkeit hat, dass viele Standardbibliotheken wählen, um es zu unterlassen. Es kann nicht einmal lassen Sie Ihren eigenen Komparator liefern, da einige Leute nicht direkt selbst sortieren ganze Zahlen wollen vielleicht so viel wie mit den ganzen Zahlen als Indizes, um etwas anderes als Schlüssel verwendet zu werden, zum Sortieren, z.B. Vergleich basierte Sorten erlauben alles, was Flexibilität, so ist es wahrscheinlich ein Fall von nur eine verallgemeinerte Lösung Einpassen 99% der Menschen des täglichen Bedarfs lieber, anstatt zu gehen aus dem Weg zu verpflegen zu, dass 1%.
sagte, dass trotz der engen Anwendbarkeit in meiner Domain finde ich mehr Einsatz für Radixsort als introsorts oder quicksorts. Ich bin in dieser 1% und kaum jemals Arbeit mit, sagen wir, String-Schlüssel, aber oft Anwendungsfälle für Zahlen feststellen, dass von Vorteil sortiert werden. Es ist, weil meine Codebasis dreht sich um Indizes zu Einheiten und Komponenten (Entity-Komponenten-System) sowie Dinge wie indizierte Maschen und es gibt eine ganze Reihe von numerischen Daten.
Als Ergebnis sortiert radix wird für alle Arten von Dingen in meinem Fall nützlich. Ein gängiges Beispiel in meinem Fall ist die Beseitigung doppelten Indizes. In diesem Fall muss ich nicht wirklich die Ergebnisse sortiert werden aber oft sortieren eine Radix Duplikate schneller als die Alternativen beseitigen können.
Eine andere findet, sagen wir, eine mittlere Split für ein kd-Baum entlang einer bestimmten Dimension. Es radix für eine bestimmte Dimension, um die Fließkommawerte der Punktsortierung gibt mir eine mittlere Position schnell in linearer Zeit den Baumknoten aufzuspalten.
Ein weiterer Grund ist Tiefensortierung auf höherer Ebene Primitiven durch z für halb richtige Transparenz alpha, wenn wir nicht in einem Splitter Shader tun es werden werden. Das gilt auch für GUIs und Vektorgrafik-Software Z-Reihenfolge Elemente.
ist ein anderer Cache freundliche sequenziellen Zugriff eine Liste von Indizes verwendet. Wenn die Indizes oft durchlaufen werden, verbessert es häufig Leistung, wenn ich sie vorher sortieren Radix, so dass der Durchlauf in der angegebenen Reihenfolge statt zufälliger Reihenfolge durchgeführt wird. Letzteres könnte Zickzack hin und her in einem Speicher, von Daten von Cache-Zeilen evicting nur den gleichen Speicherbereich wiederholt innerhalb der gleichen Schleife erneut zu laden. Wenn Radix ich die Indizes sortieren zuerst bevor sie wiederholt den Zugriff auf das aufhört passieren, und ich kann Cache-Misses erheblich reduzieren. Das ist eigentlich meine häufigste Verwendung für Radixsort und es ist der Schlüssel zu meinem ECS seinem Cache-freundlich, wenn Systemen für den Zugriff Einheiten wollen mit zwei oder mehr Komponenten.
In meinem Fall habe ich einen multithreaded Radixsort, die ich ziemlich oft. Einige Benchmarks:
--------------------------------------------
- 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 ]
Ich kann durchschnittlich etwas wie 6-7 ms eine Million Zahlen einmal auf meiner dinky Hardware sortieren, die schnell nicht so ist, wie ich mag da 6-7 Millisekunden nach wie vor von den Benutzern manchmal in interaktiven Kontexten wahrgenommen werden können, aber noch eine ganze Menge besser als 55-85 ms wie im Fall von C ++ 's std::sort oder C des qsort, die auf jeden Fall sehr offensichtlich Schluckauf in Frame-Raten führen würden. Ich habe sogar SIMD von Menschen Implementierung Radixsort Verwendung gehört, obwohl ich keine Ahnung, wie sie das geschafft. Ich bin nicht schlau genug, um mit einer solchen Lösung zu kommen, auch wenn meine naive kleine Radixsort ist recht gut im Vergleich zu den Standardbibliotheken.
Ein Beispiel wäre, wenn Sie eine sehr große Menge oder Array von ganzen Zahlen sind zu sortieren. Eine Radix Sort und alle anderen Typen Verteilung sortiert sind extrem schnell, da die Datenelemente in erster Linie in einer Anordnung von Warteschlangen (max 10 Warteschlangen für eine LSD Radixsort) und Neuzuordnung zu einem anderen Index Position des gleichen Eingangsdaten die Warteschlange eingereiht wird, sortiert werden. Es gibt keine verschachtelten Schleifen so der Algorithmus mehr linear zu verhalten neigt als die Anzahl der Dateneingabe ganzen Zahlen sortiert werden wird deutlich größer. Im Gegensatz zu anderen Sortierverfahren, wie die äußerst ineffizient BubbleSort Methode, Art die Radix nicht implementiert Vergleichsoperationen zu sortieren. Es ist nur ein einfacher Prozess, der ganzen Zahlen zu verschiedenen Indexpositionen Remapping, bis die Eingabe schließlich sortiert ist. Wenn Sie möchten, dass Art ein LSD radix testen, für sich selbst, ich habe ein und gespeichert auf Github geschrieben, die leicht auf einer Online-js getestet werden können ide wie Codierung Sandbox eloquent Javascript. Fühlen Sie sich frei, mit ihm zu spielen, um und beobachten, wie sie mit einer unterschiedlichen Anzahl von n verhält. Ich habe mit bis zu 900.000 unsortierte ganzen Zahlen mit einer Laufzeit <300 ms getestet. Hier ist der Link, wenn Sie mit ihm spielen, um möchten.
https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6
