Haskell 分析

Question

我正在浏览 LYAH，并一直在研究处理列表时列表理解与映射/过滤器的使用。我已经分析了以下两个函数，并包含了教授的输出。如果我正确地阅读了教授的内容，我会说 FiltB 的运行速度比 FiltA 慢很多(尽管只有千分之一秒)。

这样说是因为 FiltB 必须评估 x^2 两次吗？

FiltA.hs(过滤奇数)

-- 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(列表推导式)

-- 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

Answer 1

是的。在这个特殊情况下，因为 n^2当且仅当 n 才是奇数很奇怪，您可以通过替换 odd (n^2) 将 FiltB 加速到与 FiltA 相同的速度与 odd n .

就像你说的，问题是对于每个元素 n它正在对它进行平方，检查这是否是奇数，如果是，则对 n 进行平方并将其添加到列表中。

更一般地说，区别在于，在列表理解中，过滤发生在映射之前，而对于映射和过滤器，您可以选择顺序。因此，如果您实际想要根据映射后列表中的值进行过滤，那么使用映射和过滤器可能是更好的选择。您仍然可以执行类似的操作，根据平方值是否为奇数进行过滤:

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

但这变得很难阅读。映射和过滤或显式过滤列表理解(即 filter odd [ n^2 | n <- [1..] ] )是更好的选择。