我有很多不同的排序算法,它们都具有以下特征:
void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);
有没有任何针对排序的测试套件,可以用于进行实证比较?
我有很多不同的排序算法,它们都具有以下特征:
void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);
有没有任何针对排序的测试套件,可以用于进行实证比较?
这篇详细的讨论文章不仅链接了大量相关网页,对于测试排序算法也提出了一组有用的输入数据(原因请参见链接页面)。总结如下:
valgrind
是一个有效但缓慢的工具。sortperf.py是一个精选的基准测试用例套件,被用来支持在多年前发现的文章(这里)并使timsort成为Python中的排序算法。请注意,最终Java可能也会采用timsort,这要归功于Josh Block(请参见此处),因此我想他们已经编写了自己版本的基准测试用例,但是我很难找到相关参考资料。(timsort是一种稳定、适应性强、迭代的自然合并排序变体,特别适用于具有引用-对象语义的语言,如Python和Java,在这些语言中,“数据移动”相对较便宜[[因为移动的只是引用或指针,而不是大小不受限制的二进制大块;-)],但比较代价相对较高[[因为没有上限的比较函数复杂度——但这同样适用于任何通过自定义比较或键提取函数来自定义排序的语言]]。)