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)