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.
