هل هناك مكتبة جيدة لفرز مجموعة كبيرة من الأرقام في ج؟

Question

إذا كان لدي مجموعة كبيرة من الأعداد الصحيحة أو العوامات، فما هي خوارزمية / تنفيذ جيدة للفرز (في ج)؟

إنه متأخر بعض الشيء في اللعبة للحصول على تعديل ... لكنني أبحث عن صحة و سرعة.

Answer 1

لفرز صفائف الأرقام، فكر في خوارزمية راديكس فرز. عند التصميم بشكل صحيح، يجب أن توفر هذه الأنواع أداء أفضل من Glibc Qsort ().

تحتوي مكتبة Usort على تطبيقات خاصة بالنوع لجميع الأنواع الرقمية C الرئيسية.

http://bitbucket.org/ais/usort/wiki/home.

تتمثل ميزة السرعة في نوع Radix عبر Glibc Qsort حوالي 2.5x لأرقام النقطة العائمة المزدوجة في N = 1000000 على جهاز الكمبيوتر المحمول Intel 64 بت. ومع ذلك، نظرا لأن N ينمو، يجب أن تكون ميزة أكبر لأن راديكس فرز هو خوارزمية وقت خطي تتطلب عددا ثابتا من البيانات عبر البيانات.

بالنسبة إلى N، فإن نفس الرمز يرسل إلى حد ما أو فرز الإدراج.

Answer 2

Qsort () من المكتبة القياسية هو Good'un.

ستكون وظائف المقارنة تافهة لهذه الحالات:

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

(تحرير: إصدار هذه القائمة على طرح B من الاعتماد على سلوك تجاوز توقيع، لذلك ليست فكرة جيدة.)

Answer 3

انها فكرة سيئة أبدا للاستخدام Qsort.... إلا إذا كنت تعرف شيئا عن الأرقام.

لقد وصفت مع راديكس فرز. ما مقدار الذاكرة التي أنت مستعد للاستثمار؟ هي الأرقام داخل مجموعة معينة؟ هل لديهم خصائص تجعل فرز radix ممكن؟

ما لم ترغب في استخدام الكثير من الذاكرة، فإن QSort هو خيار رائع.

Answer 4

بالنظر إلى كمية هائلة من ذاكرة الوصول العشوائي، فإننا نحصل في الوقت الحاضر، والفرز المحدد التالي ممكن: قم بتمييز البتة في صفيف بت كبير RAM لكل رقم، ثم اقرأها مرة أخرى عن طريق مسح ذاكرة الوصول العشوائي. يمكن تطبيق الكثير من التحسينات الخاصة بالأجهزة للحصول على مراحل العلامة والمسح.