c# - 为什么我的 Base 10 LSD 基数排序比我的位移位基数排序更快？

Question

因此，我正在为一个学校项目试验不同类型的基数排序，我们必须尽快对 500,000 个随机整数(我自己生成，每个整数的界限在 0 到 MaxValue 之间)进行排序。我首先进行了基数为 10 的 LSD(最低有效数字)基数排序，对 500,000 个随机整数进行排序平均需要 110 到 115 毫秒。这是它的代码:

public static int[] RadixSort(int[] RandomNumbers)
        {
            List<int>[] Buckets = new List<int>[10];

            int singleDigit = 0;
            int[] temp;
            int[] mult = new int[10] {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

            for (int z = 0; z < 10; z++)
            {
                Buckets[0] = new List<int>();
                Buckets[1] = new List<int>();
                Buckets[2] = new List<int>();
                Buckets[3] = new List<int>();
                Buckets[4] = new List<int>();
                Buckets[5] = new List<int>();
                Buckets[6] = new List<int>();
                Buckets[7] = new List<int>();
                Buckets[8] = new List<int>();
                Buckets[9] = new List<int>();

                if (z == 0)
                {
                    temp = (int[])RandomNumbers.Clone();
                }
                else
                {
                    temp = (int[])RandomNumbers.Clone();

                    for (int i = 0; i < SIZE; i++)
                    {
                        temp[i] /= (mult[z]);
                    }
                }

                for (int i = 0; i < SIZE; i++)
                {
                    singleDigit = temp[i] % 10;

                    Buckets[singleDigit].Add(RandomNumbers[i]);
                }

                List<int> NewList = new List<int>(SIZE);

                for (int i = 0; i < 10; i++)
                {
                    NewList.AddRange(Buckets[i]);
                }

                int[] NewArray = NewList.ToArray();

                RandomNumbers = NewArray;
            }

            return RandomNumbers;
        }

但是，我听说在位移位基数排序中使用二进制更快。因此，我创建了一个基于掩码的位移位基数排序，总体上看起来不那么困惑，其中进行的操作也更少，但它的平均排序速度约为 250 毫秒。这是它的代码:

public static int[] BitShiftRadixSort(int[] RandomNumbers)
        {
            List<int>[] Buckets = new List<int>[2];
            int binary;
            int mask;

            for (int shift = 0; shift < 32; shift++)
            {
                Buckets[0] = new List<int>(SIZE);
                Buckets[1] = new List<int>(SIZE);

                mask = 1 << shift;

                for (int i = 0; i < SIZE; i++)
                {
                    binary = RandomNumbers[i] & mask;

                    if (binary != 0)
                    {
                        Buckets[1].Add(RandomNumbers[i]);
                    }
                    else
                    {
                        Buckets[0].Add(RandomNumbers[i]);
                    }
                }

                List<int> NewList = new List<int>(SIZE);

                for (int i = 0; i < 2; i++)
                {
                    NewList.AddRange(Buckets[i]);
                }

                int[] NewArray = NewList.ToArray();

                RandomNumbers = NewArray;
            }

            return RandomNumbers;
        }

我原以为位移比 LSD 基数排序更快，但事实并非如此。 C# 中的数学运算是否经过高度优化？我会感谢大家的意见!

Answer 1

根据马特·蒂默曼 (Matt Timmerman) 关于使用基数 256 的建议，此版本的无符号整数对于 500,000 个 32 位无符号整数大约需要 10 毫秒。对于有符号整数，您需要对符号位进行补码并将它们视为无符号整数(然后将符号补回来)。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace RadixSort
{
    class Program
    {

        static void RadixSort(uint [] a, uint count)
        {
        uint [,] mIndex = new uint [4,256];     // count / index matrix
        uint [] b = new uint [count];           // allocate temp array
        uint i,j,m,n;
        uint u;
            for(i = 0; i < count; i++){         // generate histograms
                u = a[i];
                for(j = 0; j < 4; j++){
                    mIndex[j,(u & 0xff)]++;
                    u >>= 8;
                }       
            }
            for(j = 0; j < 4; j++){             // convert to indices
                m = 0;
                for(i = 0; i < 256; i++){
                    n = mIndex[j,i];
                    mIndex[j,i] = m;
                    m += n;
                }       
            }
            for(j = 0; j < 4; j++){             // radix sort
                for(i = 0; i < count; i++){     //  sort by current lsb
                    u = a[i];
                    m = (u>>((int)(j<<3)))&0xff;
                    b[mIndex[j,m]++] = u;
                }
                uint [] t = a;                  //  swap references
                a = b;
                b = t;
            }
        }

        static void Main(string[] args)
        {
            const int SIZE = 500000;
            uint [] a = new uint[SIZE];
            uint u;
            Random r = new Random(1);
            Stopwatch sw = new Stopwatch();
            for (uint i = 0; i < a.Length; i++)
            {
                u = (uint)r.Next(1 << 16);
                u = (u << 16) | (uint)r.Next(1 << 16);
                a[i] = u;
            }
            sw.Start();
            RadixSort(a, (uint)a.Length);
            sw.Stop();
            for (uint i = 1; i < a.Length; i++)
            {
                if(a[i] < a[i-1])
                {
                    Console.WriteLine("failed");
                    break;
                }
            }
            Console.WriteLine("milliseconds: {0:D}\n",sw.ElapsedMilliseconds);
        }
    }
}