By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,929 Members | 1,598 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
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:
>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
<http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/325205NOT
the original recipe but the comment by Chris Spencer titled "A
working example".

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 #3

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...

</F>

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.

</F>

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.

</F>
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
<http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/325205NOT
the original recipe but the comment by Chris Spencer titled "A
working example".

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 #8

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...

</F>
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, rather
than break code it cannot deal with? that has been a pretty standard
import 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 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'
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.