This is very nice. Thank you in advance, Roger. However, I would prefer if memoization is implemented in pure J level not compromising efficiency greatly.
J has dictionary facility like m&i. through special codes, but I guess the internal hash table, which the special codes use, has to be rebuilt bottom up when the table is updated -- say one pair of key/value is added; key/value update is very expensive. For example, python has dictionary type as one of the primitive types supported by the language, and memoization using it is very easy to implement without losing efficiency. (see http://wiki.python.org/moin/PythonDecoratorLibrary#head-11870a08b0fa59a8622201abfac735ea47ffade5 ) It is not very expensive to update/add key-value pairs with python dictionaries. 2006/9/7, Roger Hui <[EMAIL PROTECTED]>:
Something in J6.02 to look forward to. Memo u M. mu lu ru u M. is the same as u but may keep a record of the argument(s) and results for later look-up and reuse. It is commonly used for multiply-recursive verbs. The current implementation retains results only for arguments that are small non-negative integer atoms. For example: fib=: 3 : 0 M. if. 1>:y do. y else. (fib y-1)+fib y-2 end. ) fibx=: 3 : 0 if. 1>:y do. y else. (fibx y-1)+fibx y-2 end. ) 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 Another example is finding the number of partition of n. The following verbs implement a recurrence relation by Euler, equation 11 in http://mathworld.wolfram.com/PartitionFunctionP.html rec=: 3 : 0 _1>.y--:k*"1 ] _1 1+/3*k=. 1+i.1+<.%:y*0.6666666 ) pn=: 3 : 0 M. if. 0>:y do. 0=y else. -/+/pn"0 rec y end. ) pnx=: 3 : 0 if. 0>:y do. 0=y else. -/+/pnx"0 rec y end. ) 6!:2 'j=: pn 27' NB. memo version 0.00147935 6!:2 'k=: pnx 27' NB. non-memo version 73.649 j 3010 k 3010 Subsequent applications of a memoized verb to the same argument produces the result quickly: 6!:2 'fib 32' 2.5049e_5 6!:2 'pn 27' 2.46019e_5 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
