Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>