Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2019
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.92 KB | None | 0 0
  1. public static float[] RadixSort(this float[] array)
  2. {
  3. // temporary array and the array of converted floats to ints
  4. int[] t = new int[array.Length];
  5. int[] a = new int[array.Length];
  6. for (int i = 0; i < array.Length; i++)
  7. a[i] = BitConverter.ToInt32(BitConverter.GetBytes(array[i]), 0);
  8.  
  9. // set the group length to 1, 2, 4, 8 or 16
  10. // and see which one is quicker
  11. int groupLength = 4;
  12. int bitLength = 32;
  13.  
  14. // counting and prefix arrays
  15. // (dimension is 2^r, the number of possible values of a r-bit number)
  16. int[] count = new int[1 << groupLength];
  17. int[] pref = new int[1 << groupLength];
  18. int groups = bitLength / groupLength;
  19. int mask = (1 << groupLength) - 1;
  20. int negatives = 0, positives = 0;
  21.  
  22. for (int c = 0, shift = 0; c < groups; c++, shift += groupLength)
  23. {
  24. // reset count array
  25. for (int j = 0; j < count.Length; j++)
  26. count[j] = 0;
  27.  
  28. // counting elements of the c-th group
  29. for (int i = 0; i < a.Length; i++)
  30. {
  31. count[(a[i] >> shift) & mask]++;
  32.  
  33. // additionally count all negative
  34. // values in first round
  35. if (c == 0 && a[i] < 0)
  36. negatives++;
  37. }
  38. if (c == 0) positives = a.Length - negatives;
  39.  
  40. // calculating prefixes
  41. pref[0] = 0;
  42. for (int i = 1; i < count.Length; i++)
  43. pref[i] = pref[i - 1] + count[i - 1];
  44.  
  45. // from a[] to t[] elements ordered by c-th group
  46. for (int i = 0; i < a.Length; i++){
  47. // Get the right index to sort the number in
  48. int index = pref[(a[i] >> shift) & mask]++;
  49.  
  50. if (c == groups - 1)
  51. {
  52. // We're in the last (most significant) group, if the
  53. // number is negative, order them inversely in front
  54. // of the array, pushing positive ones back.
  55. if (a[i] < 0)
  56. index = positives - (index - negatives) - 1;
  57. else
  58. index += negatives;
  59. }
  60. t[index] = a[i];
  61. }
  62.  
  63. // a[]=t[] and start again until the last group
  64. t.CopyTo(a, 0);
  65. }
  66.  
  67. // Convert back the ints to the float array
  68. float[] ret = new float[a.Length];
  69. for (int i = 0; i < a.Length; i++)
  70. ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
  71.  
  72. return ret;
  73. }
  74.  
  75. ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
  76.  
  77. ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
  78.  
  79. NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf
  80.  
  81. float[] test = new float[10000000];
  82. Random rnd = new Random();
  83. for (int i = 0; i < test.Length; i++)
  84. {
  85. byte[] buffer = new byte[4];
  86. rnd.NextBytes(buffer);
  87. float rndfloat = BitConverter.ToSingle(buffer, 0);
  88. switch(i){
  89. case 0: { test[i] = float.MaxValue; break; }
  90. case 1: { test[i] = float.MinValue; break; }
  91. case 2: { test[i] = float.NaN; break; }
  92. case 3: { test[i] = float.NegativeInfinity; break; }
  93. case 4: { test[i] = float.PositiveInfinity; break; }
  94. case 5: { test[i] = 0f; break; }
  95. default: { test[i] = test[i] = rndfloat; break; }
  96. }
  97. }
  98.  
  99. Stopwatch sw = new Stopwatch();
  100. sw.Start();
  101.  
  102. float[] sorted1 = test.RadixSort();
  103.  
  104. sw.Stop();
  105. Console.WriteLine(string.Format("RadixSort: {0}", sw.Elapsed));
  106. sw.Reset();
  107. sw.Start();
  108.  
  109. float[] sorted2 = test.OrderBy(x => x).ToArray();
  110.  
  111. sw.Stop();
  112. Console.WriteLine(string.Format("Linq OrderBy: {0}", sw.Elapsed));
  113. sw.Reset();
  114. sw.Start();
  115.  
  116. Array.Sort(test);
  117. float[] sorted3 = test;
  118.  
  119. sw.Stop();
  120. Console.WriteLine(string.Format("Array.Sort: {0}", sw.Elapsed));
  121.  
  122. RadixSort: 00:00:03.9902332
  123. Linq OrderBy: 00:00:17.4983272
  124. Array.Sort: 00:00:03.1536785
  125.  
  126. RadixSort: 00:00:00.0012944
  127. Linq OrderBy: 00:00:00.0072271
  128. Array.Sort: 00:00:00.0002979
  129.  
  130. static public void RadixSortFloat(this float[] array, int arrayLen = -1)
  131. {
  132. // Some use cases have an array that is longer as the filled part which we want to sort
  133. if (arrayLen < 0) arrayLen = array.Length;
  134. // Cast our original array as long
  135. Span<float> asFloat = array;
  136. Span<int> t = MemoryMarshal.Cast<float, int>(asFloat);
  137. // Create a temp array
  138. Span<int> a = new Span<int>(new int[arrayLen]);
  139.  
  140. // set the group length to 1, 2, 4, 8 or 16
  141. // and see which one is quicker
  142. int groupLength = 16;
  143. int bitLength = 32;
  144.  
  145. // counting and prefix arrays
  146. // (dimension is 2^r, the number of possible values of a r-bit number)
  147. var dim = 1 << groupLength;
  148. var count = new int[dim];
  149. var pref = new int[dim];
  150. int groups = bitLength / groupLength;
  151. int mask = (dim) - 1;
  152. int negatives = 0, positives = 0;
  153.  
  154. for (int c = 0, shift = 0; c < groups; c++, shift += groupLength)
  155. {
  156. // reset count array
  157. for (int j = 0; j < dim; j++) count[j] = 0;
  158.  
  159. // counting elements of the c-th group
  160. for (int i = 0; i < arrayLen; i++)
  161. {
  162. count[(a[i] >> shift) & mask]++;
  163.  
  164. // additionally count all negative
  165. // values in first round
  166. if (c == 0 && a[i] < 0)
  167. negatives++;
  168. }
  169. if (c == 0) positives = a.Length - negatives;
  170.  
  171. // calculating prefixes
  172. pref[0] = 0;
  173. for (int i = 1; i < dim; i++) pref[i] = pref[i - 1] + count[i - 1];
  174.  
  175. // from a[] to t[] elements ordered by c-th group
  176. for (int i = 0; i < a.Length; i++)
  177. {
  178. // Get the right index to sort the number in
  179. int index = pref[(a[i] >> shift) & mask]++;
  180.  
  181. if (c == groups - 1)
  182. {
  183. // We're in the last (most significant) group, if the
  184. // number is negative, order them inversely in front
  185. // of the array, pushing positive ones back.
  186. if (a[i] < 0)
  187. index = positives - (index - negatives) - 1;
  188. else
  189. index += negatives;
  190. }
  191. t[index] = a[i];
  192. }
  193.  
  194. // swap the arrays and start again until the last group
  195. var temp = a;
  196. a = t;
  197. t = temp;
  198. }
  199.  
  200. // Convert back the ints to the float array if we did an uneven number of copy swap runs
  201. if (groups % 2 != 0)
  202. {
  203. asFloat = MemoryMarshal.Cast<int, float>(a);
  204. for (int i = 0; i < arrayLen; i++) array[i] = asFloat[i];
  205. }
  206. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement