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
