Saturday, September 29, 2012

Database caching, NHibernate and Redis-powered

How we wish, that with a flick of a switch, this sample query will perform as fast as you needed it be when it’s repeatedly called:


var peopleList =
   (from p in session.Query<Person>()
     .Fetch(x => x.CountryBorned)
    orderby p.CountryBorned.CountryId, p.PersonId 
    select new { PersonName = p.PersonName, BornedAt = p.CountryBorned.CountryName }).ToList();
                    


Fortunately for folks who are using good ORM like NHibernate, it has a mechanism to do so:


var peopleList =
  (from p in session.Query<Person>()
    .Fetch(x => x.CountryBorned)
    .Cacheable() // do my bidding automagically
   orderby p.CountryBorned.CountryId, p.PersonId 
   select new { PersonName = p.PersonName, BornedAt = p.CountryBorned.CountryName }).ToList();



You can do your own manual caching but that would be a little problematic when the user adds, update or delete a record. They would be mildly amused when they can’t see what they have saved, imagine opening an Excel file from a network drive and it gives you the yesterday version of it, instead of the one you have edited earlier this morning just because your network doesn’t employ smarter way to cache things. In this regard, the system leaks an abstraction, your users would no longer think that a network drive is the same thing as the drives (thumbdrives, memory card, etc) they are familiar with. You then need to inform your users all the wonderful things about caching and whathaveyou.


With NHibernate’s caching, your cache won't ever become stale as long as all your data manipulation goes through it, just follow this simple rule, and you are golden. You and NHibernate will be chums for life. With a caching mechanism bolted right to your ORM, stale cache is a thing of the past. That’s the advantage if things are seamlessly integrated, It Just Works.



See the demo code here: https://github.com/MichaelBuen/Demo_NHibernate_Plus_Redis


Here's the benchmark that I've used:
function test() {
 
 var start = new Date().getTime();
 
 var content = $('table > tbody');
 
 var repeat = 200;
 
 var z = 0;
 for (i = 1; i <= repeat; ++i) {
 
  $.ajax({ url: '/Home/People', success: function (data) {
 
   ++z;
 
   if (z == repeat) {
    var elapsed = new Date().getTime() - start;
    $('#hei').text(elapsed);
   }
 
   content.empty();
 
   for (var x in data) {
    var p = data[x];
 
    var newRow = $('<tr/>');
    var tdN = $('<td/>').text(z);
    var tdLastname = $('<td/>').text(p.PersonName);
    var tdFirstname = $('<td/>').text(p.BornedAt);
 
    newRow.append(tdN).append(tdLastname).append(tdFirstname);
 
 
    content.append(newRow);
 
   }
 
  }, async: true
  , error: function (a, b, c) { alert(a); }
  });
 }
 
 
}


It pounds the web server 200 times, then it shows the elapsed time. On my machine, without caching it took 38 seconds, with caching it's just 23 seconds.


On the demo solution, I also included a commandline project where you can persist an object to the database. NHibernate caching can see when you persist an object to the database, and it can cache those objects on-the-fly.


To setup Redis caching with NHibernate, just follow this instruction: http://www.d80.co.uk/post/2011/05/17/NHibernate-Caching-with-Redis.aspx

Thursday, September 13, 2012

Shunting-yard algorithm and RPN computer

The father of non-cross-platform Java(read: J++) is so moving to JavaScript


"Java used to be cross-platform but is no longer cross-platform; the new cross-platform language in town is JavaScript" -- Anders Hejlsberg


It would be ironic if he would introduce another variant of JavaScript. They could be making IE's JavaScript uberfast, or they could make a transpiler(portmanteau of translator and compiler) for C# to JavaScript. They could even introduce another MVC framework for JavaScript, I'm pining for this.


If you wanted to see a glimpse of future JavaScript programming, you can check AngularJS. It's an MVC framework for JavaScript that allows Web Developers to do JavaScript programming sans the DOM/HTML concerns(for Web Designers). As with any MVC framework, AngularJS allows your Controller to be free from View concerns, View just receive values from Model; lastly, Controller doesn't directly manipulate the View, it just feed the View with Model. Proper separation of concerns at its finest.


