本文是《深入理解C#(第2版)》网站上作者的文章

原文地址:http://www.csharpindepth.com/Articles/Chapter11/StreamingAndIterators.aspx

简介

LINQ to Objects是基于迭代器的。后者一直是.NET的一部分,并且是foreach语句的基础,但对于LINQ to Objects来说,它们要比以往更加重要。本文将探讨什么是迭代器、如何在C# 2(或3)中实现迭代器,以及LINQ to Objects的基础内容。本文不是LINQ to Objects的完整教程,只提供了核心构建块的背景知识(当然还包括LINQ本身的一小部分内容)。

什么是迭代器?

迭代器模式是很常用的设计模式。在.NET中,它被封装在IEnumerableIEnumerator接口以及它们的泛型版本中。(大多数情况下,我将使用非泛型形式来进行阐述,用泛型形式来演示代码。显然,泛型形式是强类型的,而非泛型形式不是,但除此之外,它们之间唯一的区别是,泛型形式实现了IDisposable。)

.NET迭代器模式的基本理念是,作为数据消费者,你调用IEnumerableGetEnumerator()来得到IEnumerator,然后迭代IEnumerator的内容(通过MoveNext()方法和Current属性),直到不再需要任何数据,或迭代器已经没有能返回的信息。例如,对IEnumerable<string>进行的简单foreach循环与下面的代码类似:

IEnumerator<string> iterator = dataSource.GetEnumerator();
while (iterator.MoveNext())
{
    string data = iterator.Current;
    // Use data within the body of the loop 
}

简便起见,上面的代码没有调用迭代器的Dispose方法。为foreach循环生成的代码使用了一个try/finally构造,来确保迭代器能够在用完之后进行处置(dispose)。这并不是模式本身所要求的,但当通过神奇的yield return语句来实现迭代器时(稍后会看到),却是十分重要的。

为什么是两个接口?

你可能会问,为什么IEnumerable自己没有MoveNext()Current成员呢?为什么要用另一个接口?好吧,想象一下有两个不同的循环,它们迭代相同的列表。你不希望两个循环互相干扰,因此需要两个独立的概念来表达“现在我访问了几个列表元素”。IEnumerator正是为此而生。它维护了独立的信息(如列表的当前索引)和集合本身的引用。尽管迭代器通常用于内存中的集合,但后面我们会看到,它并不局限于此,还能用于“请求数据、处理数据、请求数据”这样的循环。

