Radix trier plus lent que le tri Rapide?

Question

Je voudrais vous montrer que parfois, radix-tri est mieux que le tri rapide.Dans cet exemple, je suis en utilisant le programme ci-dessous:

#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());
}

Il effectue comme suit:

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

Je sais que Rapide Tri doit effectuer dans O(n log n) alors que Radix Tri sera en O(d (n + r)) ~= O(6 * n).Pour n = 52428800, log(n) = 17.Je suis puis attendre de Radix Sorte d'être 3 fois plus rapide que le Tri Rapide...

Ce n'est pas ce que j'observe.

Ce qui me manque?

Answer 1

1. qsort est pas Quicksort.qsort est ce que le réalisateur de la bibliothèque standard a décidé.

2. Tri de 50 millions de valeurs identiques est très représentatif.Il y a qsort implémentations qui permet de trier 50 millions de dollars à l'identique, soit 50 millions de tri ou inverser les éléments triés dans le temps linéaire.

3. Radix sorte de 50 millions de numéros à six chiffres est évidemment absurde.Six chiffres signifie que vous vous attendez à 64 valeurs différentes, et donc utiliser le comptage de tri.De moins de 26 chiffres qu'il n'a pas de sens.

4. Votre radix trier un tas de copie, et pire, en mémoire cache, à la copie.

5. Votre tri radix ne produit pas correctement triés résultat si les chiffres est un nombre impair.

6. Votre qsort appel ne produit pas correctement triés résultat si le tableau contient de très grandes et de très petits nombres.