The way memoization would typically work (when I've implemented it in the past, manually) is that you track every bit of state that you will use to get the answer - if you have a pure function with no global access and all parameters in the function call, you make a signature of the function call in such a way that the signature will be unique. In this case, for example, there are two pieces of information, the left argument which is the "D" and the right argument, which is probably the level of call. Say those were two integers. The "signature" could be as simple as getting a long, shifting one argument 32 bits left, and oring it with the other one.
Now, when the function returns, the return value is stored with the signature. At the time the function is called, you search for the signature in the list of signatures. In order to do a single call, without memoization, my routine might have required thousands of recursive calls, more likely many many millions. Remember it ran an hour, without memoization. With memoization, it ran comparatively quickly, because once it made a call from level 2 to level 1 with a particular D, it never did that again. Usually, the scheme that you use to store the signatures is to keep them in a hash or a tree or something that requires few probes and comparisons to find many many signatures. My guess (and this is solely based on performance) is that J is either keeping them in a unbalanced tree that has miserable (perhaps pathological) performance when the keys increase (that is, when the calls are with keys that are generally sorted, perhaps it has the same performance as searching a linked list). That or the keys are just kept in a linked list. We have access to the J source, I should just look at it. But I have no way to build it on Windows if I want to try and see if I can make an improvement. On Wed, Oct 19, 2011 at 6:35 PM, David Vaughan <[email protected] > wrote: > How exactly does memoization work? > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- 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
