My web application to shortening url

Web applications are part of web technology. There are many ways to develop a scalable web application. Google app engine  is a product of google which enables us to build powerful web applications. I created a web application to shortening the urls using Google app engine.  We can easily create  and maintain our  application in app engine  and  there is no need of any other server. With app engine we can build web application using languages such as java ,python ,Go. I selected python for my  application because it provide many libraries , tools and frameworks. When we use python a fast Python 2.5 interpreter needed. A Python web app interacts with the App Engine web server using the CGI protocol. Google app engine is reliable because our application run in a secure environment.

First  download and install software development kit from http://code.google.com/appengine/downloads.html. Then create a folder that contain our  application . I called mine application as ‘ urlshorten-neethu’.  To develop application our folder contain following files

• app.yaml    –  basic settings for application
• index.html  –  contain our application’s home page
• index.yaml  – generate automatically
• main.py     – main python program contain main functions for application

please visit my bitbucket account to see the codes contain above files , its url is https://bitbucket.org/neethuedappal/url-shortener

app.yaml contain name of our application , version,runtime and api_version .’Handlers’ are way of handling urls, script is our main python program. After creating app.yaml we can start like this.

dev_appserver.py ~/full/path/to/urlshorten-neethu

The web server listens on port 8080 by default. You can visit the application at this URL: http://localhost:8080/. And when we make changes to our app, the server will automatically load them, so we don’t need to worry about restarting it for changes.

The main program main.py contain all url shortening functions and datastore models . Our application is to short the long urls into tiny url, so we can use datastore property of google app engine. App engine datastore provide scalable storage of  web application also provide replication of data. Datastore saves data objects known as entities and entities have one or more properties. For our application we create a object and its two properties are original url which we enter and short url which we make. When we enter a url ,then first check whether it already present  in datastore, If already presents then fetch its short url from datastore. Otherwise create object and its propertis as entering url and short url and save object.

To redirecting our short url we create another class and check short url present in database using query and if present fetch and redirect its original url. After creating our application uploading it in google app engine.To upload our finished applicaton,run the following command

‘appcfg.py update urlshorten-neethu’

Now i  can provide  my url  shortening service to every one. please visit my application here http://urlshorten-neethu.appspot.com/  and short your urls…..

Prototype for managing unmanned level cross

Railways ,being cheapest mode of transportation in the world. But railway safety is a crucial aspect of rail operations . There are many accidents at unmanned railway cross due to lack of care . Here a solution to accidents at unmanned railway  level crossing. A GPS receiver is used to detect the current position of train by giving latitude and longitude. Then send this parameters to receiver system contain Atmega16 microcontroller using wireless communication. Receiver system calculate distance between level crossing and train , if distance less than a particular value flashing lights.

Advantages

• Cost effective
• Less security threats
• Number of GPS receiver same as number of trains
• Incremental introduction of new technology
• Reduce cost by saving expensive wiring

Data Flow Digrams

Here is the link for complete code https://bitbucket.org/neethuedappal/main-project-codes

Time complexity of various operations in python list

Time complexity is the amount of time required to execute the program . Time complexity  is calculated using “Big O”

Here i give a description of amount of time take each opeartions in python data types. Let us take input size as “n” and “m’ is additional parameter

List

A list in python is like array contain a sequence . Below a description about time complexity of varous list operations. Individual actions (append etc.) in any operation take  time complexity is O(1) else depend on size of input because after some operation elements must move their positions and time will vary (insert , extend etc.)

append       –  O(1)       insert element at end of list , no moving

insert             – O(n)    inserting begining or at a position , so elements move to right n times

delete item     – O(n)    elements move after deleted positon depend upon size of input

iteration        – O(n)    iterating n times

get slice        –  O(k)    k a value of parameter

extend          –  O(k)    k is new list to extend

get item        –  O(1)

set item        –  O(1)

get length     –  O(1)

i in list         –  O(n)

sort              –  O(n logn)

Optimization strategy of fibonacci series

Fibnoacci series is a basic example which teach recursion . Recursion a powerful programming  paradigm in which a function call itself .

Here a simple program of fibonacci series using recursion

def f(n):
 if n < 2:
   return n
 return  f(n-1) + f(n-2)

But this program just getting f(40) take atleast 8 minutes and for f(50) take really a long time , so it  is less efficient and too slow

why it slow?

The short answer is ‘recursion’ . Let us see how many times fibnocci function  calls itself recursively to compute f(50)

• f(50) is called once
• f(49) is called once
• f(48) is called 2 times
• f(47) is called 3 times
• f(46) is called 5 times
• f(45) is called 8 times
• …..
• f(1) is calculated 12,586,269,025 times

Number of recursively call grows  high rate , this simple program take O(2^n) times.

The main problem is that there is no way of remembering already calulated values . So it recalculate the same again, this recalculation take a larger time and then efficiency decreses and if number of input larger then duplicate calculation increses., and result take more time, therfore  we need a optimization strategy

Memoization

Memoization is a optimization strategy  which store the results for  later use and no recalculation

