Haskell性能分析

Question

我正在学习LYAH，正在研究处理列表时使用列表推导与map/filter的区别。我已经对以下两个函数进行了分析，并包含了prof输出结果。如果我正确理解prof的话，我会说FiltB比FiltA运行得慢很多（虽然只是以毫秒为单位）。

我可以说FiltB需要计算两次x^2，这样才能说明吗？

FiltA.hs (filter odd)

-- FiltA.hs

module Main
    where

main = do
    let x = sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
    print x

    Sat Jul 26 18:26 2014 Time and Allocation Profiling Report  (Final)

       Filta.exe +RTS -p -RTS

    total time  =        0.00 secs   (0 ticks @ 1000 us, 1 processor)
    total alloc =      92,752 bytes  (excludes profiling overheads)

COST CENTRE MODULE           %time %alloc

main        Main               0.0   10.1
main.x      Main               0.0   53.0
CAF         GHC.IO.Handle.FD   0.0   36.3


                                                         individual     inherited
COST CENTRE MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                        37           0    0.0    0.2     0.0  100.0
 CAF        GHC.IO.Encoding.CodePage    61           0    0.0    0.1     0.0    0.1
 CAF        GHC.IO.Encoding             58           0    0.0    0.1     0.0    0.1
 CAF        GHC.IO.Handle.FD            52           0    0.0   36.3     0.0   36.3
 CAF        Main                        44           0    0.0    0.2     0.0   63.3
  main      Main                        74           1    0.0   10.1     0.0   63.1
   main.x   Main                        75           1    0.0   53.0     0.0   53.0

FiltB (list comprehensions)

-- FiltB.hs

module Main
    where

main = do
    let x = sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)])
    print x

    Sat Jul 26 18:30 2014 Time and Allocation Profiling Report  (Final)

       FiltB.exe +RTS -p -RTS

    total time  =        0.00 secs   (2 ticks @ 1000 us, 1 processor)
    total alloc =     107,236 bytes  (excludes profiling overheads)

COST CENTRE MODULE           %time %alloc

main        Main              50.0    8.8
CAF         Main              50.0    0.1
main.x      Main               0.0   59.4
CAF         GHC.IO.Handle.FD   0.0   31.4


                                                         individual     inherited
COST CENTRE MODULE                     no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                        37           0    0.0    0.2   100.0  100.0
 CAF        GHC.IO.Encoding.CodePage    61           0    0.0    0.1     0.0    0.1
 CAF        GHC.IO.Encoding             58           0    0.0    0.0     0.0    0.0
 CAF        GHC.IO.Handle.FD            52           0    0.0   31.4     0.0   31.4
 CAF        Main                        44           0   50.0    0.1   100.0   68.3
  main      Main                        74           1   50.0    8.8    50.0   68.1
   main.x   Main                        75           1    0.0   59.4     0.0   59.4

- Dave0504

Answer 1

是的。在这个特定的情况下，由于只有当n为奇数时n^2才为奇数，因此您可以通过将odd (n^2)替换为odd n来加速FiltB，使其与FiltA的速度相同。

正如您所说，问题在于对于每个元素n，它会将其平方，检查是否为奇数，如果是，则将n的平方加到列表中。

然而，更一般地说，区别在于，在列表推导中，过滤发生在映射之前，而使用map和filter时，您可以选择顺序。因此，如果您实际上想要根据映射后列表中的值进行过滤，则使用map和filter可能是更好的选择。您仍然可以像这样根据平方值是否为奇数进行过滤：

sum (takeWhile (<10000) [ x | x <- [ n^2 | n <- [1..] ], odd x ])

但是这样阅读起来很困难。使用map和filter或显式地在列表推导式中过滤（即filter odd [ n^2 | n <- [1..] ]）是更好的选择。

- djfoote

---

谢谢，我很确定这是正确的。我之所以要求澄清是因为我仍在理解Haskell的惰性求值，并不确定GHC是否会进行某种优化，使其只被评估一次。 - Dave0504

如果你在推导式中使用 let，那么阅读起来就很容易：[x | n <- [1..], let x = n^2, odd x]。顺便说一句，既然这是关于性能的（@Dave0504），你可以只留下列表中的偶数部分，从而完全删除 odd 测试：takeWhile (<10000) [x^2 | x <- [1,3..]] 或者 [x ^ 2| x <- [1,3..99]。 - Zeta