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

Question

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

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

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

1. 将其提高到2
2. 乘以 2
3. 添加 1

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

那么是哪一个呢？Haskell 是浏览该列表 3 次还是只浏览一次？

Answer 1

您可以在设置统计模式下进行简单的检查ghci，并尝试以两种方式运行表达式，但使用较大的大小。对列表求和并打印其总和以强制进行全面评估。

\n

像这样：

\n

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

\n

因此，使用优化的表达式会带来一些性能提升，但远小于 3 倍。

\n

附录：

\n

当然，为了完整起见，我们还必须检查使用-O2 编译的 GHC 代码，在命令行上使用以下语法来获取统计信息：

\n

$ myHaskellExe +RTS -s -RTS\n...\n

\n

性能比使用 好得多ghci，所以让我们考虑 1 亿而不是仅仅 100 万。

\n

源代码#1：

\n

sumx1 :: Integer -> Integer\nsumx1 n = sum ( map (+1) $ map (*2) $ map (^2) [1..n] )\n\nmain:: IO ()\nmain = do\n    let  k   = 100*1000*1000\n         res = sumx1 k\n    putStrLn $ "k=" ++ (show k) ++ "  res1=" ++ (show res)\n

\n

结果#1：

\n

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

\n

源代码#2：

\n

sumx2 :: Integer -> Integer\nsumx2 n = sum ( map  ((+1) . (*2) . (^2))  [1..n] )\n\nmain:: IO ()\nmain = do\n    let  k   = 100*1000*1000\n         res = sumx2 k\n    putStrLn $ "k=" ++ (show k) ++ "  res2=" ++ (show res)\n

\n

结果#2：

\n

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

\n

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

\n