Java开发网 |
注册 |
登录 |
帮助 |
搜索 |
排行榜 |
发帖统计
|
您没有登录 |
» Java开发网 » Design Pattern & UML
打印话题 寄给朋友 订阅主题 |
作者 | 转载:Iterator vs Visitor,PullvsPush (转自javaeye,原创者:buaawhl) |
gaoxt1983
发贴: 67 积分: 0 |
于 2006-08-28 16:40
Iterator vs Visitor, Pull vs Push 名词界定 Iterator Pattern也叫做Generator, Sequence, Stream等。Java里面有Iterator Interface,大家应该比较熟悉,不再赘述。 完整的具有Visitor和Visited (Visitable) 两个部分的Visitor Pattern的使用并不广泛。 简单的只有Visitor部分的Simple Visitor Pattern比较常见,比如Callback, Interceptor, Filter,Functor, Selector, Extractor等,都可以看作是Simple Visitor Pattern。 它们都只有Visitor部分,而没有Visited部分。或者说他们的Visitor需要处理的Visited Object通常只有一种通用数据类型,所以不需要专门提出来一个Visited Interface -- accept(visitor)。 这种情况和Observer Pattern很相似。不过这也不奇怪,很多Design Pattern都是非常类似的,有的几乎只有名字不同。 为了避免不必要的口舌之争后,这么说吧,Visitor和Observer的侧重点不同。 Visitor一般来说是Visit一个集合,通常在一个遍历算法中密集完成,获取的信息(Node Object)之间一般都有密切关联,比如父子关系,兄弟关系。 而Observer Patten则是监听一个长期运行的系统,零零散散地不定期地运行,获取的信息之间不存在密切联系,或者说,没什么关系。比如订阅的报纸到了,订购的牛奶到了。 费了半天口舌,澄清各种可能的误会,我们继续Iterator vs Visitor之旅。 Iterator Pattern和Simple Visitor Pattern处理的问题领域几乎是重合的。它们面对的共同问题模型的组成部分如下: (1)有一个算法Algorithm,通常是遍历算法(Traversal)。而且通常是复杂的数据结构,Tree、Graph等结构的遍历算法。 (2)算法的使用者,需要和算法的每一步遇到的Node Object进行交流。 所不同的是, Iterator是一种主动模型,Pull模型,Ask and Get。Iterator听候用户的调遣。 Vistor是一种被动模型,Push模型,Plugin / callback模型,Push and Pray and Wait。Visitor听候算法的调遣。 Iterator相当于算法公司的一名业务人员,代表公司和用户打交道。用户并不需要深入到算法公司内部。 而Visitor相当于用户派出的代表,深入到算法公司内部,由算法公司安排访问行程。 Iterator的典型使用方法是: iterator = traversal.getIterator(); item = iterator.next(); do some thing with item Vistor的典型使用方法是 visitor = new Visitor(){ .. visit(item) { do something with item } }; traversal.traverse(visitor); 一个典型的例子是StAX和SAX和两种操作XML的方式。 (参见http://www.xmlpull.org/,关于StAX的典型用法,网上有些经典文章,本文不再赘述。请使用StAX XMLPull XML等关键字进行搜索) StAX就是一个典型的Pull Model, Iterator Pattern。 而SAX是Push Model, Simple Visitor Pattern (Event Listener)。(如果较真,你当然可以把它叫做Oberver Pattern)。 另外一个有趣的例子是DOM Traversal。 W3的DOM Level 2规范定义了DOM Traversal。 http://www.w3.org/TR/2000/REC-DOM-Level-2-Traversal-Range-20001113/traversal.html DocumentTraversal, TreeWalker, NodeIterator, NodeFilter。 DOM Traversal主要是一个Iterator Pattern,TreeWalker, NodeIterator都是Iterator;但DOM Traversal同时也是一个简单的Visitor Pattern —— NodeFiter可以作为简单的Visitor被注入到Traversal算法里面,对遇到的每个Node进行过滤。 不过,这个NodeFiter的method name比较有意思,叫做accept。而我们知道Visitor Pattern的Visited Object具有一个accept方法。不过,不要误会。这个NodeFilter仍然是一个Visitor。这里的Accept的意思就是Intercept, Filter。 用法是这样。 NodeIterator iterator = DocumentTraversal.createNodeIterator(…NodeFilter …) 按照我的设想,这个API设计,还可以有另外的思路。把Filter加在Iterator身上,而不是加在Traversal算法身上。因为Iterator Pattern很容易地做到这一点。 NodeIterator iterator = New FilteredIterator( DocumentTraversal().createNodeIterator() , … NodeFilter …); 这样,DOM Traversal就是一个纯粹的Iterater Pattern了。 特性比较 Iterator属于问答模式,或者说消费者/生产者模式。 如果消费者不问不要,生产者就不答不给。Iterator的使用者完全掌握了主动权,是控制舞步节奏的领舞者,随时可以中止这场问答游戏。 Iterator的用法本身就是Lazy的,一问一答,遍历算法停在那里恭候Iterator使用者的调遣。 Visitor则完全是被动的,Visitor的提供者/使用者把Visitor扔到Traversal算法里面,然后运行算法,同时祈祷并等候算法的完成(Push and Wait),完全失去了控制权,只能等待算法整个完成或者中止,才能重新拿到控制权。 Vistor的用法很难做到Lazy,算法必须提供一些机制,接受Visitor每一步调用发出的指令,进行相应的策略选择。 换句话说,Visitor Pattern里面的算法必须做出相应的Lazy支持,而且Visitor必需积累前面步骤的状态,然后判断这次调用中发出什么样的指令。 比如,有这样一个需求:遍历一棵树,搜集到前5个名字是Apple的Node。然后返回这5个Node。假设树遍历算法已经有了。 这时候采用Iterator Pattern视线起来很容易。不再多说。 Visitor Pattern则需要: Vistor使用一个集合来保存每次遇到的名字是Apple的Node,每次都判断是否已经找到了5个,如果已经找到,那么发出一个Stop Signal给算法。 如果遍历算法不接受这种指令怎么办? 只好等待算法完成。或者实在等不及,预计到后面还有上万个Node需要遍历,那么就干脆 throw new RuntimeException(), throw new Throwable()。 也许算法并没有聪明到捕获这些Exception。那么这个Trick就成功了。外面使用一个Try Catch捕获这个Exception。不过,这是Very Very Bad Smell。 Iterator的应用场景是这样: 我在商品定购目录上看到一个公司有我感兴趣的产品系列。于是我打电话给该公司,要求派一个销售代表来。销售代表上门之后,从包里拿出一个一个的产品给你看,我看了几个,没什么满意的,于是打了个哈欠说,今天就先到这里吧,下次再说。打发了销售代表,我就转身去做自己的事情了。 我的地盘,我做主。这就是Iterator Pattern的理念。 Vistior的应用场景是这样: 我在商品定购目录上看到一个公司有我感兴趣的产品系列。于是我上门拜访该公司,公司给我安排了一场产品性能展示,我看了几个之后,没有什么满意的,于是我说,我肚子疼,想先回去了。遇到好心的公司代表,当然说,身体要紧,慢走。遇到固执的公司代表,一定会说,对不起,我们公司有自己的工作流程,完成产品演示之前,产品厅的门锁是打不开的。我只好勃然大怒,吵吵嚷嚷(throw exception),期待能够杀出重围,这时候,假设该公司的保安系统反映比较灵敏(try catch every visitor exception),就会有几个保安跑过来,把我按在椅子上继续听讲。 入乡随俗,客随主便。别人的地盘,别人做主。这就是Visitor Pattern的理念。 Iterator Pattern的优势当然不仅如此。这只是个特殊的例子。 更常见的是,Iterator Pattern能够支持基于Iterator的很多算法。 比如,Functional Programming的Map, Reduce, Filter等函数都是接受一个Iterator (Sequence, List, Stream等)。Map, Filter等函数还可以组合成一个新的Iterator。这个组合可以一直下去。 当然,Visitor也是可以组合的。但是限制严格,缺乏扩展性。 比如这样一个需求: 有T1和T2两棵树。首先遍历T1的10个Node,如果发现Apple,那么摘下来,然后继续遍历,如果10步都没有发现Apple,那么切换到T2;遍历T2的规则也是如此,10步之内发现目标,就继续,否则就切换到T1。 Iterator Pattern实现起来很简单。相当于我是买方,情势是买方市场,我可以让两个公司的销售代表同时到我的公司来,我可以同时接待他们,让他们各自按顺序展示自己的产品。 Visitor Pattern怎么做?情势是卖方市场,我巴巴地跑上门去,看T1公司的产品展示,看了10个之后说,请送我到T2公司的产品展示现场,我看10个之后,再回来。 一个用户可以同时使用多个算法的Iterator;但是用户的一个Visitor只能同时进入一个算法。 这就是两者核心理念的不同。 实现难度 读者说了,Iterator这么方便,你就使用Iterator好了,说这么多干什么。 如果别人提供了Iterator,我当然会使用。 现在的问题是,假设你是算法公司的成员。你是提供Visitor Pattern的API,还是Iterator Pattern的API? Visitor Pattern的实现比较简单。自己知道自己公司的内部组织结构,一个一个的遍历,并传递给Visitor就行了。 Iterator Pattern的实现难度,可以说,那是相当的大。 内部数据结构简单的数组、链表好说,做一个类似于Closure, Context, Continuation的保存了当前调用步骤(数组索引,或者当前指针)和调用环境(内部数据集)的结构,返回给用户就可以了。用户每次调用iterator.next,iterator就把索引或指针向后移动一下。 如果是内部数据复杂的Tree, Graph结构,就相当复杂了。比如是遍历一棵树,而且这棵树的Node里面没有Parent引用,那么Iterator必须自己维护一个栈把前面的所有的Parent Node都保存起来。当用户调用iterator.next的时候,iterator就必须检查自己当前的状态,如果所有的Child Node都走完了,那么就要返回到上面的Parent,继续检查。 而在Visitor Pattern里面,这个算法的实现简直是小菜一碟,只要一个简单的递归就够了。计算机会自动帮你分配和管理运行栈,保存前面的Parent Node,执行返回的时候,这个Parent Node又自动交还给你。 Coroutine 有没有简单的方法来实现Iterator Pattern API呢?如同实现Visitor Pattern API那样容易? 幸福得象花儿一样。简单得像Visitor一样。能不能那样? 聪明的人们把目光转向了Coroutine。 Coroutine本来是一个通用的概念。表示几个协同工作的程序。 比如,消费者/生产者,你走几步,我走几步;下棋对弈,你一步我一步。 由于协同工作的程序通常只有2个,而且这两个程序交换的数据通常只有一个。于是人们就很容易想到用Coroutine来实现Iterator。 这里面Iterator就是Coroutine里面的生产者Producer角色,数据提供者。所以,也叫做Generator。 每次Iterator程序就是等在那里,一旦用户(消费者Consumer角色)调用了iterator.next, Iterator就继续向下执行一步,然后把当前遇到的内部数据的Node放到一个消费者用户能够看到的公用的缓冲区(比如,直接放到消费者线程栈里面的局部变量)里面,然后自己就停下来(wait)。然后消费者用户就从缓冲区里面获得了那个Node。 这样Iterator就可以自顾自地进行递归运算,不需要自己管理一个栈,而是迫使计算机帮助它分配和管理运行栈。于是就实现了幸福得像花儿一样,简单得像Visitor一样的梦想。 比如,这样一段代码,遍历一棵二叉树。 public class TreeWalker : Coroutine { private TreeNode _tree; public TreeWalker(TreeNode tree) { _tree = tree; } protected override Execute() { Walk(_tree); } private void Walk(TreeNode tree) { if (tree != null) { Walk(tree.Left); Yield(tree); Walk(tree.Right); } } } 其中的Yield指令是关键。意思是,首先把当前Node甩到用户的数据空间,然后自己暂停运行(类似于java的thread yield方法或者object.wait方法),把自己当前运行的线程挂起来,这样虚拟机就为自己保存了当前的运行栈(context)。 有人说,这不就是continuation吗? 对。只是Coroutine这里多了一个产生并传递数据的动作。 实现原理如果用Java Thread表示大概就是这样。当然下面的代码只是一个示意。网上有具体的Java Coroutine实现,具体代码我也没有看过,想来实现原理大致如此。 public class TreeIterator implements Iterator{ TreeWalker walker; // start the walker thread .. Object next(){ walker.notify(); // wait for a while so that walker can continue run return walker.currentNode; } } class TreeWalker implements Runnable{ TreeNode currentNode; TreeWarker(root){ currentNode = root; } void run(){ walk(curentNode); } private void Walk(TreeNode tree) { if (tree != null) { Walk(tree.Left); currentNode = tree; this.wait(); Walk(tree.Right); } } } 我们看到,Iterator本身是一个Thread,用户也是一个Thread。Iterator Thread把数据传递给User Thread。 说实话,我宁可自己维护一个Stack,也不愿意引入Coroutine这类Thread Control的方式来实现Iterator。 总结 千言万语一句话。 Iterator是好的,但不是免费的。 |
话题树型展开 |
人气 | 标题 | 作者 | 字数 | 发贴时间 |
10011 | 转载:Iterator vs Visitor,PullvsPush (转自javaeye,原创者:buaawhl) | gaoxt1983 | 7235 | 2006-08-28 16:40 |
已读帖子 新的帖子 被删除的帖子 |
Powered by Jute Powerful Forum® Version Jute 1.5.6 Ent Copyright © 2002-2021 Cjsdn Team. All Righits Reserved. 闽ICP备05005120号-1 客服电话 18559299278 客服信箱 714923@qq.com 客服QQ 714923 |