Discover the power of algorithms

Complexities of algorithm, thier applicability. Optimization techniques associated with diffrent algos.

Discover Power of Blogging

What is Blogging , is it a Dream or Passion or Award or Making Money ?

Think Diffrent, be creative

Let's see how much conclusion one can draw from it. This will help testing your creativity.

Discover the power of technology

Technolgy, Programming, Optimization , Gadgets and more...

Discover the power of Blogging

Google widgets and gadgets.

Sep 11, 2011

new vs malloc ?

C++ often confuses beginners with its multiple way to allocate and free memory. Most of them understand them that free must be used with malloc and delete with new. But still they are not clear with the differences. This article will help in understanding the concept behind new and malloc.

Lets see the broader level differences first :-


  •  'new' helps in constructing an object (calls constructor), malloc does not. One of the most important differences between them.
           e.g. Consider a
           Class A { 
           public : A() { cout <<"In constructor"; }
           }
           
          A* pobjA =  new A(); //this will call constructor and displays "In constructor"
          A* pa       = (A*) malloc(sizeof(A));  //this will not call constructor
  • new requires type of object to be allocated, malloc requires you to specify the total number of bytes to allocate.
  • operator new is an operator, malloc is a function.
  • operator new throws an exception if there is not enough memory, malloc returns a NULL.                   As both function help allocating memory dynamically, there are chances for run-time failure due to non availability of memory. For such cases both shows different behavior and hence need to be handled accordingly.
          very important pint to be noticed over here is
When new is used to allocate memory for a C++ class object, the object's constructor is called after the memory is allocated.
  • operator new can be overloaded, malloc cannot be overloaded.
  • operator new/new[] must be matched with operator delete/delete[] to deallocate memory, malloc() must be matched with free() to deallocate memory.
Another big question is

How to choose between malloc and new ?

While working with C++, its always recommended to use "new", because it has additive advantage over malloc which are:-
  • Its type safe.
  • It calls constructor and helps in implementing very important Object Oriented feature Inheritence (constructor chaining). 
One can though use malloc while working with buffer (non class and struct base) , which they want to resize with time with the help of realloc. But still it can be achieved with the combination new/delete too.

How much one can allocate ?

One more query one can have now is, "How much one can allocate"? The largest possible memory block malloc can allocate depends on the host system, particularly the size of physical memory and the operating system implementation. Theoretically, the largest number should be the maximum value that can be held in a size_t type, which is an implementation-dependent unsigned integer representing the size of an area of memory. The maximum value is 2power(CHAR_BIT*sizeof(size_t) − 1), or the constant SIZE_MAX in the C99 standard.

More relevant article:-





Sep 10, 2011

Post a Suggestion/Query

Open post for adding suggestions/queries to be considered for next posting.


Queries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and SuggestionsQueries and Suggestions





What is Hashing , HashTable, Hash Function and its collision resolution strategies

Hashing is the technique used for performing almost constant time search in case of insertion, deletion and find operation. Taking a very simple example of it, an array with its index as key is the example of hash table.
So each index (key) can be used for accessing the value in a constant search time. This mapping key must be simple to compute and must helping in identifying the associated value. Function which helps us in generating such kind of key-value mapping is known as Hash Function.

Hash Table a.k.a Hash Map is a data structure which uses hash function to generate key corresponding to the associated value.

lets look at some sample hash function for strings

Folding Method:-
int h(String x, int D)
{
     int i, sum;
     for (sum=0, i=0; i<x.length(); i++)
         sum+= (int)x.charAt(i);
     return (sum%D);
}

Cyclic Shift :-
static long hashCode(String key, int D)
{
  int h=0;
  for (int i=0, i<key.length(); i++)
  {
        h = (h << 4) | ( h >> 27);
        h += (int) key.charAt(i);
  }
  return h%D;
}



good link for hash function on string : click here

Coming to very important part of hashing , which is collision resolution. Since its always not possible to design perfect hash function with minimal overhead which would generate unique key. To address this problem following are the two main collision resolving techniques :-
1) Open Hashing also known as separate chaining 
2) Closed Hashing also known as open addressing

Lets understand the difference between them
1) Open Hashing :- In this strategy collision is resolved by keeping the conflicting element in a list. That is to keep all element in a list which generate same hash.
Open Hashing

From above figure its clear that how collision get resolved by keeping a linked list.

2) Closed Hashing :- In this strategy collision is resolved by placing the conflicting element near to the slot generated by the hash function. Associated with closed hashing is a rehash strategy:
     “If we try to place x in bucket h(x) and find it occupied, find alternative location h1(x), h2(x), etc. Try each in order, if none empty table is full,”
Lets take an example to understand it

HASH_TABLE_SIZE = 8
Input data :- a,b,c,d   Hash for them H(a) = 0, H(b) = 3, H(c) = 7 and  H(d) = 3

Now as 'c' and 'd' has same hash, where to insert 'd' then ?
Finding position using linear hashing :
h1(d) = (h(d)+1)%8 = 4%8 = 4

Adding 1 to hash function of h(d) we get new position 4, and slot 4 is currently non occupied. So entering d at position 4. In this way Closed hashing works.

Disadvantage of closed hashing is that it consumes more space as compared to open hashing 
also it has less flexibility in accommodating for duplicate hash element.
Major advantage of closed hashing is that it reduces the overhead of introducing new data structure and reduces cost of new memory allocation per new element insertion.



