ISourceCode

Make the frequent cases fast and the rare case correct

Monthly Archives: February 2012

C# – Thread safe, Lazy Initialized [.NET 4.0 Lazy(T)] , Generic Singleton

Implementing a thread safe lazy initialized singleton has been made easy through .NET 4.0 release and introduction of Lazy(Of T) Class.

In this article Jon Skeet Author of C# in Depth explains in detail the various versions of implementing a singleton.

The below implementation is a small modification of this code from Judith Bishop’s book C# 3.0 Design Patterns.

By default, all public and protected members of the Lazy(Of T) class are thread safe and may be used concurrently from multiple threads. These thread-safety guarantees may be removed optionally and per instance, using parameters to the type’s constructors. – Lazy(Of T) MSDN.

Jon Skeet in his article lists the four characteristics of a Singleton:
A single constructor, which is private and parameterless. This prevents other classes from instantiating it (which would be a violation of the pattern). Note that it also prevents subclassing – if a singleton can be subclassed once, it can be subclassed twice, and if each of those subclasses can create an instance, the pattern is violated. The factory pattern can be used if you need a single instance of a base type, but the exact type isn’t known until runtime.

The class is sealed. This is unnecessary, strictly speaking, due to the above point, but may help the JIT to optimise things more.

A static variable which holds a reference to the single created instance, if any.

A public static means of getting the reference to the single created instance, creating one if necessary.

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

//  Singleton Pattern Judith Bishop Dec 2006 - Slight modification
namespace GenericLazySingleton
{
    public class Singleton<T> where T : class, new()
    {
        Singleton() { }

        private static readonly Lazy<T> instance = new Lazy<T>(() => new T());

        public static T UniqueInstance
        {
            get { return instance.Value; }
        }
    }

    class Test1 { }
    class Test2 { }

    class Program
    {

        static void Main()
        {
            Test1 t1a = Singleton<Test1>.UniqueInstance;
            Test1 t1b = Singleton<Test1>.UniqueInstance;

            if (t1a == t1b)
            {
                Console.WriteLine("Objects are the same instance");
            }
            Console.ReadLine();
        }
    }
}

OUTPUT:

Objects are the same instance

C# – Heapsort implementation with in-place cascade down

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.- Wikipedia

In my previous article i have explained :

1 . BUILD-MAX-HEAP – runs in linear time, resultant max-heap from an unordered input array.
2 . MAX-HEAPIFY – maintains heap property and runs in O(lg n) time.
3 . MAX-HEAP-INSERT – O(lg n)
4 . HEAP-EXTRACT-MAX – O(lg n)
5 . HEAP-INCREASE-DECREASE-KEY – O(lg n) //not needed for heapsort

The function of heapsort is to insert all the unordered items into a heap using the normal Insert() from the previous article and repeatedly using Remove() will then remove the items in sorted order.

The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).

Heapsort competes with Mergesort as both have worst case O(nlg n) however a well implemented quicksort is better than heapsort since the while loop in the CascadeDown() has more operations which drag the performance as compared to few operations in a quicksort.

To improve heapsort performance a little more

For Time efficiency:
we can replace the Insert() and Remove() function which take O(n) by a single function called CascadeDown(). When we build a heap from an unordered array the elements from N/2 – 1 to n correspond to the nodes on the bottom row i.e those with no children and these are already correct heaps, because they are trees with only one node;we don’t need to apply CascadeDown() to these nodes. We can start at node N/2-1, the rightmost node with children to Cascade. Thus, we need only half as many Cascade operations.

This way we save some time.

For space efficiency:
We can use the same unordered array to store the removed elements. As the max node is removed it can be placed into the last position in the array as the elements would have shifted by one index towards the start of the array.

This improvement could make considerable difference on large data and thus heapsort O(nlg n) run time is better than O(n2) of a quicksort.

Implementation : Note getting rid of Insert() and Remove() functions.


