get “Set” and go!

In an attempt to optimize some code I wrote a few years back, I started checking the amount of time each of code is taking for which I used a simple Line Profiler. I always believed using the right Data Structure for the right task could essentially get you a lift on you performance big time, like no fancy stuff only simple data structure.

So imagine a task where all you need to do is check if the list has a particular value of no. A simple list would use some searching algorithm based on the length of the list (Programming languages have a series of Algorithm implemented and based on the size of list they select the most suitable algorithm for the same) and If the element exist would return true, worst case O(n) operation, for a linear brute force search where data structure used would be simple array or a linked list.

Now we all are smarter then this so what we now do is sort the list and use Binary search, bingo! there we are at log(n) but wait there is a catch, if the list is dynamic in nature ie frequent additions to the list then insertion of new element would take another log(n) amount of time.

So here was the problem the list had huge number of “Tokens” (words) and I needed to check was if a certain token existed in this List.
Eventually what I ended up doing is convert the list into a Set(Hash), search and insert both are O(1) (generally is used a proper hashing algorithm.)