Re: Re: Finding the closest number from a list

*To*: mathgroup at smc.vnet.net*Subject*: [mg39551] Re: [mg39517] Re: Finding the closest number from a list*From*: Dr Bob <drbob at bigfoot.com>*Date*: Sat, 22 Feb 2003 03:39:00 -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

Robert's solution: 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]]] 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 -> 1]; estimates = lint[things]; lower = Floor[estimates]; upper = Ceiling[estimates]; MapThread[GetClosest[##, sorted] &, {lower, upper, things}]] My solution (inspired by Robert's): closest[list_?VectorQ, things_?VectorQ] := Module[{sorted = Sort[list], lint, first, last, n = Length[list]}, first = Max[Min[things], First[sorted]] - 1; last = Min[Max[things], Last[sorted]] + 1; lint = Interpolation[Transpose@{ Join[{first}, sorted, {last}], Join[{1}, Range[ n], {n}]}, InterpolationOrder -> 1]; list[[Round@lint@things]] ] Test data: n = 30000; list = Table[Random[], {n}]; things = Table[Random[], {10000}]; Timings: Timing[ClosestMatches[list, things]; ] {0.9679999999999893*Second, Null} Timing[closest[list, things];] {0.5319999999999965*Second, Null} The answers aren't the same: Take[things, 5] Take[ClosestMatches[list, things], 5] Take[closest[list, things], 5] {0.6384367070141534, 0.6250093104126428, 0.12184236611421798, 0.09511197717954557, 0.679769352921642} {0.6383160624966754, 0.624879790611537, 0.12186365194457346, 0.09509389371548846, 0.679694223307205} {0.6384510214302745, 0.6250442930656402, 0.12184191844340701, 0.09512514224893226, 0.6797705952963301} Rounding the Interpolation output gets the closer result, and faster. 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>