（++）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的列表：

  *主> 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秒，4767099960字节）
 * Main> sum $ newList_good [1..15000] 
 225015000 
（0.03秒，3190716字节）
  

为什么 newList_bad 函数的工作速度比 newList_good 慢200倍？我明白这不是一个好的解决方案。但为什么这个无辜的代码工作如此缓慢？

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

编译后：

  C：\ 1> ghc -O  - 生成test.hs 
 C：\ 1> test.exe 
 225015000 
总计时间（newList_bad [1..15000 ]）为4.445889s 
 225015000 
总计时间（newList_good [1..15000]）为0.0025005s 
  

解决方案

经典列表行为。

回想一下：
$ b $ （1）复杂性
（++） - O（n）复杂性
/ pre>



所以你要创建一个O（n ^ 2）算法，而不是O（n）。\\ b
$ b

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

I have this code:

import Data.List

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

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]

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

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?

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

After compilation:

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

解决方案

Classic list behavior.

Recall:

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

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

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

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