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 xs
The 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 xs
This 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.