445,929 Members | 1,598 Online
Need help? Post your question and get tips & solutions from a community of 445,929 IT Pros & Developers. It's quick & easy.

# efficient memoize decorator?

 P: n/a im plugging away at the problems at http://www.mathschallenge.net/index.php?section=project im trying to use them as a motivator to get into advanced topics in python. one thing that Structure And Interpretation Of Computer Programs teaches is that memoisation is good. all of the memoize decorators at the python cookbook seem to make my code slower. is using a decorator a lazy and inefficient way of doing memoization? can anyone point me to where would explain how to do it quickly. or is my function at fault? the code in question is as follows """ from memoize import memoize,memoize2 @memoize def col(n, count): if n == 1: return count elif n % 2 == 0: return col(n/2, count+1) else: return col((3*n+1)/2, count+2) import psyco psyco.full() start = time() maxlength = 0 best = 0 for i in range(1, 1000001): length = col(i,1) if length maxlength: maxlength = length best = i print maxlength, best end = time() print 'took', end-start Aug 18 '06 #1
11 Replies

 P: n/a sorry memoize is http://aspn.activestate.com/ASPN/Coo.../Recipe/496879 memoize2 is http://aspn.activestate.com/ASPN/Coo.../Recipe/466320 im plugging away at the problems at http://www.mathschallenge.net/index.php?section=project im trying to use them as a motivator to get into advanced topics in python. one thing that Structure And Interpretation Of Computer Programs teaches is that memoisation is good. all of the memoize decorators at the python cookbook seem to make my code slower. is using a decorator a lazy and inefficient way of doing memoization? can anyone point me to where would explain how to do it quickly. or is my function at fault? the code in question is as follows """ from memoize import memoize,memoize2 @memoize def col(n, count): if n == 1: return count elif n % 2 == 0: return col(n/2, count+1) else: return col((3*n+1)/2, count+2) import psyco psyco.full() start = time() maxlength = 0 best = 0 for i in range(1, 1000001): length = col(i,1) if length maxlength: maxlength = length best = i print maxlength, best end = time() print 'took', end-start Aug 18 '06 #2

 P: n/a At Friday 18/8/2006 17:14, th*************@gmail.com wrote: >sorrymemoize ishttp://aspn.activestate.com/ASPN/Coo.../Recipe/496879 This implementation uses cPickle to generate a key from the supplied function arguments, which is very slow and defeats the purpose of memoizing. In your example -function with no keyword arguments- use the much simpler implementation from

 P: n/a Gabriel Genellina wrote: This implementation uses cPickle to generate a key from the supplied function arguments, which is very slow and defeats the purpose of memoizing. depends on the cost of recreating an object, of course. it's a bit surprising that so many programmers seem to think that there are "one size fits all" solutions to caching and memoization... Aug 19 '06 #4

 P: n/a th*************@gmail.com wrote: all of the memoize decorators at the python cookbook seem to make my code slower. if you want good performance, use the following pattern: def col(n, count, memo={}): try: return memo[n, count] except KeyError: # ... calculate value ... memo[n, count] = value return value for some access patterns, the following may be faster: def col(n, count, memo={}): value = memo.get((n, count)) if value is None: # ... calculate value ... memo[n, count] = value return value to get maximum performance, make the memo dictionary public, and make the check at the original call site. is using a decorator a lazy and inefficient way of doing memoization? lazy, yes. inefficient? it depends. Aug 19 '06 #5

 P: n/a th*************@gmail.com wrote: im plugging away at the problems at http://www.mathschallenge.net/index.php?section=project im trying to use them as a motivator to get into advanced topics in python. one thing that Structure And Interpretation Of Computer Programs teaches is that memoisation is good. all of the memoize decorators at the python cookbook seem to make my code slower. is using a decorator a lazy and inefficient way of doing memoization? can anyone point me to where would explain how to do it quickly. or is my function at fault? Your problem is that you are mixing psyco and memoize decorators; psyco cannot accelerate inner functions that use nested scopes (see http://psyco.sourceforge.net/psycogu...supported.html ). You could try using the memoize decorator from: http://wiki.python.org/moin/PythonDecoratorLibrary , which doesn't use functions with closures, or use Fredrik Lundh's solution which puts memoization directly into the function. Ziga Aug 19 '06 #6

 P: n/a thanks, i was not just being lazy. i wanted to play with decorators and tell people on the forums how cool python is :) cheers for getting back to me, i could have done that myself i think, bar the error checking. do you have any links on good practice in python (i do think i am very lazy re: error checking and would like to make myself better) cheers, tom Fredrik Lundh wrote: th*************@gmail.com wrote: all of the memoize decorators at the python cookbook seem to make my code slower. if you want good performance, use the following pattern: def col(n, count, memo={}): try: return memo[n, count] except KeyError: # ... calculate value ... memo[n, count] = value return value for some access patterns, the following may be faster: def col(n, count, memo={}): value = memo.get((n, count)) if value is None: # ... calculate value ... memo[n, count] = value return value to get maximum performance, make the memo dictionary public, and make the check at the original call site. is using a decorator a lazy and inefficient way of doing memoization? lazy, yes. inefficient? it depends. Aug 19 '06 #7

 P: n/a does not seem to work for standalone functions, this is a method decorator only then? Traceback (most recent call last): File "prob14memoize.py", line 94, in ? length = col(i,1) File "prob14memoize.py", line 49, in __call__ object = self.cache[args] = self.fn(self.instance, *args) AttributeError: 'Memoize' object has no attribute 'instance' cheers, tom Gabriel Genellina wrote: At Friday 18/8/2006 17:14, th*************@gmail.com wrote: sorry memoize is http://aspn.activestate.com/ASPN/Coo.../Recipe/496879 This implementation uses cPickle to generate a key from the supplied function arguments, which is very slow and defeats the purpose of memoizing. In your example -function with no keyword arguments- use the much simpler implementation from

 P: n/a am i correct in thinking that psyco will just not accelerate, rather than break code it cannot deal with? that has been a pretty standard import on all my programs tom Ziga Seilnacht wrote: th*************@gmail.com wrote: im plugging away at the problems at http://www.mathschallenge.net/index.php?section=project im trying to use them as a motivator to get into advanced topics in python. one thing that Structure And Interpretation Of Computer Programs teaches is that memoisation is good. all of the memoize decorators at the python cookbook seem to make my code slower. is using a decorator a lazy and inefficient way of doing memoization? can anyone point me to where would explain how to do it quickly. or is my function at fault? Your problem is that you are mixing psyco and memoize decorators; psyco cannot accelerate inner functions that use nested scopes (see http://psyco.sourceforge.net/psycogu...supported.html ). You could try using the memoize decorator from: http://wiki.python.org/moin/PythonDecoratorLibrary , which doesn't use functions with closures, or use Fredrik Lundh's solution which puts memoization directly into the function. Ziga Aug 19 '06 #9

 P: n/a I suppose that lesson should not suprise me, programming is a subtle art that i need spend some time mastering thanks to all that have replied tom Fredrik Lundh wrote: Gabriel Genellina wrote: This implementation uses cPickle to generate a key from the supplied function arguments, which is very slow and defeats the purpose of memoizing. depends on the cost of recreating an object, of course. it's a bit surprising that so many programmers seem to think that there are "one size fits all" solutions to caching and memoization... Aug 19 '06 #10

 P: n/a At Saturday 19/8/2006 07:58, th*************@gmail.com wrote: >am i correct in thinking that psyco will just not accelerate, ratherthan break code it cannot deal with? that has been a pretty standardimport on all my programs Don't optimize what doesn't deserve optimization... That's a pretty standard mantra. Gabriel Genellina Softlab SRL __________________________________________________ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas Aug 19 '06 #11

 P: n/a At Saturday 19/8/2006 07:56, th*************@gmail.com wrote: >does not seem to work for standalone functions, this is a methoddecorator only then?Traceback (most recent call last): File "prob14memoize.py", line 94, in ? length = col(i,1) File "prob14memoize.py", line 49, in __call__ object = self.cache[args] = self.fn(self.instance, *args)AttributeError: 'Memoize' object has no attribute 'instance' For a standalone function, you should remove __del__ and self.instance, but I haven't tried it... Gabriel Genellina Softlab SRL __________________________________________________ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas Aug 19 '06 #12

### This discussion thread is closed

Replies have been disabled for this discussion.