“Simultaneous” minimum and maximum of a list

  • A+
Category:Languages

This function returns a 2-tuple with the minimum and the maximum of a list:

import Control.Arrow ((***), (>>>), (&&&)) import Data.Semigroup (getMin, getMax, Min(..), Max(..))  bounds :: (Bounded a, Ord a) => [a] -> (a,a) bounds = foldMap (Min &&& Max) >>> getMin *** getMax 

Example:

> x = [1..10 :: Int] > bounds x (1,10) 

Is it more efficient than (minimum x, maximum x) ?

Or is there another way more efficient than (minimum x, maximum x) ?


First off, your two functions do not behave the same. (minimum xs, maximum xs) dies when xs is an empty list.

Is it more efficient than (minimum x, maximum x)?

They're both O(n), but the only way to answer questions like this is to benchmark them competitively. I think I'd expect the foldMap solution to be faster, as it makes only a single pass over the list, but let's find out.

import Control.Arrow ((***), (>>>), (&&&)) import Data.Semigroup (getMin, getMax, Min(..), Max(..)) import System.Random import Criterion.Main  bounds1, bounds2 :: (Bounded a, Ord a) => [a] -> (a,a) bounds1 = foldMap (Min &&& Max) >>> getMin *** getMax bounds2 xs = (minimum xs, maximum xs)  randomList :: Int -> IO [Int] randomList count = take count <$> randoms <$> newStdGen  mkBench n = env (randomList n) $ /list -> bgroup (show n) [     bench "foldMap" $ nf bounds1 list,     bench "minMax" $ nf bounds2 list     ]  main = defaultMain $ map mkBench [100, 1000, 10000, 100000, 1000000] 

“Simultaneous” minimum and maximum of a list

Tabulated, that's

100/foldMap 1.411 μs 100/minMax 517.6 ns  1000/foldMap 28.94 μs 1000/minMax 5.078 μs  10000/foldMap 488.4 μs 10000/minMax 51.56 μs  100000/foldMap 21.08 ms 100000/minMax 537.3 μs  1000000/foldMap 268.9 ms 1000000/minMax 8.989 ms 

So (minimum xs, maximum xs) turns out to be faster than the foldMap idea, across the board.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: