conditional computation

[robert]

I want to use a computation cache scheme like


o = CACHECOMPUTE complex-key-expr expensive-calc-expr


frequently and elegantly without writing complex-key-expr or expensive-calc-expr twice.
So its ugly:

_=complex-key-expr; o=cache.get(_) or cache.setdefaul t(_,expensive-calc-expr)

Any ideas?

-robert

[Gabriel Genellina]

Re: conditional computation

At Thursday 26/10/2006 16:30, robert wrote:

>I want to use a computation cache scheme like
>
>
o = CACHECOMPUTE complex-key-expr expensive-calc-expr
>
>
>frequently and elegantly without writing complex-key-expr or
>expensive-calc-expr twice.
>So its ugly:
>
_=complex-key-expr; o=cache.get(_) or
cache.setdefaul t(_,expensive-calc-expr)
>
>Any ideas?

The memoize pattern can help; in
http://wiki.python.org/moin/PythonDecoratorLibrary you can see an
implementation using decorators.


--
Gabriel Genellina
Softlab SRL

_______________ _______________ _______________ _____
Correo Yahoo!
Espacio para todos tus mensajes, antivirus y antispam ¡gratis!
¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar

[Mike Kent]

Re: conditional computation


robert wrote:

I want to use a computation cache scheme like
>
>
o = CACHECOMPUTE complex-key-expr expensive-calc-expr
>
>
frequently and elegantly without writing complex-key-expr or expensive-calc-expr twice.
So its ugly:
>
_=complex-key-expr; o=cache.get(_) or cache.setdefaul t(_,expensive-calc-expr)
>
Any ideas?
>
-robert

Your question is a bit terse, so my answer might not be spot on for it,
but it sounds like you want what is typically called 'memoization',
whereby a function caches its expensive-to-calculate return values,
where the cache is keyed by the function arguments.

See:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201

and various other implimentations in the Cookbook for details.

[robert]

Re: conditional computation

Gabriel Genellina wrote:

At Thursday 26/10/2006 16:30, robert wrote:
>

>I want to use a computation cache scheme like
>>
>>
> o = CACHECOMPUTE complex-key-expr expensive-calc-expr
>>
>>
>frequently and elegantly without writing complex-key-expr or
>expensive-calc-expr twice.
>So its ugly:
>>
> _=complex-key-expr; o=cache.get(_) or
>cache.setdefau lt(_,expensive-calc-expr)
>>
>Any ideas?

>
The memoize pattern can help; in
http://wiki.python.org/moin/PythonDecoratorLibrary you can see an
implementation using decorators.
>

thanks, as such it will not help hooking single line expressions, but it helped me remember the lambda ! :shame: :


class MemoCache(dict) : # cache expensive Objects during a session (memory only)
def memo(self, k, f):
try: return self[k]
except IndexError:
return self.setdefault (k, f())
cache=MemoCache ()
....

o = cache.memo( complex-key-expr, lambda: expensive-calc-expr )



Thats pythonic now.

-robert

[Fredrik Lundh]

Re: conditional computation

robert wrote:

I want to use a computation cache scheme like
>
o = CACHECOMPUTE complex-key-expr expensive-calc-expr
>
frequently and elegantly without writing complex-key-expr or expensive-calc-expr twice.
So its ugly:
>
_=complex-key-expr; o=cache.get(_) or cache.setdefaul t(_,expensive-calc-expr)
>
Any ideas?

in Python 2.5:

cache = collections.def aultdict(lambda : expensive-calc-expr)
value = cache[complex-key-expr]

or, if expensive-calc-expr needs access to the key:

class mycache(dict):
def __missing__(sel f, key):
value = expensive-calc-expr(key)
self[key] = value
return value

cache = mycache()
value = cache[complex-key-expr]

or, if expensive-calc-expr needs access to more than just the key, or
you need to run this on more than just 2.5:

cache = {}

key = complex-key-expr
try:
value = cache[key]
except KeyError:
value = cache[key] = expensive-calc-expr

</F>

[robert]

Re: conditional computation

Mike Kent wrote:

robert wrote:

>I want to use a computation cache scheme like
>>
>>
> o = CACHECOMPUTE complex-key-expr expensive-calc-expr
>>
>>
>frequently and elegantly without writing complex-key-expr or expensive-calc-expr twice.
>So its ugly:
>>
> _=complex-key-expr; o=cache.get(_) or cache.setdefaul t(_,expensive-calc-expr)
>>
>Any ideas?
>>
>-robert

>
Your question is a bit terse, so my answer might not be spot on for it,
but it sounds like you want what is typically called 'memoization',
whereby a function caches its expensive-to-calculate return values,
where the cache is keyed by the function arguments.
>
See:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201

and various other implimentations in the Cookbook for details.
>

thanks, yes, but the challenge was to hook expressions for memoizing ad hoc. See above solution.

[Bruno Desthuilliers]

Re: conditional computation

robert a écrit :
(snip)

class MemoCache(dict) : # cache expensive Objects during a session
(memory only)
def memo(self, k, f):
try: return self[k]
except IndexError:
return self.setdefault (k, f())
cache=MemoCache ()
...
>
o = cache.memo( complex-key-expr, lambda: expensive-calc-expr )
>

And how do you get back the cached value without rewriting both
complex-key-expr *and* expensive-calc-expr ? Or did I missed the point ?

[robert]

Re: conditional computation

Bruno Desthuilliers wrote:

robert a écrit :
(snip)

>class MemoCache(dict) : # cache expensive Objects during a session
>(memory only)
> def memo(self, k, f):
> try: return self[k]
> except KeyError: #<--------- was error
> return self.setdefault (k, f())
>cache=MemoCach e()
>...
>>
>o = cache.memo( complex-key-expr, lambda: expensive-calc-expr )
>>

>
And how do you get back the cached value without rewriting both
complex-key-expr *and* expensive-calc-expr ? Or did I missed the point ?

the complex-key-expr is written only once in the code - execution inevitable.

expensive-calc-expr is written only once in code and expensive execution (I have mostly matrix math) is only done at "f()" time.


-robert

[Bruno Desthuilliers]

Re: conditional computation

robert wrote:

Bruno Desthuilliers wrote:

>robert a écrit :
>(snip)

>>class MemoCache(dict) : # cache expensive Objects during a session
>>(memory only)
>> def memo(self, k, f):
>> try: return self[k]
>> except KeyError: #<--------- was error
>>return self.setdefault (k, f())
>>cache=MemoCac he()
>>...
>>>
>>o = cache.memo( complex-key-expr, lambda: expensive-calc-expr )
>>>

>>
>And how do you get back the cached value without rewriting both
>complex-key-expr *and* expensive-calc-expr ? Or did I missed the point ?

>
the complex-key-expr is written only once in the code

How do you get something back from the cache then ?

expensive-calc-expr is written only once in code

Same problem here... I fail to understand how you intend to use this
"cache".



--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in 'onurb@xiludom. gro'.split('@')])"

[robert]

Re: conditional computation

Bruno Desthuilliers wrote:

robert wrote:

>Bruno Desthuilliers wrote:

>>robert a écrit :
>>(snip)
>>>class MemoCache(dict) : # cache expensive Objects during a session
>>>(memory only)
>>> def memo(self, k, f):
>>> try: return self[k]
>>> except KeyError: #<--------- was error
>>> return self.setdefault (k, f())
>>>cache=MemoCa che()
>>>...
>>>>
>>>o = cache.memo( complex-key-expr, lambda: expensive-calc-expr )
>>>>
>>And how do you get back the cached value without rewriting both
>>complex-key-expr *and* expensive-calc-expr ? Or did I missed the point ?

>the complex-key-expr is written only once in the code

>
How do you get something back from the cache then ?
>

>expensive-calc-expr is written only once in code

>
Same problem here... I fail to understand how you intend to use this
"cache".

the first time, "self.setdefaul t(k, f())" executes the lambda ("f()"), stores it to the cache dict and the value is returned.

then on cache hit the stored value is just returned from the cache dict "try: return self[k]" and the lambda is not executed again.

note: the lambda expression expensive-calc-expr is just compiled but not executed as long as it is not called ( "f()" )

-robert

[Bruno Desthuilliers]

Re: conditional computation

robert wrote:

Bruno Desthuilliers wrote:

>robert wrote:

