I have review the source code for M. . It uses a hash table whose size doubles periodically as the number of entries increases, always keeping the load factor under 0.5. I have no idea why your use of M. is slow, and I can not take the time now to study the long message you posted on Oct 17/18. It is possible that you have hit a pathological case for the hashing used, but I doubt it.
I have also reviewed my solution to Euler problem 66. I solved it without benefit of M., and the code seems pretty straightforward. On Wed, Oct 19, 2011 at 9:48 PM, Nick Simicich <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
