For A=:500 1000?.@$2 I get (JQt J807 64 nonavx windows) +--------+-------+-----------+------------+ |Sentence|Space |Time |Space * Time| +--------+-------+-----------+------------+ | v0 A |3679296|0.70414781 |2590768.2 | +--------+-------+-----------+------------+ | v1 A |3679296|0.54953837 |2021914.3 | +--------+-------+-----------+------------+ | v2 A |601792 |0.043914231|26427.233 | +--------+-------+-----------+------------+ | v4 A |3163968|0.32526764 |1029136.4 | +--------+-------+-----------+------------+ | v5 A |2102336|0.10568039 |222175.68 | +--------+-------+-----------+------------+
So LdF is (by far) the winner, his solution being fast and lean. The relative scores are +-------+-----------+------------+ |Space |Time |Space * Time| +---------+---------+---------+ |6.1138998|16.034616|98.034032| +---------+---------+---------+ |6.1138998|12.513902|76.50874 | +---------+---------+---------+ |1 |1 |1 | +---------+---------+---------+ |5.2575774|7.4068846|38.942268| +---------+---------+---------+ |3.4934595|2.4065181|8.4070731| +---------+---------+---------+ MD sig2 is the runner up. I get a stack error on v3 R.E Boss > -----Oorspronkelijk bericht----- > Van: Programming <[email protected]> > Namens Jose Mario Quintana > Verzonden: donderdag 14 februari 2019 23:58 > Aan: Programming forum <[email protected]> > Onderwerp: Re: [Jprogramming] nubsieve modulo rotation > > Comparisons based on solutions offered. > > (Beware of line-wrapping!) > > v0=. ~:@:({.@(/:~)@(i.@# |."0 1 ]) "1) NB. RH v1=. ~:@:(([: {.@/:~ {:@$ [\ > (, > }:))"1) NB. REB v2=. ~:@:((|.~ >:@(# -~ {: i. 1:)@((_1 |. ] #^:_1 (= > <./)@#~)^:(1 < > +/@])^:a: 1"0))"1) > NB. LdF > v3=. ~:@:((|.~ canonshift=. 3 : 0)"1) NB. HR > NB. Try each atom of y until we find one that works for_t. /:~ ~. y do. > NB. get spacing between positions of t, including the wraparound > cyclt =. 2 -~/\ tpos =. (, (#y) + {.) t I.@:= y > NB. if there is only 1 value, use its position > if. 1 = # cyclt do. {. tpos end. > NB. If all spacings are the same, try the next value > if. (}. -: }:) cyclt do. continue. end. > NB. Canonicalize cyclt. Use its result to canonicalize y > (canonshift cyclt) { tpos return. > end. > NB. No atom worked; must be abcabc...; canonize by moving smallest to > front (i. <./) y > ) > > v4=. ~:@:(({.@(/:~)@:(|."0 1~) (I.@:=<./))"1) NB. MD (sig1) v5=. ~:@:(([: {. > [: > /:~ ] |."0 1~ ([: I. ] = <./) #~ [: (= <./) ] {~ [: <: > [: I. ] = <./)"1) > NB. MD (sig2) > > stp=. ] (([ ((<;._1 '|Sentence|Space|Time|Space * Time') , (, */&.:>@:(1 > 2&{))@:(] ; 7!:2@:] ; 6!:2)&>) (10{a.) -.&a:@:(<;._2@,~) ]) [ (0 0 $ > 13!:8^:((0 e. ])`(12"_)))@:(2 -:/\ ])@:(".&.>)@:((10{a.) -.&a:@:(<;._2@,~) > ]) ::(0 0&$@(1!:2&2)@:('Mismatch!'"_))) ".@:('0( : 0)'"_) > > A=: ". 12 59 $ (0 : 0) -. CRLF > 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 _1 4 1 > 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 1 4 _1 _1 4 > 1 4 4 1 _4 _1 _4 1 1 _4 _1 _4 _4 _1 4 1 4 _1 _1 4 > 4 1 1 4 _1 4 1 _4 _4 1 _4 _1 _1 _4 1 _4 _1 4 4 _1 > 4 1 1 4 _1 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 > _1 4 1 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 > _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 1 4 _1 > _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 _1 4 1 1 4 > _1 4 4 _1 _4 1 _4 _1 _1 _4 1 _4 _4 1 4 _1 4 1 1 4 > 4 _1 _1 4 1 4 _1 _4 _4 _1 _4 1 1 _4 _1 _4 1 4 4 1 > 4 _1 _1 4 1 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 > 1 4 _1 _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 > ) > > > JQt J807 (64 nonavx windows) performance results... > > (v3 was excluded; otherwise, J crases (on v3 A)! Can anyone confirm?) > > stp 111 > v0 A > v1 A > v2 A > v4 A > v5 A > ) > ┌────────┬─────┬──────────┬────────────┐ > │Sentence│Space│Time │Space * Time│ > ├────────┼─────┼──────────┼────────────┤ > │ v0 A │15680│9.79728e_5│1.53621 │ > ├────────┼─────┼──────────┼────────────┤ > │ v1 A │15680│4.4752e_5 │0.701711 │ > ├────────┼─────┼──────────┼────────────┤ > │ v2 A │6016 │9.1532e_5 │0.550657 │ > ├────────┼─────┼──────────┼────────────┤ > │ v4 A │7360 │4.14325e_5│0.304943 │ > ├────────┼─────┼──────────┼────────────┤ > │ v5 A │6016 │5.29863e_5│0.318766 │ > └────────┴─────┴──────────┴────────────┘ > > > Corresponding J806 results... > > (v3 is included.) > > stp 111 > v0 A > v1 A > v2 A > v3 A > v4 A > v5 A > ) > ┌────────┬─────┬──────────────┬────────────┐ > │Sentence│Space│Time │Space * Time│ > ├────────┼─────┼──────────────┼────────────┤ > │ v0 A │14336│0.000118566885│1.69977487 │ > ├────────┼─────┼──────────────┼────────────┤ > │ v1 A │12160│5.34553436e_5 │0.650016979 │ > ├────────┼─────┼──────────────┼────────────┤ > │ v2 A │11264│0.000124958141│1.4075285 │ > ├────────┼─────┼──────────────┼────────────┤ > │ v3 A │18688│0.000427807898│7.99487399 │ > ├────────┼─────┼──────────────┼────────────┤ > │ v4 A │7296 │4.23078038e_5 │0.308677736 │ > ├────────┼─────┼──────────────┼────────────┤ > │ v5 A │6272 │5.04595455e_5 │0.31648227 │ > └────────┴─────┴──────────────┴────────────┘ > > > On Thu, Feb 14, 2019 at 11:27 AM 'Mike Day' via Programming < > [email protected]> wrote: > > > FWIW, slightly better and faster versions of my rushed efforts of > > yesterday > > > > NB. rotate each occurrence of minimum to front > > sig1 =: {.@(/:~)@:(|."0 1~) (I.@:=<./) > > > > NB. rotate each occurrence of minimum with minimum left neighbour > > sig2 =: 13 : '{./:~ y |."0 1~ i#~ (=<./) y{~ <: i =. I. y = <./ y' > > > > Still not too elegant, but quite fast for the small example, a. Don’t > > know about bigger arrays. > > > > Mike > > > > Sent from my iPad > > > > > On 14 Feb 2019, at 03:26, Roger Hui <[email protected]> > wrote: > > > > > > And what would you use if you need a noun? Normal form? Again, > > > more of > > a > > > mouthful. > > > > > > Other terms I would use for identity problems, when explaining to > > > laymen, is "ID number". They usually get it immediately. > > > > > > > > >> On Wed, Feb 13, 2019 at 6:55 PM Raul Miller <[email protected]> > > wrote: > > >> > > >> I like “normalize” personally. > > >> > > >> The ideas I associate with “signature” are not robust enough for a > > reliable > > >> nub (and so would require additional care elsewhere). > > >> > > >> If that matters... > > >> > > >> Thanks, > > >> > > >> — > > >> Raul > > >> > > >> On Wednesday, February 13, 2019, Roger Hui > > >> <[email protected]> > > >> wrote: > > >> > > >>> In this context, I prefer words like signature or representative > > >>> rather than canonical form. Shorter and less scary and puts one's > > >>> mind on the right track in multiple problems. > > >>> > > >>> e.g. What's a good representative for identity problems? ~. i. ] > > (index > > >>> in nub). What's a good representative for ordering problems? > > >>> (Seen a couple of weeks ago.) /:~@, i.!.0 ] (ordinals). > > >>> > > >>> > > >>> > > >>> > > >>> > > >>>> On Wed, Feb 13, 2019 at 5:19 PM Henry Rich > <[email protected]> > > wrote: > > >>>> > > >>>> This is what I was looking for. It works on REB's testcase but > > >>>> has > > >> less > > >>>> than quadratic run time I think. > > >>>> > > >>>> NB. Get # left-shifts to canonicalize y > > >>>> > > >>>> canonshift =: 3 : 0 > > >>>> > > >>>> NB. Try each atom of y until we find one that works > > >>>> > > >>>> for_t. /:~ ~. y do. > > >>>> > > >>>> NB. get spacing between positions of t, including the > > >>>> wraparound > > >>>> > > >>>> cyclt =. 2 -~/\ tpos =. (, (#y) + {.) t I.@:= y > > >>>> > > >>>> NB. if there is only 1 value, use its position > > >>>> > > >>>> if. 1 = # cyclt do. {. tpos end. > > >>>> > > >>>> NB. If all spacings are the same, try the next value > > >>>> > > >>>> if. (}. -: }:) cyclt do. continue. end. > > >>>> > > >>>> NB. Canonicalize cyclt. Use its result to canonicalize y > > >>>> > > >>>> (canonshift cyclt) { tpos return. > > >>>> > > >>>> end. > > >>>> > > >>>> NB. No atom worked; must be abcabc...; canonize by moving > > >>>> smallest to > > >>> front > > >>>> > > >>>> (i. <./) y > > >>>> > > >>>> ) > > >>>> > > >>>> ~: (|.~ canonshift)"1 a > > >>>> 1 1 1 1 1 0 1 1 1 1 1 0 > > >>>> > > >>>> The canonical form used here does not always put the smallest > > >>>> atom at > > >> the > > >>>> front, but I think it causes vector that differ only by a > > >>>> rotation to canonicalize identically. > > >>>> > > >>>> Henry Rich > > >>>> > > >>>> > > >>>> > > >>>>> On 2/13/2019 7:29 PM, Roger Hui wrote: > > >>>>> Idea k: a minimum vector necessarily begins with a minimum > > >> sub-sequence > > >>>> in > > >>>>> x,(k-1){.x of length k , itself necessarily begins with the > > >>>>> minimal > > >>> item. > > >>>>> > > >>>>> > > >>>>> On Wed, Feb 13, 2019 at 9:52 AM Roger Hui > > >>>>> <[email protected] > > >>> > > >>>> wrote: > > >>>>> > > >>>>>> Yes, well, left as an exercise for the reader. :-) > > >>>>>> > > >>>>>> Idea: the minimum rotation of a vector necessarily begins with > > >>>>>> its > > >>>> minimal > > >>>>>> item. > > >>>>>> > > >>>>>> On Wed, Feb 13, 2019 at 9:34 AM Henry Rich > > >>>>>> <[email protected]> > > >>>> wrote: > > >>>>>> > > >>>>>>> Yes; but now suppose the lines are very long. Is there a way > > >>>>>>> to > > >> find > > >>>>>>> the signature (I would call it a canonical form) that doesn't > > >> require > > >>>>>>> enumerating rotations? (I haven't found a good way yet). > > >>>>>>> > > >>>>>>> Henry Rich > > >>>>>>> > > >>>>>>>> On 2/13/2019 12:16 PM, Roger Hui wrote: > > >>>>>>>> For each row, find a "signature", then find the nub sieve of > > >>>>>>>> the signatures. The signature I use here is the minimum of > > >>>>>>>> all > > >> possible > > >>>>>>>> rotations. > > >>>>>>>> > > >>>>>>>> signature=: {. @ (/:~) @ (i.@# |."0 1 ]) > > >>>>>>>> > > >>>>>>>> ~: signature"1 a > > >>>>>>>> 1 1 1 1 1 0 1 1 1 1 1 0 > > >>>>>>>> > > >>>>>>>> > > >>>>>>>> > > >>>>>>>> > > >>>>>>>> On Wed, Feb 13, 2019 at 8:55 AM R.E. Boss > > >>>>>>>> <[email protected]> > > >>>> wrote: > > >>>>>>>> > > >>>>>>>>> Let the 12 x 20 matrix be defined by > > >>>>>>>>> a=: 0 : 0 > > >>>>>>>>> 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 _1 4 1 > > >>>>>>>>> 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 1 4 _1 _1 4 > > >>>>>>>>> 1 4 4 1 _4 _1 _4 1 1 _4 _1 _4 _4 _1 4 1 4 _1 _1 4 > > >>>>>>>>> 4 1 1 4 _1 4 1 _4 _4 1 _4 _1 _1 _4 1 _4 _1 4 4 _1 > > >>>>>>>>> 4 1 1 4 _1 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 > > >>>>>>>>> _1 4 1 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 > > >>>>>>>>> _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 1 4 _1 > > >>>>>>>>> _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 _1 4 1 1 4 > > >>>>>>>>> _1 4 4 _1 _4 1 _4 _1 _1 _4 1 _4 _4 1 4 _1 4 1 1 4 > > >>>>>>>>> 4 _1 _1 4 1 4 _1 _4 _4 _1 _4 1 1 _4 _1 _4 1 4 4 1 > > >>>>>>>>> 4 _1 _1 4 1 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 > > >>>>>>>>> 1 4 _1 _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 > > >>>>>>>>> ) > > >>>>>>>>> > > >>>>>>>>> Required is the nubsieve for the items modulo rotation. > > >>>>>>>>> So two arrays are considered to be equal if one is a > > >>>>>>>>> rotation of > > >>> the > > >>>>>>> other. > > >>>>>>>>> The answer I found is > > >>>>>>>>> 1 1 1 1 1 0 1 1 1 1 1 0 > > >>>>>>>>> > > >>>>>>>>> > > >>>>>>>>> R.E. Boss > > >>>>>>>>> > > >>>> ----------------------------------------------------------------- > > >>>> ----- > > >>>>>>>>> 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 > > >>>> > > >>>> ----------------------------------------------------------------- > > >>>> ----- 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
