"shows using M. in F is useless."
Right...
fast0=. <@({: 0:`1:`(($:&<: + (- +:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0
= ])`0:@.(2 | -))@.(1 + *@-)M."0 (103!:0) ])\@i.M.
(6!:2)'fast0 50'
0.00777864
fast1=. <@({: 0:`1:`(($:&<: + (- +:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0
= ])`0:@.(2 | -))@.(1 + *@-)M."0 (103!:0) ])\@i.
(6!:2)'fast1 50'
0.00767782
slow=. <@({: 0:`1:`(($:&<: + (- +:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0
= ])`0:@.(2 | -))@.(1 + *@-) "0 (103!:0) ])\@i.
(6!:2)'slow 50'
6.21316
fast1 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 1:47 PM, Aai <[email protected]> wrote:
> 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<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><http://www.**
>>>> jsoftware.com/forums.htm <http://www.jsoftware.com/forums.htm>>
>>>>
>>> ------------------------------**------------------------------**
>>> ----------
>>> 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<http://www.jsoftware.com/forums.htm>
>>
>
> --
> 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
