       Re: Finding the closest number from a list

• To: mathgroup at smc.vnet.net
• Subject: [mg39525] Re: [mg39510] Finding the closest number from a list
• From: Sseziwa Mukasa <mukasa at jeol.com>
• Date: Fri, 21 Feb 2003 04:08:10 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

```On Thursday, February 20, 2003, at 05:14 AM, Jacob Rome wrote:

> Hi,
>
> I have a seemingly simple problem. I want to find the element in a
> list that is closest to a number I specify. In my case, I have a list
> of about 30,000 numbers (y[i]). I want to find the closest match for
> each of about 10,000 other numbers (call them x[i]). Obviously, speed
> is important. I've sorted the large list, and right now I'm going
> through each y[i] from lowest to highest and testing it to see if x[i]
> is less than that value. This takes about .1 seconds for each x[i].
>

Are you doing a binary search?  I tested searching for items from a
list using a binary search routine as follows:

binarysearch[item_, lst_] := Block[{left = 1, middle =
Quotient[Length[lst], \
2], right =
Length[lst]}, If[
middle == 0, Return]; While[True, If[lst[[middle]] ==
item, Return[middle], If[right - left ¡Â 1,
If[lst[[right]] - item < item - lst[[left]], Return[right], Return[
left]], If[
item > lst[[middle]], left = middle,
right = middle]]]; middle = Quotient[left + right, 2]]]

and using map to search for 10000 values (ie
binarysearch[#,lst]&/@items) and it takes about 6 seconds on a 1GHz G4
with a list of 30000 items.

> I'm wondering if anyone has had a similar problem, and if there is a
> better function built-in to Mathematica. Alternatetively, I could
> build my own. I've just recently realized that I could also reduce the
> search time considerably if I sort the x[i] list as well, and only
> start my search from where I last left off.  Any ideas on which
> approach would be more efficient? Thanks.
>
>

Since a binary search scales as log n, dropping items from the list to
be searched may actually be slower due to overhead in manipulating the
list.  To get a factor of 2 improvement in the search you need to drop
the list size to sqrt(n).  This code takes about 11 seconds on my
machine:

Block[{mylist = lst, pos, dropped = 0}, Table[pos =
binarysearch[items[[i]], mylist]; mylist = Drop[mylist, pos -
1]; dropped +=
pos - 1, {i, Length[items]}]]

I tried a version using Mathematica's Select function which is far too
slow to consider for your problem and a version in which I precomputed
intervals in order to short circuit the search.  That approach is
negligibly faster than the straightforward search and 3 times more
memory intensive.

Regards

Ssezi

```

• Prev by Date: Re: Re: Porting graphics to MicroSoft Point, with quality - no
• Next by Date: Re: Finding the closest number from a list
• Previous by thread: Re: Finding the closest number from a list
• Next by thread: Re: Finding the closest number from a list