Below program explain how memoizing in fibonacci series

cache = {}
def fib(n):
  if n in cache:
     return cache[n]
  else:
     if n <2:
       cache[n]=n
     else:
      cache[n]= fib(n-1) + fib(n-2)
     return cache[n]

Here the dictionary named cache store the numbers which already calculated. When fibnocci function is called it check the cache if it contain result, if contain then function return immediately and no more recursive calls. If not ,  it has to compute new value and this value added to cache.

so using memoization there is no recalculation and we got result faster for large numbers. This test take less than one second please try it ….and see how faster it..

Basics of python

Python a scripting language with simple syntax and does not need compilation.  Its codes are too short and flexible, i interested to learn python because it easy to learn and simple.  Due to its open source nature python is portable also we run the program directly from the source code.

In my laptop python version 2.6.4 already installed and i started to programming in python ,this my first step to  world of python

just type python on terminal and then enter,

$ python
Python 2.6.4 (r264:75706, Oct 29 2009, 15:38:25)
[GCC 4.4.1] on linux2
Type “help”, “copyright”, “credits” or “license” for more information.
>>> print ‘Hello world’
Hello world
>>>

Python gives you the output of the line immediately! What you just entered is a single Python statement. We use print to  print any value that you supply to it. Here, we are supplying the text Hello world and this is promptly printed to the screen.

python  as a simple calculator

We can type any expression in interpreter and it will write value, operators +, -, * and / work just like in most other languages

>>> 2+2
4
>>> 2-2
0
>>> 2//2
1
>>> 2/2
1b
>>> (50-5*6)/4
5
>>> 7/-3
-3
>>>

Different python datatypes

    Strings

  Strings in python is a series of  characters . Strings surrounded by   ”  ”  or   ‘  ‘

  Strings are immutable

  >>> flower=”Rose”
  >>> print flower
  Rose
 >>> len(flower)
 4
 

String slices   –  Substring of a string called slice

>>> fruit=”banana”
>>> fruit[:3]
‘ban’
>>> fruit[3:]
‘ana’
>>> fruit[2:]
‘nana’

The operator [n:m] returns the part of the string from the n-th character to the m-eth character, including the first but excluding the last.

Lists

Lists are ordered set of values defined with index

>>> list=[1,2,3,4,5]
>>> list
[1, 2, 3, 4, 5]
>>>
Common list operations

• list.append(elem) — adds a single element to the end of the list.
• list.insert(index, elem) — inserts the element at the given index, shifting elements to the right.
• list.extend(list2) -adds the elements in list2 to the end of the list. Using + or += on a list is similar to using extend().
• list.index(elem) — searches for the given element from the start of the list and return index               
• list.remove(elem) — searches for the first instance of the given element and removes it
• list.sort() — sorts the list in place (does not return it). (The sorted() function shown below is preferred.)
• list.reverse() — reverses the list in place (does not return it)
• list.pop(index) — removes and returns the element at the given index. Returns the rightmost element if index is omitted (roughly the opposite of append()).

Dictionary

Python built-in  mapping type. Map keys to values

>>> dict={}
>>> dict[‘a’]=1
>>> dict[‘b’]=2
>>> dict[‘c’]=3
>>> dict
{‘a’: 1, ‘c’: 3, ‘b’: 2}
>>>

File

• To open a file  –   file=open(filename, mode)
•  To read a file  –    file.read()
•  To write to file  – file.write()
• To close a file  –  file.close()                   
  

Regular expressions  –     

Regular expressino is for pattern matching in a text file. ‘re ‘ module provide all functions for regular expressions .

• re.search(pat, text)  – Search a pattern in given text
• match.group() – Return the pattern
• re.findall() – All instances match this expression
• re.sub(paten,  replace, str)  – Search  all instances of given pattern in string and replace

Python utilities      Python provide many utility modules

os module - os module include functions to interact with filesystem

• filenames = os.listdir(dir)  – list of filenames in directory  ‘dir’
• os.path.join(dir,  filename)  – path of filename in directory
• os.path.abspath(path)  – given a path ,return absolute form
• os.path.dirname(path)  – give as dir/foo/bar.html
• os.path.basename(path) – give basename as bar.html
• os.path.exists()   – true if exists
• os.mkdir(dir) – make a directory
• shutil.copy(sourcepath, destpath)  –  copy files from source to destination

 commands module - Run external commands and capture output

• (status, output) = commands.getstatusoutput(cmd) – run command and return status and output.  if status is nonzero command failed
• commands.getstatus()  –  give status
• commands.getoutput()  – return value is a string containing output

urllib module - provide url fetch

• ufile = urllib.urlopen(url) -return file for given url
• text=ufile.read() – read like a file
• info = ufile.info() — the meta info for that request
• baseurl = ufile.geturl() — gets the “base” url for the request
• urllib.urlretrieve(url, filename) — downloads the url data to the given file path
• urlparse.urljoin(baseurl, url) — given a url that may or may not be full, and the baseurl of the page come and return full url