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