Re: Finding the closest number from a list
- To: mathgroup at smc.vnet.net
- Subject: [mg39554] Re: Finding the closest number from a list
- From: Uri Zwick <zwick at tau.ac.il>
- Date: Sun, 23 Feb 2003 04:59:51 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Hi,
Here is an improvement over my previous suggestion.
It runs about three times faster:
fnd3[x_,y_] :=
Module[ {inv,ind,one,pos,ly,x1,z1,z2,avr,sgn} ,
inv = ind = Ordering[ Join[ y ,
x1 = Sort[ Join[x,{-$MaxMachineNumber,$MaxMachineNumber}] ] ] ] ;
inv[[ind]] = Range[1,Length[ind]] ;
ly = Length[y]+0.5 ; one = Sign[ Sign[ind-ly] + 1 ] ;
pos = FoldList[Plus,one[[1]],Drop[one,1]] [[Take[inv,Length[y]]]] ;
z1 = x1[[pos]] ; z2 = x1[[pos+1]] ; avr = (z1+z2)/2 ;
sgn = Sign[ Sign[ Sign[y-avr]-0.5 ] + 1 ] ;
(1.-sgn)z1 + (sgn+0.) z2
]
On my 900Mhz Pentium III I get:
In[1]:= x = Table[Random[], {30000}];
In[2]:= y = Table[Random[], {10000}];
In[3]:= Timing[fnd3[x, y];]
{0.15 Second, Null}
It is interesting to note that "(1.-sgn)z1 + (sgn+0.) z2"
is much faster than "(1-sgn)z1 + sgn z2". Also, using 0.5
instead of 1/2 inside the Sign speeds things up.
The posting of Daniel Lichtblau suggests a similar
approach, though the implementation details are
quite different.
Does anyone know why 0 comes before -Infinity in the
standard ordering? (See my previous posting in this thread.)
Also, did anyone encounter an
"assertion failed at "\[InvisibleSpace]"
after perturbation steplength > 0"
while calling ConstrainedMin? (See a separate posting.)
Uri