是否有一个良好的radixsort，实现在C＃中的花车 [英] Is there a good radixsort-implementation for floats in C#
问题描述
我有浮动型字段的数据结构。这些结构的集合需要由浮子的值进行排序。是否有一个基数排序实现这一点。
I have a datastructure with a field of the float-type. A collection of these structures needs to be sorted by the value of the float. Is there a radix-sort implementation for this.
如果没有，有没有快速的方法来访问指数，符号和尾数。 因为如果你的彩车第一个尾数排序，指数，和指数的最后一次。你那种漂浮在为O（n）。
If there isn't, is there a fast way to access the exponent, the sign and the mantissa. Because if you sort the floats first on mantissa, exponent, and on exponent the last time. You sort floats in O(n).
推荐答案
更新：
我是这个话题很感兴趣，所以我坐下来实现它（使用这速度非常快，内存保守的实施）。我也看了这个（感谢的席琳），并发现你甚至不必须拆分成花车尾数和指数来排序。你只需要取位一到一个，执行一个int排序。你只需要关心负值，即必须负摆在了积极的正面在算法结束时（我做的，一步到位的算法的最后一次迭代，以节省一些CPU时间）。
I was quite interested in this topic, so I sat down and implemented it (using this very fast and memory conservative implementation). I also read this one (thanks celion) and found out that you even dont have to split the floats into mantissa and exponent to sort it. You just have to take the bits one-to-one and perform an int sort. You just have to care about the negative values, that have to be inversely put in front of the positive ones at the end of the algorithm (I made that in one step with the last iteration of the algorithm to save some cpu time).
所以，我的继承人浮动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;
}
有，因为该数组复印在函数，其中该浮体是按位复制到整数和背面的开始和结束的比int基数排序稍慢。虽然如此，整体功能又是O（N）。在任何情况下，不是像你提出的分选3次，连续快得多。我没有看到很大的优化了，但如果有人做：随时告诉我。
It is slightly slower than an int radix sort, because of the array copying at the beginning and end of the function, where the floats are bitwise copied to ints and back. The whole function nevertheless is again O(n). In any case much faster than sorting 3 times in a row like you proposed. I dont see much room for optimizations anymore, but if anyone does: feel free to tell me.
要降序排序变化这条线在最后：
To sort descending change this line at the very end:
ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
这样：
ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
测量：
我设置了一些简短的测试，包括花车的所有特殊情况（南安+/-天道酬勤，最小值/最大值，0）和随机数。它完全排序的顺序相同的LINQ或的Array.Sort 排序花车：
I set up some short test, containing all special cases of floats (NaN, +/-Inf, Min/Max value, 0) and random numbers. It sorts exactly the same order as Linq or Array.Sort sorts floats:
NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf
所以，我跑了一个测试与一个巨大的10M数字数组：
So i ran a test with a huge array of 10M numbers:
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; }
}
}
和停止的不同的排序算法的时间：
And stopped the time of the different sorting algorithms:
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。这是不坏。但还是没有那么快为的Array.Sort ，也没有那么差很多。但我真的很惊讶这一个：我希望它是略慢于LINQ的在非常小的阵列。但后来我跑了一个测试只有20个元素：
roughly more than four times as fast as Linq. That is not bad. But still not yet that fast as Array.Sort, but also not that much worse. But i was really surprised by this one: I expected it to be slightly slower than Linq on very small arrays. But then I ran a test with just 20 elements:
RadixSort: 00:00:00.0012944
Linq OrderBy: 00:00:00.0072271
Array.Sort: 00:00:00.0002979
甚至这个时候我Radixsort比Linq的更快，但是的办法的比数组排序慢。 ：）
and even this time my Radixsort is quicker than Linq, but way slower than array sort. :)
更新2：
我做了一些更多的测量，并发现了一些有趣的事情：再组长度的常量意味着更少的迭代和使用更多内存。如果您使用的16位（仅2次迭代）一组的长度，你有一个庞大的内存开销的排序小数组的时候，但你能击败的Array.Sort 如果涉及到数组比100K左右的元素更大，即使不是非常多。图表轴都logarithmized：
I made some more measurements and found out some interesting things: longer group length constants mean less iterations and more memory usage. If you use a group length of 16 bits (only 2 iterations), you have a huge memory overhead when sorting small arrays, but you can beat Array.Sort if it comes to arrays larger than about 100k elements, even if not very much. The charts axes are both logarithmized:
这篇关于是否有一个良好的radixsort，实现在C＃中的花车的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
