(I apologize if this comes through twice).
Raul, I tested your scheme, and the result was a "fast routine" time of
under half a second, and a "slow routine" time of 1.12 seconds. I did the
thing by using an M. and a string to change the value of the number for
every routine.
Then I tried doing the definitions like this:
NB. ". 'E66a=: e66a&([ ',(":i),'&]) M.'
NB. ". 'E66p=: e66p&([ ',(":i),'&]) M.'
NB. ". 'E66q=: e66q&([ ',(":i),'&]) M.'
NB. ". 'E66P=: e66P&([ ',(":i),'&]) M.'
NB. ". 'E66Q=: e66Q&([ ',(":i),'&]) M.'
E66a =: e66a M.
E66p =: e66p M.
E66Q =: e66Q M.
E66P =: e66P M.
E66q =: e66q M.
You can see I NB.'d out the variable headers, and just used a simple
indirect header. Boom. Fastest times yet. This is actually a great
technique, by attaching memoization to an indirect header, you can control
specifically which calls you want to be memoized and which you don't. In
fact, you could create multiple active memo buckets by using multiple
aliases and calling the indirect routine through the appropriate alias.
But this indirection means that I can reset the memo buckets once per
internal routine.
(E66a =: e66a M.),(E66p =: e66p M.),(E66Q =: e66Q M.),(E66P =: e66P
M.),(E66q =: e66q M.)
Coding it like this makes the whole thing a lot better looking imho in that
it does not spread out the program. There is no difference in execution
time, at all.
The final run time was 1.1 seconds for the "slow" routine, and 0.475 seconds
for the "fast" routine. This is probably max benefit from memoization with
near zero holdup from old memoized trash. I doubt that there is another
order of magnitude to squeeze out of this...but, essentially, almost the
entire improvement was squeezed out of the memoization routines by clearing
them as often as reasonable.
Just for the heck. I put in
if. 0=1|i do.
(E66ax =: e66ax M.),(E66px =: e66px M.),(E66Qx =: e66Qx M.),(E66Px =: e66Px
M.),(E66qx =: e66qx M.)
end.
There was no measurable change in execution speed. I then did runs with
0=2|i, 0=3|i 0=4|i and so forth, by 1 to 5, then 10, 15, 20. The program
runs fastest with 0=1|i, that is, with the memo buckets cleared every cycle.
Every increase in delay in clearing the memo buckets makes the program run
slightly slower.
Now I probably was not clear. I was hoping that *any* function definition
would clear the memo buckets. So I defined a random but unused function,
and that didn't clear the memos. I thought that the functions were too big
to redefine completely in line. But the only way I had to completely
redefine the memoized function was to load the defs from the file, and that
had a lot of overhead, there were other functions, the trip to the O/S and
so forth.
I just plain didn't think of putting memoization on an intermediate
function. I've written a function for one of the euler things where some
fraction of the calls were well served by memoization, but about 3/4 of the
calls would never be made again. This scheme would have been perfect,
separate entries, for different callers, one with memoization, one without.
Further, as I mentioned, this would allow you to increase the memoization
space, although you might have to pass in the name you called a function by,
when you called it, so it would know what name it needed to call itself
recursively by.
On Tue, Oct 18, 2011 at 9:11 AM, Raul Miller <[email protected]> wrote:
>
>
> I am surprised that function redefinition does not clear the
> memoization, but maybe the memo is keyed by the function definition?
>
I think we misunderstood each other. Function redefinition does clear the
memoization, since reloading the functions from disk cleared the memoization
tables. That was the first thing I noticed. I was trying to do as little as
I could to clear the memoization, and the second function was the winner.
>
> Anyways, I would try updating the definition with an extraneous
> constant. Since J does not do data flow analysis, that should be
> sufficient.
>
> In other words, if you have something like:
> F=: f&([ 23&]) M.
>
> then changing the number should get you a fresh set of memo buckets
> (if my hypothesis about M. implementation is correct).
>
>
--
Of course I can ride in the carpool lane, officer. Jesus is my constant
companion.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
