Skip to content

Instantly share code, notes, and snippets.

@amok

amok/ast vs rpn.js

Forked from koorchik/ast vs rpn.js
Last active August 29, 2015 14:03
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save amok/9f61b1234695f35c290e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save amok/9f61b1234695f35c290e to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. koma revised this gist Jul 13, 2014. 1 changed file with 16 additions and 10 deletions.
    26 changes: 16 additions & 10 deletions ast vs rpn.js
    View file
    Original file line number Diff line number Diff line change
    @@ -53,29 +53,35 @@ Evaluator.prototype = {
    return rpn;
    }

    var evaluationStack = [];

    var evaluationStack = new Array(rpn.length); // -200ms
    var length = 0; // -100ms

    for (var i = 0; i < rpn.length; i++) {
    var token = rpn[i];

    if ( token === '^' ) {
    var oper = evaluationStack.pop();
    var oper = evaluationStack[--length];
    var func = this.functions[oper];
    var arity = this.isBinaryFunction[oper] ? 2 : evaluationStack.pop();
    var arity =
    oper === '+' ||
    oper === '-' ||
    oper === '*' ||
    oper === '/' // -200ms
    ? 2 : evaluationStack[--length];

    var args = [];
    for (var j = 0; j < arity; j++) {
    args.push( evaluationStack.pop() );
    args[j] = evaluationStack[--length]; // -800ms
    }

    var res = func(args);
    evaluationStack.push(res);
    evaluationStack[length++] = res;
    } else {
    evaluationStack.push(token);
    evaluationStack[length++] = token;
    }
    }

    return evaluationStack.pop();
    return evaluationStack[--length];
    },

    evaluateAST: function(ast) {
    @@ -89,7 +95,7 @@ Evaluator.prototype = {
    var evaluatedArgs = [];

    for (var i = 1; i < ast.length; i++) {
    evaluatedArgs.push( this.evaluateAST(ast[i]) );
    evaluatedArgs[i-1] = this.evaluateAST(ast[i]); // -700ms
    }

    var res = func(evaluatedArgs);
    @@ -180,4 +186,4 @@ var rpn1 = AST2RPN(ast1);


    timeRPN(rpn1);
    timeAST(ast1);
    timeAST(ast1);
  2. @koorchik koorchik revised this gist Jul 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion ast vs rpn.js
    View file
    Original file line number Diff line number Diff line change
    @@ -50,7 +50,7 @@ function Evaluator() {
    Evaluator.prototype = {
    evaluateRPN: function(rpn) {
    if ( ! Array.isArray(rpn) ) {
    return value;
    return rpn;
    }

    var evaluationStack = [];
  3. @koorchik koorchik revised this gist Jul 13, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion ast vs rpn.js
    View file
    Original file line number Diff line number Diff line change
    @@ -8,7 +8,7 @@
    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.
    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?
    */

  4. @koorchik koorchik revised this gist Jul 13, 2014. 1 changed file with 8 additions and 4 deletions.
    12 changes: 8 additions & 4 deletions ast vs rpn.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,11 +1,15 @@
    /*
    There is an AST (Abstract syntax tree) in JSON format. AST represents Excel spreadsheet formula.
    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++?
    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?
    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
  5. @koorchik koorchik revised this gist Jul 13, 2014. 1 changed file with 10 additions and 0 deletions.
    10 changes: 10 additions & 0 deletions ast vs rpn.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,13 @@
    /*
    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() {
  6. @koorchik koorchik revised this gist Jul 13, 2014. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions ast vs rpn.js
    View file
    Original file line number Diff line number Diff line change
    @@ -72,13 +72,13 @@ Evaluator.prototype = {
    var oper = ast[0];
    var func = this.functions[oper];

    var preparedArgs = [];
    var evaluatedArgs = [];

    for (var i = 1; i < ast.length; i++) {
    preparedArgs.push( this.evaluateAST(ast[i]) );
    evaluatedArgs.push( this.evaluateAST(ast[i]) );
    }

    var res = func(preparedArgs);
    var res = func(evaluatedArgs);

    return res;
    }
  7. @koorchik koorchik renamed this gist Jul 13, 2014. 1 changed file with 0 additions and 0 deletions.
    0 ast vs rpn → ast vs rpn.js
    View file
    File renamed without changes.
  8. @koorchik koorchik created this gist Jul 13, 2014.
    169 changes: 169 additions & 0 deletions ast vs rpn
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,169 @@
    // 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 preparedArgs = [];

    for (var i = 1; i < ast.length; i++) {
    preparedArgs.push( this.evaluateAST(ast[i]) );
    }

    var res = func(preparedArgs);

    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);