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

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

天真的定义:

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明显更快？

P.S.我还编写了一个尾递归的惰性函数(就像slen一样，但是很懒)，以尝试关闭原因-也许是因为它是尾递归的-但是它的执行效果与朴素的定义相同。

最佳答案

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

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

1 + 1 + 1 + 1 + len []

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

在GHCi中，我们可以使用:sprint命令更轻松地检查这种重击行为。 :sprint命令将打印给定值，而不会强制评估任何重击(您可以从: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

关于performance - 为什么严格长度函数的执行速度明显更快？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27392665/