To complete the comparison, canonize is twice as efficient as the best solution before (sigi of de Forcrand).
ts'canonize 1000 (?.@$~ 10^])7' 0.36269515 2.6845101e8 R.E. Boss > -----Oorspronkelijk bericht----- > Van: Programming <[email protected]> > Namens Henry Rich > Verzonden: zondag 24 februari 2019 19:03 > Aan: [email protected] > Onderwerp: Re: [Jprogramming] nubsieve modulo rotation > > J807-c, just now released, fixes the crash that my script detected. I have a > better version now anyway, given below. > > Sample run: > > canonize 1e6 $ 0 1 > 0 1 0 1 0 1... > > Henry Rich > > NB. Get # left-shifts to canonicalize y > > canonnub =: ~:@:canonize =: ((|.~ canonshift =: 3 : 0)"1) > > NB. Try each atom of y, in ascending order, until we find one that works > > lowvalues =. 0$0 NB. In case no recursion possible, remember the first value > with the lowest frequency > > for_t. /:~ ~. y do. > > NB. Get the positions occupied by t. If they are more than half the > positions, skip t since it won't make much progress > > if. (#y) < +: # tpos =. t I.@:= y do. continue. end. > > NB. If there is only 1 position, it is the shift amount - return it > > if. 1 = # tpos do. {. tpos return. end. > > NB. get spacing between positions of t, including the wraparound > > cyclt =. 2 -~/\ (, (#y) + {.) tpos > > NB. If not all spacings are the same, recur on the positions of t to find a > canonical rotation > > if. (}. -.@-: }:) cyclt do. (canonshift cyclt) { tpos return. end. > > NB. All the distances between t values are the same. There is nothing to > choose between them. Try the next input value, > > NB. but remember a shift value for the input that had the smallest > frequency > > if. (#tpos) < {.!._ lowvalues do. lowvalues =. (# , {.) tpos end. > > end. > > NB. No atom worked; must be aaaa... or abcabc...; canonize by moving > smallest to front > > {: lowvalues NB. 0 if all values identical > > ) > > > > > > On 2/21/2019 12:41 PM, 'Mike Day' via Programming wrote: > > Have I missed an update, then? > > Thanks, > > Mike > > > > > > Sent from my iPad > > > >> On 21 Feb 2019, at 16:58, Henry Rich <[email protected]> wrote: > >> > >> The crash should be fixed in the latest released version, but I > >> haven't verified that. > >> > >> Henry Rich > >> > >> On Thu, Feb 21, 2019, 5:40 AM 'Mike Day' via Programming < > >> [email protected]> wrote: > >> > >>> 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 > > ---------------------------------------------------------------------- > > For information about J forums see > http://www.jsoftware.com/forums.htm > > > > --- > This email has been checked for viruses by AVG. > https://www.avg.com > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