using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace HeapSort
{
    class Node
    {
        private int nodeItem;
        public Node(int value)
        { nodeItem = value; }
        public int getvalue()
        { return nodeItem; }
        public void setvalue(int id)
        { nodeItem = id; }
    }

    class Heap
    {
        private Node[] heapArray;
        private int maxSize;
        private int currentSize;
        public Heap(int maxHeapSize)
        {
            maxSize = maxHeapSize;
            currentSize = 0;
            heapArray = new Node[maxSize];
        }
        public bool IsEmpty()
        { return currentSize == 0; }

        public Node Remove() // Remove maximum value node
        {
            Node root = heapArray[0];
            heapArray[0] = heapArray[--currentSize];
            CascadeDown(0);
            return root;
        }
        public void CascadeDown(int index)
        {
            int largerChild;
            Node top = heapArray[index]; 
            while (index < currentSize / 2) 
            {
                int leftChild = 2 * index + 1;
                int rightChild = leftChild + 1;
                if (rightChild < currentSize && heapArray[leftChild].getvalue() < heapArray[rightChild].getvalue())
                    largerChild = rightChild;
                else
                    largerChild = leftChild;
                if (top.getvalue() >= heapArray[largerChild].getvalue())
                    break;
                heapArray[index] = heapArray[largerChild];
                index = largerChild; 
            } 
            heapArray[index] = top; 
        }
        public void displayArray()
        {
            for(int j=0; j<maxSize; j++)
                Console.Write(heapArray[j].getvalue() + " ");
            Console.WriteLine("");
        }
        public void InsertAt(int index, Node newNode)
        { heapArray[index] = newNode; }
        public void setSize()
        { currentSize = 10; } // we have 10 elements
        public void DisplayHeap()
        {
            Console.WriteLine();
            Console.Write("Elements of the Heap Array are : ");
            for (int m = 0; m < currentSize; m++)
                if (heapArray[m] != null)
                    Console.Write(heapArray[m].getvalue() + " ");
                else
                    Console.Write("-- ");
            Console.WriteLine();
            int emptyLeaf = 32;
            int itemsPerRow = 1;
            int column = 0;
            int j = 0;
            String separator = "...............................";
            Console.WriteLine(separator + separator);
            while (currentSize > 0)
            {
                if (column == 0)
                    for (int k = 0; k < emptyLeaf; k++)
                        Console.Write(' ');
                Console.Write(heapArray[j].getvalue());

                if (++j == currentSize)
                    break;
                if (++column == itemsPerRow)
                {
                    emptyLeaf /= 2;
                    itemsPerRow *= 2;
                    column = 0;
                    Console.WriteLine();
                }
                else
                    for (int k = 0; k < emptyLeaf * 2 - 2; k++)
                        Console.Write(' ');
            }
            Console.WriteLine("\n" + separator + separator);
        }
    }
    class Program
    {
        public static void Main(String[] args)
        {
            int size = 10;
            Heap theHeap = new Heap(size);
            theHeap.InsertAt(0,new Node(40));
            theHeap.InsertAt(1,new Node(70));
            theHeap.InsertAt(2,new Node(20));
            theHeap.InsertAt(3,new Node(60));
            theHeap.InsertAt(4,new Node(50));
            theHeap.InsertAt(5,new Node(100));
            theHeap.InsertAt(6,new Node(82));
            theHeap.InsertAt(7,new Node(35));
            theHeap.InsertAt(8,new Node(90));
            theHeap.InsertAt(9,new Node(10));
            theHeap.setSize();

            for(int j=size/2-1; j>=0; j--) 
                theHeap.CascadeDown(j);
            Console.Write("Heap: ");
            theHeap.displayArray();
            theHeap.DisplayHeap();
            for(int j=size-1; j>=0; j--) 
            { // put the max value at end of array and so on ascending sort
                Node biggestNode = theHeap.Remove();
                theHeap.InsertAt(j, biggestNode);
            }
            Console.Write("Sorted array is : ");
            theHeap.displayArray(); 
            
            Console.ReadLine();
        }
    }
}

OUTPUT:

C# – Tree Sort – In-order traversal of a binary search tree

A tree sort is a sort algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree (in-order) so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.

Adding one item to a binary search tree is on average an O(log(n)) process, so adding n items is an O(n log(n)) process, making Tree Sort a so-called, ‘fast sort’. But adding an item to an unbalanced binary tree needs O(n) time in the worst-case, when the tree resembles a linked list (degenerate tree), causing a worst case of O(n2) for this sorting algorithm. The worst case scenario then is triggered by handing a Tree Sort algorithm an already sorted set. This would make the time needed to insert all elements into the binary tree O(n2). The dominant process in the Tree Sort algorithm is the “insertion” into the binary tree, assuming that the time needed for retrieval is O(n).
The worst-case behaviour can be improved upon by using a self-balancing binary search tree. Using such a tree, the algorithm has an O(n log(n)) worst-case performance, thus being degree-optimal. – Wikipedia


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

