Haskell foldl' 性能不佳(++) [英] Haskell foldl' poor performance with (++)

问题描述

我有这个代码:

import Data.List

newList_bad  lst = foldl' (acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (acc x -> x*2 : acc) [] lst

这些函数返回每个元素乘以 2 的列表:

These functions return lists with each element multiplied by 2:

*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]

在 ghci 中:

*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)

为什么 newList_bad 函数的运行速度比 newList_good 慢 200 倍?我知道这不是该任务的好解决方案.但是为什么这个无辜的代码运行得这么慢?

Why newList_bad function works 200 times slower than newList_good? I understand that it's not a good solution for that task. But why this innocent code works so slow?

这个4767099960 字节"是什么??对于这么简单的操作，Haskell 使用了 4 GiB??

What is this "4767099960 bytes"?? For that simple an operation Haskell used 4 GiB??

编译后:

C:1>ghc -O --make test.hs
C:1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s
225015000
Time for sum (newList_good [1..15000]) is 0.0025005s

推荐答案

经典列表行为.

回忆:

(:)  -- O(1) complexity
(++) -- O(n) complexity

所以你正在创建一个 O(n^2) 算法，而不是一个 O(n) 算法.

So you are creating an O(n^2) algo, instead of an O(n) one.

对于这种以增量方式附加到列表的常见情况，请尝试使用 dlist，或者在最后反转.

For this common case of appending to lists incrementally, try using a dlist, or just reverse at the end.

这篇关于Haskell foldl' 性能不佳(++)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！