Есть ли хорошая Radixsort-внедрение для поплавков в C #

Question

У меня есть Datastructure с полем поплавкового типа. Коллекция этих структур должна быть отсортирована по значению поплавка. Есть ли реализация Radix-Sort для этого.

Если нет, есть ли быстрый способ доступа к экспоненту, знаку и мантиссе. Потому что если вы сортируете поплавки сначала на Mantissa, экспоненту, и на экспонент в последний раз. Вы сортируете плавать в O (n).

Answer 1

Обновлять:

Я был вполне интересен эту тему, поэтому я сел и внедрил его (используя Это очень быстрое и память консервативной реализации). Я также читаю Вот этот (Спасибо Celion) И выяснил, что вам даже не нужно разбивать поплавки в Mantissa и экспоненту, чтобы сортировать его. Вам просто нужно взять биты один на один и выполнить сорт INT. Вам просто нужно заботиться о негативных значениях, которые должны быть обратно поставлены перед положительными в конце алгоритма (я сделал это, на один шаг с последней итерацией алгоритма для сохранения некоторого времени ЦП).

Итак, вот мой поплавок 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;
}

Это немного медленнее, чем SINT RADIX сортировка, из-за копирования массива в начале и конце функции, где поплавки побитовые скопированы в Ints и обратно. Вся функция, тем не менее, снова о (n). В любом случае намного быстрее, чем сортировка 3 раза в ряд, как вы предлагали. Я больше не вижу большой комнаты для оптимизаций, но если кто-то делает: не стесняйтесь сказать мне.

Сортировать по убыванию Изменить эту строку в самом конце:

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

к этому:

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

Измерение:

Я устанавливаю короткий тест, содержащий все особые случаи поплавков (NAN, +/- Inf, Min / Max значение, 0) и случайных чисел. Это сортирует точно тот же порядок, что и linq или Array.Sort Сортирует поплавки:

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

Поэтому я пробежал тест с огромным массивом номеров 10 м:

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 итерации), у вас есть огромная нагрузка на память при сортировке небольших массивов, но вы можете победить Array.Sort Если дело доходит до массивов больше, чем около 100К элементов, даже если не очень много. Оси диаграммы оба логарифмированы:

_{(источник: daubmeier.de.)}

Answer 2

Там приятное объяснение того, как выполнить Radix Worm на поплавке здесь:http://www.codercorner.com/radixsortrevisited.htm.

Если все ваши ценности являются положительными, вы можете уйти с использованием двоичного представления; Ссылка объясняет, как обрабатывать отрицательные значения.

Answer 3

Вы можете использовать unsafe блок к мемкпи или псевдоним float * к А. uint * извлечь биты.

Answer 4

Выполняя некоторые причудливые литья и замену массивов вместо копирования этой версии, является 2 раза быстрее для чисел 10 м в виде оригинала Philip Daubmeiers оригинал с обозначением, установленным на 8. Это 3x быстрее, как Array.sort для этого arraysize.

 static public void RadixSortFloat(this float[] array, int arrayLen = -1)
        {
            // Some use cases have an array that is longer as the filled part which we want to sort
            if (arrayLen < 0) arrayLen = array.Length;
            // Cast our original array as long
            Span<float> asFloat = array;
            Span<int> a = MemoryMarshal.Cast<float, int>(asFloat);
            // Create a temp array
            Span<int> t = new Span<int>(new int[arrayLen]);

            // set the group length to 1, 2, 4, 8 or 16 and see which one is quicker
            int groupLength = 8;
            int bitLength = 32;

            // counting and prefix arrays
            // (dimension is 2^r, the number of possible values of a r-bit number) 
            var dim = 1 << groupLength;
            int groups = bitLength / groupLength;
            if (groups % 2 != 0) throw new Exception("groups must be even so data is in original array at end");
            var count = new int[dim];
            var pref = new int[dim];
            int mask = (dim) - 1;
            int negatives = 0, positives = 0;

            // counting elements of the 1st group incuding negative/positive
            for (int i = 0; i < arrayLen; i++)
            {
                if (a[i] < 0) negatives++;
                count[(a[i] >> 0) & mask]++;
            }
            positives = arrayLen - negatives;

            int c;
            int shift;
            for (c = 0, shift = 0; c < groups - 1; c++, shift += groupLength)
            {
                CalcPrefixes();
                var nextShift = shift + groupLength;
                //
                for (var i = 0; i < arrayLen; i++)
                {
                    var ai = a[i];
                    // Get the right index to sort the number in
                    int index = pref[( ai >> shift) & mask]++;
                    count[( ai>> nextShift) & mask]++;
                    t[index] =  ai;
                }

                // swap the arrays and start again until the last group 
                var temp = a;
                a = t;
                t = temp;
            }

            // Last round
            CalcPrefixes();
            for (var i = 0; i < arrayLen; i++)
            {
                var ai = a[i];
                // Get the right index to sort the number in
                int index = pref[( ai >> shift) & mask]++;
                // 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 ( ai < 0) index = positives - (index - negatives) - 1; else index += negatives;
                //
                t[index] =  ai;
            }

            void CalcPrefixes()
            {
                pref[0] = 0;
                for (int i = 1; i < dim; i++)
                {
                    pref[i] = pref[i - 1] + count[i - 1];
                    count[i - 1] = 0;
                }
            }
        }

Answer 5

Я думаю, что ваша лучшая ставка, если значения не слишком близки, и есть разумные прецизионные требования, вы можете просто использовать фактические поплавные цифры до и после десятичной точки, чтобы сделать сортировку.

Например, вы можете просто использовать первые 4 десятичных случая (будь то 0 или нет), чтобы сделать сортировку.