Algorithms performance: big O notation: simplified short notes

 The big O notation is used to analyze runtime time complexity. big O notation provides an abstract measurement by which we can judge the performance of algorithms without using mathematical proofs. Some of the most common big O notations are:

  • O(1) : constant: the operation doesn’t depend on the size of its input, e.g. adding a node to the tail of a linked list where we always maintain a pointer to the tail node.
  • O(n): linear: the run time complexity is proportionate to the size of n.
  • O(log n): logarithmic: normally associated with algorithms that break the problem into similar chunks per each invocation, e.g. searching a binary search tree.
  • O(n log n): just n log n: usually associated with an algorithm that breaks the problem into smaller chunks per each invocation, and then takes the results of these smaller chunks and stitches them back together, e.g, quicksort.
  • O(n2): quadratic: e.g. bubble sort.
  • O(n3): cubic: very rare
  • O(2n): exponential: incredibly rare.

Brief explanation:     
Cubic and exponential algorithms should only ever be used for very small problems (if ever!); avoid them if feasibly possible. If you encounter them then this is really a signal for you to review the design of your algorithm always look for algorithm optimization particularly loops and recursive calls. 

The biggest asset that big O notation gives us is that it allows us to essentially discard things like hardware means if you have two sorting algorithms, one with a quadric run time and the other with a logarithmic run time then logarithmic algorithm will always be faster than the quadratic one when the data set becomes suitably large. This applies even if the former is ran on a machine that is far faster than the latter, Why?

Because big O notation isolates a key factor in algorithm analysis: growth. An algorithm with quadratic run time grows faster than one with logarithmic run time.

Note: The above notes are for quick reference. Understanding algorithmic performance is a complex but interesting field. I would recommend picking a good book to understand the nitty-gritty of big O and other notations.

Python learning: scrapbook

While browsing my Evernote I found a scrapbook which I have made while learning Python some years back. Thought to share if this helps someone. I am pasting directly (no editing so there might be some spell and grammar mistake).

  • Python 2 division, just use integer part (3/2=1) whereas Python 3 uses real division 3/2 = 1.5
  • Strings in Python are immutable means you can’t change the in-place value of a char. Once string is created you can’t change/replace its elements
  •  s= “Hello World” s[::-1] this will reverse string s “dlroW olleH” double colon is used to tell the range and also how many elements can be skipped
  • if you want to use Python 3 functions in Python 2 then use ‘from __future__ import print_function‘ and similarly other functions 
  • List are mutable but tuples are not mutable (does not support item assignment) aka immutable, fewer methods in tuples then why to use instead of a list? The key is immutability. in a program if you want sequence/Val does not to get changed then tuple is a solution e.g.; storing calendar dates which know will not change during your programs. 
  • Set is a collection of un-ordered unique items it looks like a dictionary (in notation) but only keys which are unique. It can help in removing repeated items means you can use set to cast list.
  • List comprehensive are an excellent way to write clean and efficient code – they are actually de-constructed for loop flatted out in a list
  • Lambda expressions can be used to shorten function this is really useful when used with map(), reduce() and filter() functions
  • First class functions: Treat functions like any other object, we can pass functions, we can return functions, we can assign functions to a variable
  • Closure: Closure takes advantage of first-class functions and returns inner functions and variables local to them.
  • Decorators: It is a function which takes another function as an argument and returns as a function without changing the source code of the original function. Decorator allows easily to add functionality inside our wrapper without modifying original function. 

Note: These are notes for quick reference. If you are serious in learning Python I encourage you to take a book or a tutorial.

Enjoy learning! More to come …

Perl development journey and books collection

While doing routine cleaning of my personal library I was surprised to see the Perl book collection I have made over the period of time. My Perl dev journey started in a full-fledged manner way back in fall 2007. Prior to that was mainly developing using C, C++, assembly language. My first impression with Perl was not very exciting mainly due to ugly syntax and the way the OO is achieved and being from C++ background initially it was really difficult to grasp. But over the years working with language and while developing a large scale web application I learned a lot of nitty-gritty of the language and still learning…  Today I can vouch for Perl for its speed, portability, great module system CPAN and excellent dedicated community. Thanks to all the module authors and contributors on Perl Monks and StackOverflow. You guys are amazing! 
Now, the books which helped me immensely to wrote better Perl programs.

New coder and Experienced coders

