我最近正在研究 F# 源代码。
在 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 }
看到上面的代码后,我测试了两个代码:
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 秒,因此是二次时间。
二次时间是合理的,例如
seq { yield! {1; 2; ...; n-1}; yield n }
翻译成Seq.append {1; 2; ...; n-1} {n}
我猜这个附加操作应该需要线性时间。而在第一个代码中,追加操作是这样的:
seq { yield n; yield! {n-1; n-2; ...; 1} }
,这花费恒定的时间。代码中的注释说它是
linear
(也许这个线性不是线性时间)。也许这个 linear
涉及使用序列的自定义实现而不是 Moand/F# 计算表达式(如 F# 规范中所述,但规范没有提及这样做的原因......)。谁能澄清这里的模糊性?非常感谢!
(p.s.因为这是一个语言设计和优化问题,所以我还附上了Haskell标签,看看那里的人有没有见解。)
最佳答案
当yield!
出现在 非尾随仓 ,它本质上与以下内容相同:
for v in <expr> do yield v
这个问题(以及为什么是二次方的原因)是对于递归调用,这会创建一个带有嵌套
for
的迭代器链。循环。您需要遍历 <expr>
生成的整个序列对于每个元素,所以如果迭代是线性的,你会得到一个二次时间(因为线性迭代发生在每个元素上)。假设
rwalk
函数生成[ 9; 2; 3; 7 ]
.在第一次迭代中,递归生成的序列有 4 个元素,因此您将迭代 4 个元素并添加 1。在递归调用中,您将迭代 3 个元素并添加 1,等等。使用图表,您可以看看它是如何二次的:x
x x
x x x
x x x x
此外,每个递归调用都会创建一个新的对象实例 (
IEnumerator
),因此也会产生一些内存成本(尽管只是线性的)。在 尾随位置 ,F# 编译器/库进行优化。它“替换”了当前的
IEnumerable
与递归调用返回的那个,所以它不需要迭代它来生成所有元素 - 它只是被返回(这也消除了内存成本)。有关的。 在 C# 语言设计中讨论了相同的问题,并且有一个 interesting paper about it (他们的
yield!
的名称是 yield foreach
)。
关于.net - F# Seq 的一个实现问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4232130/