هل هناك تقسس جيد للطفو في العوامات في C#

Question

لدي داسك بنية مع حقل من النوع العائم. يجب فرز مجموعة من هذه الهياكل من خلال قيمة التعويم. هل هناك تطبيق Radix-Sort لهذا الغرض.

إذا لم يكن هناك ، هل هناك طريقة سريعة للوصول إلى الأسس والعلامة و Mantissa. لأنه إذا قمت بفرز العوامات أولاً على Mantissa ، الأسعار ، وعلى الأسعار في المرة الأخيرة. يمكنك فرز العوامات في o (n).

Answer 1

تحديث:

كنت مهتمًا جدًا بهذا الموضوع ، لذا جلسته ونفذته (باستخدام هذا التنفيذ السريع للغاية والذاكرة المحافظة). قرأت أيضا هذا (شكرًا سيليون) واكتشفت أنك لا تضطر إلى تقسيم العوامات إلى مانتيسا وفرزها. عليك فقط أن تأخذ البتات واحدة إلى واحد وتنفيذ نوع int. عليك فقط أن تهتم بالقيم السلبية ، التي يجب وضعها بشكل عكسي أمام تلك الإيجابية في نهاية الخوارزمية (لقد جعلت ذلك في خطوة واحدة مع التكرار الأخير للخوارزمية لتوفير بعض وقت وحدة المعالجة المركزية).

لذلك هيريس الخاص بي راديكسينات:

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 radix ، بسبب نسخ المصفوفة في بداية ونهاية الوظيفة ، حيث يتم نسخ العوامات إلى INTs والظهر. الوظيفة بأكملها مع ذلك مرة أخرى o (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 بت (فقط تكراران) ، لديك ذاكرة ضخمة عند فرز المصفوفات الصغيرة ، ولكن يمكنك التغلب Array.Sort إذا يتعلق الأمر بالمصفوفات أكبر من حوالي 100 ألف عنصر ، حتى لو لم يكن كثيرًا. محاور المخططات كلاهما لوغاريتميات:

_{(مصدر: daubmeier.de)}

Answer 2

هناك شرح لطيف لكيفية أداء نوع Radix على العوامات هنا:http://www.codercorner.com/radixsortrevisited.htm

إذا كانت كل قيمك إيجابية ، فيمكنك الابتعاد عن استخدام التمثيل الثنائي ؛ يشرح الرابط كيفية التعامل مع القيم السلبية.

Answer 3

يمكنك استخدام unsafe حظر إلى memcpy أو الاسم المستعار float * إلى uint * لاستخراج البتات.

Answer 4

من خلال القيام ببعض صفائف الصب والتبديل الفاخرة بدلاً من نسخ هذا الإصدار ، يكون 2x أسرع لأرقام 10 أمتار مثل Philip Daubmeiers الأصلي مع تعيين Grouplength إلى 8. إنه أسرع 3x كصفعة.

 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 أم لا) للقيام بالفرز.