November « 2011 « Matt’s Blog

Matt’s Blog Just another weblog

27Nov/11Off

Clean implementation of static class instances

Sometimes an application requires a single static instance of a class for the duration of the life of the application. This is typically done by following the Single Design Pattern. One way to demonstrate such an implementation in C# is as follows,

public class Dog {
    private static Dog m_Instance = null;
    public static Dog Instance {
        get {
            if (m_Instance == null) {
               m_Instance = new Dog();
            }
            return m_Instance;
        }
    }
    // Dog implementation follows ...
}

However, can we do better? For instance, what if we have a number of classes which should have a single static instance? We would have to repeat the above code within each class to provide an Instance property. I was recently presented with this exact problem and realized that there is something quite common in the Instance implementation.

In fact, just about the entirety of the code is common except the invocation of the constructor for a particular type. Using generics and reflection we can abstract the Instance property by providing a single abstract class that implements the Instance property for any class type with a default constructor.

The following is a neat implementation of just that.

    public abstract class StaticInstance<T> where T : class, new()
    {
        private static T instance = null;
        public static T Instance
        {
            get
            {
                if (instance == null)
                {
                    instance = Activator.CreateInstance<T>();
                }
                return instance;
            }
        }
    }

Now, we can implement Dog as follows,

public class Dog : StaticInstance<Dog> {
    public Dog() { ... }
    // Dog implementation follows ...
}

which gives the Dog class the Instance property. Neat!

Filed under: Code No Comments
27Nov/11Off

Efficient p=0.5 Probability Calculation

There are certain applications that require computing a random variable with p=0.5. That is, the simulation of a coin toss. Another common use case is inserting elements into a Skip List data structure. When a new element is inserted into a Skip List, a tower height must be calculated for that element. In particular, the height is equivalent to calculating the number of consecutive coin flips that land heads. In mathematical language, the height follows the negative binomial distribution with parameters 1 and 0.5, that is, H ~ NB(1, 0.5).

Utilizing Google Code Search, I've found a few Skip List implementations that calculate the height of a new element as follows,

while nextRandomInteger() % 1 == 1 and elementHeight < maxTowerHeight
    Increment elementHeight

The problem with the above implementation is that for each iteration of the while loop, we call nextRandomInteger() which we would expect to call some rand(2) function. Computing a random integer is actually a pretty expensive operation, consuming both CPU power and entropy. However, these random functions usually return an integer that is much larger than a single bit and it is possible to take advantage of these extra bits in calculating the element height. The goal is to eliminate the number of calls to rand(2), thus, speeding up the executing of the Skip List insertion.

Let's assume that rand(2) returns an n-bit integer. An n-bit integer has the form, X1, X2, ..., Xn, where an any X can be either a 0 or a 1 and they are all independent. It follows that since each bit is a Bernoulli Trial, a random n-bit integer follows the binomial(n, 0.5) distribution. A binomial distribution and a negative binomial distribution are closely related. Recall that we are interested in modelling a negative binomial distribution to compute the height of our Skip List element. We can accomplish this task by examining each bit of our n-bit integer and counting the number of consecutive "success" bits. Concretely, define a success bit to be a 1 and rand(2) returns an 8-bit integer, say, 01011011, then reading from the right we see, "011", that is, two successes followed by a failure. This is precisely the negative binomial distribution that we are looking to model and the height for this element would be 2.

It's nice to utilize the entire entropy of the pseudo-random number generator! Also worth investigating that by taking various patterns of successive bit configurations we can actually model other binamiol(n, p) distributions.

Filed under: Guide No Comments