懒惰评估 - 空间泄漏 [英] Lazy Evaluation - Space Leak

问题描述

在功能上与Haskell思考提供以下代码来计算 Float 列表的平均值。

 意思是:: [Float]  - > Float 
 mean [] = 0 
 mean xs = sum xs / fromIntegral（length xs）
  

Richard Bird评论：

现在我们准备好了解什么是错误的意思：它有空间泄漏。评估意味着[1..1000] 会导致列表在求和之后展开并保留在内存中，因为有第二个指针指向它，即计算其长度。

如果我正确理解这段文字，他会说，如果没有指向 xs ，那么 xs 内存可以在计算总和之后被释放 / code>？

我的困惑是 - 如果 xs 已经在内存中， length 函数简单地使用已经被占用的内存吗？

我不明白空间泄漏在这里。

解决方案

sum 函数不需要保留记忆中的整个列表;它可以一次查看一个元素，然后在它移动到下一个元素时将其忽略。

因为Haskell默认情况下是懒惰的评估，所以如果你有一个函数可以创建一个列表 sum 可能会消耗它，而不会将整个列表存储在内存中（每次由生成函数生成一个新元素时，它将被 sum 然后释放）。

完全相同的事情发生在长度。另一方面，平均值函数将列表提供给 sum code>和长度。因此，在评估 sum 时，我们需要将列表保留在内存中，以便稍后可以通过 length 处理。

[更新]要清楚了，这个清单最终会被垃圾收集。问题在于它比需要的时间更长。在这种简单的情况下，这不是一个问题，但是在更复杂的函数中，对无限流进行操作时，这很可能导致内存泄漏。

Thinking Functionally with Haskell provides the following code for calculating the mean of a list of Float's.

mean :: [Float] -> Float
mean [] = 0
mean xs = sum xs / fromIntegral (length xs)

Prof. Richard Bird comments:

Now we are ready to see what is really wrong with mean: it has a space leak. Evaluating mean [1..1000] will cause the list to be expanded and retained in memory after summing because there is a second pointer to it, namely in the computation of its length.

If I understand this text correctly, he's saying that, if there was no pointer to xs in the length computation, then the xs memory could've been freed after calculating the sum?

My confusion is - if the xs is already in memory, isn't the length function simply going to use the same memory that's already being taken up?

I don't understand the space leak here.

解决方案

The sum function does not need to keep the entire list in memory; it can look at an element at a time then forget it as it moves to the next element.

Because Haskell has lazy evaluation by default, if you have a function that creates a list, sum could consume it without the whole list ever being in memory (each time a new element is generated by the producing function, it would be consumed by sum then released).

The exact same thing happens with length.

On the other hand, the mean function feeds the list to both sum and length. So during the evaluation of sum, we need to keep the list in memory so it can be processed by length later.

[Update] to be clear, the list will be garbage collected eventually. The problem is that it stays longer than needed. In such a simple case it is not a problem, but in more complex functions that operate on infinite streams, this would most likely cause a memory leak.

这篇关于懒惰评估 - 空间泄漏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！