An MVC example, expression evaluator: http://jsfiddle.net/7jh9f/2/


The expression evaluator utilizes Shunting-yard algorithm and RPN evaluator. The jsFiddle example let you visualize how those two algorithms works. With MVC, your algorithm(at the Controller) doesn't need to manipulate the HTML(View) in order to make visualization for the algorithm's steps; it's the other way around, the View automagically react to the values of your Model(which is the only thing your algorithm(at the Controller) directly manipulates), your View is able to reflect how your algorithm works.

Model and Controller:

function Controller($scope) {
    
    // $scope is similar to *this* keyword of OOP, it disambiguates local variable
    // against the class-level variable
    
    // ====Model====
    
    // result: 11
    // $scope.expression = '1 + 2 * 3 - 4 + 5 * 6 / 2 - 2 * 3 ^ 2 + ( 2 + 5 ) * 2';
    $scope.expression = '2 + 3 * 4 - 5 + 7 * 6 / 3 - 2 * 3 ^ 2 + ( 5 - 2 ) * 2';
    
    // result: 16
    // $scope.expression = '1 + 2 * 3 - 4 + 5 * 6 / 2 - 2';

    
    $scope.yieldIntermediateResults = true;
    $scope.normal = null;
    
    $scope.rpn = [];  
    $scope.opStack = [];    
    
   
    $scope.values = [];
    
    
    // ====Controller's Actions====
    
    
    $scope.structure = function() {
        $scope.normal = $scope.expression.split(' ');          
    };
    
    $scope.convertToRpn = function() {
        while ((elem = $scope.normal.shift()) != null)  {
           
            
            if (elem == '(' || elem == ')') {
                if (elem == '(')
                    $scope.opStack.push(elem);
                else if (elem == ')') {
                    while((op = $scope.opStack.pop()) != '(') {
                        $scope.rpn.push(op);
                    }
                }                    
            }
            else if (!elem.isOperator()) {                
                $scope.rpn.push(elem);
            }
            else {
                
                var peek = $scope.opStack[$scope.opStack.length - 1];

                
                while ($scope.opStack.length > 0 &&
                    (
                        (elem.isLeftAssociative() && elem.operatorPrecedence() <=  peek.operatorPrecedence())
                        ||
                        elem.operatorPrecedence() < peek.operatorPrecedence()
                    )                        
                       
                      ) { 
                      
                     $scope.rpn.push($scope.opStack.pop());
                          
                     if ($scope.opStack.length > 0)
                         peek = $scope.opStack[$scope.opStack.length - 1];                          
                          
                }//while  

               
                
                $scope.opStack.push(elem);                
                
                
                              
            }// if
                
            if ($scope.yieldIntermediateResults)            
                return;
        } // while
        
        while($scope.opStack.length > 0) {
            $scope.rpn.push($scope.opStack.pop());
            
            if ($scope.yieldIntermediateResults)            
                return;            
        }
        
       
        
        
    };
    
    
    $scope.solveRpn = function() {
        while ((elem = $scope.rpn.shift()) != null)  {
            
            if (elem.isOperator()) {
                var opB = parseInt($scope.values.pop());
                var opA = parseInt($scope.values.pop());
                
                var result = 0;
                
                if (elem == '^') {
                    result = Math.pow(opA, opB);
                } else if (elem == '*') {
                    result = opA * opB;
                } else if (elem == '/') {
                    result = opA / opB;
                } else if (elem == '+') {
                    result = opA + opB;                    
                } else if (elem == '-') {
                    result = opA - opB;
                } 
                
                $scope.values.push(result);
                
            } else {
                $scope.values.push(elem);
            }
            
            if ($scope.yieldIntermediateResults)            
                return;
            
        }//while
        

        // $scope.tellAnswer = 'Answer is ' + $scope.values.pop();
    };
    
}

String.prototype.isOperator = function() {
    return this == '*' || this == '/' || this == '+' || this == '-' || this == '^';
};

String.prototype.isRightAssociative = function() {
    return this == '^';
};

String.prototype.isLeftAssociative = function() {
    return !this.isRightAssociative();
};

