?

前言:
　　規(guī)則引擎中, 往往涉及到多個(gè)條件構(gòu)成了復(fù)雜布爾表達(dá)式的計(jì)算. 對(duì)于這類布爾表達(dá)式, 一是動(dòng)態(tài)可變的(取決于運(yùn)營人員的設(shè)定), 二是其表達(dá)式往往很復(fù)雜. 如何快速的計(jì)算其表達(dá)式的值, 該系列文章將以兩種方式, Antlr4動(dòng)態(tài)生成AST(抽象語法樹), 以及Groovy動(dòng)態(tài)編譯的方式來對(duì)比評(píng)估, 看看哪種方式性能更優(yōu), 以及各自的優(yōu)缺點(diǎn). 本篇文章將側(cè)重于介紹Antlr4的實(shí)現(xiàn)思路.

模型簡(jiǎn)化:
　　每個(gè)規(guī)則可以理解為多個(gè)條件構(gòu)建的復(fù)雜布爾表達(dá)式, 而條件本身涉及不同的變量和閾值(常量), 以及中間的操作符(>=, >, <, <=, !=, =).
　　比如某個(gè)具體的規(guī)則:

rule = expr1 && (expr2 || expr3) || expr4

　　而其具體條件expr1/expr2/expr3/expr4如下:

expr1 => var1 >= 20 expr2 => var2 != 10 expr3 => var3 < 3.0 expr4 => var4 = true

　　為了簡(jiǎn)化評(píng)估, 我們簡(jiǎn)單設(shè)定每個(gè)條件就是一個(gè)布爾變量(bool). 這樣每個(gè)規(guī)則rule就可以理解為多個(gè)布爾變量, 通過&&和||組合的表達(dá)式了, 簡(jiǎn)單描述為:

rule = 1 && (2 || 3) || 4

　　數(shù)字N(1,2,...)為具體的布爾變量, 類似這樣的簡(jiǎn)化模型, 方便性能評(píng)估.?

Antlr4構(gòu)建:
　　Anltr4是基于LL(K), 以遞歸下降的方式進(jìn)行工作. 它能自動(dòng)完成語法分析和詞法分析過程，并生產(chǎn)框架代碼.
　　具體可參閱文章: 利用ANTLR4實(shí)現(xiàn)一個(gè)簡(jiǎn)單的四則運(yùn)算計(jì)算器, 作為案列參考.
　　其實(shí)表達(dá)式解析比四則混合運(yùn)算的語法gammar還要簡(jiǎn)單.
　　編寫EasyDSL.g4文件:

grammar EasyDSL;/** PARSER */ line : expr EOF ; expr: '(' expr ')' # parenExpr| expr '&&' expr # andEpr| expr '||' expr # orEpr| ID # identifier ;/** LEXER */ WS : [ \t\n\r]+ -> skip ; ID : DIGIT+ ; fragment DIGIT : '0'..'9';

　　其在idea工程中, 如下所示:
　　
　　配置pom.xml, 添加dependency和plugin.

<dependencies><dependency><groupId>org.antlr</groupId><artifactId>antlr4-runtime</artifactId><version>4.3</version></dependency></dependencies><plugins><build><plugin><groupId>org.antlr</groupId><artifactId>antlr4-maven-plugin</artifactId><version>4.3</version><executions><execution><id>antlr</id><goals><goal>antlr4</goal></goals><!--<phase>none</phase>--></execution></executions><configuration><outputDirectory>src/main/java</outputDirectory><listener>true</listener><treatWarningsAsErrors>true</treatWarningsAsErrors></configuration></plugin></plugins></build>

　　具體執(zhí)行命令

mvn antlr4:antlr4

　　則生成對(duì)應(yīng)的代碼
　　

?

代碼擴(kuò)展:
　　Antlr4幫我們構(gòu)建了基礎(chǔ)的詞法和語法解析后, 后續(xù)工作需要我們自己做些功能擴(kuò)展.
　　首先我們定義操作枚舉類:

package com.dsl.perfs;public enum ExprType {AND,OR,ID;}

　　然后是具體的節(jié)點(diǎn)類:

package com.dsl.perfs;public class ExprNode {public ExprType type;public String id;public ExprNode left;public ExprNode right;public ExprNode(ExprType type, String id, ExprNode left, ExprNode right) {this.type = type;this.id = id;this.left = left;this.right = right;}}

　　最后重載Listener類, 對(duì)這可抽象語法樹進(jìn)行構(gòu)建.

