可以对此Haskell代码进行哪些优化？

--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福利局 - 短短几天到它。如果我做的事情显然是错误的，whoopsies可以对此Haskell代码进行哪些优化？

来源

2016-02-05 jaggedGoofy

如果代码正常工作，而您只是想要改进建议，则应该在codereview.stackexchange.com上发帖。否则，您需要明确指出您想解决的问题。 – chepner

这是最大的子阵列问题的一个奇怪的变化。我猜测模n'位是为了打破标准（高效）解决方案而设计的。我不确定是否有类似的有效解决方案，但我对此表示怀疑。一般来说，模块化算术和最大化并不能很好地啮合。 – dfeuer

在这类问题中，你应该总是包含一个规范，用简单的话来说明程序应该做什么。这将提供更多的可见性 - 我想大多数读者只会看到一段代码并停止阅读。代码中有一个非常简短的代码，在'd'上面的注释中，但是它在噪声中丢失了。 – chi

您可以通过观察map sum (produceContiguous d n)（其运行时Ω提高运行了很多（m^2），可以折叠为scanl (+) 0 (drop n d)（其具有运行时间O（m）），因此您可以在每个迭代中追加到acc的末尾，因此可能需要O（m^3）时间。我还会做很多其他的风格变化，但这是我能想到的主要算法。

清理所有风格的东西，我可能会写：

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有只有我提到的优化在我应用的第一段中，运行时/内存使用情况统计信息略好于在ghci中运行时的dmwitMax（但基本上与dmwitMax相同，两者均编译为wi th -O2）。所以你可以看到，即使是适度的输入尺寸，这种优化也可以产生很大的差异。

来源

2016-02-05 03:06:03

我建议使用'<= <'代替'> =>'保持所有成分以相同的方式流动。 – dfeuer

这就是Haskell的迷人之处，它吸引了我。感谢您的解释 – jaggedGoofy

@dfeuer好主意;完成。 –

可以对此Haskell代码进行哪些优化？

回答

相关问题