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: [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>