Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Memoization Handler

Is it "good practice" to create a class like the one below that can handle the memoization process for you? The benefits of memoization are so great (in some cases, like this one, where it drops from 501003 to 1507 function calls and from 1.409 to 0.006 seconds of CPU time on my computer) that it seems a class like this would be useful.

However, I've read only negative comments on the usage of eval(). Is this usage of it excusable, given the flexibility this approach offers?

This can save any returned value automatically at the cost of losing side effects. Thanks.

import cProfile

class Memoizer(object):
    """A handler for saving function results."""
    def __init__(self):
        self.memos = dict()
    def memo(self, string):
        if string in self.memos:
            return self.memos[string]
        else:
            self.memos[string] = eval(string)
            self.memo(string)

def factorial(n):
    assert type(n) == int
    if n == 1:
        return 1
    else:
        return n * factorial(n-1) 

# find the factorial of num
num = 500
# this many times
times = 1000

def factorialTwice():
    factorial(num)
    for x in xrange(0, times):
        factorial(num)
    return factorial(num)

def memoizedFactorial():
    handler = Memoizer()
    for x in xrange(0, times):
        handler.memo("factorial(%d)" % num)
    return handler.memo("factorial(%d)" % num)


cProfile.run('factorialTwice()')

cProfile.run('memoizedFactorial()')
like image 910
827 Avatar asked Jul 31 '10 07:07

827


People also ask

What is memoization used for?

In programming, memoization is an optimization technique that makes applications more efficient and hence faster. It does this by storing computation results in cache, and retrieving that same information from the cache the next time it's needed instead of computing it again.

Is memoization same as caching?

Memoization is a specific form of caching that involves caching the return value of a function based on its parameters. Caching is a more general term; for example, HTTP caching is caching but not memoization.

What is memoization algorithm?

Memoization is a technique for improving the performance of recursive algorithms. It involves rewriting the recursive algorithm so that as answers to problems are found, they are stored in an array. Recursive calls can look up results in the array rather than having to recalculate them.

Can you memoize a hook?

Use memoization hooks only when there are benefits in terms of rendering performance. For example, when rendering large lists, a memoized result may speed up the actual rendering performance. For simple cases, it is not required to use memoization because the overhead may not offset the performance improvement.


2 Answers

You can memoize without having to resort to eval.

A (very basic) memoizer:

def memoized(f):
    cache={}
    def ret(*args):
        if args in cache:
            return cache[args]
        else:
            answer=f(*args)
            cache[args]=answer
            return answer
    return ret

@memoized
def fibonacci(n):
    if n==0 or n==1:
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

print fibonacci(100)
like image 150
MAK Avatar answered Nov 02 '22 10:11

MAK


eval is often misspelt as evil primarily because the idea of executing "strings" at runtime is fraught with security considerations. Have you escaped the code sufficiently? Quotation marks? And a host of other annoying headaches. Your memoise handler works but it's really not the Python way of doing things. MAK's approach is much more Pythonic. Let's try a few experiments.

I edited up both the versions and made them run just once with 100 as the input. I also moved out the instantiation of Memoizer. Here are the results.

>>> timeit.timeit(memoizedFactorial,number=1000)
0.08526921272277832h
>>> timeit.timeit(foo0.mfactorial,number=1000)
0.000804901123046875

In addition to this, your version necessitates a wrapper around the the function to be memoised which should be written in a string. That's ugly. MAK's solution is clean since the "process of memoisation" is encapsulated in a separate function which can be conveniently applied to any expensive function in an unobtrusive fashion. This is not very Pythonic. I have some details on writing such decorators in my Python tutorial at http://nibrahim.net.in/self-defence/ in case you're interested.

like image 45
Noufal Ibrahim Avatar answered Nov 02 '22 11:11

Noufal Ibrahim