Memoize in python and html5

Memoization is a concept from algorithms which finds heavy use in dynamic programming. It is an optimization technique which gains time at the cost of space. So yes, this is an useful technique to know and implement in your algorithms.

The key idea is to have a data store which stores values computed and reuses them to compute the current iteration. The equation is particularly of the form

T(n) = T(n-k1) operator T(n-k2),

In case of the fibonacci series, f(n) = f(n-1) + f(n-2). If you see a computation of this form, you can readily apply a DP technique. Memoization provides a good infrastructure for writing such computations.

The implementation in python is really simple. Apply a decorator, hash the input parameter and if the function is called on the same input just return the already computed value. This is of course assuming all else is stationary and there are no side effects in the program.

Here is a small example from python which is from http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

import collections
import functools

class memoized(object):
   '''Decorator. Caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned
   (not reevaluated).
   '''
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      if not isinstance(args, collections.Hashable):
         # uncacheable. a list, for instance.
         # better to not cache than blow up.
         return self.func(*args)
      if args in self.cache:
         return self.cache[args]
      else:
         value = self.func(*args)
         self.cache[args] = value
         return value
   def __repr__(self):
      '''Return the function's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

@memoized
def fibonacci(n):
   "Return the nth fibonacci number."
   if n in (0, 1):
      return n
   return fibonacci(n-1) + fibonacci(n-2)

print fibonacci(12)

This is pretty neat if you ask me, saves you a lot of time when dealing with computations.

Now the fun part, HTML5 provides localStorage which is basically a dictionary into which you can write values and read back across page refreshes, AKA semi-persistence. This is sought to be a sort of replacement to cookies and most of the computation is done client side. So you could fetch data from the server and store it here, so you are paying for the network latency everytime.

The access usage goes somewhat like this

if(localStorage){
    if(localStorage['myvalue1'])
        return localStorage['myvalue1']
    else
        localStorage['myvalue1'] = value1

This is readily accessible structure, and should dramatically improve your performance. But as with anything web, there are security concerns. This is visible to anyone or anything with machine access, so

1. Encrypt your keys.
2. Don't store anything extra sensitive here.
3. Ask the user before doing this. Its only fair.

 Happy memoization.

Dependency Injection

Figuring out dependency injection manually is hard, I mean it really really hard. linkedIn has a library for depenecy injection https://github.com/Jakobo/inject. This is really great, but considering I don't care much about doing a require for others to load its not my cake.

underscore.js has unique features _bind to

Understanding currying

As functional paradigms are increasingly finding ways into my non-functional programs, I felt it was time to upgrade my skills.

I have been dabbling with haskell lately and will update some functional concepts.

Currying: What is it?

Currying is parameter application to functions. In c++, we can have arguments passed to a function.

int foo(type par1, type par2, ...){

    //perform operations on the par's

} 

This is really great, but in functional programming paradigm; every function takes only a single argument. Oh no! what are we to do? Well here is where currying comes to the rescue. If you pass a function multiple parameters in functional programming languages, such as scheme and haskell, they perform currying of the function.

How it works

The function takes the first parameter, then another function is applied to the 2nd parameter.

>let x3 x y z = x*y*z 

>x3 2 3 4

24

The above function takes 3 parameters and multiplies them together. This is just repeated application of the * function, right? I could have said (x*y)*z.

This is exactly what currying is doing. Internally I look at it like this

func1 = x3 (x)

func2 = func1(y)

func3 = func2(z)

The function is applied to one argument, the applied function is then called on the 2nd argument and so on.

This can be used with partial functions to create simple and intuitive data flow mechanisms.

haskell primitives

Haskell the lazy purely functional programming

1. The basic primitives

This is the greatest

Matlab Parfor

In the parallelization sphere of things, matlab is pretty up-to the mark. There are a lot of ways to parallelize in matlab.

The easiest is to create a matlabpool of workers and run you for loops in parallel using parfor. (the upper limit is 12 on a local machine) This is great if you using this on a local machine to prototype some application, but if you do want to deploy your application (compile and make an executable); you run into problems.