http://www.jsoftware.com/jwiki/Essays/Order_Statistics
y=: 1e6 [EMAIL PROTECTED] 2e9
x=: ?#y
x selecta y
1961326174
x{/:~y
1961326174
6!:2 'x selecta y'
0.0303065
6!:2 'x{/:~y'
0.133332
x select y
991409
x{/:y
991409
6!:2 'x select y'
0.0750835
6!:2 'x{/:y'
0.210581
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Thursday, March 20, 2008 18:14
Subject: Re: [Jprogramming] Biggest values from list
To: Programming forum <[email protected]>
> 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
