Radix sort mais lento do que a classificação Rápida?

Question

Eu gostaria de demonstrar que em algum momento radix-sort é melhor do que quick-sort.Neste exemplo estou usando o programa abaixo:

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

Ele executa como a seguir:

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

Eu sei que a Classificação Rápida vai realizar em O(n log n) enquanto a Base de Classificação será em O(d (n + r)) ~= O(6 * n).Para n = 52428800, log(n) = 17.Eu estou esperando Radix Sort a ser 3 vezes mais rápido do que a Classificação Rápida...

Este não é o que observo.

O que eu estou ausente?

Answer 1

1. qsort não é o Quicksort.qsort é o que a implementação da biblioteca padrão decidiu.

2. Ordenação de 50 milhões de idênticos valores é altamente representativos.Há qsort implementações que irá classificar 50 milhões idênticos, ou seja, 50 milhões de classificados ou inversa ordenados de elementos em tempo linear.

3. Radix sort de 50 milhões de números com seis dígitos é, obviamente, absurdo.Seis dígitos significa que você espera apenas 64 valores diferentes e, portanto, seria usar a contagem de classificação.Com menos de 26 dígitos não faz sentido.

4. O radix sort faz uma enorme quantidade de copiar, e, pior, sem cache copiar.

5. O radix sort não produzir um classificadas corretamente resultado se algarismos é um número ímpar.

6. Seu qsort chamada de não produzir um classificadas corretamente resultado se a matriz contém muito grandes e muito pequenos números.