Essays/Memo
< Essays
Jump to navigation
Jump to search
A demonstration of the efficacy of memoization.
comb0 is the classical doubly recursion definition found in Gilman and Rose; combm is the same thing with M. applied; comb is from the for. page of the dictionary and has been worked on for more than 30 years by myself and others.
comb0=: 4 : 0 NB. All size x combinations of i.y if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb0&.<: y),1+x comb0 y-1 end. ) combm=: 4 : 0 M. if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combm&.<: y),1+x combm y-1 end. ) comb=: 4 : 0 k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z )
The benchmark is 10 comb 20 .
time space comb0 4.04831 25169088 combm 0.16492 44554944 comb 0.159853 24965312
Thus, combm is a straightforward definition which is competitive in time and space with the highly polished comb .
combm1 is like combm but captures the arguments in cases where the body of the verb is evaluated with arguments. combm1 can be called multiple times with some of these arguments, but all but the first call is intercepted by the M. mechanism and the result computed by table look-up.
foo=: 0 2$0 combm1=: 4 : 0 M. foo=: foo,x,y if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combm1&.<: y),1+x combm1 y-1 end. ) $ 10 combm1 20 184756 10 $ foo 123 2 _20 <\ ": foo ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │10 20│ 5 5│ 9 12│ 9 14│ 1 6│ 2 10│ 2 12│ │10 19│ 4 5│ 8 11│ 8 13│ 1 7│ 1 9│ 1 11│ │10 18│ 4 4│ 7 10│ 7 12│ 0 6│ 0 8│ 0 10│ │10 17│ 3 4│ 6 9│ 6 11│ 9 16│ 9 18│ │ │10 16│ 3 3│ 5 8│ 5 10│ 8 15│ 8 17│ │ │10 15│ 2 3│ 4 7│ 4 9│ 7 14│ 7 16│ │ │10 14│ 2 2│ 3 6│ 3 8│ 6 13│ 6 15│ │ │10 13│ 1 2│ 2 5│ 2 7│ 5 12│ 5 14│ │ │10 12│ 1 1│ 1 4│ 1 6│ 4 11│ 4 13│ │ │10 11│ 0 1│ 0 3│ 0 5│ 3 10│ 3 12│ │ │10 10│ 9 11│ 9 13│ 9 15│ 2 9│ 2 11│ │ │ 9 10│ 8 10│ 8 12│ 8 14│ 1 8│ 1 10│ │ │ 9 9│ 7 9│ 7 11│ 7 13│ 0 7│ 0 9│ │ │ 8 9│ 6 8│ 6 10│ 6 12│ 9 17│ 9 19│ │ │ 8 8│ 5 7│ 5 9│ 5 11│ 8 16│ 8 18│ │ │ 7 8│ 4 6│ 4 8│ 4 10│ 7 15│ 7 17│ │ │ 7 7│ 3 5│ 3 7│ 3 9│ 6 14│ 6 16│ │ │ 6 7│ 2 4│ 2 6│ 2 8│ 5 13│ 5 15│ │ │ 6 6│ 1 3│ 1 5│ 2 7│ 4 12│ 4 14│ │ │ 5 6│ 0 2│ 0 4│ 2 6│ 3 11│ 3 13│ │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
Contributed by Roger Hui.