Gibt es eine gute radixsort-Implementierung für Floats in C#

Question

Ich habe eine Datenstruktur mit einem Feld vom Typ float. Eine Sammlung dieser Strukturen muss nach dem Wert des Floats sortiert werden. Gibt es dafür eine radix-sort-Implementierung?

Wenn nicht, gibt es einen schnellen Weg, um auf den Exponenten, das Vorzeichen und die Mantisse zuzugreifen. Weil, wenn Sie die Floats zuerst auf Mantisse, Exponent und Exponent das letzte Mal sortieren. Sie sortieren in O (n).

Answer 1

Update:

Ich war sehr an diesem Thema interessiert, so setzte ich mich hin und setzte es (mit this very fast and memory conservative implementation). Ich lese auch this one (danke celion) und fand heraus, dass Sie nicht sogar die Schwimmer in Mantisse und Exponent teilen müssen, um es zu sortieren. Sie müssen nur die Bits eins zu eins nehmen und eine int-Sortierung durchführen. Man muss sich nur um die negativen Werte kümmern, die am Ende des Algorithmus invers vor die positiven gesetzt werden müssen (das habe ich in einem Schritt mit der letzten Iteration des Algorithmus gemacht, um etwas CPU-Zeit zu sparen).

So herer mein Schwimmer RadixSort:

public static float[] RadixSort(this float[] array) 
{ 
    // temporary array and the array of converted floats to ints 
    int[] t = new int[array.Length]; 
    int[] a = new int[array.Length]; 
    for (int i = 0; i < array.Length; i++) 
     a[i] = BitConverter.ToInt32(BitConverter.GetBytes(array[i]), 0); 

    // set the group length to 1, 2, 4, 8 or 16 
    // and see which one is quicker 
    int groupLength = 4; 
    int bitLength = 32; 

    // counting and prefix arrays 
    // (dimension is 2^r, the number of possible values of a r-bit number) 
    int[] count = new int[1 << groupLength]; 
    int[] pref = new int[1 << groupLength]; 
    int groups = bitLength/groupLength; 
    int mask = (1 << groupLength) - 1; 
    int negatives = 0, positives = 0; 

    for (int c = 0, shift = 0; c < groups; c++, shift += groupLength) 
    { 
     // reset count array 
     for (int j = 0; j < count.Length; j++) 
      count[j] = 0; 

     // counting elements of the c-th group 
     for (int i = 0; i < a.Length; i++) 
     { 
      count[(a[i] >> shift) & mask]++; 

      // additionally count all negative 
      // values in first round 
      if (c == 0 && a[i] < 0) 
       negatives++; 
     } 
     if (c == 0) positives = a.Length - negatives; 

     // calculating prefixes 
     pref[0] = 0; 
     for (int i = 1; i < count.Length; i++) 
      pref[i] = pref[i - 1] + count[i - 1]; 

     // from a[] to t[] elements ordered by c-th group 
     for (int i = 0; i < a.Length; i++){ 
      // Get the right index to sort the number in 
      int index = pref[(a[i] >> shift) & mask]++; 

      if (c == groups - 1) 
      { 
       // We're in the last (most significant) group, if the 
       // number is negative, order them inversely in front 
       // of the array, pushing positive ones back. 
       if (a[i] < 0) 
        index = positives - (index - negatives) - 1; 
       else 
        index += negatives; 
      } 
      t[index] = a[i]; 
     } 

     // a[]=t[] and start again until the last group 
     t.CopyTo(a, 0); 
    } 

    // Convert back the ints to the float array 
    float[] ret = new float[a.Length]; 
    for (int i = 0; i < a.Length; i++) 
     ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0); 

    return ret; 
} 

Es ist etwas langsamer als eine Art int radix, weil der Array Kopierens am Anfang und Ende der Funktion, wo der Schwimmer ist bitweise kopiert Ints und zurück. Die ganze Funktion ist jedoch wieder O (n). In jedem Fall viel schneller als das Sortieren 3 Mal in Folge wie Sie vorgeschlagen. Ich sehe nicht mehr viel Raum für Optimierungen, aber wenn jemand das tut, kannst du es mir sagen.

sortieren Änderung am Ende dieser Zeile absteigend:

ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0); 

dazu:

ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0); 

Messen:

