Radix Ordina più lento del rapido ordinamento?

Question

Vorrei dimostrare che un po 'di radix-ordinamento è migliore del tipo rapido.In questo esempio sto usando il programma qui sotto:

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

.

si esibisce come segue:

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

.

So che questo tipo rapido si esibirà in O (N Log N) mentre il radix Sort sarà in O (D (N + R)) ~= O (6 * n) .Per n = 52428800, log(n) = 17.Mi aspetto quindi il radix ordina di essere 3 volte più velocemente del rapido ordinamento ...

Questo non è quello che osservo.

Cosa mi manca?

Answer 1

.

1. qsort non è quicksort.QSort è qualunque sia l'implementore della Biblioteca standard decisi.

2. Ordinamento di 50 milioni di valori identici è altamente non rappresentativi.Esistono implementazioni QSort che ordinano 50 milioni di elementi ordinati o di 50 milioni o di 50 milioni o di 50 milioni di elementi ordinati in tempo lineare.

3. Radix Sort di 50 milioni di numeri con sei cifre è ovviamente senza senso.Sei cifre significa che ti aspetti solo 64 valori diversi e quindi utilizzerebbe il conto del conteggio.Con meno di 26 cifre non ha senso.

4. Il tuo ordinamento radix fa un sacco di copia di copia e peggio e peggio, scavando.

5. Il tuo ordinamento del radix non produce un risultato ordinato correttamente se le cifre sono un numero dispari.

6. La tua chiamata QSort non produce un risultato ordinato correttamente se l'array contiene numeri molto grandi e molto piccoli.