Differences between revisions 4 and 5
 ⇤ ← Revision 4 as of 2008-06-05 05:41:52 → Size: 3193 Editor: RogerHui Comment: ← Revision 5 as of 2008-12-08 10:45:53 → ⇥ Size: 3188 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 4: Line 4: A demonstration of the efficacy of [wiki:JDic:dmcapdot memoization]. A demonstration of the efficacy of [[JDic:dmcapdot|memoization]]. Line 7: Line 7: found in [:../Bibliography#Gilman&Rose:Gilman and Rose];` combm `is the same thing with` M. `applied;` comb `is from the` for. `page of the [wiki:JDic:cfor dictionary] found in [[../Bibliography#Gilman&Rose|Gilman and Rose]];` combm `is the same thing with` M. `applied;` comb `is from the` for. `page of the [[JDic:cfor|dictionary]] Line 84: Line 84: [[BR]] <
>

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 RogerHui.

Essays/Memo (last edited 2008-12-08 10:45:53 by anonymous)