Re: Finding the closest number from a list
- To: mathgroup at smc.vnet.net
- Subject: [mg39542] Re: [mg39510] Finding the closest number from a list
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sat, 22 Feb 2003 03:37:55 -0500 (EST)
- References: <200302201014.FAA11320@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.
If all elements are machine real numbers this can be done quite fast by
sorting both lists together, augmenting elements in each list with an
index of e.g. 1 or 2 to denote from which list they originate. To allow
for fast code throughout we use machine reals for these as well (so
packed array technology will be used behind the scenes).
We use fake "ends" for the second list in order to be certain the entire
merged list is bracketed by elements from that list. We will choose them
in such a way that they cannot be taken as closest elements to elements
in the first list.
Once sorted, we go through the list and augment each element by the
closest element from the second list that is to its left. We repeat that
with closest elements to the right.
list. They now have the nearest second list elements from each side
attached to them. We determine which is closer, and return pairs of the
form
{list 1 element, closest list 2 element}.
If instead we want to retain original positions in the first list and/or
give positions of closest elements in second list, minor modifications
of the code below (to retain list index positions) could be used. Again
one would want to store them as machine reals in order to get optimal
speed.
closestPoints = Compile[{{list1,_Real,1}, {list2,_Real,1}},
Module[{lo, hi, n1, n2, len1=Length[list1], len2=Length[list2]+2,
full, bound=1., t1},
lo = -2.*(Abs[Min[list1]] + Abs[Min[list2]]);
hi = 2.*(Abs[Max[list1]] + Abs[Max[list2]]);
n1 = Transpose[{list1,Table[1.,{len1}]}];
n2 = Transpose[{Join[{lo},list2,{hi}], Table[2.,{len2}]}];
full = Sort[Join[n1,n2]];
t1 = Table[
If [full[[j,2]]==2., bound = full[[j,1]]];
Append[full[[j]],bound]
, {j, len1+len2}
];
t1 = Table[
If [full[[j,2]]==2., bound = full[[j,1]]];
Append[t1[[j]],bound]
, {j, len1+len2, 1, -1}
];
t1 = Select[t1, (#[[2]]==1.)&];
Map[
If[#[[1]]-#[[3]] < #[[4]]-#[[1]],
{#[[1]],#[[3]]}, {#[[1]],#[[4]]}]&, t1]
]];
Example:
l1 = Table[Random[], {30000}]
l2 = Table[Random[], {10000}]
In[66]:= Timing[closestPoints[l1,l2];]
Out[66]= {0.58 Second, Null}
This on a 1.5 GHz machine.
Daniel Lichtblau
Wolfram Research
- References:
- Finding the closest number from a list
- From: jrome@mail.com (Jacob Rome)
- Finding the closest number from a list