I’ve found that a big difference between new coders and experienced coders is faith: faith that things are going wrong for a logical and discoverable reason, faith that problems are fixable, faith that there is a way to accomplish the goal. The path from “not working” to “working” might not be obvious, but with patience, you can usually find it.

Read the above quote somewhere on medium, myself as a programmer can easily sync with the saying. Have observed this many many times in my coding experience of the last two decades. To add, patience is needed much more while dealing with critical real-time production bugs.

I personally feel that analysis of the problem with a cool head and focus and pateince is is the key to debug and resolve critical problems.

Happy Coding!

date sorting in datatables using moment js

Sorting dates could be tricky because of various date and time format used. Fortunately there is awsome js lib called moment.js library avaliable, this is free and open source. I have made a small demo of how moment.js is used with datatables. for date sorting. First let have a look into how many date time types which moment.js supports.

Format Dates

moment().format('MMMM Do YYYY, h:mm:ss a'); // March 12th 2019, 6:46:42 pm
moment().format('dddd');                    // Tuesday
moment().format("MMM Do YY");               // Mar 12th 19
moment().format('YYYY [escaped] YYYY');     // 2019 escaped 2019
moment().format();                          // 2019-03-12T18:46:42+05:30
                                            // undefined

Relative Time

moment("20111031", "YYYYMMDD").fromNow(); // 7 years ago
moment("20120620", "YYYYMMDD").fromNow(); // 7 years ago
moment().startOf('day').fromNow();        // 19 hours ago
moment().endOf('day').fromNow();          // in 5 hours
moment().startOf('hour').fromNow();       // an hour ago
                                          // undefined

Calendar Time

moment().subtract(10, 'days').calendar(); // 03/02/2019
moment().subtract(6, 'days').calendar();  // Last Wednesday at 6:46 PM
moment().subtract(3, 'days').calendar();  // Last Saturday at 6:46 PM
moment().subtract(1, 'days').calendar();  // Yesterday at 6:46 PM
moment().calendar();                      // Today at 6:46 PM
moment().add(1, 'days').calendar();       // Tomorrow at 6:46 PM
moment().add(3, 'days').calendar();       // Friday at 6:46 PM
moment().add(10, 'days').calendar();      // 03/22/2019
                                          // undefined

Multiple Locale Support

moment.locale();         // en
moment().format('LT');   // 6:46 PM
moment().format('LTS');  // 6:46:42 PM
moment().format('L');    // 03/12/2019
moment().format('l');    // 3/12/2019
moment().format('LL');   // March 12, 2019
moment().format('ll');   // Mar 12, 2019
moment().format('LLL');  // March 12, 2019 6:46 PM
moment().format('lll');  // Mar 12, 2019 6:46 PM
moment().format('LLLL'); // Tuesday, March 12, 2019 6:46 PM
moment().format('llll'); // Tue, Mar 12, 2019 6:46 PM
                        

I have used the following libs to make this demo:

  • jquery
  • data table
  • moment.js
  • datetime-moment.js

HTML source


<h3 class="ui_title">Employee joining data</h3>
<div class="ui_block">
<table id="myTable1" class="ui_table">
<thead id="table_head">
<tr>
<th style="width:150px;">Name</th>
<th style="width:50px;">Designation</th>
<th>Joining date</th>
</tr>
</thead>
<tbody>
<tr>
	<td>Ram</td>	
	<td>Engineer</td>
	<td>18/10/2015</td>	
</tr>
<tr>
	<td>Shyam</td>	
	<td>Engineer</td>
	<td>05/01/2012</td>	
</tr>
<tr>
	<td>Suresh</td>	
	<td>Sr. Engineer</td>
	<td>22/06/2010</td>	
</tr>
<tr>
	<td>Ahmed</td>	
	<td>Manager</td>
	<td>02/02/2002</td>	
</tr>
<tr>
	<td>Leena</td>	
	<td>Sr. Manager</td>
	<td>01/01/2018</td>	
</tr>
<tr>
	<td>Pradeep</td>	
	<td>Architect</td>
	<td>21/05/2012</td>	
</tr>
</tbody>
</table>
</div>

jQuery

jQuery(document).ready(function() {
$.fn.dataTableExt.oPagination.iFullNumbersShowPages = 3;
$.fn.dataTable.moment('DD/MM/YYYY');
		$("#myTable1").DataTable({	
		"autoWidth": false,
		"destroy": true,
		"order": [[2, 'desc']],
		"pageLength": 15,
		"lengthMenu": [ [10, 25, 50, -1], [10, 25, 50, "All"] ],
		"pagingType": "full_numbers"
});
});	

