       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>
• 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:=
> 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:=
> 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:=
> n = 30000;
> list = Table[Random[],{n}];
> things = Table[Random[],{10000}];
>
> This finds the matches
>
> In:=
> Timing[ClosestMatches[list, things];]
>
> Out=
> {2.51 Second,Null}
>
>
>
> The timing was done on a 750MhZ PentiumIII system.
>
>
>
>

--
majort at cox-internet.com
Bobby R. Treat

```

• Prev by Date: Re: Finding the closest number from a list
• Next by Date: Re: Re: Finding the closest number from a list
• Previous by thread: Re: Finding the closest number from a list
• Next by thread: Re: Re: Finding the closest number from a list