为什么递归比使用此随机数计数器的过滤器慢

Question

我正在编写一个函数，该函数生成一百万个 1 或 0 的随机数，然后计算生成了多少个 0。

import System.Random
import Control.Monad
countZeros :: Int -> IO Int
countZeros n = (length . filter (==0)) <$> (replicateM n $ randomRIO (0,1 :: Int))
countZeros' :: Int -> IO Int
countZeros' n = go n 0 
where
go :: Int -> Int -> IO Int
go x acc = do
r  <- randomRIO (0,1 :: Int)
case x of
0 -> pure acc
_ -> let acc' = if r == 0 then succ acc else acc
in  go (pred x) acc'

当我以 1000000 的输入运行函数时

>λ= countZeros 1000000
499716
(0.93 secs, 789,015,080 bytes)
>λ= countZeros' 1000000
500442
(2.02 secs, 1,109,569,560 bytes)

我不明白为什么素数函数比另一个慢两倍。我假设他们本质上是在幕后做同样的事情。

我正在使用GHCi。

我错过了什么？

Answer 1

使用爆炸模式，并使用-O2进行适当的编译，"prime"函数更快：

{-# LANGUAGE BangPatterns #-}
module Main where
import System.Random
import Control.Monad
import System.Environment
countZeros :: Int -> IO Int
countZeros n = (length . filter (==0)) <$> (replicateM n $ randomRIO (0,1 :: Int))
countZeros' :: Int -> IO Int
countZeros' n = go n 0 
where
go :: Int -> Int -> IO Int
go !x !acc = do
r  <- randomRIO (0,1 :: Int)
case x of
0 -> pure acc
_ -> let acc' = if r == 0 then succ acc else acc
in  go (pred x) acc'
main :: IO ()
main = do
[what] <- getArgs
let n = 1000 * 1000 * 10
fun = case what of
"1" -> countZeros
"2" -> countZeros'
_   -> error "arg not a number"
putStrLn "----"
print =<< fun n
putStrLn "----"

编译方式

$ stack ghc -- RandomPerf.hs -O2 -Wall
$ stack ghc -- --version
The Glorious Glasgow Haskell Compilation System, version 8.6.3

测试：

$ time ./RandomPerf.exe 1
----
4999482
----
real    0m3.329s
user    0m0.000s
sys     0m0.031s
$ time ./RandomPerf.exe 2
----
5001089
----
real    0m2.338s
user    0m0.000s
sys     0m0.046s

重复测试会给出可比较的结果，所以这不是侥幸。

结果：countZeros'功能明显更快。

使用标准并运行适当的基准测试将作为练习。

您可能使用 GHCi 来评估性能，这会阻止优化器完成其工作。GHCi 牺牲了适当的优化，以更快地加载文件，并以交互方式更易于使用。

Answer 2

这些实际上以不同的方式工作，在一个重要的层面上。而且两者都很慢。

使用replicateM的版本不好，因为replicateMinIO无法流式传输其结果。在filter和length开始操作之前，将立即构建整个列表。它更快的原因是length的累加器很严格，所以它不会像你的其他版本那样产生一个巨大的嵌套思维链。这对性能来说更糟糕。

递归版本不使用严格的累加器。这意味着它返回的值是一个巨大的嵌套链，通过列表索引保留所有生成的条目和一堆间接调用。这比过滤器版本使用的内存更多，因为它保留了一堆闭包以及所有值。但即使修复了，它仍然会很慢。使用!!只会破坏性能。当一个简单的 if 可以更有效地完成相同的工作时，它是递归的。