namespace TreeSort
{
    class Node
    {
        public int item;
        public Node leftChild;
        public Node rightChild;
        public void displayNode()
        {
            Console.Write("[");
            Console.Write(item);
            Console.Write("]");
        }
    }
    class Tree
    {
        public Node root;
        public Tree()
        { root = null; }
        public Node ReturnRoot()
        {
            return root;
        }
        public void Insert(int id)
        {
            Node newNode = new Node();
            newNode.item = id;
            if (root == null)
                root = newNode;
            else
            {
                Node current = root;
                Node parent;
                while (true)
                {
                    parent = current;
                    if (id < current.item)
                    {
                        current = current.leftChild;
                        if (current == null)
                        {
                            parent.leftChild = newNode;
                            return;
                        }
                    }
                    else
                    {
                        current = current.rightChild;
                        if (current == null)
                        {
                            parent.rightChild = newNode;
                            return;
                        }
                    }
                }
            }
        }
        public void Preorder(Node Root)
        {
            if (Root != null)
            {
                Console.Write(Root.item + " ");
                Preorder(Root.leftChild);
                Preorder(Root.rightChild);
            }
        }
        public void Inorder(Node Root)
        {
            if (Root != null)
            {
                Inorder(Root.leftChild);
                Console.Write(Root.item + " ");
                Inorder(Root.rightChild);
            }
        }
        public void Postorder(Node Root)
        {
            if (Root != null)
            {
                Postorder(Root.leftChild);
                Postorder(Root.rightChild);
                Console.Write(Root.item + " ");
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Tree theTree = new Tree();
            theTree.Insert(42);
            theTree.Insert(25);
            theTree.Insert(65);
            theTree.Insert(12);
            theTree.Insert(37);
            theTree.Insert(13);
            theTree.Insert(30);
            theTree.Insert(43);
            theTree.Insert(87);
            theTree.Insert(99);
            theTree.Insert(9);

            Console.WriteLine("Inorder traversal resulting Tree Sort");
            theTree.Inorder(theTree.ReturnRoot());
            Console.WriteLine(" ");

            Console.WriteLine();
            Console.WriteLine("Preorder traversal");
            theTree.Preorder(theTree.ReturnRoot());
            Console.WriteLine(" ");

            Console.WriteLine();
            Console.WriteLine("Postorder traversal");
            theTree.Postorder(theTree.ReturnRoot());
            Console.WriteLine(" ");

            Console.ReadLine();
        }
    }
}

OUTPUT:

C# – Binary max-heap implementation

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) – Wikipedia

The heap data structure is not the same as the storage used for garbage collection(heap).

This article is an introduction to a binary heap.

A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
The heap property: each node is greater than or equal to each of its children according to a comparison predicate defined for the data structure.

Heaps with a mathematical “greater than or equal to” comparison function are called max-heaps; those with a mathematical “less than or equal to” comparison function are called min-heaps. Min-heaps are often used to implement priority queues – Wikipedia .

The binary heap is a special case of the d-ary heap in which d = 2.

MIT recitation, summary of heap operation algorithms:

1 . BUILD-MAX-HEAP – runs in linear time, resultant max-heap from an unordered input array.
2 . MAX-HEAPIFY – maintains heap property and runs in O(lg n) time.
3 . MAX-HEAP-INSERT – O(lg n)
4 . HEAP-EXTRACT-MAX – O(lg n)
5 . HEAP-INCREASE-DECREASE-KEY – O(lg n)

Since we build a heap array, note that for any given node i (starts from zero), its children would be found at 2i + 1 and 2i + 2 index of the array. – Heap implementation using arrays

Some points to remember:

For a heap of height h the minimum number of elements is 2h
and the maximum number of elements is 2h+1− 1.

A array sorted from lowest to highest is a min-heap

minimum value of max heap in an array can be found from the values of array[i+1] to array[n] where Leaf nodes of the max heap or n-element heap are found from index i+1 to n. Here i=n/2; n is array length.

There is no effect calling MAX-HEAPIFY(A, i) for i > size[A]/2 as all the nodes leaf nodes.

There are at most ceil(n/2h+1) nodes of height h in an n-element heap.

Another approach to implement heap is to actually build a binary tree. However this is weakly ordered since heaps do not have a strong ordering policy like a binary search tree. We can use binary numbers to represent path from root to a node to keep track of the nodes and for traversing and this is tedious.

