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