MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Efficient search for bounding list elements

  • To: mathgroup at smc.vnet.net
  • Subject: [mg114181] Re: Efficient search for bounding list elements
  • From: Barrie Stokes <Barrie.Stokes at newcastle.edu.au>
  • Date: Fri, 26 Nov 2010 05:29:00 -0500 (EST)

Hi David

I didn't quite understand Oliver Ruebenkoenig's answer to your question, so I looked at the documentation for Nearest, and ended up with:

a = Range[1000, 5000, 250];
Map[ (s\[Function]Position[ a, s ]), Nearest[a, 1600, 2] ]//Flatten

(Thanks, Oliver!)

You might like to compare these timings with your loop approach:

In[86]:= a=Range[1,500000,2];
Map[(s\[Function]Position[a,s]),Nearest[a,1600,2]]//Flatten//Timing
Out[87]= {0.156,{800,801}}
In[88]:= a=Range[1,5000000,2];
Map[(s\[Function]Position[a,s]),Nearest[a,1600,2]]//Flatten//Timing
Out[89]= {1.528,{800,801}}

Cheers

Barrie

>>> On 25/11/2010 at 9:58 pm, in message <201011251058.FAA21975 at smc.vnet.net>,
David Skulsky <edskulsky at gmail.com> wrote:
> I've been looking for a way to efficiently find the indices of the two
> elements of a monotonically increasing list which bound a number.  For
> example, if
> 
> a = Range[1000,5000,250]
> 
> and
> 
> x=1600
> 
> then I'd like this function (e.g., searchFunction[x,a]) to return
> {3,4}, which correspond to the 3rd and 4th elements of a, which are
> 1500 and 1750, respectively.
> 
> I can easily do this in a loop, but in my application a can be very
> large (hundreds of thousands or millions of elements) and this
> operation needs to repeated thousands of times, so efficiency is
> critical.
> 
> Any suggestions would be greatly appreciated!
> 
> Thanks,
> 
> David Skulsky



  • Prev by Date: Re: Why does this pattern fail to match?
  • Next by Date: Re: understanding code
  • Previous by thread: Re: Efficient search for bounding list elements
  • Next by thread: Re: Efficient search for bounding list elements