Radix Sort Quick Sortより遅くなりますか?
-
29-09-2020 - |
質問
基数ソートが迅速なソートより優れていることを実証したいと思います。この例では、以下のプログラムを使用しています。
#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());
}
.
続かせるように実行します。
$ gcc bench.c -lm
$ ./a.out
Init memory (200 MB)...
Sorting n = 52428800 data elements...
931920169 1.858300 s
314572812 1.541998 s
.
私は o(n log n)でクイックソートが実行されることを知っていますが、基数ソートは o(d(n + r))〜= O(6 * n)。n = 52428800
、log(n) = 17
の場合。その後、Radix SortがQuick Sortよりも3倍高速になることを期待しています...
これは私が観察するものではありません。
私は何が足りないの?
解決
-
qsortはQuickSortではありません。QSORTは、標準ライブラリの実装者が決定したものであれです。
-
ソート5000万の同一の値は非常に過程状である。1,000万の同一または5000万のソートされた要素または逆のソートされた要素を線形時間に分類するQSORT実装があります。
-
基数6桁の5000万の数字は明らかにナンセンスです。6桁の桁は、64の異なる値しかないことを意味し、それ故にカウントソートを使用することを意味します。26桁未満では意味がありません。
-
あなたのRadix Sortは、コピーされ、悪化していないコピーをひどく、そして悪いコピーをします。
-
数字が奇数の場合、Radix Sortは正しくソートされた結果を生成しません。
-
配列に非常に大きく非常に小さい数字が含まれている場合、QSORT呼び出しは正しくソートされた結果を生み出しません。
所属していません cs.stackexchange