Yes. I should have known this.
Also, fresh executing of F without M.
6!:2 'F 250'
2.97763
and F with M.
6!:2 'F 250'
2.99724
shows using M. in F is useless.
I fooled myself by using
6!:2 , 7!:2@]
and small arguments for F (e.g. 30).
Sorry for the noise.
On 01-05-13 18:02, Marshall Lochbaum 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
--
Met vriendelijke groet,
@@i = Arie Groeneveld
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
