Vincent.Chan‘s Blog

常用链接

统计

积分与排名

网站

最新评论

Iterator vs Visitor, Pull vs Push

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 是好的,但不是免费的。

posted on 2006-07-16 01:47 Vincent.Chen 阅读(350) 评论(0)  编辑  收藏 所属分类: Java


只有注册用户登录后才能发表评论。


网站导航: