MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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




  • 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