Re: Finding the closest number from a list
- To: mathgroup at smc.vnet.net
- Subject: [mg39541] Re: Finding the closest number from a list
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Sat, 22 Feb 2003 03:37:50 -0500 (EST)
- Organization: University of Washington
- References: <b32ab1$b3o$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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.
>