-
-
Save amok/9f61b1234695f35c290e to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| 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. Than 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 value; | |
| } | |
| 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); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment