({.,#)/. is supported by special code
(http://www.jsoftware.com/docs/help803/dictionary/special.htm)
tst=: 1e6 ?@$ 12
10 timespacex '(({.,#);.1~ 1,2~:/\]) /:~ tst'
0.0169435 1.1542e7
10 timespacex '/:~@(~. ,. #/.~) tst'
0.0087152 4224
10 timespacex '([: /:~ ({.,#)/.~) tst'
0.00552655 4224
On Wed, Apr 1, 2015 at 8:06 AM, Marshall Lochbaum <[email protected]>
wrote:
> If you're going to sort the list you can then split on the boundaries
> between groups of equal terms (that is, split where adjacent items are
> unequal):
>
> (({.,#);.1~ 1,2~:/\]) /:~ list
> 0 1
> 1 2
> 2 8
> 3 11
> 4 8
> 5 7
> 6 5
> 7 5
> 8 5
> 9 2
>
> This seems to be about half as fast as the solution with (~.,.#/.~), but
> is slightly quicker for an already-sorted list. The functions ~. and /.
> are implemented using hashing (or, for appropriate integer lists,
> small-range special code) and take linear time. Sorting uses a radix-ish
> sort (or small-range special code) and also takes linear time.
>
> Marshall
>
> On Tue, Mar 31, 2015 at 05:35:10PM +0100, Jon Hough wrote:
> > Raul, Pascal,
> > Thanks. I had a feeling there was going to be a "Oh yeah, J uses its own
> thing" type answer. Playing around with your verbs and writing my own, I
> have my own humble attempt:
> >
> > duplicates =: (/:~@:~.) ,: (#/.~@:/:~)
> >
> >
> > Seems to work, although doing sort /:~ twice doesn't feel good.
> >
> >
> > Nuvoc indicates that the /. is optimized but I still wonder what sort of
> time complexity we're looking at.
> >
> >
> > I suppose I should do some quick tests to measure the time taken on
> various lists.
> >
> >
> >
> >
> > For completeness I also have my original verb as a tacit verb:
> duplicates =: +/ @: ((/:~@~.) (="_ 0) ])
> >
> >
> >
> > Thanks,Jon
> > > From: [email protected]
> > > Date: Tue, 31 Mar 2015 12:17:49 -0400
> > > To: [email protected]
> > > Subject: Re: [Jprogramming] Interview question and answer with J
> > >
> > > I usually use something like this:
> > >
> > > (~. ,. #/.~) list
> > > 2 8
> > > 3 11
> > > 4 8
> > > 5 7
> > > 6 5
> > > 7 5
> > > 8 5
> > > 9 2
> > > 1 2
> > > 0 1
> > >
> > > You can sort that if you prefer:
> > >
> > > /:~ (~. ,. #/.~) list
> > > 0 1
> > > 1 2
> > > 2 8
> > > 3 11
> > > 4 8
> > > 5 7
> > > 6 5
> > > 7 5
> > > 8 5
> > > 9 2
> > >
> > > That said, when working with really large data sets, sometimes it
> > > makes more sense to sort the values and then look for where they
> > > change.
> > >
> > > L=: /:~ list
> > > b=: 1,2 ~:/\ L
> > > ...
> > >
> > > Thanks,
> > >
> > > --
> > > Raul
> > >
> > > On Tue, Mar 31, 2015 at 12:10 PM, Jon Hough <[email protected]>
> wrote:
> > > > A fairly common technical question for programming interviews is to
> write (on a whiteboard)a method to find how many duplicates of each number
> exist in a list of numbers.
> > > > e.g. if list = 1 3 2 1 5 2
> > > > then the answer would be 2 1's, 2 2's, one 3 and one 5.
> > > > The trick is to do it in a time efficient way. In a standard
> programming language (Java, C++ etc),the naive approach is to do two passes
> and count how many of each number are duplicated. This approach takes
> n(n-1)/2 comparisons, so could be regarded as O(n^2).The better approach
> would be to create a dictionary / hashtable for each number and add items
> to the correctslot (i.e. key in the dictionary).
> > > >
> > > > But for J, it seems there is not a readily available fast approach
> to this.e.g.
> > > >
> > > > list =: 2 3 4 3 2 3 4 5 6 5 4 7 8 9 7 6 4 6 2 1 2 3 4 3 2 3 4 5 7 5
> 2 3 5 8 9 0 4 3 2 3 1 2 6 5 7 8 7 8 3 4 5 3 6 8
> > > >
> > > >
> > > > I want to count how many duplicates appear:
> > > >
> > > >
> > > >
> > > >
> > > > +/ ((i.10)&="_ 0)list
> > > >
> > > >
> > > > (result: 1 2 8 11 8 7 5 5 5 2)
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > I think this is O(n^2), since it first constructs nxn table before
> folding +/.
> > > >
> > > >
> > > > My result is correct but my method is slooow.
> > > > Is there a better (faster, lower complexity) way to solve this?
> > > >
> > > >
> > > > Regards,
> > > > Jon
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> ----------------------------------------------------------------------
> > > > 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
