新书推介:《语义网技术体系》
作者:瞿裕忠,胡伟,程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
  •   Add to Google

    >> 本版讨论.NET,C#,ASP,VB技术
    [返回] 中文XML论坛 - 专业的XML技术讨论区计算机技术与应用『 Dot NET,C#,ASP,VB 』 → C# 2.0 中Iterators的改进与实现原理浅析 查看新帖用户列表

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 3666 个阅读者  浏览上一篇主题  刷新本主题   树形显示贴子 浏览下一篇主题
     * 贴子主题: C# 2.0 中Iterators的改进与实现原理浅析 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     admin 帅哥哟,离线,有人找我吗?
      
      
      
      威望:9
      头衔:W3China站长
      等级:计算机硕士学位(管理员)
      文章:5255
      积分:18407
      门派:W3CHINA.ORG
      注册:2003/10/5

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给admin发送一个短消息 把admin加入好友 查看admin的个人资料 搜索admin在『 Dot NET,C#,ASP,VB 』的所有贴子 点击这里发送电邮给admin  访问admin的主页 引用回复这个贴子 回复这个贴子 查看admin的博客楼主
    发贴心情 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.*]
    上一篇
    返回上一页
    回到目录
    回到页首


       收藏   分享  
    顶(0)
      





    关闭广告显示

    ----------------------------------------------

    -----------------------------------------------

    第十二章第一节《用ROR创建面向资源的服务》
    第十二章第二节《用Restlet创建面向资源的服务》
    第三章《REST式服务有什么不同》
    InfoQ SOA首席编辑胡键评《RESTful Web Services中文版》
    [InfoQ文章]解答有关REST的十点疑惑

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2004/11/9 2:26:00
     
     GoogleAdSense
      
      
      等级:大一新生
      文章:1
      积分:50
      门派:无门无派
      院校:未填写
      注册:2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 Dot NET,C#,ASP,VB 』的所有贴子 点击这里发送电邮给Google AdSense  访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2025/7/17 6:35:35

    本主题贴数1,分页: [1]

    管理选项修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    109.375ms