18
$\begingroup$

Ordering can quickly find the position of the largest/smallest element in a list, but finding the position of the $n^\text{th}$ largest/smallest element is much slower:

data = RandomReal[10, 10^7];

Ordering[data, -1] //AbsoluteTiming
Ordering[data, {-2}] //AbsoluteTiming

{0.053113, {8502130}}

{1.87766, {180842}}

In this example, finding the $2^\text{nd}$ largest elements takes 36 times longer. Is it possible to create a function that finds the position of the $n^\text{th}$ largest/smallest element (for smallish $n$) more quickly?

$\endgroup$
  • 1
    $\begingroup$ The second one is just as slow as a full Sort/Ordering, so I guess that's what it does. $\endgroup$ – Szabolcs Sep 2 '17 at 18:23
  • 1
    $\begingroup$ I guess this is related to why RankedMin[] and RankedMax[] are slow. $\endgroup$ – J. M. is away Sep 3 '17 at 4:36
  • $\begingroup$ @J.M. I am not seeing anything that I might view as a speed deficiency in either TakeLargest[data, 2] or RankedMax[data,2]. What sort of settings are you using to get slow results? (There are some internal switches between methods for TakeLargest, based on the value of the second argument. I do not think RankedMax has any such though.) $\endgroup$ – Daniel Lichtblau Sep 3 '17 at 15:16
  • $\begingroup$ @Daniel, I'll have to dig up that notebook where I tried out the Ranked*[] functions for slightly large lists, but I distinctly remember being disappointed and coming back to using Ordering[]. (Granted, that was back in version 8 if memory serves, so maybe things are indeed different now.) $\endgroup$ – J. M. is away Sep 3 '17 at 15:24
18
$\begingroup$

One possibility is to use Nearest:

Nth[data_, k_] := If[k>0,
    Nearest[data->"Index", Min[data], k][[k]],
    Nearest[data->"Index", Max[data], -k][[-k]]
]

Test:

data = RandomReal[10, 10^7];

Ordering[data, {-2}] //AbsoluteTiming
Nth[data, -2] //AbsoluteTiming

Ordering[data, {20}] //AbsoluteTiming
Nth[data, 20] //AbsoluteTiming

{1.91244, {1740219}}

{0.021692, 1740219}

{1.81072, {5932298}}

{0.02104, 5932298}

