c - Quicksort - 为什么我的 dutch-flag 实现比我的 Hoare-2-partition 实现慢？

Question

作为学习练习，我正在用 C 语言实现快速排序算法。枢轴是 3 个值的中位数，对于具有 4 个或更少元素的分区，我切换到插入排序。

现在我一直在测试两种变体:一种使用 Hoare's partition scheme , 另一个用途 Dutch Flag .

更新:包括两个变体的整个文件。

霍尔的:

#include <stdlib.h>
#include "quicksort.h"

#define THRESHOLD 4
#define SWAP(a, b)          \
{                           \
    char *a_swap = (a);     \
    char *b_swap = (b);     \
    int size_swap = size_q; \
    char tmp;               \
    while(size_swap-- > 0) {\
        tmp = *a_swap;      \
        *a_swap++ = *b_swap;\
        *b_swap++ = tmp;    \
    }                       \
}

#define MEDIAN_OF_3(left, mid, right)       \
{                                           \
    char *l = (left);                       \
    char *m = (mid);                        \
    char *r = (right);                      \
    if((*cmp_q)((void *)m, (void *)l) < 0) {\
        SWAP(m, l);                         \
    }                                       \
    if((*cmp_q)((void *)r, (void *)m) < 0) {\
        SWAP(r, m);                         \
    } else {                                \
        goto jump;                          \
    }                                       \
    if((*cmp_q)((void *)m, (void *)l) < 0) {\
        SWAP(m, l);                         \
    }                                       \
    jump:;                                  \
}

#define COPY(dest, src)             \
{                                   \
    char *src_copy = (src);         \
    char *dest_copy = (dest);       \
    size_t size_copy = size_q;      \
    while(size_copy-- > 0) {        \
        *dest_copy++ = *src_copy++; \
    }                               \
}

static size_t size_q = 0;
static char *e = NULL;
static int (*cmp_q)(const void *, const void *) = NULL;

void sort(char *left, char *right) {

    int elements = (right+size_q-left)/size_q;
    //========== QUICKSORT ==========
    if(elements > THRESHOLD) {

        //========== PIVOT = MEDIAN OF THREE ==========
        char *mid = left+size_q*((right-left)/size_q>>1);
        MEDIAN_OF_3(left, mid, right);
        char *pivot = mid;

        //========== PARTITIONING ==========
        char *left_part = left+size_q;
        char *right_part = right-size_q;
        while(left_part < right_part) {

            while((*cmp_q)((void *)left_part, (void *)pivot) < 0) {
                left_part += size_q;
            }

            while((*cmp_q)((void *)right_part, (void *)pivot) > 0) {
                right_part -= size_q;
            }

            if(left_part < right_part) {

                SWAP(left_part, right_part);

                if(pivot == left_part) {
                    pivot = right_part;
                } else if(pivot == right_part) {
                    pivot = left_part;
                }

                left_part += size_q;
                right_part -= size_q;
            }
        }

        //========== RECURSIVE CALLS ==========
        sort(left, right_part);
        sort(left_part, right);

    } else if(elements > 1) {

        //========== INSERTION SORT ==========
        char *i, *j;
        for(i = left+size_q; i <= right; i += size_q) {

            if((*cmp_q)((void *)i, (void *)(i-size_q)) < 0) {

                COPY(e, i);
                for(j = i-size_q; j >= left && (*cmp_q)((void *)e, (void *)j) < 0; j -= size_q) {
                    COPY(j+size_q, j);
                }
                COPY(j+size_q, e);
            }
        }
    }
}

void quicksort(void *array, size_t num, size_t size, int (*cmp)(const void *a, const void *b)) {
    char *array_q = (char *)array;
    size_q = size;
    cmp_q = cmp;
    e = malloc(size_q);
    sort(array_q, array_q+size_q*(num-1));
    free(e);
}

荷兰国旗:

#include <stdlib.h>
#include "quicksort.h"

#define THRESHOLD 4
#define SWAP(a, b)          \
{                           \
    char *a_q = (a);        \
    char *b_q = (b);        \
    int size_swap = size_q; \
    char tmp;               \
    while(size_swap-- > 0) {\
        tmp = *a_q;         \
        *a_q++ = *b_q;      \
        *b_q++ = tmp;       \
    }                       \
                            \
}

