问题描述
我挖到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#序列的实现问题的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!