Re: Finding the closest number from a list
- To: mathgroup at smc.vnet.net
- Subject: [mg39558] Re: Finding the closest number from a list
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Sun, 23 Feb 2003 05:00:04 -0500 (EST)
- Organization: University of Washington
- References: <b32ab1$b3o$1@smc.vnet.net> <b37ev5$piv$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hi all,
Upon further consideration, I thought of a way to modify my previous attempt
so that the closest matches were found. My new function follows:
makeinterp[y_]:=Module[{sy},
sy=Sort[y];
Interpolation[Transpose[{ListCorrelate[{1/2,1/2},Join[sy,{sy[[-1]]}]],sy}],I
nterpolationOrder->0]
This function creates an interpolating function which returns the y value
closest to its argument. As an example,
y=Table[Random[],{30000}];
x=Table[Random[],{10000}];
closest=makeinterp[y];//Timing
closest[x];//Timing
{0.078 Second, Null}
{0.047 Second, Null}
One could instead make a single function which takes x and y values as
arguments (as most others have done), but I think splitting up the work as I
have done makes more sense. One could apply the same interpolating function
to different sets of x values this way. By way of comparison, Rob Knapp's
solution (closestr), Daniel Lichtblau's solution (closestl), Uri Zwick's
solution (closestu), and Hartmut Wolf's solution (closestw) had timings of
closestr[y,x];//Timing
closestl[y,x];//Timing
closestu[y,x];//Timing
closestw[x,y];//Timing
{1.063 Second, Null}
{0.796 Second, Null}
{0.204 Second, Null}
{0.75 Second, Null}
I didn't include DrBob's solutions, as they didn't seem to give correct
results. Also, Rob Knapp's solution didn't always give the closest y value.
Note that not all solutions returned the same output of a list of the y
values corresponding to the list x, as Hartmut Wolf's solution returned a
sorted list and Daniel Lichtblau's solution returned a list of pairs of x
values and corresponding y values.
If one wanted to find the closest matches to a single set of x values, then
Uri's and my solutions are comparable in timing. However, if one wanted to
find closest matches to multiple sets of x values, then clearly my approach
would be the speediest, as one would need to create the interpolating
function only once.
Carl Woll
Physics Dept
U of Washington
"Carl K. Woll" <carlw at u.washington.edu> wrote in message
news:b37ev5$piv$1 at smc.vnet.net...
> Hi Jacob,
>
> The first thought that I had was to use Interpolation, similar to what Rob
> Knapp posted. However, Rob's function found the closest y whether it was
> greater than or less than your x[i]. If you only care to find the first
y[i]
> that is greater (or less than) a particular x[i] (and this seems to be
what
> you wanted), it is possible to speed up Rob's solution considerably.
Again,
> we create an interpolating function, but this time we use the
Interpolation
> function, as in:
>
> ulint=Interpolation[Transpose[{y,y}],InterpolationOrder->0];
>
> The ulint function is a ladder function which gives the value of the first
y
> greater than its argument. Since interpolating functions are listable, we
> just apply ulint to your set of x values:
>
> closestabove=ulint[x];
>
> where closestabove is the list of closest values of y to each x (actually,
> the first y greater than each x).
>
> If instead, you want the first y lower than a particular value of x, we
need
> to modify as follows:
>
> llint=Interpolation[Transpose[-{y,y}],InterpolationOrder->0];
>
> closestbelow=-llint[-x];
>
> In my testing, this approach was an order of magnitude faster than both
> Hartmut Wolf's and Rob Knapp's solutions.
>
> Carl Woll
> Physics Dept
> U of Washington
>
> "Jacob Rome" <jrome at mail.com> wrote in message
> news:b32ab1$b3o$1 at smc.vnet.net...
> > Hi,
> >
> > I have a seemingly simple problem. I want to find the element in a
> > list that is closest to a number I specify. In my case, I have a list
> > of about 30,000 numbers (y[i]). I want to find the closest match for
> > each of about 10,000 other numbers (call them x[i]). Obviously, speed
> > is important. I've sorted the large list, and right now I'm going
> > through each y[i] from lowest to highest and testing it to see if x[i]
> > is less than that value. This takes about .1 seconds for each x[i].
> >
> > I'm wondering if anyone has had a similar problem, and if there is a
> > better function built-in to Mathematica. Alternatetively, I could
> > build my own. I've just recently realized that I could also reduce the
> > search time considerably if I sort the x[i] list as well, and only
> > start my search from where I last left off. Any ideas on which
> > approach would be more efficient? Thanks.
> >
>
>
>