Redis

When your question gets answered very fast in stackoverflow, you have Redis to thanks for that. Ok, that's an oversimplification.


When you asked a question, its INSERT can be served very fast by SQL Server as there are no SELECTs needed be ran when other users are merely browsing for existing answers and questions, and that includes your currently written question too. Less database contentions, more questions gets easily served.


Sources:

http://highscalability.com/blog/2011/3/3/stack-overflow-architecture-update-now-at-95-million-page-vi.html

http://meta.stackoverflow.com/questions/69164/does-stack-overflow-use-caching-and-if-so-how

Salivating at C# 5's async/await + Redis combo: http://marcgravell.blogspot.com/2011/04/async-redis-await-booksleeve.html

Shades of XY problem

Shades of XY problem. A colleague asked me how to prevent nested substitution of the token when it's inside of an attribute, the following...

foreach(var token in arr) 
{
 sb.Replace( token, string.Format("<li id='{0}' class='meh'>{1}</li>", token, GetDescriptive(token)) );
}

...resulted to this (say token is "bp") nested substitution:

<li id='<li id='bp' class='meh'>BasePay</li>' class='meh'>BasePay</li> 
+ (<li id='<li id='bp' class='meh'>BasePay</li>' class='meh'>BasePay</li> 
* <li id='pi' class='meh'>PercentIncrease</li>)

...then I quickly suggested this:

var d = new Dictionary<Guid,string>();


foreach(var token in arr) 
{
 var g = Guid.NewGuid();
 d[g] = token;
 sb.Replace( token, string.Format("<li id='{0}' class='meh'>{1}</li>", g, GetDescriptive(token)) );
}


foreach(KeyValuePair<Guid,string> kv in d) 
{
        // essentially putting back the original token inside of attribute
 sb.Replace(kv.Key, kv.Value); 
}

That produces correct output:

<li id='bp' class='meh'>BasePay</li> 
+ (<li id='bp' class='meh'>BasePay</li> * <li id='pi' class='meh'>PercentIncrease</li>)

However, I dwell too much on how to prevent values substitution when it's inside of an attribute, in fact I'm thinking of regular expression approach too; sometimes though, when you formulate a regular expression solution you'll have two problems later. And so the proverbial light bulb lit up on my puny brain, why not just use Guid so when the next repeating substitution occur it won't replace those tokens inside of attribute?! Then I devise the Dictionary+Guid combo solution above. It works! Brilliant! Or so I thought I'm brilliant, it works but...


Then it occurred to me while I'm going back home, why did the string replacement occurred two times in the first place? Should doing it once would suffice?


Then upon arriving back to the office the next day, I re-check why the string substitution could occur two times, and then I saw this:

BasePay + (BasePay * PercentIncrease)

Darn, that's why the nested substitution occurred, BasePay occurred two times in the equation.


I even remember my colleague explained the above equation the day before. The colleague explained both the X (equation with repeating token) problem and the Y solution (prevent operands inside of attribute from being nestedly replaced) being attempted first. The colleague cannot be faulted, I focused too much on Y. Admit it or not, to most programmers, challenging problems are what piqued our curiosity the most, and to me it was how to prevent that-goddamn-token-inside-of-attribute-from-being-nestedly-replaced. When we can't connect to a database server, we are most likely to suggest to a colleague to look at the firewall configuration first, or connect directly to IP address, or connect to named pipes instead of TCP/IP, etc, it's rare of us to suggest to look first if the network cable is disconnected, you get my drift.


The most elegant solution is to prevent duplicate tokens from appearing multiple times in the list:

foreach(var token in arr.Distinct()) 
{
 sb.Replace(token, string.Format("<li id='{0}' class='meh'>", token));
}

It works and very simple. And while I'm writing this post, it hit my mind that it is best to tackle the problem from its root cause.

var arr = formula.Split("/+-*()".ToCharArray(), StringSplitOptions.RemoveEmptyEntries).Distinct();

foreach(var token in arr) 
{
 sb.Replace(token, string.Format("<li id='{0}' class='meh'>", token));
}

The root cause of any problems in a Y solution comes from X requirement. So when someone is asking you a question, and you think they are just presenting you their Y, demand for X.

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

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;
}​

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