#define MEDIAN_OF_3(left, mid, right)       \
{                                           \
    char *l = (left);                       \
    char *m = (mid);                        \
    char *r = (right);                      \
    if((*cmp_q)((void *)m, (void *)l) < 0) {\
        SWAP(m, l);                         \
    }                                       \
    if((*cmp_q)((void *)r, (void *)m) < 0) {\
        SWAP(r, m);                         \
    } else {                                \
        goto jump;                          \
    }                                       \
    if((*cmp_q)((void *)m, (void *)l) < 0) {\
        SWAP(m, l);                         \
    }                                       \
    jump:;                                  \
}

#define COPY(dest, src)             \
{                                   \
    char *src_copy = (src);         \
    char *dest_copy = (dest);       \
    size_t size_copy = size_q;      \
    while(size_copy-- > 0) {        \
        *dest_copy++ = *src_copy++; \
    }                               \
}

static size_t size_q = 0;
static char *pivot = NULL;
static char *e = NULL;
static int (*cmp_q)(const void *, const void *) = NULL;

void sort(char *left, char *right) {

    int elements = (right+size_q-left)/size_q;
    //========== QUICKSORT ==========
    if(elements > THRESHOLD) {

        //========== PIVOT = MEDIAN OF THREE ==========
        char *mid = left+size_q*((right-left)/size_q>>1);
        MEDIAN_OF_3(left, mid, right);
        COPY(pivot, mid);

        //========== 3-WAY PARTITIONING (DUTCH FLAG PROBLEM) ==========
        char *less = left;
        char *equal = left;
        char *greater = right;
        int value;
        while(equal <= greater) {
            value = (*cmp_q)((void *)equal, (void *)pivot);
            if(value < 0) {
                SWAP(less, equal);
                less += size_q;
                equal += size_q;
            } else if(value > 0) {
                SWAP(equal, greater);
                greater -= size_q;
            } else {
                equal += size_q;
            }
        }

        //========== RECURSIVE CALLS ==========
        sort(left, less-size_q);
        sort(greater+size_q, right);

    } else if(elements > 1) {

        //========== INSERTION SORT ==========
        char *i, *j;
        for(i = left+size_q; i <= right; i += size_q) {
            if((*cmp_q)((void *)i, (void *)(i-size_q)) < 0) {

                COPY(e, i);

                for(j = i-size_q; j >= left && (*cmp_q)((void *)e, (void *)j) < 0; j -= size_q) {
                    COPY(j+size_q, j);
                }

                COPY(j+size_q, e);
            }

        }
    }
}

void quicksort(void *array, size_t num, size_t size, int (*cmp)(const void *a, const void *b)) {
    char *array_q = (char *)array;
    size_q = size;
    cmp_q = cmp;
    pivot = malloc(size_q);
    e = malloc(size_q);
    sort(array_q, array_q+size_q*(num-1));
    free(pivot);
    free(e);
}

两者得到相同的输入，一系列文件，每个文件包含 10^n 范围为 [0:(10^n)+1]< 的随机整数值。 n 的范围从 1 到 7(10 到 1000 万个元素)。我希望 Dutch Flag 的实现速度至少与 Hoare 的一样快，但事实并非如此。

标志:-O3

Implementation    Size    Runs   Time
Hoare's           10^7    10     avg=2.148s
Dutch Flag        10^7    10     avg=3.312s

然后我更改了输入:相同的大小，10^n，但值是 [0:10^(n-1)]，这保证了很多重复值(value)观。

结果:

Implementation    Size    Runs   Time
Hoare's           10^7    10     avg=0.170s
Dutch Flag        10^7    10     avg=0.260s

即使对于重复值，Dutch Flag 也比 Hoare 慢。为什么？所选择的枢轴似乎不太可能是唯一的。

我的环境，如果重要的话:

CPU=Intel(R) Core(TM) i7-6820HK @ 2.70GHz
VM OS=Linux version 4.4.0-36-generic, Ubuntu 16.04.2, gcc version 5.4.0
Host=Microsoft Windows 10 Home
IDE=Eclipse CDT Neon

Answer 1

1. 不要使用malloc 和free。每次递归调用(总共N次)都要用到它们，耗费大量时间。

2. 如果启用优化 (-O3)，比较将更有用。

3. SWAP 是宏还是函数？如果是函数，尽量让它内联。