Какие оптимизации можно сделать для этого кода Haskell?

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] 

Я Haskell Newb - всего несколько дней в нем .. Если я делаю что-то явно не так, whoopsies

Answer 1

Вы можете улучшить среду выполнения много, заметив, что map sum (produceContiguous d n) (которая во время выполнения Ом (m^2), m длина drop n d - возможно время O (m^3), поскольку вы добавляете до конца acc на каждой итерации) может быть свернута до scanl (+) 0 (drop n d) (которая имеет время выполнения O (m)). Есть много других стилистических изменений, которые я бы сделал, но это основной алгоритмический, о котором я могу думать.

Очистка все стилистические вещи, я бы, наверное, написать:

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

В 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) 

Не показано здесь является версия jaggedGoofyMax, которая имеет только оптимизации я упомянул в моем первом абзаце, который имеет немного лучшую статистику использования времени/памяти до dmwitMax при запуске в ghci (но в основном идентичен dmwitMax, когда оба скомпилированы wi th -O2). Таким образом, вы можете видеть, что для даже скромных размеров ввода эта оптимизация может иметь большое значение.