Haskell：代码的两个版本之间的速度差

Question

我已经开始通过尝试解决一些小问题来潜入Haskell。

我于“标准哈斯克尔友好”解决方案，我“极丑和Haskell不友好”版本之间有很大的性能差异（〜100-200x）绊倒了。

我敢肯定，对于同性恋者来说，这种表现上的差异有一个很好的理由，我错过了，可以教我关于这个话题。

问题：查找数字串

内的最高5位数字都用在解决相同概念：产生所有5位数字，并找出最大。

优雅和快速的代码

digit5 :: String -> Int 
digit5 = maximum . map (read . take 5) . init . tails 

长得丑，而且速度很慢的代码（一旦字符串大小大）

digit5' :: String -> String -> String 
-- xs - input string 
-- maxim - current maximal value 
digit5' xs maxim 
    | (length xs) < 5 = maxim 
    | y > maxim = digit5' (drop 1 xs) y -- use new detected maximum value 
    | otherwise = digit5' (drop 1 xs) maxim 
    where y = take 5 xs 

digit5 :: String -> Int 
digit5 xs 
-- return the original string if the input size is smaller than 6 
    | length (xs) < 6 = read xs 
    | otherwise = read $ digit5' xs "00000" 

对于小的投入，我得到大致相同的执行时间，对于大的投入我开始看到很大的差异（对于44550个元素的输入）：

Computation time for ugly version: 2.047 sec 
Computation time for nice version: 0.062 sec 

我的肤浅对此的了解是，快速代码是使用预先提供的高阶功能。对于较慢的版本递归使用，但我认为咬尾应该是可能的。但在天真的水平，对我来说似乎都做同样的事情。

而较慢的功能确实比较对字符串，而不是将它们转换为数字，我也试着转换字符串整数，但没有任何大的改善

我试着使用GHC不带任何标志，并与编译下面的命令：

ghc 
ghc -O2 
ghc -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no- 
recomp 
stack runhaskell 
ghc -O3 

对于重复性我加入的链接代码contaning也测试向量的缘故：https://pastebin.com/kuS5iKgd

Answer 1

与“慢”的版本问题是THI s的线路：

| length xs < 5 = maxim 

此计算的xs长度，并且因为Haskell的列表是单链表，这操作需要整个列表的完整遍历，其为O（n）。它发生在每一次迭代。并且有N次迭代。这使得整个过程O（n^2）。

另一方面，“快速”代码只是线性的，在大型输入上显示得淋漓尽致。

如果只需更换与此问题的行：

| null xs = maxim 

就会使整个事情只是线性的，这将是一样快的“优雅”的解决方案。当然，这会导致额外的5次迭代，但是这种损失通过降低整体复杂性而得到补偿。

，或者，可以使“优雅”的解决方案只是通过过滤掉5个字符或短尾巴一样慢：

digit5 = maximum . map (read . take 5) . filter ((>= 5) . length) . tails