clant

Figure 3.?AlphaNodes

Drools 通過散列法優(yōu)化了從 ObjectTypeNode 到 AlphaNode 的傳播。每次一個 AlphaNode 被加到一個 ObjectTypeNode 的時候，就以字面值（ literal value ）作為 key ，以 AlphaNode 作為 value 加入 HashMap 。當(dāng)一個新的實例進入 ObjectTypeNode 的時候，不用傳遞到每一個 AlphaNode ，它可以直接從 HashMap 中獲得正確的 AlphaNode ，避免了不必要的字面檢查。

<!--[if !supportEmptyParas]-->

2-input 節(jié)點通常被稱為 BetaNode 。 Drools 中有兩種 BetaNode ： JoinNode 和 NotNode 。 BetaNodes 被用來對 2 個對象進行對比。這兩個對象可以是同種類型，也可以是不同類型。

我們約定 BetaNodes 的 2 個輸入稱為左邊（ left ）和右邊（ right ）。一個 BetaNode 的左邊輸入通常是 a list of objects 。在 Drools 中，這是一個數(shù)組。右邊輸入是 a single object 。兩個 NotNode 可以完成‘ exists ’檢查。 Drools 通過將索引應(yīng)用在 BetaNodes 上擴展了 RETE 算法。下圖展示了一個 JoinNode 的使用：

Figure 4 .?JoinNode

注意到圖中的左邊輸入用到了一個 LeftInputAdapterNode ，這個節(jié)點的作用是將一個 single Object 轉(zhuǎn)化為一個單對象數(shù)組（ single Object Tuple ），傳播到 JoinNode 節(jié)點。因為我們上面提到過左邊輸入通常是 a list of objects 。

<!--[if !supportEmptyParas]-->

Terminal nodes 被用來表明一條規(guī)則已經(jīng)匹配了它的所有條件（ conditions ）。 在這點，我們說這條規(guī)則有了一個完全匹配（ full match ）。在一些情況下，一條帶有“或”條件的規(guī)則可以有超過一個的 terminal node 。

Drools 通過節(jié)點的共享來提高規(guī)則引擎的性能。因為很多的規(guī)則可能存在部分相同的模式，節(jié)點的共享允許我們對內(nèi)存中的節(jié)點數(shù)量進行壓縮，以提供遍歷節(jié)點的過程。下面的兩個規(guī)則就共享了部分節(jié)點：

這里我們先不探討這兩條 rule 到的是什么意思，單從一個直觀的感覺，這兩條 rule 在它們的 LHS 中基本都是一樣的，只是最后的 favouriteCheese ，一條規(guī)則是等于 $cheddar ，而另一條規(guī)則是不等于 $cheddar 。下面是這兩條規(guī)則的節(jié)點圖：

Figure 5 .?Node Sharing

從圖上可以看到，編譯后的 RETE 網(wǎng)絡(luò)中， AlphaNode 是共享的，而 BetaNode 不是共享的。上面說的相等和不相等就體現(xiàn)在 BetaNode 的不同。然后這兩條規(guī)則有各自的 Terminal Node 。

<!--[if !supportEmptyParas]-->

RETE 算法的第二個部分是運行時（ runtime ）。當(dāng)一個應(yīng)用 assert 一個對象，引擎將數(shù)據(jù)傳遞到 root node 。從那里，它進入 ObjectTypeNode 并沿著網(wǎng)絡(luò)向下傳播。當(dāng)數(shù)據(jù)匹配一個節(jié)點的條件，節(jié)點就將它記錄到相應(yīng)的內(nèi)存中。這樣做的原因有以下幾點：主要的原因是可以帶來更快的性能。雖然記住完全或部分匹配的對象需要內(nèi)存，它提供了速度和可伸縮性的特點。當(dāng)一條規(guī)則的所有條件都滿足，這就是完全匹配。而只有部分條件滿足，就是部分匹配。（我覺得引擎在每個節(jié)點都有其對應(yīng)的內(nèi)存來儲存滿足該節(jié)點條件的對象，這就造成了如果一個對象是完全匹配，那這個對象就會在每個節(jié)點的對應(yīng)內(nèi)存中都存有其映象。）

2. Leaps 算法：

Production systems 的 Leaps 算法使用了一種“ lazy ”方法來評估條件（ conditions ）。一種 Leaps 算法的修改版本的實現(xiàn)，作為 Drools v3 的一部分，嘗試結(jié)合 Leaps 和 RETE 方法的最好的特點來處理 Working Memory 中的 facts 。

古典的 Leaps 方法將所有的 asserted 的 facts ，按照其被 asserted 在 Working Memory 中的順序（ FIFO ），放在主堆棧中。它一個個的檢查 facts ，通過迭代匹配 data type 的 facts 集合來找出每一個相關(guān)規(guī)則的匹配。當(dāng)一個匹配的數(shù)據(jù)被發(fā)現(xiàn)時，系統(tǒng)記住此時的迭代位置以備待會的繼續(xù)迭代，并且激發(fā)規(guī)則結(jié)果（ consequence ）。當(dāng)結(jié)果（ consequence ）執(zhí)行完成以后，系統(tǒng)就會繼續(xù)處理處于主堆棧頂部的 fact 。如此反復(fù)。