>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Voc  !:  Help  Dictionary

Memo u M.  mu lu ru

u M. is the same as u but may keep a record of the arguments and results for reuse. It is commonly used for multiply-recursive verbs.                                                                        

The following examples illustrate the difference that memoization can make. fib n is the n-th Fibonacci number. pn finds the number of partitions of an integer using a recurrence relation due to Euler, equation 11 in http://mathworld.wolfram.com/PartitionFunctionP.html .
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.
)

   timer=: 6!:2

   timer 'fib 32'
0.000479377
   timer 'fibx 32'
43.696

   fib"0 i.18
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597

pn =: -/@(+/)@:($:"0)@rec ` (x:@(0&=)) @. (0>:]) M.
pnx=: -/@(+/)@:($:"0)@rec ` (x:@(0&=)) @. (0>:])
rec=: - (-: (*"1) _1 1 +/ 3 * ]) @ (>:@i.@>.@%:@((2%3)&*))

   timer 'pn 28'
0.000675355
   timer 'pnx 28'
61.7146

   pn"0 i.18
1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297
   pn 1000
24061467864032622473692149727991
Subsequent applications of a memoized verb to a previously evaluated argument produce the result quickly:
   timer 'fib 32'
2.62393e_5
   timer 'pn 28'
4.01456e_5
M. is applicable to anonymous verbs and to verbs with non-atomic results. Thus:
   timer '+/@:($:"0)@:(-&1 2)`]@.(1>:]) M. 32'
0.000186387
   timer '+/@:($:"0)@:(-&1 2)`]@.(1>:])    32'
8.61349

comb=: 4 : 0 M.   NB. All size x combinations of i.y
 if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end.
)

   3 comb 5
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4


>>  <<  Usr  Pri  JfC  LJ  Phr  Dic  Voc  !:  Help  Dictionary