5
В качестве учебного упражнения я реализую алгоритм Quicksort в C. Pivot является медианом из 3 значений, а для разделов с 4 или менее элементами я переключаюсь на Insertion Sort.Quicksort - почему реализация моего флагманского флага медленнее, чем моя реализация разделов Hoare-2?
Теперь я тестировал два варианта: один использует 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 до 10 миллионов элементов). Я ожидал, что реализация голландского флага будет, по крайней мере, так же быстро, как и Хоар, но это было не так.
Флаги: -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)], которые гарантировали много повторяющихся значений.
Результат:
Implementation Size Runs Time
Hoare's 10^7 10 avg=0.170s
Dutch Flag 10^7 10 avg=0.260s
Даже для повторных значений голландский флаг медленнее, чем Хоара. Зачем? Не похоже, что выбранный стержень уникален.
Моя среда, если это имеет значение:
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
Как вы генерируете свои ценности? Какой тип вы фактически сортируете? – 2501
Код не компилируется. Я не знаю, что делают все переменные. –
@ 2501: Значения уже созданы. Я просто читаю их из файла в массив, а затем передаю его. –