我正在开发排序算法，并惊讶地发现c的qsort所用的时间是Julia默认排序算法的1.6倍。我想我犯了某种基准错误。以下是我的基准测试程序及其结果:
朱莉娅:
# time (julia bench.jl)
using Printf
function main()
len = 100_000_000
x = rand(Int64, len)
t = @elapsed sort!(x)
@printf "%d elements:nclaimt%fs" len t
end
main()
c
// time (gcc -O3 bench.c && ./a.out)
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
int comp (const void * elem1, const void * elem2)
{
int f = *((int*)elem1);
int s = *((int*)elem2);
if (f > s) return 1;
if (f < s) return -1;
return 0;
}
long long utime()
{
struct timeval now_time;
gettimeofday(&now_time, NULL);
return now_time.tv_sec * 1000000LL + now_time.tv_usec;
}
int main(int argc, char* argv[])
{
long length = 100000000;
long long *x;
x = (long long *) malloc(length * sizeof(long long));
if (x == NULL)
{
printf("Malloc failedn");
return 1;
}
for (long cnt = 0 ; cnt < length ; cnt++)
x[cnt] = rand();
long long start = utime();
qsort (x, length, sizeof(*x), comp);
long long end = utime();
//for (long cnt = 0 ; cnt < length ; cnt += length/10)
// printf("%lldn", x[cnt]);
free(x);
printf ("%ld elements:nclaimt%fs", length, (end-start)/1000000.0);
return 0;
}
结果
bash-3.2$ time (julia bench.jl)
100000000 elements:
claim 12.405531s
real 0m16.560s
user 0m13.883s
sys 0m1.297s
bash-3.2$ time (gcc -O3 bench.c && ./a.out)
100000000 elements:
claim 20.592641s
real 0m24.604s
user 0m21.352s
sys 0m2.479s
Julia的算法(对于少于20个元素的插入排序基数为3个快速排序的中位数)比c的qsort要快得多，这是真的吗?c中的排序能比qsort快吗?
比C的qsort更容易排序。例如，您可以使用c++的std::sort。c++库之所以更快并不是因为它使用了更好的算法;更确切地说，这是因为c++的泛型允许编译器避免调用比较函数的开销和qsort的交换(需要处理任意大小的元素)的较小开销。
在下面，sortbench-c和sortbench-cc之间的唯一区别是后者使用了std::sort:
$ diff sortbench-c.c sortbench-cc.cc
1c1
< // time (gcc -O3 sortbench-c.c && ./a.out)
---
> // time (gcc -O3 sortbench-cc.cc && ./a.out)
2a3
> #include <algorithm>
7,14d7
< int comp (const void * elem1, const void * elem2)
< {
< int f = *((int*)elem1);
< int s = *((int*)elem2);
< if (f > s) return 1;
< if (f < s) return -1;
< return 0;
< }
38c31
< qsort (x, length, sizeof(*x), comp);
---
> std::sort(x, x+length);
差异是显著的:
$ time (gcc -O3 sortbench-c.c && ./a.out)
100000000 elements:
claim 16.673827s
real 0m17.774s
user 0m17.387s
sys 0m0.379s
$ time (gcc -O3 sortbench-cc.cc && ./a.out)
100000000 elements:
claim 9.948971s
real 0m11.133s
user 0m10.926s
sys 0m0.204s
qsort:
没有性能保证尽管有这个名字，C和POSIX标准都不要求使用快速排序来实现这个函数，也不要求做任何复杂性或稳定性保证。
要在Julia和C之间进行适当的排序基准测试，您将需要另一个实现。
问题是rand函数[可能]不同。
快速排序依赖于数据/顺序。例如，归并排序总是在相同的时间内执行，不管它排序的是什么数据。
但是，快速排序的时间会根据数据的不同而变化。
要做一个正确的基准测试，不要使用rand，除非你自己写，或者保证Julia的版本和libc的版本完全相同。
我会为这两种语言写一个初始化函数。例如，必需的for (i = 0; i < length; ++i) array[i] = length - i;或诸如此类的，以便保证初始数据是相同的。
你可以使用一个随机函数如果你有一个程序生成数组并保存到一个文件。然后，另一个程序可以读入[相同的]数据。
有时，我编写一个单独的程序来生成输入数据，并将其保存到文件中。然后，我将该文件传递给两个程序。这将测试数据从被测程序中分离出来。