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