>>Bruno Desthuilliers wrote:
>>>robert a écrit :
>>>(snip)
>>>>class MemoCache(dict) : # cache expensive Objects during a session
>>>>(memory only)
>>>> def memo(self, k, f):
>>>> try: return self[k]
>>>> except KeyError: #<--------- was error
>>>> return self.setdefault (k, f())
>>>>cache=MemoC ache()
>>>>...
>>>>>
>>>>o = cache.memo( complex-key-expr, lambda: expensive-calc-expr )
>>>>>
>>>And how do you get back the cached value without rewriting both
>>>complex-key-expr *and* expensive-calc-expr ? Or did I missed the
>>>point ?
>>the complex-key-expr is written only once in the code

>>
>How do you get something back from the cache then ?
>>

>>expensive-calc-expr is written only once in code

>>
>Same problem here... I fail to understand how you intend to use this
>"cache".

>
the first time, "self.setdefaul t(k, f())" executes the lambda ("f()"),

(snip)
Robert, that's not the point. I do have enough Python knowledge to
understand this (totally trivial) code !-)

What I don't understand is how this code is supposed to save you from
having to actually write both complex-key-expr and
expensive-calc-expression more than once. You need them both each time
you access the cache - whether the result of expensive-calc-expression
has already been cached or not.

Now this seems so obvious that I guess I failed to understand some point
in your original spec (emphasis is mine):
"""
I want to use a computation cache scheme like


o = CACHECOMPUTE complex-key-expr expensive-calc-expr

frequently and elegantly *without writing complex-key-expr or
expensive-calc-expr twice*.
"""


--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in 'onurb@xiludom. gro'.split('@')])"

[robert]

Re: conditional computation

Robert, that's not the point. I do have enough Python knowledge to

understand this (totally trivial) code !-)
>
What I don't understand is how this code is supposed to save you from
having to actually write both complex-key-expr and
expensive-calc-expression more than once. You need them both each time
you access the cache - whether the result of expensive-calc-expression
has already been cached or not.
>
Now this seems so obvious that I guess I failed to understand some point
in your original spec (emphasis is mine):
"""
I want to use a computation cache scheme like
>
>
o = CACHECOMPUTE complex-key-expr expensive-calc-expr
>
frequently and elegantly *without writing complex-key-expr or
expensive-calc-expr twice*.
"""

But it is written only once.? And I have the cache functionality.

"You need them both each time you access the cache" : What you mean with "need"? I still suppose you think expensive-calc-expr is executed every time. But it is not - only the first time.

In my first ugly solution ...

_=complex-key-expr; o=cache.get(_) or cache.setdefaul t(_,expensive-calc-expr)

.. it is also only executed once - because the part after "or" is only evaluated if cache.get(_) doesn't find it in the cache.

Just ..

o = memo( complex-key-expr, lambda: expensive-calc-expr )

... is much more elegant.

Contrast to explain: Uncaching (stupid) would be for example:

o = cache.setdefaul t(complex-key-expr, expensive-calc-expr)

Because expensive-calc-expr is executed every time. (I remember once I had such a speed blocker bug in sloppy written code and only found it with the profiler)
Javaish ugly without writing the expressions twice (thus using variables) would be:

key=complex-key-expr
if key in cache:
o=cache[key]
else:
o=expensive-calc-expr
cache[key]=o


But who wants to write such code with python, when you have to convert many lines in an optimization effort in your code like

store-var = expensive-calc-expr
....
store-var = expensive-calc-expr
store-var = expensive-calc-expr
store-var = expensive-calc-expr
store-var = expensive-calc-expr
....


Thus what is not solved or what would you do better than:

store-var = memo( complex-key-expr, lambda: expensive-calc-expr )
....
store-var = memo( complex-key-expr, lambda: expensive-calc-expr )
store-var = memo( complex-key-expr, lambda: expensive-calc-expr )
store-var = memo( complex-key-expr, lambda: expensive-calc-expr )
store-var = memo( complex-key-expr, lambda: expensive-calc-expr )
.....

I think there is no principally better solution. Maybe format it for the art museum with operators to clean ,-brakets ...


store-var = rmemo(complex-key-expr) << lambda: expensive-calc-expr


-robert