15
$\begingroup$

Suppose a list of items such as:
L1 = RandomReal[{0, 100}, 1000];

I need to find the position of each k-neighbor in the original list. And very quickly if possible.
As we can see, the problem is divided into two main parts :
- The search for k-neighbors.
- The search for their positions in the original list.



Mathematica code




On Mathematica 9.0

Doedalos :

KPosition1[x_, y_] :=
  Block[
        {step0, step1, step2},
         step0 = Range[1, Length@x, 1];
         step1 = (Nearest[x, x[[#]], y][[2 ;; -1]]) & /@ step0;
         step2 = Map[Position[x, #][[1, 1]] &, step1, {2}]
       ];


KPosition2[x_, y_] :=
  Block[
        {step0, step1, step2},
         step0 = Thread[x -> Range[1, Length@x, 1]];
         step1 = Nearest[step0 , #, y] & /@ x
       ];

Bill s :

KPosition3[x_, y_] :=
  Block[
        {step0, step1, step2},
         step0 = Thread[x -> Range[1, Length@x, 1]];
         step1 = Nearest[step0];
         step2 = Map[step1[#, y][[2 ;; -1]] &, x]
       ];



On Mathematica 10.0

kale :

KPosition4[x_, y_] :=
  With[
       {p = PositionIndex[x]},
        Map[p[#][[1]] &, Nearest[x, x, y][[All, 2 ;; -1]], {2}]
      ];

Mr.Wizard :

KPosition5[x_, y_] := Nearest[x -> Range@Length@x, x, y];


Benchmarking


Warning : Only Kposition1, Kposition2 and Kposition3 are tested.

1) By varying the length of the lists.

enter image description here enter image description here

2) By varying the dimension of the points.

enter image description here enter image description here


Commentary


On Mathematica 9.0

Sort by execution's speed :
Kposition3 > Kposition2 > Kposition1

On Mathematica 10.0

If somebody wants to make the benchmarks... Currently, I has not the version 10 of Mathematica.

$\endgroup$
0

3 Answers 3

16
$\begingroup$

You can speed it up by only invoking the NearestFunction once:

KPosition3[x_, y_] := 
  Module[{step0, step1, nf}, 
   step0 = Thread[x -> Range[1, Length@x, 1]];
   nf = Nearest[step0];
   step1 = nf[#, y] & /@ x];

Running your three timing tests gives:

{0.003057, 0.004344, 0.051009}
$\endgroup$
3
  • $\begingroup$ Is it possible to show the dynamics of the search process via a suitable graph? $\endgroup$
    – thils
    Commented Jun 19, 2015 at 6:57
  • $\begingroup$ Thanks for your answer. I do not think it's possible to be faster with a simpler code. $\endgroup$
    – Doedalos
    Commented Jun 19, 2015 at 8:44
  • 2
    $\begingroup$ I suspect that it is almost always possible to find faster and simpler code! $\endgroup$
    – bill s
    Commented Jun 19, 2015 at 9:27
9
$\begingroup$

Here's a way using Nearest a little differently, remembering Nearest's second argument can be a list...

KPosition[x_, y_] := With[{p = PositionIndex[x]}, 
 Map[p[#][[1]] &, Nearest[x, x, y][[All, 2 ;;]], {2}]]

And my timings:

KPosition[Tst1, 8]; // AbsoluteTiming
KPosition[Tst2, 8]; // AbsoluteTiming
KPosition[Tst3, 8]; // AbsoluteTiming

{0.00255016, Null}

{0.0201945, Null}

{0.103676, Null}

$\endgroup$
1
  • $\begingroup$ I'm seeing a ~3% speedup using WorkingPrecision -> MachinePrecision in Nearest[] in your implementation of KPosition[]. Varying Method and DistanceFunction had no oveservable improvement. (Octrees were substantially worse.) 3% may not be sufficient for the OP. $\endgroup$ Commented Jun 18, 2015 at 21:11
5
$\begingroup$

Edit: now including Michael E2's improvement.

Building on your own code and the existing answers this seems both cleaner and faster:

wizKP[x_List, n_] := Nearest[x -> Automatic, x, n]
$\endgroup$
6
  • $\begingroup$ I will made new benchmarks soon... $\endgroup$
    – Doedalos
    Commented Jun 19, 2015 at 10:28
  • $\begingroup$ Actually, when I try to test your code I have the following error : " Nearest :: dmtch : The dimension of ... and ... does not match" $\endgroup$
    – Doedalos
    Commented Jun 19, 2015 at 11:25
  • $\begingroup$ @Doedalos A limitation of version 9 perhaps. Please tell me what you get from Nearest[Thread[x -> Range @ Length @ x], x, n] ? $\endgroup$
    – Mr.Wizard
    Commented Jun 19, 2015 at 11:36
  • $\begingroup$ I have the same error. I think you're right about Mathematica 9. I see nothing in the documentation of version 9, which mentions the possibility of using a list in second position. This is not the case in the documentation of version 10. I think, it is time for me to change. $\endgroup$
    – Doedalos
    Commented Jun 19, 2015 at 11:48
  • 1
    $\begingroup$ Shouldn't Nearest[x -> Automatic, x, n] work? $\endgroup$
    – Michael E2
    Commented Jun 20, 2015 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.