> 1) How is it that the first call to fib is faster? Would not the > creation and storage of values in the associated array actually slow > the computation down? Or did I misunderstand something here?
Memoization is commonly used for multiply-recursive verbs. For such verbs the "first call" already involves many calls to the verb on the same argument. This is illustrated by the fib verb: fib=: 3 : 0 M. if. 1>:y do. y else. (fib y-1)+fib y-2 end. ) The sequence of calls that would happen if M. is not used: fib 8 (fib 7)+(fib 6) (fib 6)+(fib 5)+(fib 5)+(fib 4) (fib 5)+(fib 4)+(fib 4)+(fib 3)+(fib 4)+(fib 3)+(fib 3)+(fib 2) ... Creating and maintaining the array of saved results does take time and space, but the resource consumed is small in return for the greatly reduced number of function calls (from exponential to linear in the case of fib). > 2) What happens to the associated array post computation? Obviously, the array has to persist to produce the behaviour reported in the J Wiki essay. > 3) How would match dyad (-:) work when comparing a Memoized and non > Memoized versions? I ask this since the essay shows the values instead > of using the match dyad. The results of the memoized and non-memoized verbs would match. Barring side-effects, of course. But then, M. should not be used on verbs that have side-effects. ----- Original Message ----- >From Yuvaraj Athur Raghuvir <[EMAIL PROTECTED]> Sent Tuesday, November 14, 2006 7:26 pm To Programming forum <[email protected]> Subject Re: [Jprogramming] The Priest Mathematician Hello, I am not sure if I understand the concept of memoization and its realization in J through M. as indicated in the essay at http://www.jsoftware.com/jwiki/Essays/Memoization When I looked at http://en.wikipedia.org/wiki/Memoization, I understood that memoization is most effective when the function is invoked later, the values in the associated array are scanned before actual computation is done. >From the essay I have: 6!:2 'j=: fib 32' NB. memo version 0.000424922 6!:2 'k=: fibx 32' NB. non-memo version 43.4159 j 2178309 k 2178309 Given that, I have the following questions: 1) How is it that the first call to fib is faster? Would not the creation and storage of values in the associated array actually slow the computation down? Or did I misunderstand something here? 2) What happens to the associated array post computation? 3) How would match dyad (-:) work when comparing a Memoized and non Memoized versions? I ask this since the essay shows the values instead of using the match dyad. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
