What optimizations can be made to this Haskell code?

Question

--Returns last N elements in list
lastN :: Int -> [a] -> [a]
lastN n xs = let m = length xs in drop (m-n) xs

--create contiguous array starting from index b within list a
produceContiguous :: [a] -> Int -> [[a]]
produceContiguous [] _ = [[]]  
produceContiguous arr ix = scanl (\acc x -> acc ++ [x]) [arr !! ix] inset
    where inset = lastN (length arr - (ix + 1)) arr

--Find maximum sum of all possible contiguous sub arrays, modulo [n]
--d is dummy data
let d = [1,2,3,10,6,3,1,47,10]
let maxResult = maximum $ map (\s -> maximum s) $ map (\c -> map (\ac -> (sum ac )`mod` (last n)) c ) $ map (\n -> produceContiguous d n ) [0..(length d) -1]

I'm a Haskell newb - just a few days into it .. If I'm doing something obviously wrong, whoopsies

If the code is working and you just want suggestions for improvement, you should post at codereview.stackexchange.com. Otherwise, you need to specify exactly what the problem is that you want solved. — chepner
– chepner, Commented Feb 5, 2016 at 2:32
This is a weird variation on the maximum subarray problem. I'm guessing the modulo n bit is designed to break the standard (efficient) solution. I'm not sure if there's any similarly efficient solution to this variant, but I doubt it. Modular arithmetic and maximization don't really mesh very well in general. — dfeuer
– dfeuer, Commented Feb 5, 2016 at 6:34
In this kind of questions, you should always include a specification, by stating in plain words what the program is supposed to do. This will provide more visibility -- I guess most readers just see a block of code and stop reading. There is a very brief one inside the code in the comment above d, but it's lost in the noise. — chi
– chi, Commented Feb 5, 2016 at 9:02
Fair enough; here is the link to the hackerrank challenge I'm attempting to solve - hackerrank.com/challenges/maximise-sum — jaggedGoofy
– jaggedGoofy, Commented Feb 5, 2016 at 20:29

Daniel Wagner · Accepted Answer · 2016-02-05 05:45:39Z

6

You can improve the runtime a lot by observing that map sum (produceContiguous d n) (which has runtime Ω(m^2), m the length of drop n d -- possibly O(m^3) time because you're appending to the end of acc on each iteration) can be collapsed to scanl (+) 0 (drop n d) (which has runtime O(m)). There are plenty of other stylistic changes I would make as well, but that's the main algorithmic one I can think of.

Cleaning up all the stylistic stuff, I would probably write:

import Control.Monad
import Data.List
addMod n x y = (x+y) `mod` n
maxResult n = maximum . (scanl (addMod n) 0 <=< tails)

In ghci:

*Main> jaggedGoofyMax 100 [1..1000]
99
(12.85 secs, 24,038,973,096 bytes)
*Main> dmwitMax 100 [1..1000]
99
(0.42 secs, 291,977,440 bytes)

Not shown here is the version of jaggedGoofyMax that has only the optimization I mentioned in my first paragraph applied, which has slightly better runtime/memory usage stats to dmwitMax when run in ghci (but basically identical to dmwitMax when both are compiled with -O2). So you can see that for even modest input sizes this optimization can make a big difference.

edited Feb 5, 2016 at 5:45

answered Feb 5, 2016 at 3:06

Daniel Wagner

156k10 gold badges231 silver badges393 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

dfeuer Over a year ago

I suggest using <=< instead of >=> to keep all the compositions flowing the same way.

jaggedGoofy Over a year ago

This is the awesomeness of Haskell that drew me to it. Thanks for the explanation

Collectives™ on Stack Overflow

What optimizations can be made to this Haskell code?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related