Iterator vs Visitor, Pull vs Push
名詞界定
Iterator Pattern
也叫做
Generator, Sequence, Stream
等。
Java
里面有
Iterator Interface
，大家應(yīng)該比較熟悉，不再贅述。
?
完整的具有
Visitor
和
Visited (Visitable)
兩個(gè)部分的
Visitor Pattern
的使用并不廣泛。
簡(jiǎn)單的只有
Visitor
部分的
Simple Visitor Pattern
比較常見(jiàn)，比如
Callback, Interceptor, Filter
，
Functor, Selector, Extractor
等，都可以看作是
Simple Visitor Pattern
。
它們都只有
Visitor
部分，而沒(méi)有
Visited
部分?；蛘哒f(shuō)他們的
Visitor
需要處理的
Visited Object
通常只有一種通用數(shù)據(jù)類型，所以不需要專門(mén)提出來(lái)一個(gè)
Visited
Interface -- accept(visitor)
。
?
這種情況和
Observer
Pattern
很相似。不過(guò)這也不奇怪，很多
Design
Pattern
都是非常類似的，有的幾乎只有名字不同。
為了避免不必要的口舌之爭(zhēng)后，這么說(shuō)吧，
Visitor
和
Observer
的側(cè)重點(diǎn)不同。
Visitor
一般來(lái)說(shuō)是
Visit
一個(gè)集合，通常在一個(gè)遍歷算法中密集完成，獲取的信息（
Node Object
）之間一般都有密切關(guān)聯(lián)，比如父子關(guān)系，兄弟關(guān)系。
而
Observer
Patten
則是監(jiān)聽(tīng)一個(gè)長(zhǎng)期運(yùn)行的系統(tǒng)，零零散散地不定期地運(yùn)行，獲取的信息之間不存在密切聯(lián)系，或者說(shuō)，沒(méi)什么關(guān)系。比如訂閱的報(bào)紙到了，訂購(gòu)的牛奶到了。
?
費(fèi)了半天口舌，澄清各種可能的誤會(huì)，我們繼續(xù)
Iterator vs Visitor
之旅。
Iterator Pattern
和
Simple Visitor Pattern
處理的問(wèn)題領(lǐng)域幾乎是重合的。它們面對(duì)的共同問(wèn)題模型的組成部分如下：
(1)
有一個(gè)算法
Algorithm
，通常是遍歷算法（
Traversal
）。而且通常是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，
Tree
、
Graph
等結(jié)構(gòu)的遍歷算法。
(2)
算法的使用者，需要和算法的每一步遇到的
Node Object
進(jìn)行交流。
?
所不同的是，
Iterator
是一種主動(dòng)模型，
Pull
模型，
Ask and Get
。
Iterator
聽(tīng)候用戶的調(diào)遣。
Vistor
是一種被動(dòng)模型，
Push
模型，
Plugin /
callback
模型，
Push and
Pray and Wait
。
Visitor
聽(tīng)候算法的調(diào)遣。
?
Iterator
相當(dāng)于算法公司的一名業(yè)務(wù)人員，代表公司和用戶打交道。用戶并不需要深入到算法公司內(nèi)部。
而
Visitor
相當(dāng)于用戶派出的代表，深入到算法公司內(nèi)部，由算法公司安排訪問(wèn)行程。
?
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);
?
一個(gè)典型的例子是
StAX
和
SAX
和兩種操作
XML
的方式。
（參見(jiàn)
http://www.xmlpull.org/
，關(guān)于
StAX
的典型用法，網(wǎng)上有些經(jīng)典文章，本文不再贅述。請(qǐng)使用
StAX
XMLPull XML
等關(guān)鍵字進(jìn)行搜索）
StAX
就是一個(gè)典型的
Pull Model, Iterator Pattern
。
而
SAX
是
Push Model, Simple Visitor Pattern
(Event Listener)
。（如果較真，你當(dāng)然可以把它叫做
Oberver Pattern
）。
?
另外一個(gè)有趣的例子是
DOM
Traversal
。
W3
的
DOM Level 2
規(guī)范定義了
DOM Traversal
。
http://www.w3.org/TR/2000/REC-DOM-Level-2-Traversal-Range-20001113/traversal.html
DocumentTraversal, TreeWalker,
NodeIterator, NodeFilter
。
?
DOM Traversal
主要是一個(gè)
Iterator Pattern
，
TreeWalker, NodeIterator
都是
Iterator
；但
DOM Traversal
同時(shí)也是一個(gè)簡(jiǎn)單的
Visitor Pattern
——
NodeFiter
可以作為簡(jiǎn)單的
Visitor
被注入到
Traversal
算法里面，對(duì)遇到的每個(gè)
Node
進(jìn)行過(guò)濾。
不過(guò)，這個(gè)
NodeFiter
的
method name
比較有意思，叫做
accept
。而我們知道
Visitor Pattern
的
Visited Object
具有一個(gè)
accept
方法。不過(guò)，不要誤會(huì)。這個(gè)
NodeFilter
仍然是一個(gè)
Visitor
。這里的
Accept
的意思就是
Intercept, Filter
。
用法是這樣。
NodeIterator iterator =
DocumentTraversal.createNodeIterator(…NodeFilter …)
?
按照我的設(shè)想，這個(gè)
API
設(shè)計(jì)，還可以有另外的思路。把
Filter
加在
Iterator
身上，而不是加在
Traversal
算法身上。因?yàn)?/span>
Iterator Pattern
很容易地做到這一點(diǎn)。
NodeIterator iterator = New
FilteredIterator(
??
DocumentTraversal().createNodeIterator() , … NodeFilter …);
?
這樣，
DOM
Traversal
就是一個(gè)純粹的
Iterater
Pattern
了。
特性比較
Iterator
屬于問(wèn)答模式，或者說(shuō)消費(fèi)者
/
生產(chǎn)者模式。
如果消費(fèi)者不問(wèn)不要，生產(chǎn)者就不答不給。
Iterator
的使用者完全掌握了主動(dòng)權(quán)，是控制舞步節(jié)奏的領(lǐng)舞者，隨時(shí)可以中止這場(chǎng)問(wèn)答游戲。
Iterator
的用法本身就是
Lazy
的，一問(wèn)一答，遍歷算法停在那里恭候
Iterator
使用者的調(diào)遣。
?
Visitor
則完全是被動(dòng)的，
Visitor
的提供者
/
使用者把
Visitor
扔到
Traversal
算法里面，然后運(yùn)行算法，同時(shí)祈禱并等候算法的完成（
Push and Wait
），完全失去了控制權(quán)，只能等待算法整個(gè)完成或者中止，才能重新拿到控制權(quán)。
Vistor
的用法很難做到
Lazy
，算法必須提供一些機(jī)制，接受
Visitor
每一步調(diào)用發(fā)出的指令，進(jìn)行相應(yīng)的策略選擇。
換句話說(shuō)，
Visitor
Pattern
里面的算法必須做出相應(yīng)的
Lazy
支持，而且
Visitor
必需積累前面步驟的狀態(tài)，然后判斷這次調(diào)用中發(fā)出什么樣的指令。
?
比如，有這樣一個(gè)需求：遍歷一棵樹(shù)，搜集到前
5
個(gè)名字是
Apple
的
Node
。然后返回這
5
個(gè)
Node
。假設(shè)樹(shù)遍歷算法已經(jīng)有了。
這時(shí)候采用
Iterator
Pattern
視線起來(lái)很容易。不再多說(shuō)。
Visitor Pattern
則需要：
Vistor
使用一個(gè)集合來(lái)保存每次遇到的名字是
Apple
的
Node
，每次都判斷是否已經(jīng)找到了
5
個(gè)，如果已經(jīng)找到，那么發(fā)出一個(gè)
Stop Signal
給算法。
如果遍歷算法不接受這種指令怎么辦？
只好等待算法完成。或者實(shí)在等不及，預(yù)計(jì)到后面還有上萬(wàn)個(gè)
Node
需要遍歷，那么就干脆
throw new RuntimeException(),? throw new Throwable()
。
也許算法并沒(méi)有聰明到捕獲這些
Exception
。那么這個(gè)
Trick
就成功了。外面使用一個(gè)
Try Catch
捕獲這個(gè)
Exception
。不過(guò)，這是
Very Very Bad Smell
。
?
Iterator
的應(yīng)用場(chǎng)景是這樣：
我
在商品定購(gòu)目錄上看到一個(gè)公司有我感興趣的產(chǎn)品系列。于是我打電話給該公司，要求派一個(gè)銷售代表來(lái)。銷售代表上門(mén)之后，從包里拿出一個(gè)一個(gè)的產(chǎn)品給你看，
我看了幾個(gè)，沒(méi)什么滿意的，于是打了個(gè)哈欠說(shuō)，今天就先到這里吧，下次再說(shuō)。打發(fā)了銷售代表，我就轉(zhuǎn)身去做自己的事情了。
我的地盤(pán)，我做主。這就是
Iterator
Pattern
的理念。
?
Vistior
的應(yīng)用場(chǎng)景是這樣：
我
在商品定購(gòu)目錄上看到一個(gè)公司有我感興趣的產(chǎn)品系列。于是我上門(mén)拜訪該公司，公司給我安排了一場(chǎng)產(chǎn)品性能展示，我看了幾個(gè)之后，沒(méi)有什么滿意的，于是我
說(shuō)，我肚子疼，想先回去了。遇到好心的公司代表，當(dāng)然說(shuō)，身體要緊，慢走。遇到固執(zhí)的公司代表，一定會(huì)說(shuō)，對(duì)不起，我們公司有自己的工作流程，完成產(chǎn)品演
示之前，產(chǎn)品廳的門(mén)鎖是打不開(kāi)的。我只好勃然大怒，吵吵嚷嚷（
throw exception
），期待能夠殺出重圍，這時(shí)候，假設(shè)該公司的保安系統(tǒng)反映比較靈敏（
try catch every visitor exception
），就會(huì)有幾個(gè)保安跑過(guò)來(lái)，把我按在椅子上繼續(xù)聽(tīng)講。
入鄉(xiāng)隨俗，客隨主便。別人的地盤(pán)，別人做主。這就是
Visitor Pattern
的理念。
?
Iterator Pattern
的優(yōu)勢(shì)當(dāng)然不僅如此。這只是個(gè)特殊的例子。
更常見(jiàn)的是，
Iterator
Pattern
能夠支持基于
Iterator
的很多算法。
比如，
Functional
Programming
的
Map, Reduce,
Filter
等函數(shù)都是接受一個(gè)
Iterator
(Sequence, List, Stream
等
)
。
Map, Filter
等函數(shù)還可以組合成一個(gè)新的
Iterator
。這個(gè)組合可以一直下去。
當(dāng)然，
Visitor
也是可以組合的。但是限制嚴(yán)格，缺乏擴(kuò)展性。
?
比如這樣一個(gè)需求：
有
T1
和
T2
兩棵樹(shù)。首先遍歷
T1
的
10
個(gè)
Node
，如果發(fā)現(xiàn)
Apple
，那么摘下來(lái)，然后繼續(xù)遍歷，如果
10
步都沒(méi)有發(fā)現(xiàn)
Apple
，那么切換到
T2
；遍歷
T2
的規(guī)則也是如此，
10
步之內(nèi)發(fā)現(xiàn)目標(biāo)，就繼續(xù)，否則就切換到
T1
。
Iterator Pattern
實(shí)現(xiàn)起來(lái)很簡(jiǎn)單。相當(dāng)于我是買(mǎi)方，情勢(shì)是買(mǎi)方市場(chǎng)，我可以讓兩個(gè)公司的銷售代表同時(shí)到我的公司來(lái)，我可以同時(shí)接待他們，讓他們各自按順序展示自己的產(chǎn)品。
Visitor Pattern
怎么做？情勢(shì)是賣(mài)方市場(chǎng)，我巴巴地跑上門(mén)去，看
T1
公司的產(chǎn)品展示，看了
10
個(gè)之后說(shuō)，請(qǐng)送我到
T2
公司的產(chǎn)品展示現(xiàn)場(chǎng)，我看
10
個(gè)之后，再回來(lái)。
?
一個(gè)用戶可以同時(shí)使用多個(gè)算法的
Iterator
；但是用戶的一個(gè)
Visitor
只能同時(shí)進(jìn)入一個(gè)算法。
這就是兩者核心理念的不同。
實(shí)現(xiàn)難度
讀者說(shuō)了，
Iterator
這么方便，你就使用
Iterator
好了，說(shuō)這么多干什么。
如果別人提供了
Iterator
，我當(dāng)然會(huì)使用。
?
現(xiàn)在的問(wèn)題是，假設(shè)你是算法公司的成員。你是提供
Visitor Pattern
的
API
，還是
Iterator
Pattern
的
API
？
Visitor Pattern
的實(shí)現(xiàn)比較簡(jiǎn)單。自己知道自己公司的內(nèi)部組織結(jié)構(gòu)，一個(gè)一個(gè)的遍歷，并傳遞給
Visitor
就行了。
Iterator Pattern
的實(shí)現(xiàn)難度，可以說(shuō)，那是相當(dāng)?shù)拇蟆?/span>
內(nèi)部數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單的數(shù)組、鏈表好說(shuō)，做一個(gè)類似于
Closure, Context, Continuation
的保存了當(dāng)前調(diào)用步驟（數(shù)組索引，或者當(dāng)前指針）和調(diào)用環(huán)境（內(nèi)部數(shù)據(jù)集）的結(jié)構(gòu)，返回給用戶就可以了。用戶每次調(diào)用
iterator.next
，
iterator
就把索引或指針向后移動(dòng)一下。
如果是內(nèi)部數(shù)據(jù)復(fù)雜的
Tree,
Graph
結(jié)構(gòu)，就相當(dāng)復(fù)雜了。比如是遍歷一棵樹(shù)，而且這棵樹(shù)的
Node
里面沒(méi)有
Parent
引用，那么
Iterator
必須自己維護(hù)一個(gè)棧把前面的所有的
Parent Node
都保存起來(lái)。當(dāng)用戶調(diào)用
iterator.next
的時(shí)候，
iterator
就必須檢查自己當(dāng)前的狀態(tài)，如果所有的
Child Node
都走完了，那么就要返回到上面的
Parent
，繼續(xù)檢查。
而在
Visitor
Pattern
里面，這個(gè)算法的實(shí)現(xiàn)簡(jiǎn)直是小菜一碟，只要一個(gè)簡(jiǎn)單的遞歸就夠了。計(jì)算機(jī)會(huì)自動(dòng)幫你分配和管理運(yùn)行棧，保存前面的
Parent Node
，執(zhí)行返回的時(shí)候，這個(gè)
Parent Node
又自動(dòng)交還給你。
Coroutine
有沒(méi)有簡(jiǎn)單的方法來(lái)實(shí)現(xiàn)
Iterator
Pattern API
呢？如同實(shí)現(xiàn)
Visitor
Pattern API
那樣容易？
幸福得象花兒一樣。簡(jiǎn)單得像
Visitor
一樣。能不能那樣？
?
聰明的人們把目光轉(zhuǎn)向了
Coroutine
。
Coroutine
本來(lái)是一個(gè)通用的概念。表示幾個(gè)協(xié)同工作的程序。
比如，消費(fèi)者
/
生產(chǎn)者，你走幾步，我走幾步；下棋對(duì)弈，你一步我一步。
由于協(xié)同工作的程序通常只有
2
個(gè)，而且這兩個(gè)程序交換的數(shù)據(jù)通常只有一個(gè)。于是人們就很容易想到用
Coroutine
來(lái)實(shí)現(xiàn)
Iterator
。
這里面
Iterator
就是
Coroutine
里面的生產(chǎn)者
Producer
角色，數(shù)據(jù)提供者。所以，也叫做
Generator
。
每次
Iterator
程序就是等在那里，一旦用戶（消費(fèi)者
Consumer
角色）調(diào)用了
iterator.next, Iterator
就繼續(xù)向下執(zhí)行一步，然后把當(dāng)前遇到的內(nèi)部數(shù)據(jù)的
Node
放到一個(gè)消費(fèi)者用戶能夠看到的公用的緩沖區(qū)（比如，直接放到消費(fèi)者線程棧里面的局部變量）里面，然后自己就停下來(lái)（
wait
）。然后消費(fèi)者用戶就從緩沖區(qū)里面獲得了那個(gè)
Node
。
這樣
Iterator
就可以自顧自地進(jìn)行遞歸運(yùn)算，不需要自己管理一個(gè)棧，而是迫使計(jì)算機(jī)幫助它分配和管理運(yùn)行棧。于是就實(shí)現(xiàn)了幸福得像花兒一樣，簡(jiǎn)單得像
Visitor
一樣的夢(mèng)想。
?
比如，這樣一段代碼，遍歷一棵二叉樹(shù)。
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
指令是關(guān)鍵。意思是，首先把當(dāng)前
Node
甩到用戶的數(shù)據(jù)空間，然后自己暫停運(yùn)行（類似于
java
的
thread yield
方法或者
object.wait
方法），把自己當(dāng)前運(yùn)行的線程掛起來(lái)，這樣虛擬機(jī)就為自己保存了當(dāng)前的運(yùn)行棧（
context
）。
有人說(shuō)，這不就是
continuation
嗎？
對(duì)。只是
Coroutine
這里多了一個(gè)產(chǎn)生并傳遞數(shù)據(jù)的動(dòng)作。
實(shí)現(xiàn)原理如果用
Java
Thread
表示大概就是這樣。當(dāng)然下面的代碼只是一個(gè)示意。網(wǎng)上有具體的
Java Coroutine
實(shí)現(xiàn)，具體代碼我也沒(méi)有看過(guò)，想來(lái)實(shí)現(xiàn)原理大致如此。
?
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
本身是一個(gè)
Thread
，用戶也是一個(gè)
Thread
。
Iterator Thread
把數(shù)據(jù)傳遞給
User Thread
。
說(shuō)實(shí)話，我寧可自己維護(hù)一個(gè)
Stack
，也不愿意引入
Coroutine
這類
Thread Control
的方式來(lái)實(shí)現(xiàn)
Iterator
。
總結(jié)
千言萬(wàn)語(yǔ)一句話。
Iterator
是好的，但不是免費(fèi)的。