Performance Measurement Method

Question

Considering exercise 14 of 99 Haskell Problems :

(*) Duplicate list items.

For instance:.

*Main> dupli''' [1..10] [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10] 

I implemented 4 solutions:

 {-- my first attempt --} dupli :: [a] -> [a] dupli [] = [] dupli (x:xs) = replicate 2 x ++ dupli xs {-- using concatMap and replicate --} dupli' :: [a] -> [a] dupli' xs = concatMap (replicate 2) xs {-- usign foldl --} dupli'' :: [a] -> [a] dupli'' xs = foldl (\acc x -> acc ++ [x,x]) [] xs {-- using foldl 2 --} dupli''' :: [a] -> [a] dupli''' xs = reverse $ foldl (\acc x -> x:x:acc) [] xs 

However, I do not know how to really measure performance.

So what is the recommended feature (from the list above) in terms of performance.

Any suggestions?

Answer 1

According to the recommendations, you can use the criteria package. Good description http://www.serpentine.com/blog/2009/09/29/criterion-a-new-benchmarking-library-for-haskell/ .

To summarize it here and adapt to your question, follow these steps: Set criteria using

 cabal install criterion -fchart 

And add the following to your code

  import Criterion.Main

 l = [(1 :: Int) .. 1000]

 main = defaultMain [bench "1" $ nf dupli l
                    , bench "2" $ nf dupli 'l 
                    , bench "3" $ nf dupli '' l
                    , bench "4" $ nf dupli '' 'l
                    ]

You need nf to force a complete list of results. Otherwise, you will only get a tone for calculation.

After that compile and run

  ghc -O --make dupli.hs
 ./dupli -t png -k png

and you will get beautiful runtime graphs of various functions.

It turns out that dupli''' is the fastest of your functions, but the foldr version specified in the pelotome is superior.

Answer 2

They all seem more complex (and / or less efficient) than they should be. Why not only this:

 dupli [] = [] dupli (x:xs) = x:x:(dupli xs) 

Your last example is close to a good implementation based on addition, but you should use foldr , which saves you from having to undo the result:

 dupli = foldr (\x xs -> x:x:xs) [] 

In terms of performance measurement, an “empirical approach” is profiling . As Haskell programs grow in size, they can be quite difficult to reason in terms of execution complexity and space, and profiling is your best bet. In addition, a crude but often effective empirical approach to measuring the relative complexity of two functions is simply to compare how much time they take to a sufficiently large input; for example, how long length $ dupli [1..1000000] takes and compares it with dupli'' , etc.

But for a program, this small value should not be too complicated to determine the complexity of the algorithm based on your knowledge of the data structure (s) in question - in this case, lists. Here's a tip: when using concatenation ( x ++ y ), the execution complexity is O ( length x ). If concatenation is used inside a recursive algorithm running on all elements of a list of size n, you will essentially have an O (n ^ 2) algorithm. Both examples I gave, and your last example is O (n), since the only operation used inside the recursive definition is (:) , which is O (1).