M. Memo

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

---

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