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: [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




  • Prev by Date: Re: On Packages and Buttons
  • Next by Date: Re: series expansions in two variables problem
  • Previous by thread: RE: Finding the closest number from a list
  • Next by thread: Re: Finding the closest number from a list