sig3 does not work:
|control error
| [10]end.
| sig3_MD=:3 :0
|[-59] f:\j\user\necklaces.ijs
After deleting the last 'end'-statement, I got, with
a=:_4 _4 _1 4 1 4 _1 _1 4 1 4 4 1 _4 _4 1 1 _4 _1 _1
sig3 a
|noun result was required: sig3_MD
| bool{~<:pad
I finally found time to implement a solution I came up last week Here I first
checked some trivial cases, which otherwise would cost you a lot of time.
sig_REB=: (|.~ 3 : 0)"1
NB. check on constant array
if. 1=#~. y do. 1 return. end.
NB. check on rep array
t=.I.t0=.(=<./) y
if. -:/ y|.~"_ 0 [2 {.t do. {.t return. end.
NB. check on unique consecutive subarrray of minimals if. (#= 1+{:-{.)t do.
{.t return. end.
NB. other cases
b=.1
c=.#y
while. 1<#t do.
t=.t#~(-:"(1) 0({/:~)]) y{~ c|((+ i.)b)+"1 0 t
NB. t=.t{~ >{.(({</.[)~/:) y{~ c|((+ i.)b)+"1 0 t
b=.2*b
end.
t
)
I compared my solution with sigb_LdF and sigi_Ldf of Louis de Forcrand and
sig1_MD and sig2_MD of Mike Day.
Obviously the special cases are easy to win, but they also revealed a bug in
sigi_LdF.
1 ( #~ 10^]) 7 NB. List of 1e7 constants
100 (i.@[ $~ 10^]) 7 NB. Periodic list
1000 (?.@$~ 10^]) 7 NB. Random list
Lists of constants:
ts'sigb_LdF 1(#~10^])3' NB. sigb of Louis de Forcrand
0.0094511174 14272
ts'sigb_LdF 1(#~10^])4'
0.69180282 85952
ts'sigi_LdF 1(#~10^])3' NB. sigi of Louis de Forcrand
|length error: sigi_LdF
| sigi_LdF 1(#~10^])3
ts'sig1_MD 1(#~10^])3' NB. sig1 of Mike Day
0.0030407711 1077696
ts'sig1_MD 1(#~10^])4'
0.3157129 1.3462982e8
ts'sig2_MD 1(#~10^])4' 3' NB. sig2 of Mike Day
0.41906069 2.684537e8
ts'sig_REB 1(#~10^])7'
0.03058715 33556480
Periodic lists:
ts'sigb_LdF 100 (i.@[ $~ 10^]) 4'
0.37122401 413120
ts'sigi_LdF 100 (i.@[ $~ 10^]) 4'
|length error: sigi_LdF
| sigi_LdF 100(i.@[$~10^])4
ts'sig1_MD 100(i.@[$~10^])4'
0.010147822 8654592
ts'sig1_MD 100(i.@[$~10^])5'
1.7994755 1.07585e9
ts'sig2_MD 100(i.@[$~10^])5'
2.5281331 2.1485343e9
ts'sig_REB 1000 (i.@[ $~ 10^]) 7'
0.45120097 5.537831e8
Random lists
ts'sigb_LdF 1000 (?.@$~ 10^]) 7'
0.98856202 4.1943392e8
ts'sigi_LdF 1000 (?.@$~ 10^]) 7' NB. Overall most efficient
0.70114667 4.0265696e8
ts'sig1_MD 100 (?.@$~ 10^])4'
0.017409918 16913024
ts'sig1_MD 100 (?.@$~ 10^])5'
2.3799804 2.1485513e9
ts'sig2_MD 1000 (?.@$~ 10^])6'
0.070785475 25168768
ts'sig2_MD 1000 (?.@$~ 10^])7'
2.6975198 2.2817036e9
ts'sig_REB 1000 (?.@$~ 10^])7'
0.71293484 6.8800032e8
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: Programming <[email protected]>
> Namens 'Mike Day' via Programming
> Verzonden: donderdag 21 februari 2019 11:40
> Aan: [email protected]
> Onderwerp: Re: [Jprogramming] nubsieve modulo rotation
>
> Back to this thread...
>
> I've worked up an explicit variant, sig3, using I. and E. - fairly
> simple-minded,
>
> but might be of interest. Also revisiting sig1 for comparison. sig3 is not so
> good for
>
> space, but is reasonably fast for the example.
>
> NB. minmd =: (({.@:/:~)`(<./)@.(0-:{.@:(0&{.)))
> minmd =: {.@:/:~ NB. this works for strings as well as numeric arrays
> sig1 =: {.@(/:~)@:(|."0 1~) (I.@:= minmd)
>
> NB. rotate each occurrence of minimum pair to front
> sig2 =: 13 : '{./:~ y |."0 1~ i#~ (=minmd) y {~ <: i =. I. y = minmd y'
>
> sig3 =: 3 : 0
> b =. (,.~) y
> NB. following replaces values by characters - assuming nub is small enough!
> NB. but it doesn't appear to save space!
> NB. b =. (,.~) ((~.@:,) (a.{~i.) ]) y 'm n' =. $y bool =. m#1 for_pad.
> }.i.<: m
> do.
> 'a b' =. ({.;}.) b
> if. bool{~<:pad do.
> if. +/ i =. (n {.a) (+/@:E.)"1 b do.
> bool =. 0 (pad + I.i) } bool
> end.
> end.
> end.
> bool
> )
>
> ts'~:sigb a'
>
> 0.000348269 6656
>
> ts'~:sigi a'
>
> 0.000235419 6272
>
> ts'~:sig3 a'
>
> 0.000233799 13248
>
> ts'~:sig1"1 a'
>
> 0.000106371 7680
>
>
> Also, I can confirm that Henry's canonical shift crashes this version of Jqt
>
> JVERSION
> Engine: j807/j64/windows
> Release-b: commercial/2019-01-22T18:51:16
> Library: 8.07.22
> Qt IDE: 1.7.9/5.9.6
> Platform: Win 64
> Installer: J807 install
> InstallPath: c:/d/j807
> Contact: www.jsoftware.com
>
> Cheers,
>
> Mike
>
>
>
> On 16/02/2019 17:52, [email protected] wrote:
> > I rewrote two explicit and perhaps clearer versions of my sig verb. Both
> work on the same principle as the original, but one uses a bit vector and the
> other uses a list of indices, and the indices are a bit faster (pun probably
> intended). I prefer the bit vector aesthetically though.
> >
> > Both basically store the set of indices where possible lexicographically
> minimal rotations could start (b and i in the verbs). On iteration n, the
> starting
> index of rotations whose nth element is not minimal among the nth
> elements of all possibly minimal rotations are removed from the
> aforementioned set. The iteration continues until only one possible rotation
> is left, and for a maximum of #y times, in which case all elements of y are
> identical and so any rotation will do.
> >
> > If I am not mistaken (I might be, have to hurry and go now), since there are
> a maximum of #y iterations and each includes at most #y comparisons (= <./),
> the number of comparisons is at worst quadratic in the length of y. This
> happens when 1=#~.y, but most of the time this number is much smaller.
> >
> > sigb=: (|.~ 3 : 0)"1
> > b=. 1"0 y
> > for. y do.
> > if. 1 = +/b do. break. end.
> > b=. (= <./)&.(b&#) y
> > y=. 1|.y
> > end.
> > b i. 1
> > )
> >
> > sigi=: (|.~ 3 : 0)"1
> > i=. i.#y
> > for. y do.
> > if. 1 = #i do. break. end.
> > i=. i ((= <./)@:{ # [) y
> > y=. 1|.y
> > end.
> > i
> > )
> >
> > Cheers,
> > Louis
> > ----------------------------------------------------------------------
> > For information about J forums see
> http://www.jsoftware.com/forums.htm
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
