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是好的,但不是免费的。
分享到:
相关推荐
访客模式 作者:Brian ( ) 您必须一组两个一组地工作 迭代器类 您已经获得了四个文件,其中包含以下五个迭代器类的声明和定义: 迭代器:这是用于定义所有其他迭代器类的接口的基类 NullIterator:此迭代器由...
Boost库中的`iterator_adaptor`是一个强大的工具,用于创建自定义迭代器。这个模板类允许程序员以一种灵活的方式包装现有的迭代器类型,以适应特定的需求或扩展其功能。`iterator_adaptor`的设计理念是基于`iterator...
在Struts2框架中,`iterator`标签是一个非常重要的组件,用于遍历各种集合对象,如List、Map等。在上述描述中,开发者遇到了一个关于`iterator`标签嵌套使用的问题,涉及到`LinkedHashMap`存储的数据结构。让我们...
ArrayList提供了一种高效的方式来管理大量的元素,并且提供了迭代器(Iterator)来遍历这些元素,使得我们可以在不暴露底层实现细节的情况下访问和修改列表中的元素。这个资源的目的是通过模拟Java ArrayList的...
### C++中的Iterator模式详解 #### 什么是Iterator模式? 在软件工程中,设计模式是一种用于解决特定问题的通用可重用解决方案。Iterator模式是其中的一种,其主要目标是在不暴露集合内部结构的情况下,为遍历集合...
### JAVA中的Iterator的用法详解 #### 一、概述 在Java编程语言中,`Iterator`接口扮演着遍历集合的重要角色。它提供了一种方式,使得开发人员能够以一致的方式遍历各种类型的集合,无需了解集合的具体实现细节。...
### Iterator迭代器详解 #### 一、Iterator简介与概念 在Java编程语言中,`Iterator`接口是一个重要的组件,它提供了遍历集合的基本方法。`Iterator`的主要作用是在不暴露集合内部结构的情况下,顺序访问集合中的...
一个运用Extjs,Struts2, json,iterator技术构建的iterator_jsonDemo2。iterator_jsonDemo1的链接:http://download.csdn.net/detail/cafebar123/8816409 运用了Extjs,Struts2, json,iterator技术, 将数据从...
在Java编程语言中,`Iterator`接口是集合框架的核心部分,它允许我们遍历集合中的元素,而无需暴露集合的内部结构。这个设计模式被称为迭代器模式,它为访问聚合对象(如数组、集合等)提供了一种统一的接口。在本...
根据提供的文件信息,本文将深入探讨Java中的`java.util.Iterator`接口及其在集合类中的应用。我们将从以下几个方面进行详细解析: ### 一、集合类的根接口:Collection `Collection`接口是Java集合框架的基础,它...
在Struts2框架中,`<s:iterator>`标签是一个非常强大的工具,用于遍历集合或数组中的元素,尤其在处理列表数据时极为有用。通过本文档提供的代码示例,我们将深入探讨`<s:iterator>`标签的使用方法及其与不同数据...
该文档是演示迭代器Iterator的使用方法和源代码,其中包括了Iterator的继承类的讲解和再Iterator中的两种方法
### Struts2中Iterator标签的深入解析与应用 在Struts2框架中,`<s:iterator>`标签是一个非常强大的工具,用于在JSP页面上循环遍历集合数据,如列表(List)、数组、Map等。它允许开发者以一种动态且灵活的方式展示...
是关于iterator的函数,以及它们的作用!
在Java编程语言中,`Iterator`接口和`Iterable`接口是处理集合数据的重要工具,而JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,广泛应用于数据传输和存储。这个"iterator_jsonDemo"实例结合了这...
"Iterator接口" Iterator接口是Java编程语言中的一种接口,用于对集合进行迭代操作。它提供了一个通用的方式来遍历集合中的元素,而不管集合的具体实现类型。 Iterator接口的主要方法有三个:hasNext()、next()和...
首先,C++标准库定义了五种不同类型的迭代器:输入迭代器(Input Iterator)、输出迭代器(Output Iterator)、前向迭代器(Forward Iterator)、双向迭代器(Bidirectional Iterator)和随机访问迭代器(Random ...
### Java源码分析:深入探讨Iterator模式 #### 一、引言 在Java编程语言中,集合框架(`java.util`包)提供了多种容器类来存储对象,如`List`、`Set`和`Map`等。为了遍历这些容器中的元素,Java引入了迭代器模式...
在Java编程语言中,迭代器(Iterator)是一个至关重要的工具,它提供了一种高效且简洁的方式来遍历和访问集合中的元素,而无需暴露集合的内部结构。迭代器设计模式遵循了“访问者”模式的原则,使得代码更加灵活和可...
JSP 自定义标签 Iterator 遍历 List 本文主要介绍了在 JSP 中使用自定义标签 Iterator 遍历 List,并对标签的实现过程进行了详细的解释。 标签的概念和作用 在 JSP 中,标签是一种特殊的组件,它可以根据需要执行...