Memoization Decorator

Recently I had the opportunity to give a short 10 min presentation on Memoization Decorator at our local UtahPython Users Group meeting.

Memoization:

• Everytime a function is called, save the results in a cache (map).
• Next time the function is called with the exact same args, return the value from the cache instead of running the function.

The code for memoization decorator for python is here: http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

Example:

The typical recursive implementation of fibonacci calculation is pretty inefficient O(2^n).

```def fibonacci(num):
print 'fibonacci(%d)'%num
if num in (0,1):
return num
return fibonacci(num-1) + fibonacci(num-2)>>> math_funcs.fibonacci(4)   # 9 function calls
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
fibonacci(2)
fibonacci(1)
fibonacci(0)
3```

But the memoized version makes it ridiculously efficient O(n) with very little effort.

```import memoized
@memoized
def fibonacci(num):
print 'fibonacci(%d)'%num
if num in (0,1):
return num
return fibonacci(num-1) + fibonacci(num-2)

>>> math_funcs.mfibonacci(4)  # 5 function calls
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
3```

We just converted an algorithm from Exponential Complexity to Linear Complexity by simply adding the memoization decorator.

Slides:

Presentation:

I generated the slides using LaTeX Beamer. But instead of writing raw LaTeX code I used reStructured Text (rst) and used rst2beamer script to generate the .tex file.

Source:

The rst file and tex files are available in Github.

https://github.com/amjith/User-Group-Presentations/tree/master/memoization_de...

Posted

Productive Meter

A few weeks ago I decided that I should suck it up and start learning how to develop for the web. After asking around, my faithful community brethren, I decided to learn Django from its docs

::Django documentation is awesome::

Around this time I came across this post about Waking up at 5am to code. I tried it a few times and it worked wonders. I've been working on a small project that can keep track of my productivity on the computer. The concept is really simple, just log the window that is on top and find a way to display that data in a meaningful way.

Today's 5am session got me to a milestone on my project. I am finally able to visaulize the time I spend using a decent looking graph. Which is a huge milestone for someone who learned how to display html tables 3 weeks ago.

Tools:

A huge thanks to my irc friends and random geeks who wrote awesome blog posts and SO answers on every problem I encountered.

I will be open-sourcing the app pretty soon. Stay tuned.

Posted

Too Many Classes Too Little Time

I'm taking a couple of the free online classes offered by Standford. One on Artifical Intelligence and one on Machine Learning

I haven't had so much fun since kindergarten. Actually that's not fair, I didn't enjoy kindergarten this much. I'm listening to the classes during my lunch, after work, during weekends. I'm working on my assignment with so much enthusiasm, I dread the day when this class ends.

Stanford just announced a slew of new online classes offered starting in Jan 2012. I was way too excited when I first read the description on them. Now I'm a little sad, becasue I want to take 8 out of the 11 courses that are being offered and I don't have enough time. :(

Woe is me.

ps: If you are not taking any of these classes you are missing out big time. Please do yourself a favor and sign up.

Posted

Picking 'k' items from a list of 'n' - Recursion

Let me preface this post by saying I suck at recursion. But it never stopped me from trying to master it. Here is my latest (successful) attempt at an algorithm that required recursion.

Background:

You can safely skip this section if you're not interested in the back story behind why I decided to code this up.

I was listening to KhanAcademy videos on probability. I was particularly intrigued by the combinatorics video. The formula to calculate the number of combinations of nCr was simple, but I wanted to print all the possible combinations of nCr.

Problem Statement:

Given 'ABCD' what are the possible outcomes if you pick 3 letters from it to form a combination without repetition (i.e. 'ABC' is the same as 'BAC').

At first I tried to solve this using an iterative method and gave up pretty quickly. It was clearly designed to be a recursive problem. After 4 hours of breaking my head I finally got a working algorithm using recursion. I was pretty adamant about not looking it up online but I seeked some help from IRC (Thanks jtolds).

Code:

```def combo(w, l):
lst = []
if l < 1:
return lst
for i in range(len(w)):
if l == 1:
lst.append(w[i])
for c in combo(w[i+1:], l-1):
lst.append(w[i] + c)
return lst```

Output:

```>>> combinations.combo('abcde',3)
['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde']```

Thoughts:

• It helps to think about recursion with the assumption that an answer for step n-1 already exists.
• If you are getting partial answers check the condition surrounding the return statement.
• Recursion is still not clear (or easy).

I have confirmed that this works for bigger data sets and am quite happy with this small victory.

Posted

Python Profiling

I did a presentation at our local Python User Group meeting tonight. It was well received, but shorter than I had expected. I should've added a lot more code examples.

We talked about usage of cProfile, pstats, runsnakerun and timeit.

Here are the slides from the presentations:

The slides were done using latex-beamer, but I wrote the slides in reStructuredText and used rst2beamer to create the tex file which was then converted to pdf using pdflatex.

The source code for the slides are available on github.

//   Posted

Programming - A Gateway Drug to Math

I decided to try my hand at the Stanford's AI Class. The pre-requisites mentioned Probability and Linear Algebra. So I started watching Probability videos on KhanAcademy

Sal Khan was teaching how to find the probability of 2 heads when you toss a coin 5 times.

A classic nCk problem:

$\small _nC_k = \frac{n!}{k!(n-k)!}$

The probability of getting 2 heads while tossing a coin 5 times is:

$P(2) = \frac{{_5C_2}}{2^5}$
But I wanted to find out the probability of getting at least 2 heads when I toss 5 coins.
Its really simple. All I had to do is P(2) + P(3) + P(4) + P(5).
But then computing$_nC_k$by hand (or a calculator) was painfully slow, let alone do it 4 times.
So I wrote two little functions in Python that will calculate factorial (yes I reinvented the wheel) and$_nC_k$
Nothing teaches you math faster than trying to write a program to do the math for you.
Writing a program is the same as teaching the computer how to do a certain task. The only way you can teach someone to do a task is to become a master at doing that task yourself.

Bonus: It also teaches you corner cases like 0! = 1 and $\small _5C_5 = 1$ that you wouldn't think of otherwise.
Tags
Posted

When was the last time I vented about C++? The answer for that is always:

"TOO LONG AGO".

The initial friction to setup a substantial project using C++ is unfucking bearable.

When we started code revamp at work recently, I decided to be a good citizen and decided to incorporate cpptest, a unit testing framework in our project.

It made me realize how unreasonably complicated Makefiles can be. After 3 hours of peeling away at the complexity I managed to add cpptest to the build dependency of the project.

Now time to write a few tests and check it out. I'm thinking "We are almost there".

FALSE!

Compilation gives me a gazillion error messages that make absolutely no sense. After about 30mins of StackOverflowing and Googling, I find out that its not enough to include string.h and map.h in my  header files, but I also need to namespace it. Of course there is no indication (not even a hint) of that in the error messages. So I add 'using namespace std' and get past it.

Awesome my first test is compiling successfully. Time to run this baby and declare victory.

Close! But no cigar.

The executable was unable to load the CppTest library during runtime. Argh!

I set my LD_LIBRARY_PATH env variable and now it's running. But I can't ask everyone in my team to do that, so I have to figure out how to statically link that library.

It's already 6pm and I'm hungry. That'll have to wait for another day.

TL;DR - C++ and Makefile can burn in a fire of thousand suns.
Posted

Rapid Prototyping in Python

I was recently assigned to a new project at work. Like any good software engineer I started writing the pseudocode for the modules. We use C++ at work to write our programs.

I quickly realized it's not easy to translate programming ideas to English statements without a syntactic structure. When I was whining about it to Vijay, he told me to try prototyping it in Python instead of writing pseudocode. Intrigued by this, I decided to write a prototype in Python to test how various modules will come together.

Surprisingly it took me a mere 2 hours to code up the prototype. I can't emphasize enough, how effortless it was in Python.

What makes Python an ideal choice for prototyping:

Dynamically typed language:

Python doesn't require you to declare the datatype of a variable. This lets you write a function that is generic enough to handle any kind of data. For eg:

```def max_val(a,b):
return a if a >b else b```

This function can take integers, floats, strings, a combination of any of those, or lists, dictionaries, tuples, whatever.

A list in Python need not be homogenous. This is a perfectly good list:

`[1, 'abc', [1,2,3]]`

This lets you pack data in unique ways on the fly which can later be translated to a class or a struct in a statically typed language like C++.

```class newDataType
{
int i;
String str;
Vector vInts;
};```

Rich Set to Data-Structures:

Built-in support for lists, dictionaries, sets, etc reduces the time involved in hunting for a library that provides you those basic data-structures.

Expressive and Succinct:

The algorithms that operate on the data-structures are intuitive and simple to use. The final code is more readable than a pseudocode.

For example: Lets check if a list has an element

```>>> lst = [1,2,3]    # Create a list
>>> res = 2 in lst   # Check if 2 is in 'lst'
True```

If we have to do it in C++.

```list lst;
lst.push_back(3);
lst.push_back(1);
lst.push_back(7);
list::iterator result = find(lst.begin(), lst.end(), 7);
bool res = (result != lst.end())```

Python Interpreter and Help System:

This is a huge plus. The presence of interpreter not only aids you in testing snippets of code, but it acts as an help system. Lets say we want to look up the functions that operate on a List.

```>>> dir([])
'__delslice__', '__doc__', '__eq__', '__format__', '__ge__',
'__getattribute__', '__getitem__', '__getslice__', '__gt__', '__hash__',
'__iadd__', '__imul__', '__init__', '__iter__', '__le__', '__len__',
'__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__',
'__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__',
'__setslice__', '__sizeof__', '__str__', '__subclasshook__', 'append',
'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

>>> help([].sort)
Help on built-in function sort:

sort(...)
L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
cmp(x, y) -> -1, 0, 1```

• The type definition of the datastructures emerge as we code.
• The edge cases start to emerge when you prototype.
• A set of required supporting routines.
• A better estimation of the time required to complete a task.
Posted

New Laptop

I finally ordered a new Macbook air for myself. One of my friends remarked at the fact that this is the first brand new laptop that I've ordered for myself. Since I'm a bit of a Linux fanatic, I tend to restore old computers and install a linux distro and make them useable. So I always get old laptops for cheap for myself. But this time I decided it's time to checkout Mac OS X. So I'll be replacing my Netboook (yep!) with the Macbook air. Anyone need a Lenovo S10 netbook :). I will even do a clean-install of Ubuntu or your choice of Linux distro.

This new Macbook air will be my primary development machine. Let's hope it can take the abuse.

Posted

Falsetto dude and the Fat man

A typical conversation between my wife and I:

Playing Ne Me Quitte Pas by Nina Simone

Yoshi : Ow! What is that abomination?
Amjith: It's a french song sung by the great Nina Simone.
Yoshi : It's a woman? Sounded like a dude singing in falsetto.
Yoshi : I'm leaving the room if you don't change the song.
Amjith: FINE. You play something then.

Yoshi puts on Ave Maria by Pavarotti.

I wait for 2 mins.

Amjith: Hey! Your fat man seems to be yelling at Maria.

Yosh leaves the room and I sleep on the couch.

The End
Posted