Memoizing Generators

[Mark]

Hi Michael,


Michael Sparks wrote:

> How would you deal with the following generator? (On the assumption you
> want a a general purpose memoisation mechanism :)

> <*snip* a generator reading from an input source>
 
> If your source is a network connection, or a real user this becomes
> further indeterminate... Not a suggestion to not try, just worth
> considering :)

I think one of the standard assumptions with memoization is that you have a
deterministic algorithm ... specifically, given an input, the output is
fixed.  So, your example of entering a file and getting different data,
throws typical (in my opinion ... which is by no means sacred) memoization
out the window.


> def runGenerator(fn,args,timeAlloted):
>    tstart = time.time()
>    gen = fn(args).next
>    r = gen()
>    while 1:
>       if time.time()-tstart >=timeAlloted:
>          break
>       r = gen()
>    return r

Now, this is a problem I like.  It would be pretty damn awsome to memoize a
function with 1) a time constraint and 2) a parameter that would indicate
when a time constraint is no longer sufficient and thus more work needs to
be done.  Finally, if the generator could _restart_ at the point of work
already done, you would be saving the work done to that point which is
memoization's purpose:

Something like:

runGenerator(PIdigits, None, 10)

and then later

runGenerator(PIdigits, None, 20)

Then our memoizer would say, well, I can get more digits in the extra 10
seconds .... so, I need to recompute this answer.  But wait, hopefully,
I've stored both the numerical result for 10 seconds along with the
generator that got me there.  So, all I need to do is look up the 10 second
generator and run it for another 10 seconds.  Humm, can we copy generators? 
I don't seem to think so.

So, the memoizer class would need some more logic and storage to determine
whether to return a stored result, computer a brand new result, or
bootstrap off a previous generator.  There would also need to be a
mechanism for determining just how long is "long enough" that more time
needs to be allocated (a really hard problem might not get any further in
12 seconds than it does in 9 seconds).  And we'd need a copy of the
generator so we could go from, say 10 second generator to 20 second, but
later go from 10 to 15 seconds.  Although, we could get around the problem
by using the maximally accurate result computed so far (presuming we can
look it up in the user specified time interval).  Then we'd only need the
generator at the farther point ... and we could just keep running it when
the user gives us more time.  Yeah, that could work nicely!

> 
> Consider the possibility that the function is a "next move" in chess and
> the time is set by the first player to "hard" - ie lots of time. The next
> time a player comes along with the time set to "easy", the memoised
> version won't be aware of this in this scenario and returns the hard

We could paramaterize the generator (and/or the memoizer) based on the
difficulty setting .... couldn't we?  

> result (but very quickly...), or worse hits stop iteration - which the

This is another interesting problem .... the "quick result" is actually a
means of making the game harder.

> Regards,
> Michael.

Great ideas.  I might code up the timing based memoizer for kicks.

Regards,
Mark