Which maximum selection algorithm is faster? (Haskell)

Question

I have a suspicion that it's the first one, but I'm not sure, and don't know how to check so I thought I'd just post here. I was also kinda lazy to provide normal examples, but the type thing is basically irrelevant to my question.

data Storage = HDD String Int Int
             | SSD String Int
             deriving(Show,Eq)

maxSSD :: [Storage] -> Int -> Int
        maxSSD (HDD{}:xs) mx = maxSSD xs mx
        maxSSD [] mx = mx
        maxSSD l@((SSD _ x):xs) (-1) = maxSSD l x
        maxSSD ((SSD _ x):xs) mx
            |x>mx = maxSSD xs x
            |otherwise = maxSSD xs mx

maxSSD' :: [Storage] -> Int
        maxSSD (HDD{}:xs) = maxSSD xs
        maxSSD [] = 0
        maxSSD ((SSD _ x):xs) 
                |x>(maxSSD xs) = x
                |True = maxSSD xs

I don't think `maxSSD'` will even compile as written; it should be recursive, not calling `maxSSD`, correct? — Pillsy, Nov 05 '21 at 13:59
@Pillsy calling self (on the reduced input) _is_ being recursive. — Will Ness, Nov 05 '21 at 14:00
I'm kind of not sure the closure is right. this Q asks this about its specific code, and the algorithms: one iterative, the other recursive, not just in general like in the proposed duplicate. — Will Ness, Nov 05 '21 at 14:28
maybe someone will want to comment on the strictness analyzer's impact on the performance or something... ping me if you need me to reopen this. — Will Ness, Nov 05 '21 at 14:37
@ the asker: do you think the "duplicate" answers your question? — Will Ness, Nov 05 '21 at 17:41

Will Ness · Accepted Answer · 2021-11-05T14:35:57.590

NB: of course the indentation is all wrong (the signatures' indentation and definitions' should be the same), and I assume all maxSSDs in the second code are actually maxSSD's.

On the face of it the first is linear and the second is worst case exponential, calculating the recursive call (maxSSD' xs) twice in some cases.

But since that expression participates in > comparison, and > is strict in both arguments, if you compile with optimizations (-O2) the strictness analyzer could hopefully kick in, preventing the re-calculation of the same value.

You can test this by compiling with -O2 and running the compiled standalone executable with -RTS +s to get the time and space statistics, then run it at few different problem sizes, say, doubling it each time. Then see whether the run time doubles as well.

see also: Empirical orders of growth

In general we can say that the first code expresses an iterative algorithm and the second a recursive one.

A simple tweak of the second will prevent any possibility of recalculation of the same value:

Just use a let / where clause, as appropriate, to introduce a binding that holds the result of the recursive call, then refer to that variable twice. This way it is guaranteed to only be calculated once.

Which maximum selection algorithm is faster? (Haskell)

1 Answers1