       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[],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:= x = Table[Random[], {30000}];
In:= y = Table[Random[], {10000}];
In:= 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

```

• Prev by Date: Re: Epsilon-Delta proofs
• Next by Date: Miller-Rabin-Selfridge Primality Test
• Previous by thread: Re: Finding the closest number from a list
• Next by thread: Re: Finding the closest number from a list