Right, I mean linear in n. In a scalar language, the advantage of heaping to find the k smallest values is that, in effect, you don't have to sort the whole way. You just have to go as far as making a heap, which takes on the order of a couple of compares and a swap per item of input. And it works for any datatype.
Once you have made the heap, you then extract the biggest items, which takes k lg n time, but that is small if k << n . It would be interesting if someone motivated were to code the heap-creation process in J and see how it compares to /:~ . Henry Rich > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Roger Hui > Sent: Thursday, March 20, 2008 4:17 PM > To: Programming forum > Subject: [Jprogramming] Re: Jprogramming] Biggest values from list > > Surely you don't mean linear in k but linear in n? > You have to examine at least every item to find > the maximum. If it's linear in n then so is > /: and /:~ (albeit with a larger factor) for vectors > of many datatypes. > > > > ----- Original Message ----- > From: Henry Rich <[EMAIL PROTECTED]> > Date: Thursday, March 20, 2008 12:42 > Subject: RE: [Jprogramming] Biggest values from list > To: 'Programming forum' <[email protected]> > > > Agreed, use /: . In a scalar language the way to do > > this is > > to build a heap and then pull the top k items, which takes > > linear time if k is much less than n. I suspect this is not > > very efficient in J. > > > > Henry Rich > > > > > -----Original Message----- > > > From: [EMAIL PROTECTED] > > > [mailto:[EMAIL PROTECTED] On Behalf Of Roger Hui > > > Sent: Thursday, March 20, 2008 11:15 AM > > > To: Programming forum > > > Subject: Re: [Jprogramming] Biggest values from list > > > > > > If you just want the largest value (and its position) then > > > it can be done conveniently without sorting or grading. > > > If you want the largest k values where k>1 then > > > the most convenient way is to grade, along the lines > > > that Raul Miller has shown. > > > > > > Why do you want to avoid sorting/grading? In J, for vectors > > > of many datatypes, including the integer and floating point > > > datatypes, sorting and grading takes linear time. > > > > > > > > > > > > ----- Original Message ----- > > > From: Nick Kostirya <[EMAIL PROTECTED]> > > > Date: Thursday, March 20, 2008 2:25 > > > Subject: [Jprogramming] Biggest values from list > > > To: [email protected] > > > > > > > Hello, All > > > > > > > > Can you please provide me with the most optimal way of > > picking > > > > out a > > > > given number of elements with the biggest values from a > huge list? > > > > > > > > The values and the elements' positions in a list are a > > matter of > > > > interest. > > > > > > > > Can we manage this without sorting? > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
