c#中是否有一个好的浮动的radixsort实现

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.

我有一个带浮点类型字段的数据结构。这些结构的集合需要根据浮点数的值进行排序。是否有一个基数排序实现。

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

如果没有，有没有快速访问指数、符号和尾数的方法。因为如果你首先对浮点数进行排序在尾数，指数和指数上。你在O(n)中排序。

4 个解决方案

#1

Update:

更新:

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

我对这个主题非常感兴趣，所以我坐下来实现了它(使用这个非常快速和内存保守的实现)。我也读了这个(谢谢celion)，发现你甚至不需要把浮点数分成尾数和指数来排序。你只需要取位一对一并执行一个int排序。你只需要关心负数的值，这些值必须放在算法末尾的正数前面(我在算法的最后一次迭代中做了一步，以节省一些cpu时间)。

So heres my float radixsort:

这是我的float 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;
}

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.

它比int基数排序稍慢一些，因为数组在函数的开始和结束处复制，浮动按位复制到ints和ints。整个函数还是O(n)在任何情况下都比像你建议的那样连续排序三次要快得多。我看不出有多少优化的空间了，但如果有的话:尽管告诉我。

To sort descending change this line at the very end:

要进行降序排序，请在最后改变这条线:

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

to this:

:

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

Measuring:

测量:

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/Max value, 0)和随机数。它的排序顺序与Linq或数组完全相同。各种浮动:

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

So i ran a test with a huge array of 10M numbers:

所以我做了一个测试，用了大量的1000万个数字:

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

And the output was (update: now ran with release build, not debug):

输出是(update: now run with release build, not debug):

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

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:

大约是Linq的四倍多。这是不坏。但还没有数组那么快。分类，但也没那么糟糕。但是我对这一点感到非常惊讶:我期望它在非常小的数组上比Linq慢一点。但是我只用了20个元素做了一个测试:

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

and even this time my Radixsort is quicker than Linq, but way slower than array sort. :)

即使是这次，我的Radixsort也比Linq快，但比数组排序慢得多。:)

Update 2:

更新2:

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:

我做了更多的测量并发现了一些有趣的事情:长组长度常量意味着更少的迭代和更多的内存使用。如果您使用的组长度为16位(只有2次迭代)，那么在对小数组进行排序时，会产生巨大的内存开销，但是您可以打败数组。如果数组的元素大于100k，即使不是很多，也要进行排序。图轴均为对数化:

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

比较图http://daubmeier.de/philip/*/radixsort_vs_arraysort.png

#2

I think your best bet if the values aren't too close and there's a reasonable precision requirement, you can just use the actual float digits before and after the decimal point to do the sorting.

我认为最好的办法是如果值不太接近并且有一个合理的精度要求，你可以使用小数点前后的浮点数来进行排序。

For example, you can just use the first 4 decimals (be they 0 or not) to do the sorting.

例如，你可以使用前4个小数(不管它们是否为0)来排序。

#3

There's a nice explanation of how to perform radix sort on floats here: http://www.codercorner.com/RadixSortRevisited.htm

这里有一个关于如何在浮动上执行基数排序的很好的解释:http://www.codercorner .com/radixsortrevisi.htm

If all your values are positive, you can get away with using the binary representation; the link explains how to handle negative values.

如果所有的值都是正的，你可以使用二进制表示法;链接解释如何处理负值。

#4

You can use an unsafe block to memcpy or alias a float * to a uint * to extract the bits.

您可以使用不安全的块来memcpy，或者将浮点*命名为uint *来提取比特。