CSS

/* 1. GENERAL */
* {
	font-family: /* 'Roboto', */ Verdana, Arial, Helvetica, sans-serif;
	font-size: 13px;
	box-sizing: border-box;
}

body {
	font-family: /* 'Roboto', */ Verdana, Arial, sans-serif;
	background: #f8f8f8; /* e2dbc5; */
	margin: 1em;
}

.ui_title {
	font-family: /* 'Open Sans', */ Verdana, sans-serif;
	color: #2A3F54;
	font-weight: 400;
	font-size: 24px;
	line-height:26.4px;
	border-bottom: 1px solid  #2A3F54;
}

.ui_title i {
	font-size: 24px;
}

/* BLOCKS */
.ui_block {
	min-width: 20px;
	background: white;
	border: 0; /* 1px solid #ebebeb;*/
	padding: 1em 1em;
	margin-bottom: 2em;
	box-shadow: 0 4px 6px 0 hsla(0,0%,0%,0.2);
}

.ui_block h3,
.ui_block h3 i {
	font-family: /* 'Open Sans', */ Verdana, sans-serif;
	border-bottom: 2px solid rgb(230,233,237);
	color: rgb(115,135,156);
	font-weight: 400;
	font-size: 16px;
	line-height: 18.7px;
	padding: 0;
	margin: 1em 0 0.5em 0;
}
.ui_block h3:first-child {
	margin: 0.5em 0 0.5em 0;
}

/* 3. TABLE */
.ui_table {
	border: 1px solid black;
	border-collapse: collapse;
	width:100%;
	margin-bottom: 1em;
}
.ui_table th {
	text-align: left;
	background: lightgray;
}
.ui_table td,
.ui_table th {
	border: 1px solid gray;
	padding: 3px 5px;
	font-size: 10pt;
	font-weight: 400;
}

Demo

jsFiddle
https://jsfiddle.net/ppant/efL3pvq2/3/
Github
https://github.com/ppant/jshacks/blob/master/data-table-date-sorting.html

References:


git amend scenerios

Sometimes we need to change the commit message of already committed/committed-pushed files. See below some of the scenarios might arise..

Scenerio 1-> Committed but not pushed

$ git commit --amend

This will open an editor with the commit message. If you are using vi editor edit the commit message and save using !wq: Check with $git log if the message has been amended correctly.

Scenerio 2-> Already pushed + most recent commit

It might be the case that if a user has already pushed the changes to git central repository, in this type of scenario we need to first amend the most recent local commit and afterward apply –force push which will forcefully push the changes to the server. In this process, one thing to keep in mind is that if in between any other user who has already synced local copy with the central repository needs to re-pull.

 $ git commit --amend
Edit the message in vi and save and exit
$ git push origin <branch_name> --force


Scenerio 3-> Not pushed + old commit

$ git rebase -i HEAD~X

where X is the number of commits to go back then move to the line of your commit, change pick and edit then change your commit message

$ git commit --amend 

Finish the rebase with:

$ git rebase --continue

Rebase opened your history and let you pick what to change. With edit, you tell that you want to change the message. Git moves you to a new branch to let you –amend the message. git rebase — continue puts you back in your previous branch with the message changes.

alternatively, you can choose reword instead of edit when rebasing to change the commit directly. Then you can skip the amend and rebase continue. You may check this link from git book for more on this.

Scenerio 4-> Already pushed + old commit
Edit your message with the same 3 steps process as menined in scenerios 2 ( rebase –i, commit –amend, rebase –continue). Then force push the commit

$git push <branch_name> master --force

But! please remember re-pushing your commit after changing it will very likely to prevent others to sync with the repo, if they already pulled a copy. You should first check with them.


References:
https://gist.github.com/nepsilon/156387acf9e1e72d48fa35c4fabef0b4

https://git-scm.com/book/en/v2/Git-Tools-Rewriting-History


SpaceVim review

As a Vim user for nearly 2 decades, recently I got an opportunity to explore
SpaceVim a new Vim distribution. Some of the features worth highlighting are:

  • Nicely built edit mode.
  • Loved the idea of collecting related plugins together to provide features.
  • Instant search results using grep, ag, rgackpt and with a great UI.

Will exlore more features in coming days and shall update the post.

Gitbub:https://github.com/SpaceVim/SpaceVim

grep and map-Two magical operators

