c# - C# 中的 float 是否有一个好的基数排序实现

Question

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

如果没有，是否有快速访问指数、符号和尾数的方法。因为如果你首先对尾数、指数和最后一次的指数对 float 进行排序。您在 O(n) 中对 float 进行排序。

Answer 1

更新:

我对这个主题很感兴趣，所以我坐下来实现了它(使用 this very fast and memory conservative implementation )。我还读了this one (感谢 celion)并发现您甚至不必将 float 拆分为尾数和指数来对其进行排序。您只需要一对一地取位并执行 int 排序。你只需要关心负值，在算法结束时必须将负值倒置在正值前面(我在算法的最后一次迭代中一步完成，以节省一些 cpu 时间)。

所以这是我的浮点基数排序:

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 基数排序稍慢，因为在函数的开头和结尾进行数组复制，其中 float 按位复制到 int 并返回。尽管如此，整个函数还是 O(n)。无论如何，比您建议的连续排序 3 次要快得多。我看不到太多优化空间了，但如果有人这样做:请随时告诉我。

要降序排序，请在最后更改此行:

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

为此:

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

测量:

我设置了一些简短的测试，包含 float 的所有特殊情况(NaN、+/-Inf、最小值/最大值、0)和随机数。它的排序顺序与 Linq 或 Array.Sort 对 float 的排序完全相同:

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

所以我用大量 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; }
    }
}

并停止了不同排序算法的时间:

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 个元素进行了测试:

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

甚至这次我的 Radixsort 比 Linq 快，但方式比数组排序慢。 :)

更新 2:

我进行了更多测量并发现了一些有趣的事情:更长的组长度常量意味着更少的迭代和更多的内存使用。如果您使用 16 位的组长度(仅 2 次迭代)，则在对小数组进行排序时会产生巨大的内存开销，但如果涉及大于大约 100k 元素的数组，您可以击败 Array.Sort ，即使不是很多。图表轴都是对数的:

_{(来源:daubmeier.de)}