代码之家 › 专栏 › 技术社区 › Johannes Rudolph

屈服!运营商-实施和可能的C等价物

enumerators yield ienumerable f# c#

Johannes Rudolph · 技术社区 · 15 年前

我现在正在学习F,我真的很喜欢 yield! (屈服点)运算符。不仅因为它的名字,当然也因为它的作用。

这个 屈服! 运算符基本上允许从序列表达式生成序列的所有元素。这对于组成枚举器很有用。由于我经常遇到大型、复杂的枚举器,所以我对策略感兴趣,我们可以使用这些策略将它们分解,并从更简单的枚举器组合起来。

不幸的是, 屈服! 操作员在C中不可用。据我所知,它的作用就像 foreach (var x in source) yield x; 但是我正在读的书( Petricek's Real World F# - Manning )表明它有更好的性能…

那么F编译器在这里究竟做了什么?(是的,我也可以用反射镜来观察它,但我想对这个机制有一个更详细的描述)。

为了在C中实现类似的结构,我探索了多种方法,但没有一种方法比 屈服! 操作员和我也不确定它们的复杂性。如果我的Bigo号码正确,有人能提供输入吗?

将枚举器分解为多个私有枚举器,然后从公共枚举器生成每个元素:
```
foreach (var x in part1()) yield x
foreach (var x in part2()) yield x
```
这将有效地在每个元素上产生“双倍收益”。那是O(2N)吗?(或者更糟?)无论如何,使用这种方法会阻止我使用 yield break; 从我的任何一个子部分。
将枚举器分解为多个私有枚举器,然后从公共枚举器中合并所有私有枚举器:
```
return part1().Concat(part2())
```
我认为这与上述解决方案没有什么不同,因为 Concat() 是按照我上面概述的方式实现的。

还有其他选择吗?

3 回复 | 直到 15 年前

kvb 15 年前

关于编译器如何翻译 yield! 操作, the paper Thomas Levesque在其答案中引用了第4.3节中的一种实现技术(尤其是,图7-9中的示例说明了一般策略)。我认为在C中的迭代器块内没有任何好的方法可以做到这一点——正如我理解您提出的解决方案,当递归使用时,它们都可能导致二次行为。您可以始终手动创建 NestedEnumerable<T> 子类以实现性能优势,但与使用普通迭代器块相比,这将非常糟糕。

Thomas Levesque 15 年前

在当前版本的C中,我认为除了 foreach... yield return 和 Concat . 我同意拥有 yield! 运算符在C中,它将使某些构造更加优雅,但我怀疑此功能是否会使其成为“必须拥有”列表,因为没有它,我们很容易做到。

你可能对这个感兴趣 MS research paper ,它引入了一个新的 yield foreach 构建:

IEnumerable<XmlNode> Traverse(XmlNode n)
{
    yield return n;
    foreach (XmlNode c in n.ChildNodes)
        yield foreach Traverse(c);
}

关于复杂性的问题:在这两种情况下 o(n) . O(2n) 不使用,因为它表示与 o(n) (线性)我不认为你能比现在的C功能做得更好…

stakx - no longer contributing Saravana Kumar 15 年前

没有直接对应的 yield! 在C语言中。你现在被一个 foreach 和 yield return .

然而,IIRC、LINQ提供了类似的服务,即 SelectMany 查询运算符,转换为多个C from .. in .. 条款。

(我希望我不会混淆两个不同的概念,但是IIRC,两者都是 屈服! 和 选择许多 基本上是“扁平化”投影;即对象的层次结构被“扁平化”成一个列表。)