Over the years I have extensively used map and grep in Perl, JavaScript, Python, Linux. I am sure most of the programmers love using these two operators. Read below some of my personal notes gathered from several resources and own understanding.

map – transforms the values of a list

The “map” function applies a transformation to each element of a list and returns the result, leaving the original list unchanged. A map can also be seen as the form of foreach loop but with the map, the implementation is much cleaner.

Ex: map { $_ => undef} is better than, map{$_=>1} the former one will save memory. It’s a better idea to use undef instead of 1.

Instead of one scalar of the value ‘1’ for every key, you get to share the same undef value for all the keys and thus don’t have to allocate tons of memory you aren’t going to use anyway.

The above idiom is a simple way of creating a list of unique values from another list, as the output of the code aptly demonstrates. However, with all those curly braces it may not be immediately obvious what’s going on, so let’s break it down.

map { $_ => 1 } @list

This is pretty straight-forward – create a list of key-value pairs where the keys are the values from @list

{ map { $_ => 1 } @list }

The surrounding pair of curly braces creates an anonymous hash which is populated with they key-value pairs from the map statement. So we now have a hash reference to an anonymous hash whose keys are the elements from @list, and because hash keys are unique, the keys of the anonymous hash represents a unique set of values.

keys %{ { map { $_ => 1 } @list } }

Finally, with the last pair of curly braces, the hash reference to the anonymous hash is dereferenced and we get its list of keys.

grep – filters a list

The “grep” function returns only the elements of a list that meet a certain condition:

@positive_numbers = grep($_ > 0, @numbers);

As you can see, each element is refered to as “$_”. This (plus the fact that parentheses are optional) allows you write commands that look similar to invocations of the Unix “grep” program:

@non_blank_lines = grep /S/, @lines;

In addition, you can specify a code block rather than a single condition:

@non_blank_lines = grep { /S/ } @lines; # Equivalent to the above.

Obviously it doesn’t matter in this case, but code blocks are helpful when you want a complex filter with multiple lines of code. The result of the code block is the result of the last statement executed:

# All positive numbers can be used as exponents,
# but negative exponents must be integers.
@can_be_used_as_exponent = grep {
if ( $_ < 0 ) {
! /./; # No decimal point -> integer.
}
else {
1; # Always true.
}
} @array;

What “grep” and “map” have in common?

"grep" and "map" have a lot in common. They both “magically” take a piece of code (either an expression or a code block) as a parameter. You need to put a comma after an expression but shouldn’t put a comma after a code block. Changing "$_" in "grep" or "map" will change the original list.

This isn’t generally a good idea because it makes the code hard to read. Remember that "map" builds a list of results by evaluating an expression, NOT by setting "$_". A side effect of this fact is that you should not use "s///" with "map". The "s///" operator changes "$_" rather than returning a result, so you won’t get what you would expect if you use it with "map" (and you CERTAINLY shouldn’t use it with "grep").

Happy programming!

References:
Discussion on PerlMonks
perldoc

Data Structures and Algorithms in Python – Sorting

Bubble Sort Implementation

The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item “bubbles” up to the location where it belongs.

  • Regardless of how the items are arranged in the initial list, n−1 passes will be made to sort a list of size n, so 1 pass n-1 comparisons, 2 pass n-2 comparions and n-1 is 1 comparions.
  • A bubble sort is often considered the most inefficient sorting method since it must exchange items before the final location is known. These “wasted” exchange operations are very costly. However, because the bubble sort makes passes through the entire unsorted portion of the list, it has the capability to do something most sorting algorithms cannot. In particular, if during a pass there are no exchanges, then we know that the list must be sorted. A bubble sort can be modified to stop early if it finds that the list has become sorted. This means that for lists that require just a few passes, a bubble sort may have an advantage in that it will recognize the sorted list and stop.
  • Performance: – Worst case: O(n2) n-square – Best case: O(n) – Average case: O(n2) n-square
arr = [2,7,1,8,5,9,11,35,25]
bubble_sort(arr)
print (arr)
[1, 2, 5, 7, 8, 11, 25, 35]
Selection Sort Implementation
  • Selection sort is a in-place algorithm
  • It works well with small files
  • It is used for sorting the files with large values and small keys this is due to the fact that selection is based on keys and swaps are made only when required
  • The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. As with a bubble sort, after the first pass, the largest item is in the correct place. After the second pass, the next largest is in place. This process continues and requires n−1 passes to sort n items, since the final item must be in place after the (n−1) st pass
  • Performance: – Worst case: O(n2) n-square – Best case: O(n) – Average case: O(n2) n-square – worst case space complexity: O(1)
arr = [2,7,1,8,5,9,11,35,25]
selection_sort(arr)
print (arr)
[1, 2, 5, 7, 8, 11, 25, 35]

 

Insertion Sort Implementation

Insertion sort always maintains a sorted sub list in the lower portion of the list Each new item is then “inserted” back into the previous sublist such that the sorted sub list is one item larger complexity O(n2) square

arr = [2,7,1,8,5,9,11,35,25]
insertion_sort(arr)
print (arr)
[1, 2, 5, 7, 8, 11, 25, 35]

 

Merge Sort Implementation

Merge sort is a recursive algorithm (example of divide and conquer) that continually splits a list in half.

  • If the list is empty or has one item, it is sorted by definition (the base case).
  • If the list has more than one item, we split the list and recursively invoke a
  • Merge sort on both halves.
  • Once the two halves are sorted, the fundamental operation, called a merge, is performed.
  • Merging is the process of taking two smaller sorted lists and combining them
  • together into a single, sorted, new list.
  • This algorithm is used to sort a linked list
  • Performance: – Worst case: O(nlog n) – Best case: O(nlog n) – Average case: O(nlog n)
arr = [11,2,5,4,7,6,8,1,23]
merge_sort(arr)
print (arr)
[1, 2, 4, 5, 6, 7, 8, 11, 23]

 

Quick Sort Implementation

The quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage also known as “partition exchange sort”.

  • As a trade-off, however, it is possible that the list may not be divided in half.
  • When this happens, we will see that performance is diminished.
  • A quick sort first selects a value, which is called the pivot value.
  • The role of the pivot value is to assist with splitting the list.
  • The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will
    be used to divide the list for subsequent calls to the quick sort.
  • Performance:
    • Worst case: O(n square)
    • Best case: O(nlog n)
    • Average case: O(nlog n)
arr = [2,7,1,8,5,9,11,35,25]
quick_sort(arr)
print (arr)
[1, 2, 5, 7, 8, 11, 25, 35]

 

Shell Sort Implementation

This is also called diminishing incremental sort

  • The shell sort improves on insertion sort by breaking the original list into a number of smaller sublists.
  • The unique way these sun lists are chosen is the key to the shell sort
  • Instead of breaking the list into sublists of contiguous items, the shell sort uses an increment ”i” to create a sublist by choosing all items that are ”i” items apart.
  • Shell sort is efficient for medium size lists
  • Complexity somewhere between O(n) and O(n2) square
arr = [45,67,23,45,21,24,7,2,6,4,90]
shell_sort(arr)
print (arr)
[2, 4, 6, 7, 21, 23, 24, 45, 45, 67, 90]

Check GitHub for the full working code.

I will keep adding more problems/solutions.

Stay tuned!

Ref:  The inspiration of implementing DS in Python is from this course

Implemeting Data Structures and Algorithms in Python: Problems and solutions

Recently I have started using Python in a lot of places including writing algorithms for MI/data science,  so I thought to try to implement some common programming problems using data structures in Python. As I have mostly implemented in C/C++ and Perl.

Let’s get started with a very basic problem.

Anagram algorithm

An algorithm will take two strings and check to see if they are anagrams. An anagram is when the two strings can be written using the exact same letters, in other words, rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once

Some examples of anagram:
“dormitory” is an anagram of “dirty room”
“a perfectionist” is an anagram of “I often practice.”
“action man” is an anagram of “cannot aim”

Our anagram check algorithm with take two strings and will give a boolean TRUE/FALSE depends on anagram found or not?
I have used two approaches to solve the problem. First is to sorted function and compare two string after removing white spaces and changing to lower case. This is straightforward.

like


def anagram(str1,str2):
# First we'll remove white spaces and also convert string to lower case letters
str1 = str1.replace(' ','').lower()
str2 = str2.replace(' ','').lower()
# We'll show output in the form of boolean TRUE/FALSE for the sorted match hence return
return sorted(str1) == sorted(str2)

The second approach is to do things manually, this is because to learn more about making logic to check. In this approach, I have used a counting mechanism and Python dictionary to store the count letter. Though one can use inbuilt Python collections idea is to learn a bit about the hash table.

Check GitHub for the full working code.

I will keep adding more problems/solutions.

Stay tuned!

Ref:  The inspiration of implementing DS in Python is from this course