Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
- ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
- NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf
- 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
- RadixSort: 00:00:00.0012944
- Linq OrderBy: 00:00:00.0072271
- Array.Sort: 00:00:00.0002979
- static public void RadixSortFloat(this float[] array, int arrayLen = -1)
- {
- // Some use cases have an array that is longer as the filled part which we want to sort
- if (arrayLen < 0) arrayLen = array.Length;
- // Cast our original array as long
- Span<float> asFloat = array;
- Span<int> t = MemoryMarshal.Cast<float, int>(asFloat);
- // Create a temp array
- Span<int> a = new Span<int>(new int[arrayLen]);
- // set the group length to 1, 2, 4, 8 or 16
- // and see which one is quicker
- int groupLength = 16;
- int bitLength = 32;
- // counting and prefix arrays
- // (dimension is 2^r, the number of possible values of a r-bit number)
- var dim = 1 << groupLength;
- var count = new int[dim];
- var pref = new int[dim];
- int groups = bitLength / groupLength;
- int mask = (dim) - 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 < dim; j++) count[j] = 0;
- // counting elements of the c-th group
- for (int i = 0; i < arrayLen; 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 < dim; 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];
- }
- // swap the arrays and start again until the last group
- var temp = a;
- a = t;
- t = temp;
- }
- // Convert back the ints to the float array if we did an uneven number of copy swap runs
- if (groups % 2 != 0)
- {
- asFloat = MemoryMarshal.Cast<int, float>(a);
- for (int i = 0; i < arrayLen; i++) array[i] = asFloat[i];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement