Archive for the ‘Programming’ Category

A Tour On Python List

Posted: May 28, 2015 in Programming
Tags: , , ,

 For those who have used Arrays in C and C++, list in Python is going to be a lucky charm . As Head First Python states, List is nothing but an array with steroids. Python list makes the life very easier as its dynamic in nature and the in-build functions are available to perform all the actions on it.

First lets list down the basic stuffs that we always do on arrays .

1. Declaring
2. Creating
3. Initializing with predefined input
4. Adding More input to it
5. Searching
6. Indexing
7. Removing
8. Erasing
9. In Built Functions

In this tutorial, am going to use 2 lists. One named numbers and other named alphabets. Lets go and see one by one .

1. Declaring a list

As we know, we need not declare a variable with appropriate data type in python . both a = 5 and a = ‘5’ are valid without specifying the corresponding data type. And more importantly, its applicable to lists as well.

2. Creating a list

When i say creating , it has 2 modes. Creating an empty one to add items later. Or creating a predefined set of elements in the list. To create an empty list, all we need to do is to write an open and closed square brackets.

numbers = []

https://shrinathsuccess.files.wordpress.com/2015/05/list2.png?w=614

3. Initializing with Predefined Input:

Sometimes, we will be really sure that we are going to work with only some specific inputs. In those situations we can create a list with pre defined inputs in it. That can be done by enclosing the inputs inside the square bracket

numbers = [1,2,3,4]

https://shrinathsuccess.files.wordpress.com/2015/05/list3.png?w=614

4. Adding more input to a List:

Adding input to the list can be categorized as following

4.1 – Adding elements one by one to a list
4.2 – Adding elements in a block
4.3 – Multiplying the list
4.4 – Adding list inside a list

4.1 – Adding elements one by one to the list :

Python has predefined function named “insert” , which can be used to add elements to the list. However, the insert takes two arguments. first one is the position and second one is the value. The list with numbers 1,2,3,4 can also be created as below

numbers = []
numbers.insert(0,1)
numbers.insert(1,2)
numbers.insert(2,3)
numbers.insert(3,4)

https://shrinathsuccess.files.wordpress.com/2015/05/list4-1.png?w=614

4.2 – Adding elements in block

If suppose we have 2 lists. first one containing numbers 1 to 3 and other one containing numbers 4 to 6. And we need to merge two list. ie. adding elements in block, then we can do it as below:

num1 = [1,2,3]
num2 = [4,5,6]
num1 + num2

or simply

[1,2,3] + [4,5,6]

https://shrinathsuccess.files.wordpress.com/2015/05/list4-2.png?w=614

4.3 – Multiplying the list

Python creates a easy way of inserting repeated items. For example, if we need a list which has 3 numbers 1,2,3 ten times. we need not write a for loop . Just a simple multiplication operator on list will do it as below

numbers = [1,2,3]
numbers * 10

https://shrinathsuccess.files.wordpress.com/2015/05/list4-3.png?w=614

4.4. Nesting Lists

Yes, we can have list inside a list. And there is a specific way for indexing the list. In the list below , 4th item is a list which contains 3 items in turn.

numAlpha = [1,2,3 [ “a”, “b”, “c” ]]

https://shrinathsuccess.files.wordpress.com/2015/05/list4-4.png?w=614

5. Searching an element in the list

If we need to check an element exists in the list , we can use “in” keyword with list which will return a boolean value (True indicating the element exists and false indicating the element doesnt exist in the list)

numbers = [1,2,3,4,5,6]
4 in numbers
7 in numbers

https://shrinathsuccess.files.wordpress.com/2015/05/list5.png?w=614

6. Indexing list

We can get the element based on the index of that element in the list. Since, all the elements are inserted into the list with the index element, we can derive any element if we know the index. Index starts with 0 and moves on as we insert the elements.

List_name[start : end]

This is the common notation . start denotes the starting index that we need to start with, to start from beginning give 0 or leave it empty. End denotes the position to which list should print

numbers = [1,2,3,4,5,6]
numbers[1:4] - show elements from index 1 till 3
numbers[:2] - show elements from beginning till 1st index
numbers[2:] - show elements from index 2 to end of the list
numbers[:] - print all elements
numbers[-2] - tricky one .. show 2nd last element in the list

https://shrinathsuccess.files.wordpress.com/2015/05/list6.png?w=614

7. Removing elements from a list :

We can remove an element from the list if we know the index or element value. remove function can be used if we know the list value and del function can be used to remove using index.

numbers = [1,2,3,4,5,6]
numbers.remove(5)
numbers
del numbers[-4]
numbers

https://shrinathsuccess.files.wordpress.com/2015/05/list7.png?w=614

8. Erasing the list :

If we need to erase all the elements in the list , we can use clear function . List_name.clear() will remove all the elements from list.

numbers = [1,2,3,4,5,6]
numbers.clear()
numbers

https://shrinathsuccess.files.wordpress.com/2015/05/list8.png?w=614

9. Inbuilt Functions :

There are lot of inbuilt functions available in python list. One that we saw is len(list_name) which gives the length . Similarly we have

len – finds the total number of elements in the list
count – finds the number of occurrence for an element
sort – sorts the list
reverse – reverse the list
index – returns the index of first matching element

https://shrinathsuccess.files.wordpress.com/2015/05/list9.png?w=614

Am completely new to python and Django . Today i made an attempt of installing Django in my ubuntu 14.04 system.

The OS is fresh installed, just did 4 days back . Django is going to be my first package installation.

I went with the Official Documentation given below

Official Documentation for Django Installation

As given in the link , there are 3 major steps.

1. Check if python is already installed in your computer.

I did by typing

python –version in my terminal and i got answer as Python 2.7.6.

Hence, i proceeded to step 2 .

2. Remove any previous versions of Django if installed.

sudo rm -rf /usr/lib/python2.7/dist-packages/django

You have to run this command to remove the previous version. Change the python version accordingly in the command

If you skip this step you might be getting an error as given below

OSError: [Errno 13] Permission denied: '/usr/local/lib/python2.7/dist-packages/django'

I tried installing Django Directly using pip which gave me this error . And i visited the following URL for the solution.

Solution for OS Error

3. Install Django.

In ubuntu 14.04 LTS i didnt have pip installed in prior. Hence i had to install that first. That can be done by

sudo apt-get install python-pip

and then you can install Django by typing this command

sudo pip install Django==1.8.1

Django installed successfully.

To verify open the python prompt by typing python in the terminal and use the following commands to see Django version

>>> import django
>>> print(django.get_version())

insertionSortCard

Best example of insertion sort is sorting deck of cards. .. As you see in the figure, say we have 2,4,5 10 and 7 clubs in our hand and we have to sort it .
As we know, we will take 7 clubs and place it between 5 and 10 clubs. Hence, for each card we need to swap the cards before it and place the key card in place .

 

Before the analysis , lets have a look at pseudo code of insertion sort. For input array A

 


INSERTION-SORT(A)

for j <-- 2 to length [A]

do key <-- A[j]

i <-- j - 1

while i > 0 and A[i] > key

do A[i + i] <-- A[i]

i <-- i - 1

A[i + 1] <-- key

&nbsp;

 

I tried implementing the same in C++. Here is the code

 

 

#include <iostream>

using namespace std;

int main()
{
int arr[] = {5,2,4,6,1,3};
int arrSize =  sizeof(arr)/sizeof(arr[0]);
int key;
int i;
for(int j=1; j<arrSize; j++)
{
        key = arr[j];
        i = j - 1;
        while(i >= 0 && arr[i] > key)
        {
                arr[i+1] = arr[i];
                i = i - 1;
        }   

        arr[i+1] = key;

}

for(int i=0; i<arrSize; i++)
cout << arr[i] << " " << endl;
return 0;
}

Output is :

insertionSortOutput

Before we start our analysis of the insertion sort, we will see how many times each statement runs.

 


INSERTION-SORT(A)

for j <-- 2 to length [A] ----------------------------  runs n times

do key <-- A[j] --------------------------------------  runs n-1 times

i <-- j - 1     --------------------------------------  runs n-1 times
                                                       n
while i > 0 and A[i] > key --------------------------- ∑ tj
                                                       j=2
                                                       n
do A[i + i] <-- A[i]  -------------------------------- ∑ tj - 1
                                                       j=2

                                                       n
i <-- i - 1 ------------------------------------------ ∑ tj - 1
                                                       j=2
A[i + 1] <-- key ------------------------------------- n-1

&nbsp;

Now, lets get into the analysis part.
Okay, In each statement , we do some operations as well i.e – increment, decrement, counter — all those are considered to be constants. Hence we name constants from c1 to c7
And also, tj is the function which does while loop operation .
If the input is already sorted, there would be no in-swapping takes place. i.e. While loop will never be executed. Since while loop is inside FOR loop which runs from 2 to n , we enclose it with sigma j = 2 to n.
Hence the equation would be
What could be the Best case ?? — A sorted input
and what could be the worst case input . — Input sequence in reverse order.

 

These 3 screenshots will explain how insertion sort is O(n) in best case and O(n square) in worst case. 

 

 

BestCase

insertion_sort

worst case

 

This you tube video will be helpful to understand the same

https://www.youtube.com/watch?v=yXwFrc5GS6A — click the view the video 

 

On an occasion i had a file with words listed one by one and i wanted to sort the file in lexicographic order. Since i work in linux machines , its just 1 command . `cat filename | sort ` to sort it in lexicographic order. But i wanted to do it in c++.  I tried googling for suggestions and found out that radix and bucket sort would help me out. And then i tried implementing the concept of Radix MSD to arrive the result. Sharing the code. I have added inline comments in the program. Hope it helps  (Note: i just wanted to arrive with the solution.. Not much concerned about efficiency of the program :-))

#include <iostream>
#include <map>
#include <vector>
#include <fstream>

using namespace std;

int main()
{

	vector<string> words;

	map<char,vector<string> > bucket;
	map<char,vector<string> > ::iterator it;
	bucket.clear();
	vector<string> tempVec;

	// initializing map with null vector and empty for variable length string
	bucket[' '] = tempVec;
	char ch;
	//for(int i=97; i<123; i++)
	for(int i=65; i<91; i++)
	{
		ch = i;
		bucket[ch] = tempVec;
	}

	words.push_back("jump");
	words.push_back("sit");
	words.push_back("carry");
	words.push_back("run");
	words.push_back("site");
	words.push_back("runner");


	/*cout << "init" << endl;
	  for(int k=0; k<words.size(); k++)
	  cout << words[k] << "  ";
	  cout << endl;*/

	// finding the maximum character
	int max = 0;
	for(int i=0; i<words.size(); i++)
	{
		max = (max > words[i].length())?max:words[i].length();
	}

	// loop from max char till first char 
	for(int i=max-1; i>=0; i--)
	{
		//cout << "Running for Phase " << i << endl;
		// loop through the entire vector
		for(int j=0; j<words.size(); j++)
		{
			string word = words[j];
			int temp_len = word.length();
			// there may be possibility that word boundary is less than max
			if(temp_len < i)
			{
				// push into the "" bucket
				//cout << "Pushing " << word << " into bucket " << "[empty]" << endl;
				bucket[' '].push_back(word);
			}
			else
			{
				// index exists .. Hence check the char
				char temp_char;
				temp_char = word[i];

				// insert into map with temp_char, word
				bucket[temp_char].push_back(word);	
				//cout << "Pushing " << word << " into bucket " << temp_char << endl;

			}


		}
		// end of this loop, all the words are inserted into corresponding buckets
		// clear the input vector -- because we are going to change the order
		words.clear();

		// iterate through the keys and write the order into input vector
		for(it=bucket.begin(); it!=bucket.end(); it++)
		{
			tempVec = it->second;
			for(int k=0; k<tempVec.size(); k++)
				words.push_back(tempVec[k]);

			tempVec.clear();
		}

		/*cout << "After bucket insertion words are  " << endl;
		  for(int k=0; k<words.size(); k++)
		  cout << words[k] << "  ";
		  cout << endl;
		 */


		// now we have the correct order of the phase .. hence clear the bucket
		tempVec.clear();
		for(it=bucket.begin(); it!=bucket.end(); it++)
		{
			it->second.clear();
		}

		//cout << endl;


	}
	cout << "Answer is " << endl;
	for(int k=0; k<words.size(); k++)
		cout << words[k] << endl;


	return 0;
}

[ALGORITHM]
1. Read the words and push into vector
2. find the max value by iterating the vector and finding length of all words
3. Iterate from max to 0
4. take each words first letter and push into corresponding bucket
5. Iterate through the buckets and save it as input word list order
6. After 0th Iteration , input vector will have the result.

[EXPLANATION]

step – 1
words pushed into vector

jump, sit, carry, run, site , runner

step – 2

finding the maximum length string
it would be runner – 6

step – 3

Iterating from index 5 to 0

ITERATION – 5 :
Note : if the word length is less than index , we need to push in empty bucket(‘ ‘)

‘ ‘ – jump,sit,carry,run,site
r – runner

Hence, array order will be – jump, sit, carry, run, site

ITERATION – 4 :

4th index of the words carry and runner are [y] and [e]

‘ ‘ – jump, sit, run, site
e – runner
y – carry

Hence, array order will be – jump, sit, run, site, runner, carry

ITERATION – 3 :

3rd index for the words jump, carry, site, runner [p],[r],[e],[n]

‘ ‘ – sit, run
e – site
n – runner
p – jump
r – carry

Hence array would be sit, run, site, runner, jump, carry

ITERATION – 2 :

2nd index for the words sit, run , site, runner, jump, carry are [t],[n],[t],[n],[m], [r]

m – jump
n – run, runner
r – carry
t – sit, site

Hence array would be jump, run, runner, carry, sit, site

ITERATION – 1

1st index for the words jump, run, runner, carry, sit, site are [u],[u],[u],[a],[i],[i]
a – carry
i – sit , site
u – jump, run, runner

Hence array would be , carry, sit, site , jump, run, runner

ITERATION – 0

0th index of the words are [c], [s], [s], [j], [r], [r]

c – carry
s – sit, site
j – jump
r – run, runner

Hence OUPUT : carry, sit , site , jump, run, runner

Very new to python Programming . I tried installing python 2.7 in my linux machine (ubuntu). Unfortunately , python 3 was already installed in the system.

For parsing the twitter tweets using python, i had to install oauth2 in my machine. i spent almost 2 to 3 hours doing it . Got almost 5 different kind of packages from internet and tried installing it.

Also installed additional libraries. PIP and all stuffs . But still, it didnt work. I got the same error as below

Traceback (most recent call last):
File “twitterstream.py”, line 1, in
import oauth2 as oauth
ImportError: No module named oauth2

At last , i found that the error was occuring because of the 2 differnt python versions in my system.

Then i started locating python directory and checked where it is pointing to. when i checked /usr/bin/python , it was pointing to python 2.7.

Instead of running the script as

python script_name.py

i changed it to

/usr/bin/python script_name.py

And yes, it worked. Sometimes we complicate few easy stuffs 🙂

As the days are passing , computers are getting faster and faster . At the same time, the amount of data that is being used is growing exponentially. Hence, we are in a path of finding how to handle, store and analyze the huge data set in a effecient manner.

One among such example is Google Books Ngram . if you just navigate to the following URL

Google Books

you will be seeing a text box asking you to enter a book name. And it will search from 5.2 million books.

Believe it or not, Google has digitized all 5.2 million books and has come up with the concept of NGRAM.

http://books.google.com/ngrams

This link will show you a default page like .

Google Books Ngram

Before getting into the page description , we need to know what is ngram . N-gram is a word in which , N is the number of times the word is being used in the books between selected years .

In graph , by default it shows the output of 3 different names, Sherlock Homes, Albert Einstein , Frankenstein . It go searches in 5.2 Million books and yields a graph with the N-gram count, which can tell you the exact amount of time the word is being used in the books on those specific years.

Even the data set is available to download and research . These kind of data analysis is used for prediction and other purpose. It yields interesting results when analyzed with selective phrases.

In my past post , i explained the insertion sort with c++ code

https://shrinathsuccess.wordpress.com/2014/03/09/insertion-sort-c/

The major overhead in the insertion sort algorithm is swapping. For each element we are performing j-i swaps if the sequence is in descending order. Swaps are much costlier and we also need a new variable involved for swapping. If we could reduce the number of swapping then we will hit with the better performance.


#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
        cout << "Enter number of elements" << endl;

        int n,i,j;
        cin >> n;
        int a[n];
        int c = 0;
        srand(time(NULL));
        for(i=n; i>0 ; i--)
        {
                a[c] = i;
                c++;
        }
        cout << "Array Before Sorting" << endl;
          for(int i=0 ; i<5; i++)
          cout << a[i] << endl;
        for(i=1 ; i<n ; i++)
        {
                int key = a[i];

                for(j=i ; j>0 ; j--)
                {
                        if(a[j-1] > key)
                        {
                                a[j] = a[j-1];
                        }
                }
                a[j] = key;
        }

        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

TRIAL :

5 4 3 2 1

i = 1
key = 4
j = 1 , 1> 0

if(a[0] > key) => if(5 > 4)
a[1] = a[0] => 5 5 3 2 1

j=0 ; 0>0 – false
end of inner for loop
a[0] = key => 4 5 3 2 1
i=2
key = 3
j = 2

i = 2
key = 3
j = 2 ; 2 > 0
if(a[1] > key) => if(5 > 3)
a[2] = a[1] => 4 5 5 2 1

j=1 ; 1>0
if(a[0] > key) => if(4 > 3)
a[1] = a[0] => 4 4 5 2 1

j=0 ; j>0 – false
a[0] = 3 => 3 4 5 2 1

and the loop goes on like this ….

Instead of swapping the elements we perform assignment operation and at the end of the loop we assign the key back to the right place.

Special thanks to Nithin for pointing this out – https://www.facebook.com/nithin.kalathingal.5