Finding $n^\text{th}$ largest/smallest element

Question

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?

Answer 1

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}

Answer 2

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.

Answer 3

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