Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Compare AST and RPN evaluation performance
/*
There is an AST (Abstract syntax tree) in JSON format.
AST represents Excel spreadsheet formula.
Is it possible in JavaScript to make RPN (Reverse Polish Notation) faster than AST?
AST evaluation is recusive and RPN evaluation is iterative.
But in any case, AST evaluation is faster despite recursion.
I guess that the main problem is in using dynamic js arrays to emulate stack.
Would RPN win if it was written in C/C++?
If C++ version of RPN is faster than AST. Then there is one more question.
Wil be RPN still faster after conversion C++ to asm.js?
*/
// EVALUATOR
function Evaluator() {
this.isBinaryFunction = {
'+': true,
'-': true,
'*': true,
'/': true
};
this.functions = {
'+': function(args) {
return args[0] + args[1];
},
'-': function(args) {
return args[0] - args[1];
},
'*': function(args) {
return args[0] * args[1];
},
'/': function(args) {
return args[0] / args[1];
},
'SUM': function(args) {
var sum = 0;
for ( var i = 0; i < args.length; i++ ) {
sum += args[i]
}
return sum;
}
};
}
Evaluator.prototype = {
evaluateRPN: function(rpn) {
if ( ! Array.isArray(rpn) ) {
return rpn;
}
var evaluationStack = [];
for (var i = 0; i < rpn.length; i++) {
var token = rpn[i];
if ( token === '^' ) {
var oper = evaluationStack.pop();
var func = this.functions[oper];
var arity = this.isBinaryFunction[oper] ? 2 : evaluationStack.pop();
var args = [];
for (var j = 0; j < arity; j++) {
args.push( evaluationStack.pop() );
}
var res = func(args);
evaluationStack.push(res);
} else {
evaluationStack.push(token);
}
}
return evaluationStack.pop();
},
evaluateAST: function(ast) {
if ( ! Array.isArray(ast) ) {
return ast;
}
var oper = ast[0];
var func = this.functions[oper];
var evaluatedArgs = [];
for (var i = 1; i < ast.length; i++) {
evaluatedArgs.push( this.evaluateAST(ast[i]) );
}
var res = func(evaluatedArgs);
return res;
}
}
// AST to RPN Convetor
var isBinaryFunction = {
'+': true,
'-': true,
'*': true,
'/': true
};
function AST2RPN(ast, rpn) {
var isReady = false;
if (!rpn) {
isReady = true;
rpn = []
};
if (!Array.isArray(ast)){
rpn.push(ast);
return ast;
}
var operator = ast[0];
rpn.push('^'); // operator flag
rpn.push(operator);
if (! isBinaryFunction[operator] ) {
// push number of arguments for not binary functions
rpn.push(ast.length-1);
}
for (var i = 1; i < ast.length; i++) {
var arg = ast[i];
AST2RPN(arg,rpn);
};
if (isReady) {
return rpn.reverse();
}
}
// BENCHMARK
function timeRPN(rpn) {
var evaluator = new Evaluator();
console.time('EVALUATE RPN');
for (var i = 0; i < 1000000; i++) {
var res = evaluator.evaluateRPN(rpn);
}
console.timeEnd('EVALUATE RPN');
}
function timeAST(ast) {
var evaluator = new Evaluator();
console.time('EVALUATE AST');
for (var i = 0; i < 1000000; i++) {
var res = evaluator.evaluateAST(ast);
}
console.timeEnd('EVALUATE AST');
}
var ast1 = ['SUM',
[ '-',['+',['/',['*',10,20],30],40],50],
[ '-',['+',['/',['*',10,20],30],40],50],
[ '-',['+',['/',['*',10,20],30],40],50],
[ '-',['+',['/',['*',10,20],30],40],50]
];
var rpn1 = AST2RPN(ast1);
timeRPN(rpn1);
timeAST(ast1);
@Fonger

This comment has been minimized.

Copy link

@Fonger Fonger commented Jun 21, 2018

Great test. Thank you!

@breeswish

This comment has been minimized.

Copy link

@breeswish breeswish commented Dec 12, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment