Y at-il une bonne mise en œuvre pour-tri par base flotteurs en C #

Question

J'ai une structure de données avec un champ du type de flotteur. Une collection de ces structures doit être trié par la valeur du flotteur. Y at-il une implémentation tri radix pour cela.

S'il n'y a pas, est-il un moyen rapide d'accéder à l'exposant, le signe et la mantisse. Parce que si vous triez les flotteurs d'abord sur mantisse, exposant, et exposant la dernière fois. Vous flotte tri dans O (n).

Answer 1

Mise à jour:

je suis très intéressé par ce sujet, donc je me suis assis et mis en œuvre (en utilisant ce très rapide et la mémoire mise en œuvre conservatrice ). Je lis aussi celui-ci (merci celion ) et a constaté que vous avez même de diviser les Do not flotteurs en mantisse et exposant de faire le tri. Il vous suffit de prendre les bits un à un et effectuer une sorte int. Il suffit de se soucier des valeurs négatives, qui doivent être inversement mis en face de ceux positifs à la fin de l'algorithme (je fait que, dans une étape avec la dernière itération de l'algorithme pour gagner du temps cpu).

Alors Heres mon flotteur tri par base:

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

Il est légèrement plus lent que d'une sorte de radix int, en raison du tableau copie au début et à la fin de la fonction, où les flotteurs sont copiés sur ints au niveau du bit et le dos. La fonction entière est néanmoins encore O (n). Dans tous les cas beaucoup plus rapide que le tri 3 fois de suite comme vous proposiez. Je ne vois pas beaucoup de place pour des optimisations plus, mais si quelqu'un fait. Sens libre de me dire

Pour trier changement descendant cette ligne à la fin:

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

à ceci:

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

mesure:

Je mis en place un certain court test, contenant tous les cas particuliers de flotteurs (NAN, +/- Inf, valeur Min / Max, 0) et des nombres aléatoires. Il trie exactement le même ordre que Linq sortes ou Array.Sort flotteurs:

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

Alors j'ai effectué un test avec un énorme tableau de nombres 10M:

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

Et arrêté le temps des différents algorithmes de tri:

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

Et la sortie a été ( Mise à jour: maintenant couru avec version build, pas debug ):

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

à peu près plus de quatre fois plus vite que Linq. Ce n'est pas mal. Mais toujours pas aussi vite que Array.Sort, mais pas non plus que bien pire. Mais je suis vraiment surpris par celui-ci: je pensais que ce serait un peu plus lent que Linq sur les tableaux très petites. Mais j'ai effectué un test avec seulement 20 éléments:

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

et même cette fois-ci mon est plus rapide que tri par base Linq, mais chemin trier plus lent que tableau. :)

Mise à jour 2:

J'ai fait un peu plus mesures et a trouvé des choses intéressantes: plus constantes de longueur moyenne des groupes moins itérations et plus l'utilisation de la mémoire. Si vous utilisez une longueur de groupe de 16 bits (seulement 2 itérations), vous avez une tête énorme de mémoire lors du tri de petits tableaux, mais vous pouvez battre Array.Sort si elle vient à des réseaux supérieurs à environ 100k éléments, même si pas beaucoup. Les axes de graphiques sont tous deux logarithmized:

_{(source: daubmeier.de )}

Answer 2

Il y a une bonne explication de la façon d'effectuer le tri par base sur flotteurs ici: http://www.codercorner.com/RadixSortRevisited.htm

Si toutes vos valeurs sont positives, vous pouvez vous en sortir avec l'aide de la représentation binaire; le lien explique comment gérer des valeurs négatives.

Answer 3

Vous pouvez utiliser un bloc unsafe à memcpy ou alias un float * à un uint * pour extraire les bits.

Answer 4

En faisant quelques coulée de fantaisie et échanger des tableaux au lieu de copier cette version est 2 fois plus rapide pour les numéros de 10M comme origine Philip Daubmeiers avec jeu de grouplength à 8. Il est 3 fois plus rapide que Array.Sort pour cette 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

Je pense que votre meilleur pari si les valeurs ne sont pas trop proches et il y a une exigence de précision raisonnable, vous pouvez simplement utiliser les chiffres réels flotteur avant et après le point décimal pour faire le tri.

Par exemple, vous pouvez simplement utiliser les 4 premières décimales (qu'ils soient ou non 0) pour faire le tri.