• API
• FAQ
• Tools
• Archive
daily pastebin goal
23%
SHARE
TWEET

# Untitled

a guest Feb 22nd, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
103.
104. sw.Stop();
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.
123. Linq OrderBy: 00:00:17.4983272
124. Array.Sort: 00:00:03.1536785
125.
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.         }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top