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