13
$\begingroup$

Searching by and I wasn't able to find an answer—but found Nearest by guessing. Nearest, however, returns the closest number itself, not the position.

After some more looking around, I learned about MapIndexed and Rules, and came up with this:

NearestPosition[haystack_, needle_] := Nearest[haystack, needle] /. MapIndexed[Rule, haystack];

Is there a more efficient way, in general?

(And what if it's guaranteed the list comes sorted—can that be leveraged?)

The reason I'm concerned about efficiency is that I intend to use NearestPosition in a DynamicModule where it may be triggered by every mouseover event. (I'm still trying to solve this problem.)

Improve this question
$\endgroup$
2
  • $\begingroup$ thinking about it computationally, you'd need to check every number to determine which one is the closest number. So best you got is O(n). If it's sorted, you obviously can do a lot better by binary search and such. Anyway, what happens if there are multiple instances of the closest number? Do you expect it to take the closest or last? $\endgroup$ Commented Oct 23, 2013 at 5:00
  • $\begingroup$ @Jonie - Currently my implementation (above) returns what Nearest would return by default: a list of all "tied" for the closest. (I don't need any of Nearest's other features, like closest-within-a-radius, closest-n, etc.) $\endgroup$ Commented Oct 23, 2013 at 5:02

2 Answers 2

Reset to default
14
$\begingroup$ 
SeedRandom[42]; haystack = RandomReal[1, 6300]; AbsoluteTiming[ f = Nearest[haystack -> Range@Length@haystack]; {f[.3, 1], haystack[[f[.3, 1]]]}] (* -> {0.015625, {{3123}, {0.300033}}} *)

Of course in this case most of the time is expended calculating the nearest function. If your points aren't changing from one use to the next, the time for calculating f[}is nil for 6K points.

The second argument of f[] specifies that Nearest[] should return only one point

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ You could use Automatic instead of Range. $\endgroup$ Commented Oct 23, 2013 at 6:45
  • $\begingroup$ Thanks for the cleaner solution. And indeed, I may be prematurely optimizing. $\endgroup$ Commented Oct 23, 2013 at 11:14
  • $\begingroup$ @SjoerdC.deVries Yep, used it here mathematica.stackexchange.com/a/34620/193 $\endgroup$ Commented Oct 23, 2013 at 15:13
  • $\begingroup$ Thanks, I didn't know that I can precalculate something like NearestFunction. :) $\endgroup$ Commented Oct 24, 2013 at 7:18
5
$\begingroup$

In versions 10+, you can have a NearestFunction that returns multiple properties, such as the "Index" of the nearest element and the "Element" itself:

SeedRandom[42]; haystack = RandomReal[1, 1000000]; f = Nearest[haystack ->{"Index", "Element"}]; AbsoluteTiming[f[.312345]]

{0.000072, {{101999, 0.312345}}}

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could someone please explain this syntax: 'Nearest[haystack ->{"Index", "Element"}]'? In particular, I have trouble understanding the role and functioning of the rule ("->") operator here. $\endgroup$ Commented May 18, 2022 at 16:51
  • $\begingroup$ @BenjaminMárkus, see Nearest >> Details and Options (and the examples 7 thru 10 in the section Scope.) $\endgroup$ Commented May 19, 2022 at 8:49

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.