efficient memoize decorator?

[thattommyhallll]

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

[thattommyhallll]

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

[Gabriel Genellina]

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

[Fredrik Lundh]

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>

[Fredrik Lundh]

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>

[Ziga Seilnacht]

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

[thattommyhallll]

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>

[thattommyhallll]

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

[thattommyhallll]

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

[thattommyhallll]

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>

[Gabriel Genellina]

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

[Gabriel Genellina]

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