Actually, the time savings are achieved at the expense of space savings yet
the trade is more than worth it (in my opinion)...
erase'f0 t0 f1 t1 f2'
1 1 1 1 1
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. )
<@({: 0:`1:`(($:&<: + (- +:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0 = ])`0:@.(2
| -))@.(1 + *@-)M."0 (103!:0) ])\@i.M.
(6!:2)'f0 50'
6.23176
(6!:2)'f1 50'
0.0101918
(6!:2)'f2 50'
0.00780284
erase'f0 t0 f1 t1 f2'
1 1 1 1 1
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. )
<@({: 0:`1:`(($:&<: + (- +:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0 = ])`0:@.(2
| -))@.(1 + *@-)M."0 (103!:0) ])\@i.M.
(7!:2)'f0 50'
46784
(7!:2)'f1 50'
211776
(7!:2)'f2 50'
218496
On Wed, May 1, 2013 at 12:17 PM, Jose Mario Quintana <
[email protected]> wrote:
> 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
