RE wrote:
> Well, what about this, after some thinking:
I personally am interested in how you come up with these performance
improvements. Maybe you could share your tips & techniques in your J blog?
Perhaps using a narrative format when you write up these races, so:
"First, we start with Ambrus' solution; here are its performance
characteristics <>. Now we notice that the sequence doubles every
time a 1 is encountered, so we bake this assumption into the verb
so <>. Here are the new performance characteristics. Now we
apply the standard refactoring, technique of using as many
specially-support idioms as possible (for example, using I.@:e.).
Now the performance characteristics are <>"
etc.
-Dan
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of R.E. Boss
Sent: Friday, August 06, 2010 11:50 AM
To: 'Programming forum'
Subject: Re: [Jprogramming] Generate the Gijswijt's sequence (A090822)
Well, what about this, after some thinking:
ts 'gwr3 5e7' NB. 50 million!
1.6894175 6.6899802e8
iofifh=: {. i...@e.~ >:@>.@:-:@:# {. ]
fiwd=: 0 i.~ 2 -:/\ ]
oie=: 1:`...@.(0 < #)
scn2=: 3 : 0
z=. <2
le=. 1
for. i. y-1 do.
t=. < ({.~ le -~ #) }. ([: (,~ [:>: [:>./ -@([: oie [: }. iofifh)
fiwd@(]\)])^:(1 ~: {.)^:(_) 2,]) ;z
le=. # ; z=. t ,z
end.
|. |.&.> z
)
gwr3=: 3 : 0
le=. <:<.2^.y
t=. scn2 le
z=. 1
for_s. t do. z=. (;s) ,~ z , z end.
if. y>#z do. z, (y-#z) {. z else. y {. z end.
)
([ dspl rnkng@:scores) 'gij 500';'gwr2 500';'gwr3 500'
+--------+----+------+------+----+
|expr |rank|et*sz |time |size|
+--------+----+------+------+----+
|gij 500 | 2 |162.84|113.80|1.43|
+--------+----+------+------+----+
|gwr2 500| 1 | 5.48| 4.33|1.27|
+--------+----+------+------+----+
|gwr3 500| 0 | 1.00| 1.00|1.00|
+--------+----+------+------+----+
([ dspl rnkng@:scores) 'gwr2 5e4';'gwr3 5e4'
+--------+----+-------+------+----+
|expr |rank|et*sz |time |size|
+--------+----+-------+------+----+
|gwr2 5e4| 1 |1184.66|938.26|1.26|
+--------+----+-------+------+----+
|gwr3 5e4| 0 | 1.00| 1.00|1.00|
+--------+----+-------+------+----+
(gwr2 -: gwr3) 5e4
1
Since appeared to be no interest in my former post, I left out the comments.
For the record only.
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: [email protected] [mailto:programming-
> [email protected]] Namens R.E. Boss
> Verzonden: donderdag 5 augustus 2010 18:48
> Aan: 'Programming forum'
> Onderwerp: Re: [Jprogramming] Generate the Gijswijt's sequence (A090822)
>
> Further improvements are possible, as always.
>
> iofifh=: {. i...@e.~ >:@>.@:-:@:# {. ] NB. index of first in
> first
> halve
> fiwd=: 0 i.~ 2 -:/\ ] NB. first index where different
> oie=: 1:`...@.(0 < #) NB. one if empty
>
> gwr1=: 3 : '|.(,~ [:>: [:>./ -@([: oie [: }. iofifh) fiwd@(]\) ])^:(y-2) 1
> 1
> '
>
> (gij -: gwr1) 100
> 1
>
> dspl rnkng scores 'gij 500';'gwr1 500'
> +----+-----+----+----+
> |rank|et*sz|time|size|
> +----+-----+----+----+
> | 1 |1.99 |1.77|1.13|
> +----+-----+----+----+
> | 0 |1.00 |1.00|1.00|
> +----+-----+----+----+
>
> Almost twice as fast.
> NB. the new element is appended at the beginning.
> Here the fact is used that not all partitions of length -@:>:@:i.@:<.@:-
> :@:#
> have to be generated, but only those of length until a next occurrence of
> {.
>
>
> dio=: (,~...@[)`(,~)@.(1~:]) NB. double if one
> gwr2=: 3 : 'y {. |.(] dio [:>: [:>./ -@([: oie [:}. iofifh) fiwd@(]\)
> ])^:(y>#)^:(y-2) 1 1 '
>
> (gij -: gwr2) 100
> 1
>
> dspl rnkng scores 'gij 500';'gwr2 500'
> +----+-----+-----+----+
> |rank|et*sz|time |size|
> +----+-----+-----+----+
> | 1 |31.84|28.17|1.13|
> +----+-----+-----+----+
> | 0 | 1.00| 1.00|1.00|
> +----+-----+-----+----+
>
> This is quite an improvement, due to the fact that the sequence is doubled
> if a 1 is encountered
> (cf. http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Sloane/sloane55.pdf ).
>
> ts 'gwr2 500'
> 0.0059088105 15232
> ts 'gwr2 5000'
> 0.096675723 103296
> ts 'gwr2 50000'
> 9.3185808 791424
>
>
> R.E. Boss
>
> ps. since Gijswijt is Dutch and 'rij' is the Dutch translation of
> 'sequence', his sequence is called a 'gijswijtrij', or gwr.
>
>
> > -----Oorspronkelijk bericht-----
> > Van: [email protected] [mailto:programming-
> > [email protected]] Namens R.E. Boss
> > Verzonden: woensdag 4 augustus 2010 15:30
> > Aan: 'Programming forum'
> > Onderwerp: Re: [Jprogramming] Generate the Gijswijt's sequence (A090822)
> >
> > You can make it slightly faster by
> >
> > gi2=: ,~ [:>:[:>./ -@:>:@:i.@:<.@:-:@:# (0 i.~2-:/\])@(]\) ]
> > gij2=: 3 :'|. gi2^:(y-2) 1 1'
> >
> >
> > R.E. Boss
> >
> >
> > > -----Oorspronkelijk bericht-----
> > > Van: [email protected] [mailto:programming-
> > > [email protected]] Namens Zsbán Ambrus
> > > Verzonden: dinsdag 3 augustus 2010 21:57
> > > Aan: [email protected]
> > > Onderwerp: Re: [Jprogramming] Generate the Gijswijt's sequence
> (A090822)
> > >
> > > The following is almost the same as my original code except it's
> > > significantly faster (but it's still very slow).
> > >
> > > gi1=: , [:>:[:>./ -@:>:@:i.@:<.@:-:@:# (0 i.~2-:/\])@(]\) |.
> > > gij=: 3 :'gi1^:(y-2) 1 1'
> > > gij 30
> > > 1 1 2 1 1 2 2 2 3 1 1 2 1 1 2 2 2 3 2 1 1 2 1 1 2 2 2 3 1 1
> > >
> > > Ambrus
> > > ----------------------------------------------------------------------
> > > 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
