使用`filter`/list comprehension的朴素排序的Haskell/GHC表现

Question

编译-O3,使用的程序

quicksort []       = []
quicksort (x : xs) = quicksort (filter (< x) xs)
                     ++ [x] ++
                     quicksort (filter (>= x) xs)

比使用的程序慢1.1倍

quicksort2 []       = []
quicksort2 (x : xs) = quicksort2 [y | y <- xs, y < x]
                      ++ [x] ++
                      quicksort2 [y | y <- xs, y >= x]

比使用的程序慢6倍

minisort [] = []
minisort xs = let x = minimum xs
              in  x : minisort (delete x xs)

这些不是Haskell本地合并sort,并不意味着.

考虑到所涉及的操作的复杂性,我注意到minisort一直运行得比两个都快得多quicksort,这似乎是可以理解的.我不明白的是一贯的轻微优势quicksort2已经结束quicksort.列表推导通常比filter表达式更有效吗？

---

由我所用,到目前为止,是标准,与nf,ghci的:set +s,和2个远程性能displayant在线编译器(ideone,rextester).

标准基准分类最坏情况[5000, 4999 .. 1] :: [Int]:

benchmarking quicksort
time                 2.283 s     (2.191 s .. 2.450 s)
                     0.999 R²    (0.998 R² .. 1.000 R²)
mean                 2.434 s     (2.368 s .. 2.485 s)
std dev              79.23 ms    (0.0 s .. 88.75 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking quicksort2
time                 2.203 s     (1.982 s .. 2.455 s)
                     0.998 R²    (0.994 R² .. 1.000 R²)
mean                 2.327 s     (2.275 s .. 2.359 s)
std dev              49.11 ms    (0.0 s .. 56.47 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking minisort
time                 257.2 ms    (229.7 ms .. 276.4 ms)
                     0.997 R²    (NaN R² .. 1.000 R²)
mean                 274.4 ms    (264.3 ms .. 280.9 ms)
std dev              9.714 ms    (2.538 ms .. 12.94 ms)
variance introduced by outliers: 16% (moderately inflated)

quicksort2总是(不同的测试用例,订单和上下文)执行得比quicksort.minisort到目前为止,表现优于两者.