-- 作者：admin
-- 发布时间：11/9/2004 2:26:00 AM
-- C# 2.0 中Iterators的改进与实现原理浅析
发信人: flier (小海 [寻找风车中]), 信区: DotNET
标 题: C# 2.0 中Iterators的改进与实现原理浅析
发信站: BBS 水木清华站 (Fri Apr 2 00:37:05 2004), 转信
http://www.blogcn.com/user8/flier_lu/main.asp?id=1511638
C# 2.0 中Iterators的改进与实现原理浅析
C#语言从VB中吸取了一个非常实用的foreach语句。对所有支持IEnumerable接口的类的实例，foreach语句使用统一的接口遍历其子项，使得以前冗长的for循环中繁琐的薄记工作完全由编译器自动完成。支持IEnumerable接口的类通常用一个内嵌类实现IEnumerator接口，并通过IEnumerable.GetEnumerator函数，允许类的使用者如foreach语句完成遍历工作。
这一特性使用起来非常方便，但需要付出一定的代价。Juval Lowy发表在MSDN杂志2004年第5期上的Create Elegant Code with Anonymous Methods, Iterators, and Partial Classes一文中，较为详细地介绍了C# 2.0中迭代支持和其他新特性。
首先，因为IEnumerator.Current属性是一个object类型的值，所以值类型(value type)集合在被foreach语句遍历时，每个值都必须经历一次无用的box和unbox操作；就算是引用类型(reference type)集合，在被foreach语句使用时，也需要有一个冗余的castclass指令，保障枚举出来的值进行类型转换的正确性。
以下为引用：
using System.Collections;
public class Tokens : IEnumerable
{
...
Tokens f = new Tokens(...);
foreach (string item in f)
{
Console.WriteLine(item);
}
...
}
上面的简单代码被自动转换为
以下为引用：
Tokens f = new Tokens(...);
IEnumerator enum = f.GetEnumerator();
try
{
do {
string item = (string)enum.get_Current(); // 冗余转换
Console.WriteLine(item);
} while(enum.MoveNext());
}
finally
{
if(enum is IDisposable) // 需要验证实现IEnumerator接口的类是否支持IDisposable接口
{
((IDisposable)enum).Dispose();
}
}
好在C# 2.0中支持了泛型(generic)的概念，提供了强类型的泛型版本IEnumerable定义，伪代码如下：
以下为引用：
namespace System.Collections.Generic
{
public interface IEnumerable<ItemType>
{
IEnumerator<ItemType> GetEnumerator();
}
public interface IEnumerator<ItemType> : IDisposable
{
ItemType Current{get;}
bool MoveNext();
}
}
这样一来即保障了遍历集合时的类型安全，又能够对集合的实际类型直接进行操作，避免冗余转换，提高了效率。
以下为引用：
using System.Collections.Generic;
public class Tokens : IEnumerable<string>
{
... // 实现 IEnumerable<string> 接口
Tokens f = new Tokens(...);
foreach (string item in f)
{
Console.WriteLine(item);
}
}
上面的代码被自动转换为
以下为引用：
Tokens f = new Tokens(...);
IEnumerator<string> enum = f.GetEnumerator();
try
{
do {
string item = enum.get_Current(); // 无需转换
Console.WriteLine(item);
} while(enum.MoveNext());
}
finally
{
if(enum) // 无需验证实现IEnumerator接口的类是否支持IDisposable接口，
// 因为所有由编译器自动生成的IEnumerator接口实现类都支持
{
((IDisposable)enum).Dispose();
}
}
除了遍历时的冗余转换降低性能外，C#现有版本另一个不爽之处在于实现IEnumerator接口实在太麻烦了。通常都是由一个内嵌类实现IEnumerator接口，而此内嵌类除了get_Current()函数外，其他部分的功能基本上都是相同的，如
以下为引用：
public class Tokens : IEnumerable
{
public string[] elements;
Tokens(string source, char[] delimiters)
{
// Parse the string into tokens:
elements = source.Split(delimiters);
}
public IEnumerator GetEnumerator()
{
return new TokenEnumerator(this);
}
// Inner class implements IEnumerator interface:
private class TokenEnumerator : IEnumerator
{
private int position = -1;
private Tokens t;
public TokenEnumerator(Tokens t)
{
this.t = t;
}
// Declare the MoveNext method required by IEnumerator:
public bool MoveNext()
{
if (position < t.elements.Length - 1)
{
position++;
return true;
}
else
{
return false;
}
}
// Declare the Reset method required by IEnumerator:
public void Reset()
{
position = -1;
}
// Declare the Current property required by IEnumerator:
public object Current
{
get // get_Current函数
{
return t.elements[position];
}
}
}
...
}
内嵌类TokenEnumerator的position和Tokens实际上是每个实现IEnumerator接口的类共有的，只是Current属性的get函数有所区别而已。这方面C# 2.0做了很大的改进，增加了yield关键字的支持，允许代码逻辑上的重用。上面冗长的代码在C# 2.0中只需要几行，如
以下为引用：
using System.Collections.Generic;
public class Tokens : IEnumerable<string>
{
public IEnumerator<string> GetEnumerator()
{
for(int i = 0; i<elements.Length; i++)
yield elements[i];
}
...
}
GetEnumerator函数是一个C# 2.0支持的迭代块(iterator block)，通过yield告诉编译器在什么时候返回什么值，再由编译器自动完成实现IEnumerator<string>接口的薄记工作。而yield break语句支持从迭代块中直接结束，如
以下为引用：
public IEnumerator<int> GetEnumerator()
{
for(int i = 1;i< 5;i++)
{
yield return i;
if(i > 2)
yield break; // i > 2 时结束遍历
}
}
这样一来，很容易就能实现IEnumerator接口，并可以方便地支持在一个类中提供多种枚举方式，如
以下为引用：
public class CityCollection
{
string[] m_Cities = {"New York","Paris","London"};
public IEnumerable<string> Reverse
{
get
{
for(int i=m_Cities.Length-1; i>= 0; i--)
yield m_Cities[i];
}
}
}
接下来我们看看如此方便的语言特性背后，编译器为我们做了哪些工作。以上面那个支持IEnumerable<string>接口的Tokens类为例，GetEnumerator函数的代码被编译器用一个类包装起来，伪代码如下
以下为引用：
public class Tokens : IEnumerable<string>
{
private sealed class GetEnumerator$00000000__IEnumeratorImpl
: IEnumerator<string>, IEnumerator, IDisposable
{
private int $PC = 0;
private string $_current;
private Tokens <this>;
public int i$00000001 = 0;
// 实现 IEnumerator<string> 接口
string IEnumerator<string>.get_Current()
{
return $_current;
}
bool IEnumerator<string>.MoveNext()
{
switch($PC)
{
case 0:
{
$PC = -1;
i$00000001 = 0;
break;
}
case 1:
{
$PC = -1;
i$00000001++;
break;
}
default:
{
return false;
}
}
if(i$00000001 < <this>.elements.Length)
{
$_current = <this>.elements[i$00000001];
$PC = 1;
return true;
}
else
{
return false;
}
}
// 实现 IEnumerator 接口
void IEnumerator.Reset()
{
throw new Exception();
}
string IEnumerator.get_Current()
{
return $_current;
}
bool IEnumerator.MoveNext()
{
return IEnumerator<string>.MoveNext(); // 调用 IEnumerator<string> 接口的实现
}
// 实现 IDisposable 接口
void Dispose()
{
}
}
public IEnumerator<string> GetEnumerator()
{
GetEnumerator$00000000__IEnumeratorImpl impl = new GetEnumerator$00000000__IEnumeratorImpl();
impl.<this> = this;
return impl;
}
}
从上面的伪代码中我们可以看到，C# 2.0编译器实际上维护了一个和我们前面实现IEnumerator接口的TokenEnumerator类非常类似的内部类，用来封装IEnumerator<string>接口的实现。而这个内嵌类的实现逻辑，则根据GetEnumerator定义的yield返回地点决定。
我们接下来看一个较为复杂的迭代块的实现，支持递归迭代(Recursive Iterations)，代码如下：
以下为引用：
using System;
using System.Collections.Generic;
class Node<T>
{
public Node<T> LeftNode;
public Node<T> RightNode;
public T Item;
}
public class BinaryTree<T>
{
Node<T> m_Root;
public void Add(params T[] items)
{
foreach(T item in items)
Add(item);
}
public void Add(T item)
{
// ...
}
public IEnumerable<T> InOrder
{
get
{
return ScanInOrder(m_Root);
}
}
IEnumerable<T> ScanInOrder(Node<T> root)
{
if(root.LeftNode != null)
{
foreach(T item in ScanInOrder(root.LeftNode))
{
yield item;
}
}
yield root.Item;
if(root.RightNode != null)
{
foreach(T item in ScanInOrder(root.RightNode))
{
yield item;
}
}
}
}
BinaryTree<T>提供了一个支持IEnumerable<T>接口的InOrder属性，通过ScanInOrder函数遍历整个二叉树。因为实现IEnumerable<T>接口的不是类本身，而是一个属性，所以编译器首先要生成一个内嵌类支持IEnumerable<T>接口。伪代码如下
以下为引用：
public class BinaryTree<T>
{
private sealed class ScanInOrder$00000000__IEnumeratorImpl<T>
: IEnumerator<T>, IEnumerator, IDisposable
{
BinaryTree<T> <this>;
Node<T> root;
// ...
}
private sealed class ScanInOrder$00000000__IEnumerableImpl<T>
: IEnumerable<T>, IEnumerable
{
BinaryTree<T> <this>;
Node<T> root;
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
ScanInOrder$00000000__IEnumeratorImpl<T> impl = new ScanInOrder$00000000__IEnumeratorImpl<T>();
impl.<this> = this.<this>;
impl.root = this.root;
return impl;
}
IEnumerator IEnumerable.GetEnumerator()
{
ScanInOrder$00000000__IEnumeratorImpl<T> impl = new ScanInOrder$00000000__IEnumeratorImpl<T>();
impl.<this> = this.<this>;
impl.root = this.root;
return impl;
}
}
IEnumerable<T> ScanInOrder(Node<T> root)
{
ScanInOrder$00000000__IEnumerableImpl<T> impl = new ScanInOrder$00000000__IEnumerableImpl<T>();
impl.<this> = this;
impl.root = root;
return impl;
}
}
因为ScanInOrder函数内容需要用到root参数，故而IEnumerable<T>和IEnumerator<T>接口的包装类都需要有一个root字段，保存传入ScanInOrder函数的参数，并传递给最终的实现函数。
实现IEnumerator<T>接口的内嵌包装类ScanInOrder$00000000__IEnumeratorImpl<T>实现原理与前面例子里的大致相同，不同的是程序逻辑大大复杂化，并且需要用到IDisposable接口完成资源的回收。
以下为引用：
public class BinaryTree<T>
{
private sealed class GetEnumerator$00000000__IEnumeratorImpl
: IEnumerator<T>, IEnumerator, IDisposable
{
private int $PC = 0;
private string $_current;
private Tokens <this>;
public int i$00000001 = 0;
public IEnumerator<T> __wrap$00000003;
public IEnumerator<T> __wrap$00000004;
public T item$00000001;
public T item$00000002;
public Node<T> root;
// 实现 IEnumerator<T> 接口
string IEnumerator<T>.get_Current()
{
return $_current;
}
bool IEnumerator<T>.MoveNext()
{
switch($PC)
{
case 0:
{
$PC = -1;
if(root.LeftNode != null)
{
__wrap$00000003 = <this>.ScanInOrder(root.LeftNode).GetEnumerator();
goto ScanLeft;
}
else
{
goto GetItem;
}
}
case 1:
{
return false;
}
case 2:
{
goto ScanLeft;
}
case 3:
{
$PC = -1;
if(root.RightNode != null)
{
__wrap$00000004 = <this>.ScanInOrder(root.RightNode).GetEnumerator();
goto ScanRight;
}
else
{
return false;
}
break;
}
case 4:
{
return false;
}
case 5:
{
goto ScanRight;
}
default:
{
return false;
}
ScanLeft:
$PC = 1;
if(__wrap$00000003.MoveNext())
{
$_current = item$00000001 = __wrap$00000003.get_Current();
$PC = 2;
return true;
}
GetItem:
$PC = -1;
if(__wrap$00000003 != null)
{
((IDisposable)__wrap$00000003).Dispose();
}
$_current = root.Item;
$PC = 3;
return true;
ScanRight:
$PC = 4;
if(__wrap$00000004.MoveNext())
{
$_current = $item$00000002 = __wrap$00000004.get_Current();
$PC = 5;
return true;
}
else
{
$PC = -1;
if(__wrap$00000004 != null)
{
((IDisposable)__wrap$00000004).Dispose();
}
return false;
}
}
// 实现 IDisposable 接口
void Dispose()
{
switch($PC)
{
case 1:
case 2:
{
$PC = -1;
if(__wrap$00000003 != null)
{
((IDisposable)__wrap$00000003).Dispose();
}
break;
}
case 4:
case 5:
{
$PC = -1;
if(__wrap$00000004 != null)
{
((IDisposable)__wrap$00000004).Dispose();
}
break;
}
}
}
}
}
通过上面的伪代码，我们可以看到，C# 2.0实际上是通过一个以$PC为自变量的有限状态机完成的递归迭代块，这可能是因为有限状态机可以很方便地通过程序自动生成吧。而Dispose()函数则负责处理状态机的中间变量。
有兴趣进一步了解迭代特性的朋友，可以到Grant Ri的BLog上阅读Iterators相关文章。
在了解了Iterators的实现原理后，再看那些讨论就不会被其表象所迷惑了 :D
--
. 生命的意义在于 /\ ____\ /\_ \ /\_\ http://flier.yeah.net.
. 希望 \ \ \___/_\/\ \ \/_/__ __ _ _★ .
. 工作 \ \ ____\\ \ \ /\ \ /'__`\ /\`'_\ .
. 爱你的人 \ \ \___/ \ \ \___\ \ \/\ __// \ \ \/ .
. 和你爱的人 \ \___\ \ \_____\ \__\ \____\ \ \_\ .
. …… \/___/ \/_____/\/__/\/____/ \/_/ @nsfocus.com.
※ 来源:·BBS 水木清华站 smth.org·[FROM: 211.167.254.*]
上一篇
返回上一页
回到目录
回到页首
|