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

Question

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

我偶然发现 "standard haskell-friendly" 解决方案和我的 "very-ugly and haskell-unfriendly" 之间存在巨大的性能差异 (~100-200x) 版本。

我敢肯定，对于其他 haskellers 来说，这种性能差异有一个很好的理由，我想念这个理由，并且可以就这个话题对我进行教育。

问题：找出数字字符串中最大的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

为了可重复性，我在代码中添加了一个 link，其中还包含测试向量：https://pastebin.com/kuS5iKgd

Answer 1

您的 "slow" 版本的问题是这一行：

| length xs < 5 = maxim

这里计算的是xs的长度，因为Haskell列表是单链表，所以这个操作需要遍历整个列表，复杂度为O(n)。它发生在每次迭代中。并且有N次迭代。这使得整个过程 O(n^2).

另一方面，"fast" 代码只是线性的，在大量输入时表现得非常生动。

如果你只是用这个替换有问题的行：

| null xs = maxim

它将使整个事情变得线性，并且与 "elegant" 解决方案一样快。当然，这将导致额外的 5 次迭代，但通过降低整体复杂性可以弥补损失。

或者，您可以通过过滤掉 5 个字符或更短的尾部来使 "elegant" 解决方案同样慢：

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

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

Haskell: speed difference between two versions of code

optimization

profiling

haskell