Re: Finding the closest number from a list

*To*: mathgroup at smc.vnet.net*Subject*: [mg39548] Re: Finding the closest number from a list*From*: Uri Zwick <zwick at tau.ac.il>*Date*: Sat, 22 Feb 2003 03:38:45 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

Hi, Here is my solution the problem. The trick is to sort the two lists together! fnd[x_,y_] := Module[ {inv,ind,one,pos,ly,x1} , inv = ind = Ordering[ Join[ y , x1 = Sort[ Join[x,{-$MaxMachineNumber,$MaxMachineNumber}] ] ] ] ; inv[[ind]] = Range[1,Length[ind]] ; ly = Length[y] ; one = Map[ (If[#<=ly,0,1])& , ind ] ; pos = FoldList[ Plus , one[[1]] , Drop[one,1] ] [[ Take[inv,Length[y]] ]] ; MapThread[ If[#1<(#2+#3)/2,#2,#3]& , { y , x1[[pos]] , x1[[pos+1]] } ] ] On my 900Mhz Pentium III I get: In[1]:= x = Table[Random[], {30000}]; In[2]:= y = Table[Random[], {10000}]; In[3]:= Timing[fnd[x, y];] {0.401 Second, Null} About two thirds of the time is spent on the last MapThread. The other costly operation is probably Map. Is there a simple way to speed these operations up? Also, it would have been cleaner to use -Infinity and Infinity instead of -$MaxMachineNumber and $MaxMachineNumber. But, according to the standard order -Infinity is larger than finite numbers !!! In[4] := Sort[ {0,-Infinity} ] {0 , -Infinity } Am I missing something here? Giving Sort and explicit ordering function slows it down considerably. Uri