Почему моя базовая 10 сортировка по радиоканалу LSD быстрее, чем моя сортировка по радикалу с битовым сдвигом?

Question

Итак, я экспериментировал с различными видами сортировки Radix для школьного проекта, где мы должны как можно быстрее отсортировать 500 000 случайных целых чисел (которые я генерирую сам, с границами от 0 до MaxValue для каждого целого числа).Сначала я сделал базовую сортировку по 10-кратному LSD (наименее значимая цифра), которая в среднем составляет от 110 до 115 мс для сортировки 500 000 случайных целых чисел.Вот код для этого:

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

Однако я слышал, что использование двоичного кода в сортировке Radix со сдвигом битов было быстрее.Поэтому я создал сортировку Radix на основе масок со сдвигом битов, которая в целом выглядит менее загроможденной и в ней выполняется меньше операций, но ее средняя скорость сортировки составляет около 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 Radix, но это не так.Математические операции в C # сильно оптимизированы?Я буду благодарен всем за вклад!

Answer 1

Используя предложение Мэтта Тиммерманса использовать основание 256, эта версия для целых чисел без знака занимает около 10 мс для 500 000 32-битных целых чисел без знака.Для целых чисел со знаком вам нужно будет дополнить бит знака и рассматривать их как целые числа без знака (затем дополнить знак обратно).

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