Memoization Library for Python 2.7

memoization library for python 2.7

Is there any specific reason as why it is not available in 2.7?

@Nirk has already provided the reason: unfortunately, the 2.x line only receive bugfixes, and new features are developed for 3.x only.

Is there any 3rd party library providing the same feature?

repoze.lru is a LRU cache implementation for Python 2.6, Python 2.7 and Python 3.2.

Documentation and source code are available on GitHub.

Simple usage:

from repoze.lru import lru_cache

@lru_cache(maxsize=500)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Python 2.7 - Using Classes as Decorators for Timing and Memoization

With your code, you are memoizing a timed function, which means the timing code is also skipped when the arguments are found in the cache. If you reverse the order of the decorators

@Timer
@Memoize
def pass_and_square_time(seconds):
    # Call time.sleep(seconds)
    time.sleep(seconds)
    # Return the square of the input seconds amount.
    return seconds**2

now you are timing a memoized function. Whether or not the arguments are found in the cache, you time the call to the memoized function.

Memoization of Imported Functions

The from module import function statement aliases the function from the module as function. Therefore, when it gets decorated, only the alias is decorated. The recursive calls are to the unaliased function (in the module) i.e. the undecorated one.

You can think of this as creating a partial memory, the aliased function will remember the results of it's own calculations, but not the intermediate steps. In the code above, fibonacci(100) will be the only entry in dictionary when it's done. (Don't wait up for it.)

Using import module syntax doesn't alias the function, module.function is it's 'real' name. Therefore, decorations applied to fibonacci.fibonacci will also decorate the function that's being recursively called.

Working implementation:

import fibonacci

def with_memoization(function):

    past_results = {}

    def function_with_memoization(*args, **kwargs):
        if args not in past_results:
            past_results[args] = function(*args, **kwargs)
        return past_results[args]
    return function_with_memoization

fibonacci.fibonacci = with_memoization(fibonacci.fibonacci)

print(fibonacci.fibonacci(100))

What can be done to speed up this memoization decorator?

You're not actually caching any data, because each time you set a new cached value you overwrite the previous:

Memoized.__cache[self.key] = {args : value}

eg.

import functools

class Memoized(object):
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    cache = {}

    def __init__(self, func):
        self.func = func
        self.key = (func.__module__, func.__name__)
        self.cache[self.key] = {}

    def __call__(self, *args):
      try:
          return Memoized.cache[self.key][args]
      except KeyError:
          value = self.func(*args)
          Memoized.cache[self.key][args] = value
          return value
      except TypeError:
          # uncachable -- for instance, passing a list as an argument.
          # Better to not cache than to blow up entirely.
          return self.func(*args)

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

    @staticmethod
    def reset():
        Memoized.cache = {}

fib(30) without caching: 2.86742401123
fib(30) with caching: 0.000198125839233

Some other notes:

Don't use __prefix; there's no reason to here and it only uglifies the code.
Instead of using a single, monolithic, class-attribute dict, give each instance of Memoized its own dict, and keep a registry of Memoized objects. This improves encapsulation, and removes the oddity of depending on the module and function names.

import functools
import weakref

class Memoized(object):
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.

    >>> counter = 0
    >>> @Memoized
    ... def count():
    ...     global counter
    ...     counter += 1
    ...     return counter

    >>> counter = 0
    >>> Memoized.reset()
    >>> count()
    1
    >>> count()
    1
    >>> Memoized.reset()
    >>> count()
    2

    >>> class test(object):
    ...     @Memoized
    ...     def func(self):
    ...         global counter
    ...         counter += 1
    ...         return counter
    >>> testobject = test()
    >>> counter = 0
    >>> testobject.func()
    1
    >>> testobject.func()
    1
    >>> Memoized.reset()
    >>> testobject.func()
    2
    """

    caches = weakref.WeakSet()

    def __init__(self, func):
        self.func = func
        self.cache = {}
        Memoized.caches.add(self)

    def __call__(self, *args):
      try:
          return self.cache[args]
      except KeyError:
          value = self.func(*args)
          self.cache[args] = value
          return value
      except TypeError:
          # uncachable -- for instance, passing a list as an argument.
          # Better to not cache than to blow up entirely.
          return self.func(*args)

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

    @staticmethod
    def reset():
        for memo in Memoized.caches:
            memo.cache = {}

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Edited: add tests, and use weakref.WeakSet. Note that WeakSet is only available in 2.7 (which the OP is using); for a version that works in 2.6, see the edit history.