递归序列会泄漏内存吗？

发布于 2024-07-25 05:13:18 字数 429 浏览 9 评论 0原文

我喜欢如下递归地定义序列：

let rec startFrom x =
    seq {
        yield x;
        yield! startFrom (x + 1)
    }

我不确定在实践中是否应该使用这样的递归序列。 yield! 似乎是尾递归的，但我不是 100% 确定，因为它是从另一个 IEnumerable 内部调用的。从我的角度来看，代码在每次调用时都会创建一个 IEnumerable 实例而不关闭它，这实际上也会使该函数泄漏内存。

这个函数会泄漏内存吗？就此而言，它甚至是“尾递归”吗？

[编辑添加]：我正在与 NProf 一起摸索寻找答案，但我认为获得有关递归序列实现的技术解释会很有帮助就这样。

原文

I like to define sequences recursively as follows:

let rec startFrom x =
    seq {
        yield x;
        yield! startFrom (x + 1)
    }

I'm not sure if recursive sequences like this should be used in practice. The yield! appears to be tail recursive, but I'm not 100% sure since its being called from inside another IEnumerable. From my point of view, the code creates an instance of IEnumerable on each call without closing it, which would actually make this function leak memory as well.

Will this function leak memory? For that matter is it even "tail recursive"?

[Edit to add]: I'm fumbling around with NProf for an answer, but I think it would be helpful to get a technical explanation regarding the implementation of recursive sequences on SO.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一口甜 2024-08-01 05:13:18

我现在正在工作，所以我正在研究比 Beta1 稍新的位，但是在我的机器上处于发布模式，然后使用 .Net Reflector 查看编译后的代码，看来这两个

let rec startFromA x =    
    seq {        
        yield x     
        yield! startFromA (x + 1)    
    }

let startFromB x =    
    let z = ref x
    seq {        
        while true do
            yield !z
            incr z
    }

在编译时生成几乎相同的 MSIL 代码“释放”模式。它们的运行速度与此 C# 代码大致相同：（

public class CSharpExample
{
    public static IEnumerable<int> StartFrom(int x)
    {
        while (true)
        {
            yield return x;
            x++;
        }
    }
}

例如，我在我的盒子上运行了所有三个版本并打印了第一百万个结果，每个版本大约花费了 1.3 秒，+/- 1 秒）。（我没有做任何内存分析；我可能错过了一些重要的东西。）

简而言之，我不会花太多时间思考这样的问题，除非你测量并发现问题。

编辑

我意识到我没有真正回答这个问题......我认为简短的答案是“不，它不会泄漏”。（有一种特殊的意义，即所有“无限”IEnumerables（带有缓存后备存储）“泄漏”（取决于您如何定义“泄漏”），请参阅

避免堆栈溢出（使用 F# 无限序列序列）

有关 IEnumerable（又名“seq”）与 LazyList 的有趣讨论以及消费者如何急切地使用 LazyLists 以“忘记”旧结果以防止某种“泄漏”。）

I'm at work now so I'm looking at slightly newer bits than Beta1, but on my box in Release mode and then looking at the compiled code with .Net Reflector, it appears that these two

let rec startFromA x =    
    seq {        
        yield x     
        yield! startFromA (x + 1)    
    }

let startFromB x =    
    let z = ref x
    seq {        
        while true do
            yield !z
            incr z
    }

generate almost identical MSIL code when compiled in 'Release' mode. And they run at about the same speed as this C# code:

public class CSharpExample
{
    public static IEnumerable<int> StartFrom(int x)
    {
        while (true)
        {
            yield return x;
            x++;
        }
    }
}

(e.g. I ran all three versions on my box and printed the millionth result, and each version took about 1.3s, +/- 1s). (I did not do any memory profiling; it's possible I'm missing something important.)

In short, I would not sweat too much thinking about issues like this unless you measure and see a problem.

EDIT

I realize I didn't really answer the question... I think the short answer is "no, it does not leak". (There is a special sense in which all 'infinite' IEnumerables (with a cached backing store) 'leak' (depending on how you define 'leak'), see

Avoiding stack overflow (with F# infinite sequences of sequences)

for an interesting discussion of IEnumerable (aka 'seq') versus LazyList and how the consumer can eagerly consume LazyLists to 'forget' old results to prevent a certain kind of 'leak'.)

回复收藏 0 原文