$\endgroup$
  • $\begingroup$ It would be nice to have these optimized in Ordering for when the input is a real or integer packed array. (Nearest doesn't generalize as well for non-numerical lists.) $\endgroup$ – Szabolcs Sep 2 '17 at 18:55
  • 4
    $\begingroup$ Notes: (1) Pre V11, use Automatic instead of "Index". (2) Nth[data, -1] is faster than the rather speedy Ordering[..], too. (3) Nearest was "fixed" in V10; for earlier versions, Nth will be slower than Ordering. $\endgroup$ – Michael E2 Sep 3 '17 at 0:37
9
$\begingroup$

Preamble

I wasn't able to beat Nearest, which is extremely fast. But one can get a decent result with Compile, that is still pretty good compared to Ordering. According to my benchmarks, my code has been consistently 4 times slower than the version with Nearest from the answer of Carl, but I decided to post it anyway, since similar techniques could be useful in some other cases where Nearest won't necessarily be helpful.

So the idea is to form a binary search tree that would store the n largest results (I only consider the largest results case, the other one is similar), and be continuously updated as we scan through the list. Then, we need to extract the smallest element from the tree (which is it's "left-most" element), which will be the n-th largest element in the list.

Code

Here is the code:

rankedMaxPosition = 
  Compile[{{lst,_Real,1}, {n,_Integer}},
    Module[{len=Length[lst],ctr=1,nodeCtr = 1, currentRoot=1, parentRoot = 1, 
      root = 1, leftchildren={0},rightchildren = {0}, current = 0., 
      min = 0., rootElem = 0., leftChild = 1, rightChild = 1
      },
      leftchildren = rightchildren = Table[0,{len}];
      min = Min[lst];
      For[ctr = 2, ctr <= len, ctr++,
        current = Compile`GetElement[lst,ctr];
        If[current < min, 
            Continue[]
        ];
        currentRoot = root;
        While[True,
          rootElem = Compile`GetElement[lst, currentRoot];
          If[current == rootElem, (* Ignore duplicates *)
            Break[]
          ]; 
          (* Insert the element into a binary search tree *)
          If[current < rootElem,
            leftChild = Compile`GetElement[leftchildren, currentRoot];
            If[leftChild == 0,
              leftchildren[[currentRoot]]=ctr;
              nodeCtr++;
              Break[],
              (*else*)
              currentRoot=leftChild;
            ],
            (* else *)
            rightChild = Compile`GetElement[rightchildren, currentRoot];
            If[rightChild == 0,
              rightchildren[[currentRoot]]=ctr;
              nodeCtr++;
              Break[],
              (*else*)
              currentRoot = rightChild;
            ]
          ]
        ];
        If[ nodeCtr > n, (* If we already store enough numbers, remove the smallest one from the tree *)
          currentRoot = root;
          While[True,
            leftChild = Compile`GetElement[leftchildren, currentRoot];
            rightChild = Compile`GetElement[rightchildren, currentRoot];
            If[leftChild == 0,
              min = lst[[currentRoot]];
              If[currentRoot == root && rightChild != 0,
                (* The element being removed is a current root. Move the root to its right child *)
                root = rightChild;
                rightchildren[[currentRoot]] = 0,
                (* else - remove the node by replacing it with it's right child *)  
                leftchildren[[parentRoot]] = rightChild;
              ];
              nodeCtr --;
              Break[]
            ];
            parentRoot = currentRoot;
            currentRoot = leftChild;
          ];
        ];
      ];
      (* Find the smallest element from those stored in the tree - this will be what we need *)
      currentRoot = root;
      While[True,
        leftChild = Compile`GetElement[leftchildren, currentRoot];
        If[leftChild == 0, Break[]];
        currentRoot = leftChild;
      ];
      currentRoot
    ]
    ,
    CompilationTarget -> "C", "RuntimeOptions" -> "Speed",
    CompilationOptions -> {"ExpressionOptimization" -> True}
]

Benchmarks

data = RandomReal[10, 10^7];
Ordering[data, {-10000}] // AbsoluteTiming
rankedMaxPosition[data, 10000] // AbsoluteTiming
Nth[data, -10000] // RepeatedTiming

(*

  {2.20912, {1937594}}

  {0.143862, 1937594}

  {0.036096, 1937594}

*)

Notes

One probably can improve the performance further, either by using something more sophisticated than a simple binary search tree approach I used here, or by switching to pure C and LibraryLink, or both.

My main point here has rather been that, lacking built-in functions like Nearest (and there may be other cases where there won't be a directly applicable built-in function), one can do reasonably well with Compile.

The case of n - th smallest number is completely analogous, so I didn't consider it here separately. One can easily extend the code of rankedMaxPosition to accept both positive and negative n.

$\endgroup$
  • $\begingroup$ Thanks for your answer, it's very helpful. This seems to be very similar to the quicksort algorithm. Is the binary search tree (k-d tree) the data structure behind Nearest? $\endgroup$ – xslittlegrass Sep 3 '17 at 3:44
  • 1
    $\begingroup$ Almost like quickselect, yeah. $\endgroup$ – J. M. is away Sep 3 '17 at 4:39
  • 1
    $\begingroup$ Probably could get e mild speed boost using an ordered heap. An added advantage is that code for these tends to be slightly more concise than for the tree-based variant. $\endgroup$ – Daniel Lichtblau Sep 3 '17 at 15:09
  • 2
    $\begingroup$ @xslittlegrass Nearest by default uses a kD-tree, with some internal setting for how many elements to allow in a "leaf" box. $\endgroup$ – Daniel Lichtblau Sep 3 '17 at 15:11
  • 2
    $\begingroup$ @DanielLichtblau I thought about it, but my SE time allowance was exhausted yesterday :) $\endgroup$ – Leonid Shifrin Sep 3 '17 at 17:03
2
$\begingroup$

The function RankedMax[list,n] gives the nth largest element of the list. And for the nth smallest element use RankedMin[list,n]

$\endgroup$
  • $\begingroup$ Does this find the position "more quickly" as asked in the OP? $\endgroup$ – Michael E2 Feb 11 '18 at 17:34
  • $\begingroup$ It seems to perform similarly the Nearest approach Carl Woll provided on my machine, at least in version 11.2. $\endgroup$ – eyorble Feb 11 '18 at 17:38
  • $\begingroup$ @eyorble It goes from twice as fast to twice as slow as the size of the list goes from 10^5 to 10^7 on my machine. However, it does not answer the question, which is to find the position, not the value. $\endgroup$ – Michael E2 Feb 11 '18 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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