I don't usually worry much about time and space but here is interesting
thing I found:
ts=: 6!:2,7!:2
ts'(,.3*4%~1-~])5^(i.5000x)'
12.7805 4.99247e7
ts '((0 3+*&5)^:(i.5000))1 0x'
0.125234 2.59924e7
f=: 13 :'(,.3*4%~1-~])5^i.y'
f
[: (,. (3 * 4 %~ 1 -~ ])) 5 ^ i.
ts 'f 5000x'
12.8862 4.95213e7
g=: 13 :'((0 3+*&5)^:(i.y))1 0'
g
3 : '((0 3+*&5)^:(i.y))1 0'
ts 'g 5000x'
0.0859978 1.48096e6
h
3 : '((0 3+*&5)^:(i.y))1 0x'
3 : '((0 3+*&5)^:(i.y))1 0x'
3 : '((0 3+*&5)^:(i.y))1 0x'
ts 'h 5000'
0.193622 2.59932e7
I found why g was so fast. Look at the first few of the 5000 lines in A.
$":(,.3*4%~1-~])5^(i.5000x)
5000 6991
$":((0 3+*&5)^:(i.5000))1 0x
5000 6991
$":f 5000x
5000 6991
$":g 5000x
5000 23
$":h 5000x
5000 6991
]A=:g 5000x
...
_ _
_ _
_ _
_ _
_ _
_ _
_ _
_ _
Linda
-----Original Message-----
From: programming-boun...@forums.jsoftware.com
[mailto:programming-boun...@forums.jsoftware.com] On Behalf Of Skip Cave
Sent: Thursday, December 20, 2012 6:03 PM
To: programm...@jsoftware.com
Subject: Re: [Jprogramming] arithmetic sequence
Alessandro is concerned about the efficiency of the approaches that were
proposed to his problem. I make the assumption here that he wants the verb
to calculate all the values up to a specific integer in the formula.
Alessandro is worried that the approaches that are proposed may recalculate
the values S(0), S(1), S(2), over and over again, wasting processing time.
This is a typical concern of someone coming from a scalar language
background, when first confronted with matrix and recursive operations in J.
Also he worries that that these proposals may take up a considerable amount
of space during execution. He is asking if any of the solutions that were
proposed to his problem avoid this replication of the calculations.
The best way to answer his question is to program the problem using his
explicit looping approach, and compare that approach with the approaches
proposed by the various members of the forum.
Let's develop an explicit looping approach to solve the problem. Here's
Alessandro's problem coded in a typical explicit scalar looping style:
ac =: 3 : 0
n =. y
a =. 1 0
z =. a
next=.0 3+*&5
while. n > 0 do.
a =. next a
z =. z,a
n =. n-1
end.
(y, 2) $ z
)
Here are some of the other solutions proposed on the forum:
NB. Henry Rich's first proposal
next=:0 3+*&5
hr1 =: 3 : 'y next@]^:(i.@[) 1 0'
NB. Henry Rich's second proposal
next1=: 5&(0 3 + *)
hr2 =: 3 : '(i. y) next1 1 0'
NB. Linda Alford's proposal
la1=: 13 :'y ,.(3*(y-1)%4)'
ans =. la1 5^i. nn
NB. They all get the same answer
nn =. 20
(hr1 nn) -: hr2 nn
1
(hr1 nn) -: la1 5^i. nn
1
(hr1 nn) -: ac nn
1
NB. So lets see how much time and space they use
nn =. 20
ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn'
0.000143973 8128
5.27389e_5 7680
8.85397e_6 1984
0.000201332 3008
Alessandro's explicit loop approach uses about half the space of the worst
case, but takes about three times the processing time. However, Linda's
scheme is by far the best, as it uses less space and time than any other
approach.
Let's make the problem bigger
nn =. 400
ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn'
0.00121992 67456
0.00101282 67008
6.58273e_5 19264
0.00347769 10688
Now the explicit looping uses about one-seventh the space as the worst case,
but still takes three times as long to execute. Linda's approach is still
much better.
Let's go even bigger:
nn =. 5000
ts&>'hr1 nn';'hr2 nn';'la1 5^i.nn';'ac nn'
0.0403787 938880
0.0389937 938432
0.00243484 295744
0.0200658 256384
Of course we know that, even though the calculations are being done, the
results are all the same after 442 iterations due to the 64-bit precision
limit. In any case, Linda's approach still wins in both categories
It's easy to convert all the verbs into extended precision by simply putting
an 'x' after the initial values in each verb. So we can see what happens
when we calculate some REALLY big numbers.
nn =. 5000x
(hr1x nn) -: hr2x nn
1
(hr1x nn) -: acx nn
1
(hr1x nn) -: la1 5^i.nn
1
ts&>'hr1x nn';'hr2x nn';'la1 5^i.nn';'acx nn'
0.0699063 2.64288e7
0.0628555 2.64615e7
7.75595 4.99236e7
2.60534 107328
To make sure:
_1{hr1x nn
1415962252209634578477123031738811510589509702067886271745966044709273451837
9577047138732343564188389817579469051279306783676415479760629182252191671480
4954482928019439147946719498651658518782306700947825912453640814308711524391
4308334045872358803907166054...
_1{hr2x nn
1415962252209634578477123031738811510589509702067886271745966044709273451837
9577047138732343564188389817579469051279306783676415479760629182252191671480
4954482928019439147946719498651658518782306700947825912453640814308711524391
4308334045872358803907166054...
_1{la1 5^i.nn
1415962252209634578477123031738811510589509702067886271745966044709273451837
9577047138732343564188389817579469051279306783676415479760629182252191671480
4954482928019439147946719498651658518782306700947825912453640814308711524391
4308334045872358803907166054...
_1{acx nn
1415962252209634578477123031738811510589509702067886271745966044709273451837
9577047138732343564188389817579469051279306783676415479760629182252191671480
4954482928019439147946719498651658518782306700947825912453640814308711524391
4308334045872358803907166054...
Well, now the explicit iterative solution wins the space battle by far.
Linda's approach looses the time battle by several orders of magnitude, with
Allessandro's verb not too far behind. . Both Henry's verbs are the winners
in the time battle using extended precision.
This shows why trying to optimize for time and space in a program can be
quite a challenge, and is often more trouble than it is worth. A
programmer's time is almost always much more valuable than a computer's time
or memory space, so getting quickly to the answer usually costs much less
than spending programming time to save computer processing time or memory.
--
Skip Cave
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
