CODEWITHSUNDEEP
haskell
avak
avak

Reputation: 189

Runtime of function composition in Haskell

Does

reverse . sort

or

sortBy

run faster when attempting to sort a list of integers in descending order?

Upvotes: 4

Views: 310

Answers (2)

user8174234
user8174234

Reputation:

Does

reverse . sort

or

sortBy

run faster when attempting to sort a list of integers in descending order?

sortBy will be faster. In reverse traverses the whole list, so reverse . sort will traverse the entire list twice. In fact, the other answer's benchmarks were pretty close to exactly two times as long for reverse . sort! If you use sortBy you just have to flip the comparison test, so it's to be preferred in all cases.

Upvotes: 1

Elliot Robinson
Elliot Robinson

Reputation: 1384

I whipped up a Criterion test sorting using (reverse . sort), and (sortBy (comparing Down)). Lists to sort were ordered and reverse ordered (should be worst and best cases, not necessarily in that order).

Code

import Criterion
import Criterion.Main

import Data.List
import Data.Ord

main :: IO ()
main = defaultMain [ bench "Sort, forward" (whnf (reverse . sort) ([1..10000] :: [Int]))
                   , bench "Sort, backward" (whnf (reverse . sort) ([10000,9999..1] :: [Int]))
                   , bench "sortby, forward" (whnf (sortBy (comparing Down)) ([1..10000] :: [Int]))
                   , bench "sortby, backward" (whnf (sortBy (comparing Down))  ([10000,9999..1] :: [Int]))
                   ]

{-
warming up
estimating clock resolution...
mean is 2.290904 us (320001 iterations)
found 79468 outliers among 319999 samples (24.8%)
  734 (0.2%) low severe
  78734 (24.6%) high severe
estimating cost of a clock call...
mean is 512.8809 ns (23 iterations)
found 4 outliers among 23 samples (17.4%)
  2 (8.7%) high mild
  2 (8.7%) high severe

benchmarking Sort, forward
mean: 551.4973 us, lb 549.7330 us, ub 553.6538 us, ci 0.950
std dev: 9.998922 us, lb 8.400519 us, ub 12.37726 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
  4 (4.0%) high mild
variance introduced by outliers: 11.316%
variance is moderately inflated by outliers

benchmarking Sort, backward
mean: 307.6627 us, lb 306.6471 us, ub 308.9350 us, ci 0.950
std dev: 5.790552 us, lb 4.777178 us, ub 7.103792 us, ci 0.950
found 9 outliers among 100 samples (9.0%)
  7 (7.0%) high mild
  2 (2.0%) high severe
variance introduced by outliers: 11.365%
variance is moderately inflated by outliers

benchmarking sortby, forward
mean: 168.2486 us, lb 167.7343 us, ub 168.8683 us, ci 0.950
std dev: 2.880548 us, lb 2.448853 us, ub 3.394461 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
  4 (4.0%) high mild
variance introduced by outliers: 9.467%
variance is slightly inflated by outliers

benchmarking sortby, backward
mean: 262.6001 us, lb 261.3540 us, ub 264.1395 us, ci 0.950
std dev: 7.096662 us, lb 6.053786 us, ub 8.634885 us, ci 0.950
found 3 outliers among 100 samples (3.0%)
  3 (3.0%) high mild
variance introduced by outliers: 20.965%
variance is moderately inflated by outliers
-}

Summary results

Reversing lists is expensive. The best case test with reverse was still significantly (statistically) slower than the worst case with sortBy.

Mean runtimes were:

  • sort, worst case: 552us
  • sort, best case: 308us
  • sortBy, worst case: 263us
  • sortBy, best case: 168us

Upvotes: 8

Related Questions