What if focusing on the correct data structure, while still understanding your algorithm, could improve maintainability and collaterally speed up execution by a factor of over 15x compared to over-engineered C# code?
Once upon a time, I saw this problem come up in a misguided polemic:
You are given an input array whose each element represents the height of a line towers. The width of every tower is 1. It starts raining. How much water is collected between the towers?
You can write a neat and correct solution in Haskell.
rainfall :: [Int] -> Int
rainfall xs = sum (zipWith (-) mins xs)
where
mins = zipWith min maxl maxr
maxl = scanl1 max xs
maxr = scanr1 max xsThe trouble is, it’s quite slow (7.2s – including setting up the world, since you didn’t exclude that from your benchmark). From here you have two options. Your first option is to write a long rant about how slow this code is and share it on the internet. Your second option is to use the right data structure and get a 114x speed up (61ms) for almost zero effort.
rainfall' :: Vector Int -> Int
rainfall' xs = V.sum (V.zipWith3 (\l r x -> (min l r) - x) maxl maxr xs)
where
maxl = V.scanl1' max xs
maxr = V.scanr1' max xsThis popular hipster code is also 15x faster than some over-engineered C# code. The drawback of the fast Haskell code is that it’s not so easy to change if your boss decides to shift the requirements under you because he believes there are real towers filling with water and insists that he wants to be able to drill holes in the walls.
Use the correct data structure. If you’re not sure, hold back on the sarcasm and ask Porges to help you out. He seems to be a smart cookie.