ich einige kurze Test einrichten, um alle Sonder enthalten Fälle von Floats (NaN, +/- Inf, Min/Max-Wert, 0) und Zufallszahlen.Es sortiert genau die gleiche Reihenfolge wie Linq oder Array.Sort Sorten schwimmt:

NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf 

Also lief ich einen Test mit einer riesigen Auswahl an 10M Zahlen:

float[] test = new float[10000000]; 
Random rnd = new Random(); 
for (int i = 0; i < test.Length; i++) 
{ 
    byte[] buffer = new byte[4]; 
    rnd.NextBytes(buffer); 
    float rndfloat = BitConverter.ToSingle(buffer, 0); 
    switch(i){ 
     case 0: { test[i] = float.MaxValue; break; } 
     case 1: { test[i] = float.MinValue; break; } 
     case 2: { test[i] = float.NaN; break; } 
     case 3: { test[i] = float.NegativeInfinity; break; } 
     case 4: { test[i] = float.PositiveInfinity; break; } 
     case 5: { test[i] = 0f; break; } 
     default: { test[i] = test[i] = rndfloat; break; } 
    } 
} 

Und die Zeit der verschiedenen Sortieralgorithmen gestoppt:

Stopwatch sw = new Stopwatch(); 
sw.Start(); 

float[] sorted1 = test.RadixSort(); 

sw.Stop(); 
Console.WriteLine(string.Format("RadixSort: {0}", sw.Elapsed)); 
sw.Reset(); 
sw.Start(); 

float[] sorted2 = test.OrderBy(x => x).ToArray(); 

sw.Stop(); 
Console.WriteLine(string.Format("Linq OrderBy: {0}", sw.Elapsed)); 
sw.Reset(); 
sw.Start(); 

Array.Sort(test); 
float[] sorted3 = test; 

sw.Stop(); 
Console.WriteLine(string.Format("Array.Sort: {0}", sw.Elapsed)); 

Und die Ausgabe war (Update: lief jetzt mit Release-Build, nicht debuggen):

RadixSort: 00:00:03.9902332 
Linq OrderBy: 00:00:17.4983272 
Array.Sort: 00:00:03.1536785 

ungefähr viermal so schnell wie Linq. Das ist nicht schlecht. Aber immer noch nicht so schnell wie Array.Sort, aber auch nicht so viel schlechter. Aber ich war wirklich überrascht von diesem: Ich erwartete, dass es auf sehr kleinen Arrays etwas langsamer als Linq sein würde. Aber dann lief ich einen Test mit nur 20 Elementen:

RadixSort: 00:00:00.0012944 
Linq OrderBy: 00:00:00.0072271 
Array.Sort: 00:00:00.0002979 

und auch diesmal mein RadixSort ist schneller als Linq, aber Weise langsamer als Array sortieren. :)

Update 2:

Ich habe einige weitere Messungen und fand heraus, einige interessante Dinge: mehr Gruppenlänge Konstanten weniger Iterationen bedeuten und mehr Speichernutzung. Wenn Sie eine Gruppenlänge von 16 Bit verwenden (nur 2 Iterationen), haben Sie einen großen Speicheraufwand beim Sortieren kleiner Arrays, aber Sie können Array.Sort schlagen, wenn es zu Arrays kommt, die größer als etwa 100k Elemente sind, wenn auch nicht sehr viel. Die Diagramme Achsen sind beide logarithmiert:

comparison chart http://daubmeier.de/philip/stackoverflow/radixsort_vs_arraysort.png

Answer 2

Ich denke, Ihre beste Wette, wenn die Werte nicht zu nahe sind und es eine vernünftige Genauigkeitsanforderung gibt, können Sie einfach die tatsächlichen Fließkommawerte vor und nach dem Dezimalpunkt verwenden, um die Sortierung durchzuführen.

Zum Beispiel können Sie einfach die ersten 4 Dezimalstellen (egal ob 0 oder nicht) für die Sortierung verwenden.

Answer 3

Es gibt eine schöne Erklärung, wie Radixsort auf auszuführen hier schwimmt: http://www.codercorner.com/RadixSortRevisited.htm

Wenn alle Werte positiv sind, können Sie mit der Verwendung der weg binäre Darstellung; Der Link erklärt, wie mit negativen Werten umgegangen wird.

Answer 4

Sie können einen unsafe Block zu memcpy oder einen Alias ​​float * zu einem uint * verwenden, um die Bits zu extrahieren.