هل الفرز الجذري أبطأ من الفرز السريع؟

Question

أود أن أوضح أنه في بعض الأحيان يكون الفرز الجذري أفضل من الفرز السريع.في هذا المثال أستخدم البرنامج أدناه:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>
#include <math.h>

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void bin_radix_sort(int *a, const long long size, int digits) {
    assert(digits % 2 == 0);

    long long count[2];
    int *b = malloc(size * sizeof(int));
    int exp = 0;

    while(digits--) {
        // Count elements
        count[0] = count[1] = 0;
        for (int i = 0; i < size; i++)
            count[(a[i] >> exp) & 0x01]++;

        // Cumulative sum
        count[1] += count[0];

        // Build output array
        for (int i = size - 1; i >= 0; i--)
            b[--count[(a[i] >> exp) & 0x01]] = a[i];

        exp++;
        int *p = a; a = b; b = p;
    };

    free(b);
}

struct timespec start;

void tic() {
    timespec_get(&start, TIME_UTC);
}

double toc() {
    struct timespec stop;
    timespec_get(&stop, TIME_UTC);
    return stop.tv_sec - start.tv_sec + (
        stop.tv_nsec - start.tv_nsec
    ) * 1e-9;
}

int main(void)
{
    const long long n = 1024 * 1024 * 50;
    printf("Init memory (%lld MB)...\n", n / 1024 / 1024 * sizeof(int));

    int *data = calloc(n, sizeof(int));

    printf("Sorting n = %lld data elements...\n", n);

    long long O;
    tic();
    O = n * log(n);
    qsort(data, n, sizeof(data[0]), cmpfunc);
    printf("%lld %lf s\n", O, toc());

    int d = 6;
    tic();
    O = d * (n + 2);
    bin_radix_sort(data, n, d);
    printf("%lld %lf s\n", O, toc());
}

وينفذ على النحو التالي:

$ gcc bench.c -lm $ ./a.out 
Init memory (200 MB)...
Sorting n = 52428800 data elements...
931920169 1.858300 s
314572812 1.541998 s

أعلم أن الفرز السريع سيعمل يا (ن سجل ن) بينما سيكون ترتيب Radix موجودًا يا (د (ن + ص)) ~= يا (6 * ن).ل n = 52428800, log(n) = 17.أتوقع بعد ذلك أن يكون الترتيب الأساسي أسرع بثلاث مرات من الفرز السريع ...

وهذا ليس ما ألاحظه.

ماذا ينقصني؟

Answer 1

1. qsort ليس فرزًا سريعًا.qsort هو ما قرره منفذ المكتبة القياسية.

2. إن فرز 50 مليون قيمة متطابقة أمر غير تمثيلي إلى حد كبير.هناك تطبيقات qsort يمكنها فرز 50 مليون عنصر متطابق، أو 50 مليون عنصر تم فرزه أو فرزه عكسيًا في وقت خطي.

3. من الواضح أن النوع الجذري المكون من 50 مليون رقم مكون من ستة أرقام هو هراء.ستة أرقام تعني أنك تتوقع 64 قيمة مختلفة فقط، وبالتالي ستستخدم الفرز العدي.مع أقل من 26 رقمًا، لا معنى لذلك.

4. يقوم النوع الجذري الخاص بك بالكثير من النسخ، والأسوأ من ذلك، النسخ غير المخبأ.

5. لا ينتج عن الفرز الجذري نتيجة مرتبة بشكل صحيح إذا كانت الأرقام عددًا فرديًا.

6. لا ينتج عن استدعاء qsort نتيجة مرتبة بشكل صحيح إذا كان المصفوفة تحتوي على أرقام كبيرة جدًا وصغيرة جدًا.