Recursion and Memoization - A Fibonacci Example

In this post, I will try to describe why memoization can be a great optmization technique in the recursive function implementations with an example of fibonacci sequence.

Straight from Wikipedia, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs.

Basically, we maintain a lookup table and store the computer values for particular cases which lets us query and use the corresponding value for particular case present in the lookup tables. This reduces function call overheads. Now in order to understand why this is a great optimization technique in recursion, lets first draw a recursion tree for finding n^th term in fibonacci sequence.

                           fib(5)                          
                             /\                              
                            /  \
                           /    \
                          /      \                      
                     fib(4)       fib(3)                                 
                      /\               /\                          
                     /  \             /  \
                    /    \           /    \
                   /      \         /      \                         
               fib(3)    fib(2)     fib(2) fib(1) -> 1                                    
                  /\         /\          /\                          
                 /  \       /  \        /  \                         
                /    \     /    \      /    \
               /      \   /      \    /      \                        
          fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) -> 0                                        
          /\        |     |      |        |    |               
         /  \       1     1      0        1    0               
    fib(1) fib(0)                                                       
       |      |                                               
       1      0 

We can clearly see the calls to fib() with same arguments several times. For example, fib(1) is called 5 times and fib(2) 3 times. Thus, we are repeating same calculations multiple times and imagine how this would look like for large value of n. If we would have maintained the value of fib(n) in the lookup table when computed the value for the first time.

The python code without memoization looks like below and notice the runtime:

#!/usr/bin/python

def fib(n):
        if n == 0:
                return 0
        if n == 1:
                return 1
        val = fib(n-1) + fib(n-2)
        return val

print fib(50)

And, now with the memoization, you will notice significant improvement in runtime.

#!/usr/bin/python

known = {0:0, 1:1}

def fib(n):
        if n in known:
                return known[n]
        known[n] = fib(n-1) + fib(n-2)
        return known[n]

print fib(50)

If you run and compare above two codes, you will find that the addition of memoization significantly improves the performance of recursive functions. Recursion are generally known to be terribly slow however memoization can make the difference insignificant. Some languages now provide memoization as the language feature natively or via third party APIs such as groovy memoize.


Read more...

Download Windows Binaries For Python Packages

Someone from the University of California has made it easier for windows python users to install python extension packages easily by providing several 32-bit and 64-bit windows binaries for several scientific open source python libraries.

If you can't figure out your way in installing python libraries, you can download the binaries for several libraries from HERE.

Most binaries are built from source code found on PyPI or in the projects public revision control systems. Definitely the page to be bookmarked for the windows python'ers if you want to easily install python libraries :)


Read more...

How To Easily Install EasyInstall In 64 bit Windows

Easy Install(easy_install) is a python module (easy_install) bundled with setuptools that lets you automatically download, build, install, and manage Python packages. Easy Install gives you a quick and painless way to install packages remotely by connecting to the cheeseshop or even other websites via HTTP. It is somewhat analogous to the CPAN and PEAR tools for Perl and PHP, respectively. This How To will guide you in installing the easy_install utility easily in windows.

First download the ez_setup.py file.

Run the above script by typing in command prompt the following:

python.exe ez_setup.py

Once the script finishes, new directory "Scripts" will be created in the python installation directory and it will contain the easy_install.exe file in that directory.

Now all you have to do is add the Scripts path to system's Environment Variables to access this tool easily.

Right click on computer, go to properties, Advanced System Settings, Environment Variables, System Variables and edit the "Path" variable by adding correct path to the Scripts directory.

I hope this helps :)


Read more...

Extracting All Hyperlinks From Webpages - Python

In this example, I am going to show how easily you can extract all the links in a webpage using python. If you are learning to write some small scale crawler, this can be a quick startup on how you can extract the links in any webpage.

Basically, we will send the http request to any webpage and we will read the HTML response except in the case when the connection can not be established. In such case, we will simply inform the user that we could not connect to the website.

For all these stuffs, we will import few modules and most important ones are re and urllib2 for regular expression stuff and HTTP request/response stuffs respectively.

We then write the regex for the hyperlinks for which we will make a search in the HTML data we get back after sending the request from the server. Note the <a href=[\'"]?([^\'" >]+). The small brackets are there to let us capture our necessary information i.e. the actual links.

Now you understood what we'll be doing, below is the python script to extract the hyperlinks from any webpage.

#!/usr/bin/python

import re, urllib2
from sys import argv

if (len(argv) != 2):
    print "No URL specified. Taking default URL for link extraction"
    url = "http://www.techgaun.com"
else:
    url = str(argv[1])
    
links_regex = re.compile('<a href=[\'"]?([^\'" >]+)', re.IGNORECASE)
url_request = urllib2.Request(url)
try:
    response = urllib2.urlopen(url_request)
    html = response.read()
    links = links_regex.findall(html)
    print '\n'.join(links)
except urllib2.URLError:
    print "Can't Connect to the website"

Now run the script as python extracter.py http://www.techgaun.com or any URL you wish to.

So isn't it a good start for writing your own simple web crawler? :P


Read more...

Emesene Password Cracker in Python

I had recently posted a small tutorial on Emesene messenger password cracking. I have coded a small python script today that automates the process of cracking the saved passwords of emesene messenger.

#!/usr/bin/python

import os, sys, pwd, binascii

def coder():
    print """
        Coded By Samar Dhwoj Acharya
        http://www.techgaun.com
        Checked in emesene1.0
        
    """

def getpass():
    user = pwd.getpwuid(os.getuid()).pw_name
    emesene_file = "/home/%s/.config/emesene1.0/users.dat" % (user)
    if os.path.exists(emesene_file) == True:
        fp = open(emesene_file, "r")
        for line in fp.readlines():
            line_list = line.split(":")
            line_list[1] = binascii.unhexlify(line_list[1])
            print "%s : %s" % (line_list[0], line_list[1])
        fp.close()
    else:
        print "Could not locate the users.dat file."
coder()
getpass()

To run this tool, type as following in the terminal:

./emesene_cracker.py

Download Emesene Password Revealer



Read more...