performance - 为什么严格长度函数的执行速度明显更快？

Question

我玩弄定义以更好地理解评估模型，并为列表的长度写了两个。

天真的定义:

len :: [a] -> Int
len [] = 0
len (_:xs) = 1 + len xs

严格(和尾递归)定义:

slen :: [a] -> Int -> Int
slen [] n = n
slen (_:xs) !n = slen xs (n+1)

len [1..10000000]大约需要 5-6 秒来执行。 slen [1..10000000] 0执行大约需要 3-4 秒。

我很好奇为什么。在我检查性能之前，我确信它们的性能大致相同，因为 len最多只能再评估一个thunk。出于演示目的:

len [a,b,c,d]
= 1 + len [b,c,d]
= 1 + 1 + len [c,d]
= 1 + 1 + 1 + len [d]
= 1 + 1 + 1 + 1 + len []
= 1 + 1 + 1 + 1 + 0
= 4

和

slen [a,b,c,d] 0
= slen [b,c,d] 1
= slen [c,d]   2
= slen [d]     3
= slen []      4
= 4

是什么让 slen明显更快？

附言我还写了一个尾递归惰性函数(就像 slen 但惰性)作为尝试关闭原因 - 也许是因为它是尾递归 - 但它的执行与天真的定义大致相同.

Answer 1

len的最后一步不是 O(1)。将 n 个数字相加是 O(n)。 len还使用 O(n) 内存，而 slen使用 O(1) 内存。

它使用 O(n) 内存的原因是每个 thunk 都会占用一些内存。所以当你有这样的事情时:

1 + 1 + 1 + 1 + len []

有五个未评估的 thunk(包括 len [] )

在 GHCi 中，我们可以使用 :sprint 更轻松地检查这种 thunk 行为。命令。 :sprint命令打印给定值而不强制评估任何 thunk(您可以从 :help 了解更多信息)。我将使用 conses ( (:))，因为我们可以更轻松地一次评估每个 thunk，但原理是相同的。

λ> let ys = map id $ 1 : 2 : 3 : [] :: [Int] -- map id prevents GHCi from being too eager here
λ> :sprint ys
ys = _
λ> take 1 ys
[1]
λ> :sprint ys
ys = 1 : _
λ> take 2 ys
[1,2]
λ> :sprint ys
ys = 1 : 2 : _
λ> take 3 ys
[1,2,3]
λ> :sprint ys
ys = 1 : 2 : 3 : _
λ> take 4 ys
[1,2,3]
λ> :sprint ys
ys = [1,2,3]

未评估的 thunk 由 _ 表示您可以在原始 ys 中看到有 4 thunk 相互嵌套，列表的每一部分都有一个(包括 [] )。

据我所知，在 Int 中没有一个好的方法可以看到这个。因为它的评估更多的是全有或全无，但它仍然以同样的方式构建了一个嵌套的 thunk。如果您能看到它，它的评估将如下所示:

len [a,b,c,d]
= 1 + len [b,c,d]
= 1 + 1 + len [c,d]
= 1 + 1 + 1 + len [d]
= 1 + 1 + 1 + 1 + len []
= 1 + 1 + 1 + 1 + 0
= 1 + 1 + 1 + 1       -- Here it stops building the thunks and starts evaluating them
= 1 + 1 + 2
= 1 + 3
= 4