F＃序列的实现问题 [英] An implementation problem of F# Seq
问题描述
我挖到F＃源$ C $ C最近。
I am digging into F# source code recently.
在Seq.fs：
// Binding.
//
// We use a type defintion to apply a local dynamic optimization.
// We automatically right-associate binding, i.e. push the continuations to the right.
// That is, bindG (bindG G1 cont1) cont2 --> bindG G1 (cont1 o cont2)
// This makes constructs such as the following linear rather than quadratic:
//
// let rec rwalk n = { if n > 0 then
// yield! rwalk (n-1)
// yield n }
看了上述code后，我测试了两款code：
After seeing the above code, I tested two code:
let rec rwalk n = seq { if n > 0 then
yield n
yield! rwalk (n-1)
}
和
let rec rwalk n = seq { if n > 0 then
yield! rwalk (n-1)
yield n
}
我找到的第一个是非常快的，而第二个是很慢的。如果n = 10000，它的成本3秒我的机器上生成该序列，从而二次时间。
I found the first one is very fast, while the second is very slow. If n = 10000, it costs 3 seconds on my machine to generate this sequence, thus quadratic time.
在二次时间是合理的，因为例如。
The quadratic time is reasonable, as e.g.
序列{屈服！ {1; 2; ...;正1};产量N} 转化为
Seq.append {1; 2; ...; n-1} {n}
此附加操作应采取线性时间，我猜。而在第一个code，追加操作是这样的：序列{产量形成;产量！ {N-1; N-2; ...; 1}} ，它的价格一定的时间。
This append operation should take linear time, I guess. While in the first code, the append operation is like this: seq { yield n; yield! {n-1; n-2; ...; 1} }, which costs constant time.
该在code评论说，这是线性（也许这个线性不是线性的时间）。也许这线性涉及使用定制实施序列，而不是Moand / F＃计算EX pression（中提到的F＃规范，但该规范没有提到的原因这样做的...）。
The the comments in code say that it is linear (maybe this linear is not linear time). Maybe this linear relates to using customized implementation for sequence rather than Moand/F# computation expression (as mentioned in F# specification, however the specification does not mention the reason for doing so...).
任何人都可以澄清模糊性在这里？非常感谢！
Could anyone clarify the fuzziness here? Thanks a lot!
（ps的，因为这是一个语言的设计和优化的问题，我还附上哈斯克尔标签，看看那里的人有见解。）
(p.s. because this is a language design and optimization problem, I also attached Haskell tag to see if people there have insights. )
推荐答案
在屈服！出现在无尾调用的位置它essentiall意味着同样的事情：
When yield! appears in a non-tail-call position, it essentiall means the same thing as:
for v in <expr> do yield v
这个问题（为什么是二次的原因）是，递归调用，这将创建一个链迭代器嵌套为循环。您需要遍历由＆LT产生的整个序列; EXPR＆GT; 为每一个元素，因此，如果迭代是线性的，你得到一个二次的时间（因为线性迭代发生对于每一个元素）。
The problem with this (and the reason why is that quadratic) is that for recursive calls, this creates a chain of iterators with nested for loops. You need to iterate over the whole sequence generated by <expr> for every single element, so if the iteration is linear, you get a quadratic time (because the linear iteration happens for every element).
比方说， rwalk 函数生成 [10; 2; 3; 7] 。在第一次迭代中，递归生成的序列有4个元素，所以你会遍历4元素，并添加1.在递归调用，你会遍历3个元素，并添加1等。用图，可以怎么看这是二次：
Let's say the rwalk function generates [ 9; 2; 3; 7 ]. In the first iteration, the recursively generated sequence has 4 elements, so you'd iterate over 4 elements and add 1. In the recursive call, you'd iterate over 3 elements and add 1, etc.. Using a diagram, you can see how that's quadratic:
x
x x
x x x
x x x x
此外，每一个递归调用创建对象的新实例（的IEnumerator ），所以也有一些内存的成本（虽然只是线性）。
Also, each of the recursive calls creates a new instance of object (IEnumerator) so there is also some memory cost (although only linear).
在尾调用的位置，F＃编译器/ librar做了优化。据取代当前的的IEnumerable 由递归调用返回，所以它并不需要遍历overe它生成的所有元素之一 - 它只是返回（和这也消除了存储成本）。
In a tail-call position, the F# compiler/librar does an optimization. It "replaces" the current IEnumerable with the one returned by the recursive call, so it doesn't need to iterate overe it to generate all elements - it is simply returned (and this also removes the memory cost).
相关。同样的问题在C＃lanaugage的设计进行了讨论，并有一个的这件事有趣的论文（他们对产生的foreach ）。
Related. The same problem has been discussed in the C# lanaugage design and there is an interesting paper about it (their name for yield! is yield foreach).
这篇关于F＃序列的实现问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
