Improvment to maxima which exploits the special code for (i.>./) :
maxima1=: 4 : 0
sb=. <./ y
rv=. ''
ri=. ''
for_i. i.x do.
mi=. (i.>./) y
mv=. mi{y
y=. sb mi}y
rv=. rv,mv
ri=. ri,mi
end.
ri;rv
)
ts '3 maxima A'
0.127937 8.39219e6
ts '3 maxima1 A'
0.0489093 8.39251e6
ts '13 maxima A'
0.470606 8.3927e6
ts '13 maxima1 A'
0.117383 8.3929e6
----- Original Message -----
From: Oleg Kobchenko <[EMAIL PROTECTED]>
Date: Thursday, March 20, 2008 16:52
Subject: Re: [Jprogramming] Biggest values from list
To: Programming forum <[email protected]>
> Here's an example of x10 speed difference:
>
> ts=: 6!:2 , 7!:[EMAIL PROTECTED]
> A=. 1e6 [EMAIL PROTECTED] 0
>
> s;s{A [ s=. 3{.\:A
> +--------------------+------------+
> |736817 218905 249629|1 1 0.999999|
> +--------------------+------------+
> 3 maxima A
> +--------------------+------------+
> |736817 218905 249629|1 1 0.999999|
> +--------------------+------------+
>
> ts 's;s{A [ s=. 3{./:A'
> 0.477354 8.91398e6
> ts '3 maxima A'
> 0.0402036 8.39219e6
>
> NB. =========================================================
> maxima=: 4 : 0
> sb=. <./ y
> rv=. ''
> ri=. ''
> for_i. i.x do.
> mv=. >./y
> mi=. y i. mv
> y=. sb mi}y
> rv=. rv,mv
> ri=. ri,mi
> end.
> ri;rv
> )
>
> NB. =========================================================
>
> It catches up at 40 for 1,000,000.
>
> ts '40 maxima A'
> 0.46322 8.39322e6
>
> k time
> 2 0.0317765
> 4 0.0536817
> 8 0.105835
> 16 0.194492
> 32 0.372339
> 64 0.724887
> 128 1.42764
>
> k % time
> 62.9396 74.5133 75.5894 82.2656 85.9432 88.2896 89.6585
>
> i.e. maxima is linear WRT k. Where /: would be practically const.
>
>
> --- Roger Hui <[EMAIL PROTECTED]> wrote:
>
> > 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
