Yes, I should have known better about those reported space savings considering how the memoization works. However, just to clarify, the time savings reported in my post stand.
On Wed, May 1, 2013 at 12:02 PM, Marshall Lochbaum <[email protected]>wrote: > Those reported space savings are inaccurate. Keep in mind that st > actually runs the given statement twice: once to find space, and once to > find time. Since J computes forks from right to left, the statement for > time is computed first. That means that when space is computed, f1 has > already memoized its result for an argument of 50, so that all the > computation that happens is a lookup in the memoization table. After a > redefinition of f1, I get > > 7!:2 'f1 50' > 423552 > > So there's only a little bit of space savings the first time f1 is run. > Of course, after running (f1 50) once, we get > > st 'f1 50' > ┌────┬────┐ > │1664│2e_5│ > └────┴────┘ > > Which is of course impressive, but doesn't reflect the actual computing > time to get those answers. > > Marshall > > On Wed, May 01, 2013 at 11:22:44AM -0400, Jose Mario Quintana wrote: > > The savings, including the reported space usage, are indeed impressive! > > > > t0=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($: > > i.@>:)@<.@-:@[)@.(0=])`0:@.(2|-))@.(1+*@-) > > "0 > > f0=: <@({: t0 ])\@i. > > > > > > t1=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($: > > i.@>:)@<.@-:@[)@.(0=])`0:@.(2|-))@.(1+*@-) > > M."0 > > f1=: <@({: t1 ])\@i. M. > > > > ( f2=. f1 f. ) NB. Using the scope for recursion (103!:0) extension: > > http://www.jsoftware.com/pipermail/programming/2013-March/031835.html > > <@({: 0:`1:`(($:&<: + (- +:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0 = ])`0:@ > .(2 > > | -))@.(1 + *@-)M."0 (103!:0) ])\@i.M. > > > > st > > 7!:2@:] ; 6!:2 > > > > st'f0 50' > > ┌─────┬──────────┐ > > │46784│6.19811211│ > > └─────┴──────────┘ > > st'f1 50' > > ┌───┬────────────┐ > > │832│0.0100949664│ > > └───┴────────────┘ > > st'f2 50' > > ┌───┬─────────────┐ > > │832│0.00793115699│ > > └───┴─────────────┘ > > > > ,. o f2 9 > > ┌─────────────────┐ > > │1 │ > > ├─────────────────┤ > > │0 1 │ > > ├─────────────────┤ > > │1 0 1 │ > > ├─────────────────┤ > > │0 2 0 1 │ > > ├─────────────────┤ > > │2 0 2 0 1 │ > > ├─────────────────┤ > > │0 4 0 2 0 1 │ > > ├─────────────────┤ > > │3 0 5 0 2 0 1 │ > > ├─────────────────┤ > > │0 7 0 5 0 2 0 1 │ > > ├─────────────────┤ > > │5 0 9 0 5 0 2 0 1│ > > └─────────────────┘ > > > > > > On Wed, May 1, 2013 at 5:11 AM, Aai <[email protected]> wrote: > > > > > From the seqfan forum I picked up the computing of the following > triangle: > > > > > > ({.~1+1 i:~ '1'=])"1 ": > F 10 > > > 1 > > > 0 1 > > > 1 0 1 > > > 0 2 0 1 > > > 2 0 2 0 1 > > > 0 4 0 2 0 1 > > > 3 0 5 0 2 0 1 > > > 0 7 0 5 0 2 0 1 > > > 5 0 9 0 5 0 2 0 1 > > > 0 12 0 10 0 5 0 2 0 1 > > > > > > The terms on a row are computed recursively (see verb xT and T). > > > > > > The triangle can be computed with J as follows: > > > > > > 1. explicit > > > > > > xT=: 4 :0 "0 > > > select. * x-y > > > case. _1 do. 0 > > > case. 0 do. 1 > > > case. do. > > > if. 1=2| x-y do. 0 return. end. > > > if. 0=y do. +/ (xT i.@>:)<.-: x else. (x xT&<: y) + (x-+:y) xT y > end. > > > end. > > > ) > > > > > > xF=: <@({: xT ])\@i. > > > > > > or > > > > > > 2. tacit: > > > > > > T=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0=])`0:@ > .(2|**-))@.(1+*@-) > > > "0 > > > F=: <@({: T ])\@i. > > > > > > > > > example: > > > > > > ,. F 9 > > > ┌─────────────────┐ > > > │1 │ > > > ├─────────────────┤ > > > │0 1 │ > > > ├─────────────────┤ > > > │1 0 1 │ > > > ├─────────────────┤ > > > │0 2 0 1 │ > > > ├─────────────────┤ > > > │2 0 2 0 1 │ > > > ├─────────────────┤ > > > │0 4 0 2 0 1 │ > > > ├─────────────────┤ > > > │3 0 5 0 2 0 1 │ > > > ├─────────────────┤ > > > │0 7 0 5 0 2 0 1 │ > > > ├─────────────────┤ > > > │5 0 9 0 5 0 2 0 1│ > > > └─────────────────┘ > > > > > > > > > The interesting thing here is the major speed up by applying double > > > memoization: > > > ( I use the tacit verbs) > > > > > > T=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0=])`0:@ > .(2|**-))@.(1+*@-) > > > M."0 > > > F=: <@({: T ])\@i. M. > > > > > > You can follow the stepwise speed up by first adding M. to T and after > > > that also to F and comparing the timings. The speed up is huge. > > > > > > > > > FYI. > > > > > > > > > BTW the triangle is of some interest: try summing the rows > > > > > > > > > > > > > > > -- > > > Met vriendelijke groet, > > > @@i = Arie Groeneveld > > > > > > > ------------------------------**------------------------------**---------- > > > For information about J forums see > http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm> > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