String.prototype.operatorPrecedence = function() {
    
    if (this == '^') return 3;
    else if (this == '*' || this == '/') return 2;
    else if (this == '+' || this == '-') return 1;
    return 0;
};​

View:

<div ng-app ng-controller="Controller">

    
    <div ng-show='normal != null'>{{expression}}</div>
    <br/>
    
    
    <div ng-show='normal == null'>
    <input type='text' style='width: 300px' ng-model='expression' />
        <br/><br/>    
        <input type='checkbox' ng-model='yieldIntermediateResults '/> Yield Intermediate Results
        <br/></br>
    
    <input type='button' value='Structure' ng-click='structure()' />
    </div>
    
    
    <div ng-show='normal.length > 0 || opStack.length > 0'>
    <input type='button' value='Convert to Reversed Polish Notation' ng-click='convertToRpn()' />
        <br/><br/>
    </div>    
    
    <div ng-show='normal.length > 0'>
        Normal: <span class='box' ng-repeat='x in normal'>{{x}}</span>
        <br/><br/>
    </div>
    
    
    
    <div ng-show='normal.length > 0 || rpn.length > 0'>
        RPN: <span class='box' ng-repeat='x in rpn'>{{x}}</span>
        <hr/>
    </div>
    
    <div ng-show='opStack.length > 0'>
        <div class='box' style='width: 10px' ng-repeat="op in opStack.slice(0).reverse()" >{{op}}</div>
    </div>
        
    <div ng-show='yieldIntermediateResults && ((normal != null && normal.length > 0) || opStack.length > 0)'>
        __OP STACK__
        <hr/>
    </div>    


  

    

    <div ng-show="(normal.length == 00 && rpn.length > 0 && opStack.length == 0)" >
    <input type='button' value='Solve RPN' ng-click='solveRpn()'/>
        <br/>
    </div>
    
    
    <div ng-show="yieldIntermediateResults && (normal.length == 00 && rpn.length > 0 && opStack.length == 0)" >
        <div class='box' style='width: 15px' ng-repeat="v in values.slice(0).reverse()" >{{v}}</div>

        __VALUES STACK__
        <hr/>
    </div>    
    
    
    <div ng-show='rpn.length == 0 && values.length == 1'>Answer is {{values[0]}}</div>
    
</div>​

CSS:
.box {
    border-width: 1px;
    border-style: solid;
    margin: 2px;
    padding: 3px;
    border-color: red;
}​

Wednesday, September 12, 2012

Basic expression evaluator

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using ExpressionComputer.Utility;

namespace ExpressionComputer
{   
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("6 == {0}\n", Exp.Compute ("1 + 2 * 3 - 4 + 5 * 6 / 2 - 2 * 3 ^ 2 + ( 5 - 2 ) * 2"));


            Console.WriteLine("19 == {0}\n", Exp.Compute("1 + 2 * 3 ^ 2"));


            Console.WriteLine("{0}\n", Exp.ConvertToRpnString("1 + 2 + 3 + 4 + 5"));

            string orig = "1 + 2 * 3 + 4";
            Console.WriteLine(orig);
            IList<string> rpn = Exp.ConvertToRpn(orig);
            Console.WriteLine(Exp.ConvertRpnToString(rpn));
            int n = Exp.ComputeRpn(rpn);
            Console.WriteLine("11 == {0}\n", n);



            string orig2 = "1 + 2 * ( 3 + 4 )";
            Console.WriteLine(orig2);
            IList<string> rpn2 = Exp.ConvertToRpn(orig2);
            Console.WriteLine("{0}", Exp.ConvertRpnToString(rpn2));
            Console.WriteLine("15 == {0}\n", Exp.ComputeRpn(rpn2));


            Console.WriteLine("23 == {0}", Exp.Compute("1 + 2 * 3 + 4 + 2 * 6"));
            Console.WriteLine("17 == {0}\n", Exp.Compute("1 + 2 * 3 + 4 + 2 * 6 / 2"));


