Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Finding the closest number from a list

• To: mathgroup at smc.vnet.net
• Subject: [mg39517] Re: Finding the closest number from a list
• From: Robert Knapp <rknapp at wolfram.com>
• Date: Fri, 21 Feb 2003 04:07:41 -0500 (EST)
• Organization: Wolfram Research, Inc.
• References: <b32ab1$b3o$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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.

• Follow-Ups:
  • Re: Re: Finding the closest number from a list
    • From: Dr Bob <drbob@bigfoot.com>
  • Re: Re: Finding the closest number from a list
    • From: Dr Bob <drbob@bigfoot.com>