So the most popular implementation is to use an array and visualize the array as a complete binary tree.

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace HeapDemo
{
    class Node
    {
        private int nodeItem; 
        public Node(int value) 
        { nodeItem = value; }
        public int getvalue()
        { return nodeItem; }
        public void setvalue(int id)
        { nodeItem = id; }
    }

    class Heap
    {
        private Node[] heapArray;
        private int maxSize; 
        private int currentSize; 
        public Heap(int maxHeapSize)
        {
            maxSize = maxHeapSize;
            currentSize = 0;
            heapArray = new Node[maxSize]; 
        }
        public bool IsEmpty()
        { return currentSize==0; }
        public bool Insert(int value)
        {
            if(currentSize==maxSize)
                return false;
            Node newNode = new Node(value);
            heapArray[currentSize] = newNode;
            CascadeUp(currentSize++);
            return true;
        } 
        public void CascadeUp(int index)
        {
            int parent = (index-1) / 2;
            Node bottom = heapArray[index];
            while( index > 0 && heapArray[parent].getvalue() < bottom.getvalue() )
            {
                heapArray[index] = heapArray[parent]; 
                index = parent;
                parent = (parent-1) / 2;
            }
            heapArray[index] = bottom;
        } 
        public Node Remove() // Remove maximum value node
        { 
            Node root = heapArray[0];
            heapArray[0] = heapArray[--currentSize];
            CascadeDown(0);
            return root;
        } 
        public void CascadeDown(int index)
        {
            int largerChild;
            Node top = heapArray[index]; 
            while(index < currentSize/2) 
            { 
                int leftChild = 2*index+1;
                int rightChild = leftChild+1;
                if(rightChild < currentSize && heapArray[leftChild].getvalue() < heapArray[rightChild].getvalue())
                    largerChild = rightChild;
                else
                    largerChild = leftChild;
                if( top.getvalue() >= heapArray[largerChild].getvalue() )
                    break;
                heapArray[index] = heapArray[largerChild];
                index = largerChild;
            }
            heapArray[index] = top;
        } 
        public bool HeapIncreaseDecreaseKey(int index, int newValue)
        {
            if(index<0 || index>=currentSize)
                return false;
            int oldValue = heapArray[index].getvalue(); 
            heapArray[index].setvalue(newValue); 
            if(oldValue < newValue) 
                CascadeUp(index); 
            else 
                CascadeDown(index); 
            return true;
        } 
        public void DisplayHeap()
        {
            Console.WriteLine();
            Console.Write("Elements of the Heap Array are : ");
            for(int m=0; m<currentSize; m++)
                if(heapArray[m] != null)
                    Console.Write( heapArray[m].getvalue() + " ");
                else
                    Console.Write( "-- ");
            Console.WriteLine();
            int emptyLeaf = 32;
            int itemsPerRow = 1;
            int column = 0;
            int j = 0; 
            String separator = "...............................";
            Console.WriteLine(separator+separator); 
            while(currentSize > 0) 
            {
                if(column == 0) 
                    for(int k=0; k<emptyLeaf; k++) 
                        Console.Write(' ');
                Console.Write(heapArray[j].getvalue());

                if(++j == currentSize) 
                    break;
                if(++column==itemsPerRow)
                {
                    emptyLeaf /= 2; 
                    itemsPerRow *= 2; 
                    column = 0;
                    Console.WriteLine(); 
                }
                else 
                    for(int k=0; k<emptyLeaf*2-2; k++)
                        Console.Write(' '); 
            } 
            Console.WriteLine("\n"+separator+separator); 
        } 
    } 
    class Program
    {
        public static void Main(String[] args)
        {
            Heap theHeap = new Heap(21); 
            theHeap.Insert(40); 
            theHeap.Insert(70);
            theHeap.Insert(20);
            theHeap.Insert(60);
            theHeap.Insert(50);
            theHeap.Insert(100);
            theHeap.Insert(82);
            theHeap.Insert(35);
            theHeap.Insert(90);
            theHeap.Insert(10);
            theHeap.DisplayHeap();

            Console.WriteLine("Inserting a new node with value 120");
            theHeap.Insert(120);
            theHeap.DisplayHeap();

            Console.WriteLine("Removing max element");
            theHeap.Remove();
            theHeap.DisplayHeap();

            Console.WriteLine("Changing root to 130");
            theHeap.HeapIncreaseDecreaseKey(0, 130);
            theHeap.DisplayHeap();

            Console.WriteLine("Changing root to 5");
            theHeap.HeapIncreaseDecreaseKey(0, 5);
            theHeap.DisplayHeap();
            Console.ReadLine();
        }
    } 
}

OUTPUT:

C# – when to use .NET framework class library (FCL) type vs an alias

I started to wonder if i should use string keyword which is an alias of System.String or String class name while coding in C# and after reading the three posts of stackoverflow 1 , 2 and 3 I have decided to follow the conventions suggested by this blogger

The blogger says “In my case I use string when I think of it as a simple type, just like I do with int, char, byte etc. Simple types aren’t classes/objects tho, so when I decide to use a method declared in the underlaying .NET Framework type in C# I use the class name, that is String, Integer, Char, Byte etc. Hence I use “string” in declarations and “String” when using the static methods and properties, like “String.IsNullOrEmpty(string)” or “String.Empty”.

Although both generate the same intermediate language.

Follow

Get every new post delivered to your Inbox.