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. > > > > >

**Re: Programing in MATHEMATICA**

**RE: Display of legend in MultiListPlot**

**Re: Finding the closest number from a list**

**J/Link under Linux Mandrake 9.0**