在列表上多次映射时间复杂度

Question

例如，如果我在同一个列表上应用 map（只是一个示例，也可以是过滤器或其他东西）3 次，Haskell 会通过列表 3 次还是仅一次？ ghci 中运行的示例：

map (+1) $ map (*2) $ map (^2) [1..100]

我想知道复杂度是否为 3n，其中 n 是列表的大小，就像在命令式语言中一样，或者 Haskell 中的惰性是否仅通过将其优化为 1n遍历列表一次，同时对每个元素执行三个操作。所以 1 它会

提高到 2
乘以 2
加 1

然后继续下一个元素，而不是先遍历整个列表，同时将每个元素都提高到 2，然后再次遍历列表并将每个元素乘以，然后第三次遍历列表将每个元素加一。

那是哪个呢？ Haskell 是遍历列表 3 次还是仅一次？

Answer 1

您可以在 ghci 下做一个简单的检查：打开统计模式，然后尝试运行两种方式的表达式，但要有一个显着的大小。 对列表求和并打印其总和以强制进行全面评估。

像这样：

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :set +s
 λ> 
 λ> n = 1000000
 (0.00 secs, 24,296 bytes)
 λ> 
 λ> sum ( map (+1) $ map (*2) $ map (^2) [1..n] )
 666667666668000000
 (1.36 secs, 865,692,136 bytes)
 λ> 
 λ> sum ( map  ((+1) . (*2) . (^2))  [1..n] )
 666667666668000000
 (1.03 secs, 753,692,056 bytes)
 λ>

所以使用优化的表达式有一些性能提升，但远低于 3 倍。

附录：

当然，为了完整起见，我们还要检查一下用-O2编译的GHC代码，在命令行中使用this syntax得到统计数据：

$ myHaskellExe +RTS -s -RTS
...

性能比 ghci 好得多，所以让我们花 1 亿而不是一百万的时间。

源代码#1：

sumx1 :: Integer -> Integer
sumx1 n = sum ( map (+1) $ map (*2) $ map (^2) [1..n] )

main:: IO ()
main = do
    let  k   = 100*1000*1000
         res = sumx1 k
    putStrLn $ "k=" ++ (show k) ++ "  res1=" ++ (show res)

结果 #1:

k=100000000  res1=666666676666666800000000
  12,679,831,656 bytes allocated in the heap
...
  GC      time    0.029s  (  0.028s elapsed)
  Total   time    5.457s  (  5.467s elapsed)

源代码#2：

sumx2 :: Integer -> Integer
sumx2 n = sum ( map  ((+1) . (*2) . (^2))  [1..n] )

main:: IO ()
main = do
    let  k   = 100*1000*1000
         res = sumx2 k
    putStrLn $ "k=" ++ (show k) ++ "  res2=" ++ (show res)

结果#2：

k=100000000  res2=666666676666666800000000
  12,679,831,656 bytes allocated in the heap
...
  GC      time    0.030s  (  0.029s elapsed)
  Total   time    5.500s  (  5.512s elapsed)

因此，对于 GHC，两个表达式之间的性能差异是微不足道的。高级优化器可能在工作。

在列表上多次映射时间复杂度

Time complexity mapping multiple times over a list

algorithm

performance

haskell

functional-programming

lazy-evaluation

附录：