Indeed. If you represent elements of a permutation by a single byte, sorting is faster. As it is (using 8-byte integers), sorting is not much slower.
a=: (?1000$!6) A. '012345' b=: (?1000$!6) A. '012345' 100 timer 'a -:&(/:~) b' 0.000133634 100 timer '*./a e. b' 0.000490982 x=: (?1000$!6) A. i.6 y=: (?1000$!6) A. i.6 100 timer 'x -:&(/:~) y' 0.000492428 100 timer '*./ x e. y' 0.000329386 On Thu, Jul 10, 2014 at 7:34 AM, Raul Miller <[email protected]> wrote: > It's not clear to me whether "no sorting required" is a meaningful > criteria. Sorting might very well be faster (depending on the size of > the data structures you are working with). > > FYI, > > -- > Raul > > On 7/10/14, Ben Gorte - CITG <[email protected]> wrote: > > In that case Dan's solution is probably optimal - no sorting required. > > ________________________________________ > > From: [email protected] > > [[email protected]] on behalf of Jon Hough > > [[email protected]] > > Sent: Thursday, July 10, 2014 14:55 > > To: [email protected] > > Subject: Re: [Jprogramming] Comaring Arrays > > > > Duplicate rows, other than 0 0 0 0 sjould never occur. If they did, there > > would be a big problem. > > 0 0 0 0 occur when J needs filler to pad out arrays. > > > > --- Original Message --- > > > > From: "Ben Gorte - CITG" <[email protected]> > > Sent: July 10, 2014 9:51 PM > > To: [email protected] > > Subject: Re: [Jprogramming] Comaring Arrays > > > > Hi Jon, > > > > Dan and I were wondering: > > > > 1. whether your matrices would be allowed to have duplicate rows > > 2. and if they are, whether such duplicate rows should occur in both > > matrices equally often, for them to be equivalent > > > > Ben > > ________________________________________ > > From: [email protected] > > [[email protected]] on behalf of Jon Hough > > [[email protected]] > > Sent: Thursday, July 10, 2014 14:16 > > To: [email protected] > > Subject: Re: [Jprogramming] Comaring Arrays > > > > I away from my computer at the moment. When I get back I will show you > my > > code. > > The gist is I am making a simple permutation group theory script(i am not > > talking about simple groups, i mean a simple script). > > Anyway, what I have so far is trying to conjugate a group with itself, > so i > > can nub out the resulting duplicates and get all the conjugacy classes of > > the group. > > > > --- Original Message --- > > > > From: "Dan Bron" <[email protected]> > > Sent: July 10, 2014 8:38 PM > > To: [email protected] > > Subject: Re: [Jprogramming] Comaring Arrays > > > > Good point. We could fix this up by asking an additional question: are > the > > items of A unique? There's a million ways to ask that, but maybe we're > in a > > cutesy mood today: > > > > e. *./@:*. ~:@:] > > > > Though with the ~:, I'm not sure this would have any performance > advantage > > over sorting. Maybe we should go back to i. : > > > > #@:] (e. < *./@:~:@:]) i. > > > > That is, look up A in B and tell me whether all elements are unique and > that > > there are no missing elements ((#A) e. A i. B). > > > > -Dan > > > > Please excuse typos; sent from a phone. > > > >> On Jul 10, 2014, at 6:48 AM, Ben Gorte - CITG <[email protected]> > >> wrote: > >> > >> Now we should ask Jon what he wants in this case: > >> > >> ]A=.3 2$1 1 1 2 1 1 > >> 1 1 > >> 1 2 > >> 1 1 > >> ]B=.3 2$1 2 1 2 1 1 > >> 1 2 > >> 1 2 > >> 1 1 > >> > >> Should the result be: > >> A *./@:e. B > >> 1 > >> or does he prefer: > >> (/:~A)-:/:~B > >> 0 > >> ? > >> > >> (I agree the first looks quicker) > >> > >> Ben > >> > >> _ > >> _______________________________________ > >> From: [email protected] > >> [[email protected]] on behalf of Dan Bron > >> [[email protected]] > >> Sent: Thursday, July 10, 2014 12:33 > >> To: [email protected] > >> Subject: Re: [Jprogramming] Comaring Arrays > >> > >> Sorting might be overkill (and/or a little expensive) for this > situation. > >> > >> If A and B are the same shape (and they'd better be, or A is definitely > >> not a permutation of B), then you really only need to know if all the > >> items (rows) of A are also items (rows) of B. > >> > >> So let's just ask that: > >> > >> A e. B > >> 1 1 1 1 > >> A *./@:e. B > >> 1 > >> > >> Now, if we needed slightly more information (and we're willing to pay > for > >> it), in particular, exactly how A is permuted from B, we could use i. > >> instead of e. : > >> > >> > >> A i. B > >> 2 0 1 3 > >> > >> And from here, we can figure out exactly how far Jon would have had to > go > >> in his quest to check every possible permutation: > >> > >> A A.@:i. B > >> 12 > >> A C.@:i. B > >> +-----+-+ > >> |2 1 0|3| > >> +-----+-+ > >> > >> Looks like about halfway ( (!#A)%2 ) . Not surprising. > >> > >> -Dan > >> > >> Please excuse typos; sent from a phone. > >> > >>> On Jul 10, 2014, at 4:17 AM, Ben Gorte - CITG <[email protected]> > >>> wrote: > >>> > >>> B=:4 4$2 3 0 1 3 2 1 0 1 0 3 2 0 0 0 0 > >> ---------------------------------------------------------------------- > >> 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
