Thursday, 26 November 2015

Sorting, the burning problem in hand...

After the introductory articles and preaching about Algorithms, Let's discuss about some practical scenarios where analysis of algorithms plays a key role.

Let's start our discussion with a simple thought. We all know about Dictionary and what it does, right ?

Oh yeah, dictionary is a place where we find the meaning of any word.

Good, now let me ask you the meaning of the word 'Modern'. So, what are you going to do ?

Hey, I will search the dictionary, probably in the middle of the pages. Cause, 'M' is almost in the middle of the dictionary.

Then I will look up at any word, let's say I found the word 'Modest' in that page, then I will look in the previous page, cause 'R' comes before 'S' and accordingly in some other 2/3 steps, I will find the word 'Modern'.

So, that's it, usually anyone in the world will basically do that. Because all of us know that the worrds are arranged in some particular fashion in the dictionary. We basically call this fashion as 'Sorted'.

Now, I would like you to put some overhead on the same problem. Just think that, the dictionary is not sorted at all and may be the dictionary has the following order of words,

Good, Place, Algorithm, Program, Zebra, Work, Bat, Cow, Ball, Billiards, Efficient, Alphabet, Access, Sort, Order, Monotonous, Migration, Immigration, External, Pouch, Internal ...........

Now, I ask you to find the meaning of the word 'Modern' from our this new dictionary.

Ohh Jesus !!! I can't do that. Please forgive me.
Well, that is what happens at a first glance, but if you think quietly, you will realize that you can find the meaning of any word from this dictionary too. Only thing you have to do is, you have to check all the words in the dictionary, until you get the word you are searching for.

Wait, that's basically none of use. If I cannot find a meaning when I require it, what is the use of finding it out ? Rather I will buy a new dictionary instead of using yours inefficient dictionary.
Here is $5 for you to buy the dictionary. ;)

Yes, that is what we basically want, a faster way to make things better and get the required element at ease.

Well, it is true that, 'Getting a right answer late is same as getting a wrong answer'.

That's where lies the beauty of sorting. Mostly, sorting helps in following two ways,
  1.  Easing the process of looking up an element from the pile
  2.  Enhancing the process of merging sequences
So, in today's world data has become huge, here is an article depicting the scenario. Just check the article and get an understanding, how huge the data has become globally. So, to find out the exact information from this data, we need a better and efficient way of searching the exact information from this huge pile of data.

Sorting helps this process in an efficient way. So, to cope up with the large data collection, we need efficient sorting process.

So, sorting has become a burning problem of today and in future also, it will be. Somewhere, I read this quote, 'We need an efficient sorting algorithm every one and half years'.

Hope that, you got an understanding on the usability of sorting. Next, we will be looking into some sorting algorithms and will analyze them.

Prev     Next
Palash Kanti Kundu

Wednesday, 18 November 2015

Motivation to learn about algorithms



If you have taken a look at my previous article, you must have observed that, I have taken some examples of the IT giants like Google, Microsoft, Facebook. So, you might be wondering, all these are related to the giants and they have found it very much useful to devise a new algorithm to solve the problem in hand, I don’t deal with such a huge data in my programs, so probably I don’t need it. Better have a coffee myself instead of reading this article.

Exactly the same I thought when I was pursuing my graduation and ignored this vital part of science. Honestly confessing, until today, I never bothered about this topic and whenever possible I had avoided the discuusion. But today, I found out how useful and interesting this field can be, I also could recall a scenario from my past IT experience. Somewhere there was a code, which was trying to sort an array of records and I remember, it was using a poor algorithm.

At the time of writing the code, the developer might not have thought of a scenario when the size of the incoming array would have crossed a limit this algorithm stands good for. So, when I was working on that piece of code, I faced the issue and the system was taking too long to respond.

No credit for me, I have not fixed the code.
:)

Credit goes to the senior team member who just took a look on the piece of code, removed the code and simply added Arrays.sort() method. I was astonished to see the performance improvement after that but could not figure out what he did on that piece of code.
Well almost after two years of that incident, I have found out the reason today. Basically, Java internally also uses algorithm to solve the case of sorting.

So, what’s the big deal, your code also had an algorithm?
Well, simply Java uses a better algorithm to solve the case of sorting.

So, how do you know about that now after such a long time?
Well, I was writing code for some algorithms and was astonished see the performance boost a good algorithm can provide you. Then I suddenly recalled the event and went to Java Docs to match my answer and my initial guess was correct that Java uses a better algorithm to solve problems.


So, I will be using the standard API, no problem. No need to study Algorithms…
Yes, I encourage you to use the standard API whenever possible. But, in some cases, you may also be stuck with a situation that I faced a long ago and you may not have a senior like you who can fix it in a minute.
To implement things in a better way, you need to figure out the existing worse way, right?

Hmm, makes sense.

Good that you are also in the same page I am into. Well, if you still have a doubt, just check out the following table which is a practical response I have got running two different algorithms on the same system, on the same data set.
Data Size
Run time for Algorithm 1 (in Milliseconds)
Run time for Algorithm 2 (in Milliseconds)
250
0 *
1
500
1
2
1000
0 *
4
1500
1
5
5000
2
26
10000
2
85
50000
11
2381
100000
12
7894
1000000
59
828873
50000000
8075
Running from November 18, 2015. I stopped the execution on November 27, 2015.

* This is inaccurate. It might have completed within a fraction of milliseconds, but definitely it has taken some time to complete but that is really negligible and tends to 0.

So, we can see that as the data size increases, the difference also increases significantly.

Actually, I earlier was stuck in the data range of 50,000. When the developer has wrote this code, he might not have thought of this scenario to be present and a difference between 2 milliseconds and 85 milliseconds is really not a very much notable difference but the difference between 11 milliseconds and 2381 milliseconds is quite observable.
So, you can get some idea why it is better to have knowledge about algorithms.


For your use, I have added all these code in my Git account, https://github.com/Palash90/algorithms.
You can check out the code to run it in your local system and  can play with it using different number sets.


Hope you enjoyed this article…

 Prev   Next
Palash Kanti Kundu