为什么不平滑更普遍?

从阅读维基百科关于sortingalgorithm的文章,似乎smoothsort是最好的sortingalgorithm。 它在所有类别中都有顶级的performance:最好的,平均的和最差的。 没有什么比它在任何类别中都要好。 它也有不断的内存需求。 唯一的缺点是它不稳定。

它在内存中击败timsort,在最坏的情况下性能和内存都能快速跳动。

但是我从来没有听说过smoothsort。 没有人提到过,大多数讨论似乎围绕着其他sortingalgorithm。

这是为什么?

大O的performance非常适合发表论文,但在现实世界中,我们也必须看看常数。 快速sorting一直是不稳定的,原地的,内存中sorting的algorithm,因为我们可以非常有效地实现其内部循环,并且非常caching友好。 即使你可以像使用快速sorting一样有效地或几乎有效地实现smoothsort的内部循环,你可能会发现它的caching缺失率会使它变慢。

我们通过花费更多的精力来select好的支架(减less病理病例的数量)和检测病理情况,从而减轻快速排便的最差情况。 查找introsort 。 Introsort首先运行快速sorting,但如果检测到过度recursion(表示快速sorting的病态),则切换到堆sorting。

更好的渐近并不意味着更好的性能(虽然通常情况下是如此)。 隐藏的常量可能会大几倍,导致在相对较小的数组( 相对较小的数组,实际上可能是任意大小,10 100 )的另一个algorithm(具有相同或甚至最差的渐近复杂度)例如,这是渐近分析)。 但是我对平滑隐藏的常量一无所知。

例如, 有一个O(n)最差时间algorithm用于查找第k阶统计量,但是如此复杂,O(n log n)最坏情况版本在大多数情况下胜过它。

另外还有一个有趣的比较 :

…你可以看到,Timsort和Smoothsort都没有切芥末。 在所有情况下,即使std:bitset被replace为原始位操作,SmoothSort也比STL更差…

那么首先我会说,这不是像Smoothsort不出名。 这取决于用户的需要,也取决于用户是否使用它。

smoothsort的优点在于,如果input已经被sorting到一定程度,它会更接近O(n)时间,而sorting平均O(n log n),而不pipe最初的sorting状态如何。

从文档 : –

smoothsortalgorithm需要能够在内存中保存string中所有堆的大小。 由于所有这些值是不同的,所以通常使用一个位向量来完成。 而且,由于在序列中最多有O(log n)个数字,所以这些比特可以用O(1)个机器字编码,假设是一个双向机器模型。