Thanks you for pointing this page out. This has some interesting algorithms, new to me.
Henry Rich > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Roger Hui > Sent: Thursday, March 20, 2008 9:11 PM > To: Programming forum > Subject: Re: [Jprogramming] Biggest values from list > > I believe the following is a better way to this in scalar languages: > > a. Find the k-th order statistic s using the algorithm by > Blum, Floyd, Pratt, Rivest, and Tarjan [1972]. > http://en.wikipedia.org/wiki/Selection_algorithm > Also section 3.6 of Aho, Hopcroft, and Ullman, > The Design and Analysis of Computer Algorithms, > 1975. > > b. Do a final pass through the data v, selecting i{v if it > is less than s. > > This is the algorithm I would use if I were doing special > code for the following dyads: > {. /: > {. /:~ > {. \: > {. \:~ > > > > ----- 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
