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
