arungeek
Hacks and Tweaks



Programming

December 31, 2013
 

Python, Memoization, Dynamic Programming, Fibonacci Series and some Fun!

More articles by »
Written by: arunenigma
Tags: , ,

fibonacci

P

ython can implement the recursive formulation directly, caching return values. Memoization is a method where if a call is made more than once with the same arguments, and the result is returned directly from the cache.

For example, we can dynamically solve the exponential Fibonacci series by using a Memoize class or a memoize function designed as an algorithm that uses nested scopes to give the wrapped function a memory boost.

Using a Memoize class as a decorator to boost the recursive call.

 Using a memoize function as a decorator to boost the recursive call.

Now since we have a Memoize class and a memoize function to boost recursion calls. Lets compare the run times between the two and the original recursion function.

Simple Recursion Function to find Fibonacci number:

 Run Time Comparison:

Simple Recursive Function : 73.918 s = 73918 ms

Recursive Function using Class Memoization: 0.025 s = 25 ms

Recursive Function using Function Memoization: 0.0275 s = 27.5 ms

As you can see, the memoized methods either using a class or a function is typically 3000 times faster!



About the Author

arunenigma
Computer Science Graduate Student @ Case Western Reserve University, Cleveland, USA



 
 

 
Factory_1

Python Factory Design Patterns using Switch Case

I googled for Factory Method Design Pattern in Python but couldn’t find a good resource. So, I  am sharing an example program to demonstrate this design pattern in Python which I frequently use. The factory method pattern is...
by arunenigma
 

 
 
Gospers_glider_gun

Conway’s Game of Life Implemetation in Python with cool patterns

he Game of Life (or simply Life) is not a game in the conventional sense. There are no players, and no winning or losing. Once the “pieces” are placed in the starting position, the rules determine everything that ha...
by arunenigma
 

 
 
bin-tree

Python AVL Tree Implementation with ASCII visualization

n computer science, an AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any tim...
by arunenigma
 

 

 
bst

Binary Search Tree in Python with ASCII art visualization

Binary search tree implementation in Python with: in, post and pre-order traversals. Also includes methods for insertion, deletion and search of nodes. Deletion is fairly complex and is made possible by keeping track of parents...
by arunenigma
 

 
 
elephant_rgb-380x285

Installing Hadoop on Mac OSX Mountain Lion (Step by Step Instructions)

Setting up a single node Apache Hadoop instance on OS X is pretty simple and much the same as on any other Linux/Unix machines, with a small bit of customer configuration. See here for official instructions. This tutorial provi...
by arunenigma