在使用 Haskell 中的 iterate
函数编写函数时,我发现使用显式递归版本的函数速度明显更快——尽管我认为在 Haskell 中应该避免使用显式递归。
同样地,我期望 GHC 能够适当地内联/优化列表组合器,使得生成的机器代码的性能与显式递归至少相似。
这里是另一个例子,它也展示了我观察到的减速现象。
steps m n
及其变种 steps'
计算达到 1 所需的 Collatz 步骤数,最多尝试 m
次。
steps
使用显式递归,而 steps'
使用列表函数。
import Data.List (elemIndex)
import Control.Exception (evaluate)
import Control.DeepSeq (rnf)
collatz :: Int -> Int
collatz n
| even n = n `quot` 2
| otherwise = 3 * n + 1
steps :: Int -> Int -> Maybe Int
steps m = go 0
where go k n
| n == 1 = Just k
| k == m = Nothing
| otherwise = go (k+1) (collatz n)
steps' :: Int -> Int -> Maybe Int
steps' m = elemIndex 1 . take m . iterate collatz
main :: IO ()
main = evaluate $ rnf $ map (steps 800) $ [1..10^7]
我通过评估所有值直到10^7
,每次在800
步后放弃来测试这些内容。 在我的机器上(使用ghc -O2
编译),明确的递归仅花费不到4秒钟(3.899s
),但列表组合器需要约5倍的时间(19.922s
)。
为什么在这种情况下明确的递归要好得多,是否有一种方式可以在不使用明确递归的情况下保持性能?
iterate
版本将会生成、匹配和收集数十亿个元素,这可以很好地解释差异。 - that other guyfindIndices
(elemIndex
是根据其书写的)编写成参与融合的形式-它肯定可以实现为一种 zip、filter 然后 map 的形式,这些都可以被融合。 - B. Mehtafoldr
和build
的。 - Carl