|
在JBoss Rules 學(xué)習(xí)（一）:什么是Rule中，我們介紹了JBoss Rules中對(duì)Rule的表示,，其中提到了JBoss Rule中主要采用的RETE算法來(lái)進(jìn)行規(guī)則匹配,。下面將詳細(xì)的介紹一下RETE算法在JBoss Rule中的實(shí)現(xiàn)，最后隨便提一下JBoss Rules中也可以使用的另一種規(guī)則匹配算法Leaps,。 1.Rete 算法 ： Rete 在拉丁語(yǔ)中是 ”net” ,，有網(wǎng)絡(luò)的意思。 RETE 算法可以分為兩部分：規(guī)則編譯（ rule compilation ）和運(yùn)行時(shí)執(zhí)行（ runtime execution ）,。 編譯算法描述了規(guī)則如何在 Production Memory 中產(chǎn)生一個(gè)有效的辨別網(wǎng)絡(luò),。用一個(gè)非技術(shù)性的詞來(lái)說(shuō)，一個(gè)辨別網(wǎng)絡(luò)就是用來(lái)過(guò)濾數(shù)據(jù),。方法是通過(guò)數(shù)據(jù)在網(wǎng)絡(luò)中的傳播來(lái)過(guò)濾數(shù)據(jù),。在頂端節(jié)點(diǎn)將會(huì)有很多匹配的數(shù)據(jù)。當(dāng)我們順著網(wǎng)絡(luò)向下走,，匹配的數(shù)據(jù)將會(huì)越來(lái)越少,。在網(wǎng)絡(luò)的最底部是終端節(jié)點(diǎn)（ terminal nodes ）。在 Dr Forgy 的 1982 年的論文中,，他描述了 4 種基本節(jié)點(diǎn)： root , 1-input, 2-input and terminal ,。下圖是 Drools 中的 RETE 節(jié)點(diǎn)類型：  Figure 1. Rete Nodes 根節(jié)點(diǎn)（ RootNode ）是所有的對(duì)象進(jìn)入網(wǎng)絡(luò)的入口,。然后，從根節(jié)點(diǎn)立即進(jìn)入到 ObjectTypeNode ,。 ObjectTypeNode 的作用是使引擎只做它需要做的事情,。例如，我們有兩個(gè)對(duì)象集： Account 和 Order ,。如果規(guī)則引擎需要對(duì)每個(gè)對(duì)象都進(jìn)行一個(gè)周期的評(píng)估,，那會(huì)浪費(fèi)很多的時(shí)間。為了提高效率,，引擎將只讓匹配 object type 的對(duì)象通過(guò)到達(dá)節(jié)點(diǎn),。通過(guò)這種方法，如果一個(gè)應(yīng)用 assert 一個(gè)新的 account ,，它不會(huì)將 Order 對(duì)象傳遞到節(jié)點(diǎn)中,。很多現(xiàn)代 RETE 實(shí)現(xiàn)都有專門的 ObjectTypeNode 。在一些情況下,， ObjectTypeNode 被用散列法進(jìn)一步優(yōu)化,。
Figure 2 . ObjectTypeNodes ObjectTypeNode 能夠傳播到 AlphaNodes, LeftInputAdapterNodes 和 BetaNodes 。 1-input 節(jié)點(diǎn)通常被稱為 AlphaNode ,。 AlphaNodes 被用來(lái)評(píng)估字面條件（ literal conditions ）,。雖然， 1982 年的論文只提到了相等條件（指的字面上相等）,，很多 RETE 實(shí)現(xiàn)支持其他的操作,。例如， Account.name = = “Mr Trout” 是一個(gè)字面條件,。當(dāng)一條規(guī)則對(duì)于一種 object type 有多條的字面條件,，這些字面條件將被鏈接在一起。這是說(shuō),，如果一個(gè)應(yīng)用 assert 一個(gè) account 對(duì)象,，在它能到達(dá)下一個(gè) AlphaNode 之前，它必須先滿足第一個(gè)字面條件,。在 Dr. Forgy 的論文中,，他用 IntraElement conditions 來(lái)表述。下面的圖說(shuō)明了 Cheese 的 AlphaNode 組合（ name = = “cheddar” ,， strength = = “strong” ）：  Figure 3. AlphaNodes Drools 通過(guò)散列法優(yōu)化了從 ObjectTypeNode 到 AlphaNode 的傳播,。每次一個(gè) AlphaNode 被加到一個(gè) ObjectTypeNode 的時(shí)候，就以字面值（ literal value ）作為 key ,，以 AlphaNode 作為 value 加入 HashMap ,。當(dāng)一個(gè)新的實(shí)例進(jìn)入 ObjectTypeNode 的時(shí)候，不用傳遞到每一個(gè) AlphaNode ,，它可以直接從 HashMap 中獲得正確的 AlphaNode ,，避免了不必要的字面檢查,。 <!--[if !supportEmptyParas]--> 2-input 節(jié)點(diǎn)通常被稱為 BetaNode 。 Drools 中有兩種 BetaNode ： JoinNode 和 NotNode ,。 BetaNodes 被用來(lái)對(duì) 2 個(gè)對(duì)象進(jìn)行對(duì)比,。這兩個(gè)對(duì)象可以是同種類型，也可以是不同類型,。 我們約定 BetaNodes 的 2 個(gè)輸入稱為左邊（ left ）和右邊（ right ）,。一個(gè) BetaNode 的左邊輸入通常是 a list of objects 。在 Drools 中,，這是一個(gè)數(shù)組,。右邊輸入是 a single object 。兩個(gè) NotNode 可以完成‘ exists ’檢查,。 Drools 通過(guò)將索引應(yīng)用在 BetaNodes 上擴(kuò)展了 RETE 算法,。下圖展示了一個(gè) JoinNode 的使用：
Figure 4 . JoinNode 注意到圖中的左邊輸入用到了一個(gè) LeftInputAdapterNode ，這個(gè)節(jié)點(diǎn)的作用是將一個(gè) single Object 轉(zhuǎn)化為一個(gè)單對(duì)象數(shù)組（ single Object Tuple ）,，傳播到 JoinNode 節(jié)點(diǎn),。因?yàn)槲覀兩厦嫣岬竭^(guò)左邊輸入通常是 a list of objects 。 <!--[if !supportEmptyParas]--> Terminal nodes 被用來(lái)表明一條規(guī)則已經(jīng)匹配了它的所有條件（ conditions ）,。 在這點(diǎn),，我們說(shuō)這條規(guī)則有了一個(gè)完全匹配（ full match ）。在一些情況下,，一條帶有“或”條件的規(guī)則可以有超過(guò)一個(gè)的 terminal node ,。 Drools 通過(guò)節(jié)點(diǎn)的共享來(lái)提高規(guī)則引擎的性能。因?yàn)楹芏嗟囊?guī)則可能存在部分相同的模式,，節(jié)點(diǎn)的共享允許我們對(duì)內(nèi)存中的節(jié)點(diǎn)數(shù)量進(jìn)行壓縮,，以提供遍歷節(jié)點(diǎn)的過(guò)程,。下面的兩個(gè)規(guī)則就共享了部分節(jié)點(diǎn)：
rule
when Cheese( $chedddar : name == " cheddar " ) $person : Person( favouriteCheese == $cheddar ) then System.out.println( $person.getName() + " likes cheddar " ); end
rule
when Cheese( $chedddar : name == " cheddar " ) $person : Person( favouriteCheese != $cheddar ) then System.out.println( $person.getName() + " does likes cheddar " ); end
這里我們先不探討這兩條 rule 到的是什么意思,，單從一個(gè)直觀的感覺(jué)，這兩條 rule 在它們的 LHS 中基本都是一樣的,，只是最后的 favouriteCheese ,，一條規(guī)則是等于 $cheddar ，而另一條規(guī)則是不等于 $cheddar ,。下面是這兩條規(guī)則的節(jié)點(diǎn)圖：
Figure 5 . Node Sharing 從圖上可以看到,，編譯后的 RETE 網(wǎng)絡(luò)中， AlphaNode 是共享的,，而 BetaNode 不是共享的,。上面說(shuō)的相等和不相等就體現(xiàn)在 BetaNode 的不同。然后這兩條規(guī)則有各自的 Terminal Node ,。 <!--[if !supportEmptyParas]--> RETE 算法的第二個(gè)部分是運(yùn)行時(shí)（ runtime ）,。當(dāng)一個(gè)應(yīng)用 assert 一個(gè)對(duì)象,，引擎將數(shù)據(jù)傳遞到 root node 。從那里,，它進(jìn)入 ObjectTypeNode 并沿著網(wǎng)絡(luò)向下傳播,。當(dāng)數(shù)據(jù)匹配一個(gè)節(jié)點(diǎn)的條件，節(jié)點(diǎn)就將它記錄到相應(yīng)的內(nèi)存中,。這樣做的原因有以下幾點(diǎn)：主要的原因是可以帶來(lái)更快的性能,。雖然記住完全或部分匹配的對(duì)象需要內(nèi)存，它提供了速度和可伸縮性的特點(diǎn),。當(dāng)一條規(guī)則的所有條件都滿足,，這就是完全匹配。而只有部分條件滿足,，就是部分匹配,。（我覺(jué)得引擎在每個(gè)節(jié)點(diǎn)都有其對(duì)應(yīng)的內(nèi)存來(lái)儲(chǔ)存滿足該節(jié)點(diǎn)條件的對(duì)象，這就造成了如果一個(gè)對(duì)象是完全匹配,，那這個(gè)對(duì)象就會(huì)在每個(gè)節(jié)點(diǎn)的對(duì)應(yīng)內(nèi)存中都存有其映象,。） 2. Leaps 算法： Production systems 的 Leaps 算法使用了一種“ lazy ”方法來(lái)評(píng)估條件（ conditions ）。一種 Leaps 算法的修改版本的實(shí)現(xiàn),，作為 Drools v3 的一部分,，嘗試結(jié)合 Leaps 和 RETE 方法的最好的特點(diǎn)來(lái)處理 Working Memory 中的 facts 。 古典的 Leaps 方法將所有的 asserted 的 facts ,，按照其被 asserted 在 Working Memory 中的順序（ FIFO ）,，放在主堆棧中。它一個(gè)個(gè)的檢查 facts ,，通過(guò)迭代匹配 data type 的 facts 集合來(lái)找出每一個(gè)相關(guān)規(guī)則的匹配,。當(dāng)一個(gè)匹配的數(shù)據(jù)被發(fā)現(xiàn)時(shí)，系統(tǒng)記住此時(shí)的迭代位置以備待會(huì)的繼續(xù)迭代,，并且激發(fā)規(guī)則結(jié)果（ consequence ）,。當(dāng)結(jié)果（ consequence ）執(zhí)行完成以后，系統(tǒng)就會(huì)繼續(xù)處理處于主堆棧頂部的 fact ,。如此反復(fù),。 |
|
|
