是否有一個很好的基數實現浮點數在C＃

Question

我有一個浮點數類型的字段的數據結構。這些結構的集合需要按浮點值進行排序。有沒有這樣的基數排序實現。

如果沒有，是否有快速訪問指數，符號和尾數的方法。 因爲如果你首先在尾數，指數和指數上對浮點數進行排序。你在O（n）中排序浮點數。

Answer 1

更新：

我是這個話題很感興趣，所以我坐下來實現它（使用this very fast and memory conservative implementation）。我還讀了this one（謝謝celion），發現你甚至不需要將浮點數分成尾數和指數來對它進行排序。你只需要一點一點地進行比特並執行一個int類型。你只需要關心負值，在算法結束時必須反面放在正值的前面（我用一次最後一次迭代算法來節省一些CPU時間）。

所以，我的繼承人浮動基數排序：

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; 
} 

這是因爲在功能，其中花車複製到按位的開始和結束的陣列複製比int基數排序稍微慢一些， ints和後面。然而，整個功能仍然是O（n）。在任何情況下，比您提議的排序連續3次快得多。我沒有看到太多的優化空間，但如果有人願意：隨時告訴我。

排序在最後降改變這一行：

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

這樣：

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

測量：

我設置了一些簡短的測試，包含所有特殊漂浮物（NaN，+/- Inf，最小/最大值，0）和隨機數。它排序完全相同的順序爲LINQ的或Array.Sort各種彩車：

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

所以我跑測試與一個巨大的10M數字數組：

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; } 
    } 
} 

，並停止的不同的排序算法的時間：

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)); 

輸出功率爲（更新：現在發行版本跑了，無法調試）：

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

大約比Linq快4倍以上。這並不壞。但仍然沒有像Array.Sort那麼快，但也沒那麼糟。但是我對這一點感到非常驚訝：我預計它會比Linq在非常小的陣列上慢一點。但後來我跑了僅20元一個測試：

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

，甚至這一次我的基數排序比LINQ的更快，但比數組排序慢方式。 :)

更新2：

我做了一些測試，發現了一些有趣的事情：再組長度的常量意味着更少的迭代和更多的內存使用情況。如果使用16位組的長度（只有2次迭代），那麼在對小陣列進行排序時存在巨大的內存開銷，但如果涉及大於大約100k個元素的數組（即使不是很多），則可以擊敗Array.Sort。這些圖表軸均取對數：

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

Answer 2

我認爲你最好的選擇，如果值不是太接近並且有合理的精度要求，你可以使用小數點前後的實際浮點數進行排序。

例如，您可以使用前4位小數（無論它們是否爲0）來進行排序。

Answer 3

還有如何執行基數排序上一個很好的說明浮標的位置： http://www.codercorner.com/RadixSortRevisited.htm

如果所有你的價值觀是積極的，你可以使用閃避二進制表示;該鏈接解釋瞭如何處理負值。

Answer 4

您可以使用unsafe塊將memcpy或別名float *設置爲uint *以提取這些位。