迭代器块(C# 2)

在C# 1中实现迭代器块是很痛苦的。你需要创建一个实现了IEnumerable的集合类型,然后还要创建一个单独的类型(即实现了IEnumerator的类型)来包含对该集合实例的引用,通常还要添加一些状态信息,来指明遍历到了什么地方。这太容易出错了,一般开发者不到万不得已是不会自己实现的。

而在C# 2中,当你使用迭代器块来实现IEnumerableIEnumerator(或它们的泛型版本)时,编译器将为我们处理所有复杂的工作。它为我们构建了一个状态机,你可以很容易地获取迭代器,执行迭代器块中的代码,并产生(yield)值。演示易于解释,我们来看一段完整的程序:

using System;
using System.Collections.Generic;

class IteratorBlockDemo
{
    static IEnumerable<string> GetDemoEnumerable()
    {
        yield return "start";

        for (int i=0; i < 5; i++)
        {
            yield return i.ToString();
        }

        yield return "end";
    }

    static void Main()
    {
        foreach (string x in GetDemoEnumerable())
        {
            Console.WriteLine(x);
        }
    }
}

程序的输出结果非常简单:

start
0
1
2
3
4
end

我不会在此深入介绍迭代器块工作的细节(更多信息请参考《深入理解C#(第二版)》或语言规范)。不过下面的内容还是十分重要的:

  1. Main调用了GetDemoEnumerable()
  2. GetDemoEnumerable()新建了编译器生成的额外类型的一个实例。目前为止,还没有执行我们编写的任何代码。
  3. Main调用了MoveNext()
  4. 执行迭代器块中的代码,直到遇到一条yield语句。在本例中,会立即发生。迭代器记住当前项为“start”,然后返回true,表示有数据。
  5. Main使用Current属性来获取数据,然后打印。
  6. Main再次调用MoveNext()
  7. 迭代器从上一次的位置继续执行(即从第一个yield return后面开始)。和之前一样,执行代码(初始化i变量),知道遇到下一个yield语句。
  8. ……重复这种模式,直到某次调用MoveNext()时到达了方法的末尾,这时该调用将返回false,表明已经没有数据了。

有三点是非常重要的:首先,在第一次调用MoveNext()之前,不会执行任何原始代码。其次,后续调用MoveNext()时,代码会跳转到上次离开时的位置。产生(yield)值就像是“暂停”了方法。最后,编译器会保留方法的状态(即局部变量),尽管i是迭代器的局部变量,它的值仍然可以保存在迭代器中,到下次调用MoveNext()的时候,仍然可以使用它。

这些特性使迭代器块完全不同于其他方法。你有可能一直搞不明白这是怎么回事,也有可能突然灵光乍现。你可以对迭代器块进行调试,来查看其工作流程。现在,我们了解了迭代器以及它们如何在C# 2中得以轻松地实现,下面看看如何将它们串联(chain)起来。

数据管道和可组合性

LINQ to Objects构建于数据管道(data pipeline)这个概念之上。我们从一个实现了IEnumerable的数据源开始,串联起一系列操作,每个操作都基于前一个的结果,并返回另一个IEnumerable(可能为不同的结果类型)。这种将一些小操作串联成一个大操作的行为称为组合(composition)。组合的重点在于真正简化每一个小操作。LINQ to Objects使用委托对输入元素进行操作,带来了很大的灵活性。例如过滤器中的谓词(predicate),指明某个特殊的值是否能通过过滤器的筛选;又如投影(projection),可以将一个值映射为另一个值。

假设我们有一个随机排列的数字序列,希望得到一个字符串序列。我们过滤掉所有的负数,对剩下的进行排序,然后调用ToString将数字转换为十六进制。在C# 3和.NET 3.5中,可以使用如下的查询表达式:

from number in numbers
where number >= 0
orderby number
select number.ToString("x")

在编译器开始处理之前,解析器将其翻译为非查询表达式的形式:

numbers.Where (number => number >= 0)
    .OrderBy (number => number)
    .Select (number => number.ToString("x"))

=>语法用于Lambda表达式——一种创建委托(和表达式树)的简单方式。WhereOrderBySelect方法都是LINQ to Objects提供的扩展方法,分别用来过滤、排序和投影。正如你所知,这其中蕴含了很多特性,但本文不会深入这些细节——我们只将注意力放在迭代器的行为上。

延迟执行vs立即执行

当我们使用迭代器块创建自己的迭代器时,上面的表达式并没有执行什么有意义的代码——它建立了管道,但没有真正地请求数据。只有在第一次请求Select返回值中的数据时,才会真正地进行过滤、排序、投影等操作。这成为延迟执行(deferred execution)。很多LINQ to Objects查询操作符都使用了延迟执行,特别是那些用于构建管道的操作符。而其他查询操作符如Count()Max()ToList()等则使用了立即执行(immediate execution),这意味着它们将立即进行工作,并返回适当的数据。

弄清楚这些是十分重要的,我们能够知道操作具体在什么时候发生。比如,你指定了一个可能会抛出异常的投影,你需要知道只有在请求数据的时候才会发生异常,调用Select不抛出异常,不代表一切正常。

流vs缓冲

还有一个概念与与延迟/立即执行大同小异,即操作符对数据进行流式传输(stream)和缓冲传输(buffer)。使用流式传输的操作符每次只(从管道的前一部分)获取它所需要的数据来给出下一条结果。Select()就是最简单的流式传输操作符,它获取下一项,执行指定的委托,投影到结果上,然后产生(yield)结果。Where()要稍微复杂一些,它会一直请求数据,直到没有数据或找到了一个可以通过过滤器的项。每当这时,它就会产生该值,而不再请求任何数据。

缓冲传输操作符则不同。它们请求数据时,会缓冲管道较早部分的所有数据,然后计算出所有结果。Reverse()是最简单的缓冲传输操作符。为了返回反序的数据,在产生(yield)任何数据之前,你必须先到达最后一个元素。LINQ to Objects中的排序和分组也使用了缓冲传输。

生成器

LINQ to Objects还包含了一些生成器操作符(generator operator)。它们会创建一个数据序列,但不基于任何其他序列。DefaultIfEmpty也被认为是生成器,但实际上不是。它基于一个已知的序列,尽管该序列可能为空(empty)。本文不会对此进行讨论。

标准的生成器有三个:EmptyRepeatRange。我们先来看看它们可能的实现,然后使用组合对实现进行少许修改。当然,实际上这些已经都为我们实现好了,但对于理解迭代器块和组合来说,重新实现一次将是非常不错的实践。

Empty

正如我们所预料的,Empty返回一个空的序列,也就是说第一次调用MoveNext()时会返回false。说来奇怪,它并没有我们想象得那么简单。既然不需要返回任何值,那么不在方法体内添加任何代码不就行了吗?其实不然,我们需要这样的代码:

public static IEnumerable<TResult> Empty<TResult>()
{
    yield break;
}

yield break语句在迭代器块中意味着“提前退休”——它就像是方法的结尾,让MoveNext()返回false。我们为什么需要它呢?因为在一个空方法体内我们无法第一时间告诉编译器我们要创建一个迭代器块。编译器只有在方法体内遇到yield returnyield break时,才会将该方法视为是迭代器块的实现。这是我能想到的唯一一处,yield break直接出现在方法末尾之前,并且产生实际效果的地方。

Repeat

Repeat包含两个参数:要返回的元素和返回的次数。它将按你指定的次数产生(yield)相同的元素,然后停止。加上验证数量不能为负的代码,该方法的总代码量也很少:

public static IEnumerable<TResult> Repeat<TResult>(TResult element, int count)
{
    if (count < 0)
    {
        throw new ArgumentOutOfRangeException("count");
    }
    for (int i = 0; i < count; i++)
    {
        yield return element;
    }
}

Range

Range也十分简单。与前两个方法不同的是,它不是泛型的:它总是返回IEnumerable<int>。你需要指定两个参数:起始点和返回值的数量。返回的序列从给定的值开始,然后计数。因此Range(10, 3)将产生10、11、12。以下是忽略了错误验证的实现:

public static IEnumerable<int> Range(int start, int count)
{
    for (int i = start; i < start + count; i++)
    {
        yield return i;
    }
}

通用生成器

以上三种生成器都有点特殊。它们不需要委托,这与LINQ to Objects中的大多数API都不同。现在我们引入一个新的生成器。它是如此通用,配得上它的名字——Generate。它将生成一个无穷序列,它以一个起始点作为参数,产生(yield)该起始点,再对当前值执行一个委托,然后产生这个当前值,如此循环往复。以下是代码(不含错误检查——通常应该判断step是否为null):

public static IEnumerable<TSource> Generate<TSource>(TSource start, Func<TSource, TSource> step)
{
    TSource current = start;
    while (true)
    {
        yield return current;
        current = step(current);
    }
}

代码跟我们希望的一样简单。但实际上我们不会直接迭代Generate的结果,因为它是个死循环。确实,如果不使用组合,Generate几乎没有任何用处。但是,每次只需要用一个操作符,我们就能轻松地实现以上三种生成器。在实际使用Generate之前,我们先来看看另外一个操作符。

Take

Take是一个“管道”操作符。与SelectWhere一样,它接受一个序列,并返回一个序列。除了“source”序列外,你还需要指定要返回source中的多少个元素。Take简单地产生(yield)source中的元素,直到没有数据,或已经返回了所要求的元素数量。因此,其实现(不含错误检查)可能为:

public static IEnumerable<TSource> Take<TSource>(this IEnumerable<TSource> source, int count)
{
    foreach (TSource element in source)
    {
        if (count == 0)
        {
            yield break;
        }
        count--;
        yield return element;
    }
}

注意,我们使用了yield break来指明当计数器为0时完成迭代。(这里我们也可以简单地使用break,因为循环之后已经没有其他代码了。但我认为还是有必要演示一个比Empty实现中的yield break更加普通的场景。)source参数之前的this表明Take是一个扩展方法。

现在我们有了TakeGenerator,可以使用组合来重新实现EmptyRepeatRange了:

public static IEnumerable<TResult> Repeat<TResult>(TResult element, int count)
{
    return Generate(element, x => x).Take(count);
}

public static IEnumerable<TResult> Empty<TResult>()
{
    return Repeat(default(TResult), 0);
}

public static IEnumerable<int> Range(int start, int count)
{
    return Generate(start, x => x + 1).Take(count);
}

实现Repeat时,我们先是用指定的元素创建一个无穷序列,在指定步长(step)时返回该元素本身。然后用Take进行组合,在到达指定长度时终止这个无穷序列。Empty序列只需要使用TResult的默认值,重复0次。最后,Range创建了另一个无穷序列,从指定的值开始,每次加1,然后用Take来返回所需的元素数量。

实际上,以这种方式来实现这三个迭代器并不是特别有用,但这却能让你从一个有趣的视角来了解组合。Generate总是创建一个无穷序列,这会让你理解数据总是在请求的时候才会生成。否则,如果Generate先创建所有值,然后再一次性返回,很快就会耗尽内存。我有一篇博文介绍了一个稍微复杂点的示例,并包含完整的代码。那是一个用来生成曼德博罗特集图形的查询表达式:

var query = from row in Enumerable.Range(0, ImageHeight)
            from col in Enumerable.Range(0, ImageWidth)
            // Work out the initial complex value from the row and column
            let c = new Complex((col * SampleWidth) / ImageWidth + OffsetX,
                                (row * SampleHeight) / ImageHeight + OffsetY)
            // Work out the number of iterations
            select Generate(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
                                                .Take(MaxIterations)
                                                .Count() into count
            // Map that to an appropriate byte value
            select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);

这里的Generate位于嵌套查询中,用于查找某个特定点的颜色。博文中可以下载完整的代码,我希望你能从中明白组合这个技术是多么强大。

结论

LINQ to Objects中到处都是序列,以及充满无限可能的简单操作符。在《深入理解C#》中,我建议你在面对一个复杂的查询表达式时,先看看它是由哪些序列组成的。理解了迭代器如何工作,以及流式/缓冲传输和延迟/立即执行,可以为有效地使用LINQ打下一个良好的基础。组合查询是非常有趣的,而且C# 2中出现的迭代器块也使得迭代器更加易用。本文举了一些例子,你肯定也能写出自己的示例。前进吧,少年,去创建自己的操作符。重要的就是,实践!

对于我们中的许多人来说,LINQ不仅是一项新技术,更是导致代码出错的原因。要真正掌握新鲜的理念,总是会花很长的时间,所以我由衷地建议你多玩玩LINQ。尽管别的LINQ provider可能比LINQ to Objects更“性感”,但当你需要在内存中定义集合并操作核心内容时,它却更纯粹、更简单、更直接。

同样,对于很多开发者来说,迭代器块也十分神秘。除非你曾创建过序列,否则可能从未编写过迭代器。本文向你展示了它是多么简单,并且在你希望产生不同行为的地方给出了一些警告。迭代器块在C# 2中已然十分有用,与LINQ相结合时则更加绚丽,而所有这一切都体现在短小精悍的代码中。同样,实践吧。路漫漫,其修远,我们在乎的不是目的地,而是沿途的风景以及看风景的心情。让心灵去旅行,这才是旅行的意义。