            string orig3 = "1 + 2 * 3 + 4 + 2 * 6 / 2 - 1";
            Console.WriteLine ("{0}",orig3);
            string exp2 = Exp.ConvertToRpnString(orig3);
            Console.WriteLine(exp2);
            Console.WriteLine("16 == {0}", Exp.Compute(orig3));

            
            




            Console.ReadLine();
        }
    }


    public static class Exp
    {

        public static string ConvertRpnToString(IList<string> rpn)
        {
            return string.Join(" ", rpn.ToArray());
        }

        public static string ConvertToRpnString(string exp)
        {
            var rpn = Exp.ConvertToRpn(exp);

            return string.Join(" ", rpn.ToArray());
        }

        public static IList<string> ConvertToRpn(string exp)
        {
            IList<string> output = new List<string>();
            Stack<string> opStack = new Stack<string>();

            string[] tokens = exp.Split(' ');

            foreach (var token in tokens)
            {
                bool isOperator = token.IsOperator();

                if (token == "(" || token == ")")
                {
                    if (token == "(")
                    {
                        opStack.Push(token);
                    }
                    else if (token == ")")
                    {
                        string op = "";
                        while ((op = opStack.Pop()) != "(")
                        {
                            output.Add(op);
                        }

                    }

                }
                else if (!isOperator)
                {
                    output.Add(token);
                }
                else
                {
                    while (opStack.Count > 0 && 
                                (
                                    (token.IsLeftAssociative() && token.OperatorPrecedence() <= opStack.Peek().OperatorPrecedence())
                                    ||
                                    (token.OperatorPrecedence() < opStack.Peek().OperatorPrecedence())
                                )                       
                          )
                    {
                        output.Add(opStack.Pop());
                    }
                    opStack.Push(token);
                }
            }

            while (opStack.Count > 0)
                output.Add(opStack.Pop());


            return output;
        }

        public static int Compute(string expr)
        {
            return ComputeRpn(ConvertToRpn(expr));
        }

        public static int ComputeRpn(IList<string> rpn)
        {
            Stack<string> values = new Stack<string>();

            int n = 0;
            foreach (string token in rpn)
            {
                bool isOperator = token.IsOperator();

                if (isOperator)
                {
                    int opB = int.Parse(values.Pop());
                    int opA = int.Parse(values.Pop());
                    int result = 0;
                    switch (token)
                    {
                        case "*":
                            result = opA * opB;
                            break;
                        case "/":
                            result = opA / opB;
                            break;
                        case "+":
                            result = opA + opB;
                            break;
                        case "-":
                            result = opA - opB;
                            break;
                        case "^":
                            result = (int)Math.Pow((double)opA, (double)opB);
                            break;
                    }
                    values.Push(result.ToString());
                }
                else
                {
                    values.Push(token);
                }
            }

            return int.Parse(values.Pop());
        }
    }

}

namespace ExpressionComputer.Utility
{
    public static class Helper
    {

        public static int OperatorPrecedence(this string op)
        {
            switch (op)
            {
                case "^":
                    return 3;
                case "*":
                case "/":
                    return 2;
                case "+":
                case "-":
                    return 1;
            }
            return 0;
        }

        public static bool HasLowerOrEqualPrecedenceThan(this string opA, string opB)
        {
            return opA.OperatorPrecedence() <= opB.OperatorPrecedence();
        }

        public static bool IsOperator(this string token)
        {
            return new[] { "*", "/", "+", "-", "^" }.Contains(token);
        }

        public static bool IsRightAssociative(this string token)
        {
            return new[] { "^" }.Contains(token);
        }

        public static bool IsLeftAssociative(this string token)
        {
            return !token.IsRightAssociative();
        }
    }


}


This can properly evaluate operator precedence between multiplication, division, addition & subtraction.


Output:
6 == 6

19 == 19

1 2 + 3 + 4 + 5 +

1 + 2 * 3 + 4
1 2 3 * + 4 +
11 == 11

1 + 2 * ( 3 + 4 )
1 2 3 4 + * +
15 == 15

23 == 23
17 == 17

1 + 2 * 3 + 4 + 2 * 6 / 2 - 1
1 2 3 * + 4 + 2 6 * 2 / + 1 -
16 == 16

IDEONE: http://ideone.com/rFVXGT