Sep 9, 2011

Iterator in C++

Iterator an object which help in traversing a container. Its like a navigator.
For beginners its very difficult to digest/learn Iterator after Array. Since access to array is very easy just pass an index and get the value.
So this post will help beginners to build understanding about Iterator.

To start with lets look out for simple array traversal.

const int nLength = 10;
int account[nLength] = {0};
//to traverse the array one can simply provide for loop upto length and access it by index
for(int i = 0; i< nLength; i++)
{
cout<<account[i];
}

Now lets solve the above problem if its a list container.

std::list lstAccount; //list container for account
stAccount.push_back(1);
lstAccount.push_back(2);
lstAccount.push_back(3);
lstAccount.push_back(4);
std::list::iterator lstAccountIterator;//iterator for traversing list
for(lstAccountIterator = lstAccount.begin(); //initialize iterator with begining
lstAccountIterator != lstAccount.end(); // traverse until iterator rach end
lstAccountIterator++) //move itertor to next element.
{
cout<<*lstAccountIterator; //print value at itertor
}

So above code will help in traversing a list container.
Some good article on Iterator can be found at following links
       http://www.cplusplus.com/reference/std/iterator/
       http://www.cprogramming.com/tutorial/stl/iterators.html
       http://en.wikipedia.org/wiki/Iterator

Now moving to next level, lets understand the iterator design pattern.

Purpose:
       To provide a way for accessing and traversing the collection of elements, without actually exposing the internal structure/representation of the collection organisation.


Benefits:
     An abstraction which helps in simplifying the traversal mechanism.

Design Layout:
Fig. Iterator Design Pattern
   





Sep 6, 2011

Some good SEO resources , links

Here are list of some good SEO resources :-

One of the best  description about SEO :-
http://searchengineland.com/guide/what-is-seo

This page contain many relevant pointers -
http://www.pronetadvertising.com/articles/top-50-seo-resources.html

Good resource :-
http://www.seoconsultants.com/seo-resources/

It takes time to be consumed by crawlers, if we talk about google search engine. And it depends on many factors but focusing on the below key points are good enough for a new blogger.
Some key facts about SEO:-
1) Choose keywords (label) very effectively.
2) Do not create complex titles.
3) Leave back-links with relevant context.
4) Be consistent with post, it will help in keeping readers interested in the blog.


Keep Blogging
-Tajendra



sizeof operator , learning with experiments

sizeof a very interesting operator, lets do some experiments with it to gain more understanding about it.

Lets look at the msdn definition of it first :-
Yields the size of its operand with respect to the size of type char [definition from msdn].

Now lets start experimenting with it :-

what will following statement yields

a) sizeof function ?
        sizeof(&main);
        sizeof(&printf);

b) sizeof an empty class ?
        class A {};
        sizeof(A)

c) Can sizeof return 0 ?

d) What will be the output of following program ?
        int i = 1;
        sizeof(i++);
        cout<<"i="<<i;

e) sizeof following class ?
       class A { char c; int i; };
       sizeof(A)

Now lets look at them one by one

a) sizeof function ?
        sizeof(&main);
        sizeof(&printf);

Answer : sizeof(&main) will return 4 on 32 bit OS.
same hold true for sizeof(&printf). And the reason is very straight forward. As its returning size of function pointer.


b) sizeof an empty class ?
        class A {};
        sizeof(A);
Answer : Its a very interesting question which have very straight forward answer. It directly depends on sizeof operator implementation, if one looks at msdn documentation it says sizeof operator never returns zero. Considering this fact it returns 1.
For more details one can go through link (stroustrup's FAQs):-
                                          http://www2.research.att.com/~bs/bs_faq2.html#sizeof-empty

c) Can sizeof return 0 ?
Answer : NO, sizeof operator never returns 0.


d) What will be the output of following program ?
        int i = 1;
        sizeof(i++);
        cout<<"i="<<i;
Answer : output would be 1, sizeof operator gets resolved at compile time only, no run-time execution will be entertained for sizeof operator. So the output would be 1.


e) sizeof following class ?
        class A { char c; int i; };
        sizeof(A);
Answer : Don't hurry up to reply with 5 byte, because it depends on the byte alignment of class.
If it is 1 byte aligned, output would be 5;
And for 4 byte aligned, output would be 8;




Sep 1, 2011

Online Regular Expression / Regex Tools and Editor

Some useful compiled link about online regex tester :-
  • Regex tester from Regular Expression Info.com

             http://www.regular-expressions.info/javascriptexample.html


RegexBuddyInteractively create and test regular expressions with RegexBuddy.
Create and analyze regex patterns with RegexBuddy's intuitive regex building blocks. Quickly test regular expressions on sample data and files in a safe sandbox. Debug regexes easily with real-time highlighting and informative regex match details. Get your own copy of RegexBuddy now.









  • Online regular Expression tester from PageColumn.
           http://www.pagecolumn.com/tool/regtest.htm
          A very fast and effective regex tester.
  • FileFormat.Info
            http://www.fileformat.info/tool/regex.htm

Table For regular expression syntax:-
            Regular Expression Syntax :- http://msdn.microsoft.com/en-us/library/1400241x(v=vs.85).aspx