package com.dsl.perfs;import com.dsl.ast.EasyDSLBaseListener; import com.dsl.ast.EasyDSLParser; import org.antlr.v4.runtime.misc.NotNull;import java.util.Stack;public class EasyDSLListener extends EasyDSLBaseListener {private Stack<ExprNode> stacks = new Stack<>();@Overridepublic void exitIdentifier(@NotNull EasyDSLParser.IdentifierContext ctx) {stacks.push(new ExprNode(ExprType.ID, ctx.getText(), null, null));}@Overridepublic void exitAndEpr(@NotNull EasyDSLParser.AndEprContext ctx) {ExprNode right = stacks.pop();ExprNode left = stacks.pop();stacks.push(new ExprNode(ExprType.AND, null, left, right));}@Overridepublic void exitOrEpr(@NotNull EasyDSLParser.OrEprContext ctx) {ExprNode right = stacks.pop();ExprNode left = stacks.pop();stacks.push(new ExprNode(ExprType.OR, null, left, right));}@Overridepublic void exitLine(@NotNull EasyDSLParser.LineContext ctx) {super.exitLine(ctx);}@Overridepublic void exitParenExpr(@NotNull EasyDSLParser.ParenExprContext ctx) {// DO NOTHING}public ExprNode getResult() {return stacks.peek();}}

　　以下是工具類, 其具體構(gòu)建AST, 并進(jìn)行具體的值評(píng)估.

package com.dsl.perfs;import com.dsl.ast.EasyDSLLexer; import com.dsl.ast.EasyDSLParser; import org.antlr.v4.runtime.ANTLRInputStream; import org.antlr.v4.runtime.CommonTokenStream;import java.util.Map; import java.util.concurrent.ConcurrentHashMap;public class ExprEvalutorHelper {private static ConcurrentHashMap<String, ExprNode> exprAstClassMap = new ConcurrentHashMap();public static boolean exec(String expr, Map<String, Boolean> params) {ExprNode root = exprAstClassMap.get(expr);if ( root == null ) {synchronized (expr.intern()) {if ( root == null ) {EasyDSLLexer lexer = new EasyDSLLexer(new ANTLRInputStream(expr));/* 根據(jù)lexer 創(chuàng)建token stream */CommonTokenStream tokens = new CommonTokenStream(lexer);/* 根據(jù)token stream 創(chuàng)建 parser */EasyDSLParser paser = new EasyDSLParser(tokens);/* 為parser添加一個(gè)監(jiān)聽器 */EasyDSLListener listener = new EasyDSLListener();paser.addParseListener(listener);/* 匹配 line, 監(jiān)聽器會(huì)記錄結(jié)果 */paser.line();root = listener.getResult();exprAstClassMap.put(expr, root);}}}return ExprEvalutorHelper.evalute(root, params);}public static boolean evalute(ExprNode cur, Map<String, Boolean> params) {if ( cur.type == ExprType.ID ) {return params.get(cur.id);} else {if ( cur.type == ExprType.AND ) {boolean leftRes = evalute(cur.left, params);// *) 剪枝優(yōu)化if ( leftRes == false ) return false;boolean rightRes = evalute(cur.right, params);return leftRes && rightRes;} else {// *) 如果為 ORboolean leftRes = evalute(cur.left, params);// *) 剪枝優(yōu)化if ( leftRes == true ) return true;boolean rightRes = evalute(cur.right, params);return leftRes || rightRes;}}}}

　　以表達(dá)式

1 && 2 || 3 || 4 && (5 || 6)

　　為例, 其最后最后的AST樹如下所示:
　　

測(cè)試評(píng)估:
　　編寫如下測(cè)試代碼, 來進(jìn)行性能評(píng)估:

package com.dsl.comp;import com.dsl.perfs.ExprEvalutorHelper;import java.util.Map; import java.util.Random; import java.util.TreeMap;public class AntlrPerf {public static void main(String[] args) {String boolExpr = "1 && 2 || 3 || 4 && (5 || 6)";int iterNums = 1000000;long randomSeed = 10001L;Random random = new Random(randomSeed);Long beg = System.currentTimeMillis();for ( int i = 0; i<=iterNums; i++ ) {Map<String, Boolean> params = new TreeMap<>();params.put("1", random.nextBoolean());params.put("2", random.nextBoolean());params.put("3", random.nextBoolean());params.put("4", random.nextBoolean());params.put("5", random.nextBoolean());params.put("6", random.nextBoolean());ExprEvalutorHelper.exec(boolExpr, params);}long end = System.currentTimeMillis();System.out.println(String.format("total consume: %dms", end - beg));}}

　　測(cè)試結(jié)果如下:

total consume: 755ms　　

　　100萬次計(jì)算, 累計(jì)消耗755ms, 似乎不錯(cuò). 但是具體的性能好壞, 需要對(duì)比, 下篇將使用Groovy方式去實(shí)現(xiàn), 并進(jìn)行對(duì)比.?

總結(jié):
　　文章介紹了Antlr去解析評(píng)估復(fù)雜布爾表達(dá)式的思路, 其性能也相當(dāng)?shù)目陀^, 下文將介紹Groovy的方式去評(píng)估, 看看兩者性能差異, 以及優(yōu)缺點(diǎn).

轉(zhuǎn)載于:https://www.cnblogs.com/mumuxinfei/p/8474375.html

總結(jié)

以上是生活随笔為你收集整理的复杂的动态布尔表达式性能评估(1)--Antlr4实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。