Re: Re: Finding the closest number from a list

*To*: mathgroup at smc.vnet.net*Subject*: [mg39550] Re: [mg39517] Re: Finding the closest number from a list*From*: Dr Bob <drbob at bigfoot.com>*Date*: Sat, 22 Feb 2003 03:38:55 -0500 (EST)*References*: <b32ab1$b3o$1@smc.vnet.net> <200302210907.EAA16923@smc.vnet.net>*Reply-to*: drbob at bigfoot.com*Sender*: owner-wri-mathgroup at wolfram.com

I think this works just as well, and a little faster: closest[list_?VectorQ, things_?VectorQ] := Module[{sorted, lint, first, last, n = Length[list], lower, upper}, \ sorted = Sort[list]; first = Max[Min[things], First[sorted]] - 1; last = Min[Max[things], Last[sorted]] + 1; lint = ListInterpolation[Join[{1}, Range[n], {n}], { Join[{first}, sorted, {last}]}, InterpolationOrder -> 1]; list[[Round@lint@things]] ] Bobby On Fri, 21 Feb 2003 04:07:41 -0500 (EST), Robert Knapp <rknapp at wolfram.com> wrote: > Jacob Rome wrote: >> 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. >> > > Here is an approach suggested by Stephen Wolfram which is very efficient: > The idea is to use a first order interpolation to find an estimate to the > closest index, then use actual comparison to determine which element is > actually closest. The reason this approach is fast is because > InterpolatingFunctions in Mathematica use a fast method to determine > where an input lies in a data list. > > This function finds which element is actually closest given an upper and > lower bound on the index into the sorted list: > > In[1]:= > GetClosest[lower_, upper_, item_, slist_] := Module[{dl, du, pos}, > pos = If[upper <= lower, > upper, > {dl, du} = Abs[item - slist[[{lower, upper}]]]; > If[du > dl, > upper, > lower] > ]; > slist[[pos]] > ] > > This function returns the list of closest matches in the List list given > a List things of items you want to find the closest matches to. I have > not included it in the argument checking, but this will only work if both > lists are real or integer -- for complex numbers a more complicated > scheme would have to be concocted. > > In[2]:= > ClosestMatches[list_?VectorQ, things_?VectorQ] := > Module[{sorted, lint, first, last, n = Length[list], lower, upper}, > sorted = Sort[list]; > first = Max[Min[things], First[sorted]] - 1; > last = Min[Max[things], Last[sorted]] + 1; > lint = > ListInterpolation[ > N[Join[{1},Range[n],{n}]],{Join[{first},sorted,{last}]}, > InterpolationOrder\[Rule]1]; > estimates = lint[things]; > lower = Floor[estimates]; > upper = Ceiling[estimates]; > MapThread[GetClosest[##, sorted]&, {lower, upper, things}] > ] > > This sets up a random list and a random set of things. > > In[3]:= > n = 30000; > list = Table[Random[],{n}]; > things = Table[Random[],{10000}]; > > This finds the matches > > In[6]:= > Timing[ClosestMatches[list, things];] > > Out[6]= > {2.51 Second,Null} > > > > The timing was done on a 750MhZ PentiumIII system. > > > > -- majort at cox-internet.com Bobby R. Treat

**References**:**Re: Finding the closest number from a list***From:*Robert Knapp <rknapp@wolfram.com>