0
$\begingroup$

The "top k of n" problem: You have n (not necessarily distinct) elements in an array, and you need to return another array containing the k elements with the highest value.

So, I'm going to need a top-k-of-n implementation for something I'm working on. Never mind exactly which programming language and hardware I'm going to use - but do mind that it's going to actually run on actual hardware. Thus there is multi-level caching so dereferencing pointers to arbitrary places should be minimized; there's the balance between computation and memory bandwidth to consider; there's multithreads/SIMDizing/whatever so I would like something parallelizable without too much communication... that's what I meant by somewhat-hardware-conscious.

Anyway, for a really small k I would probably just use a priority queue which fits in cache (or even linear search through several registers). But - what if your k is large? Large that the top k elements won't just be hiding at the top end of an estimated distribution? In this case I was thinking of estimating k using sampling, then (sort of) partitioning on that guess k; seeing how badly I missed; and iterating that, either partitioning my more-than-k or my more-than-n-minus-k. On one hand the length decreases quickly, and on the other hand I get closer to the really-small-k case, until I can settle for a priority queue (say for each core even) for the last bit.

So, my questions are:

  • Can someone describe known algorithms for this variant of the problem, meeting my "vague hardware consciousness" constraint?
  • Does the algorithm sketch I described sound like something you know?
  • If not, does it sound like a good idea or can you describe shortcomings of this kind of an approach?

Notes:

  • You may assume the data are non-negative integers if it helps in any way (I don't think it should), or make any any other reasonable assumptions.
  • This problem is different that the partial sorting problem in that the output does not need to be sorted. Of course, for small k = $o(\sqrt{n})$ there isn't that much of a difference.
  • The data is in memory, i.e. this is not a streaming algorithm and you can read data multiple times. You can't alter the input; you can make a full copy but hopefully that should be overkill.
$\endgroup$
  • 1
    $\begingroup$ Your idea is similar to Quickselect. $\endgroup$ – Raphael Oct 20 '16 at 20:54
  • 1
    $\begingroup$ Idea: Split your data into cache-sized parts. Solve the problem on these parts in parallel. Proceed similarly with all the top $k$ elements you find until only $k$ elements are left. $\endgroup$ – Raphael Oct 20 '16 at 20:56
  • 1
    $\begingroup$ You said in the question that $k = \Theta(\sqrt{n})$, so that example isn't relevant here. $k = (1 - 1/1000) n$ doesn't satisfy $k = \Theta(\sqrt{n})$. $\endgroup$ – D.W. Oct 20 '16 at 21:49
  • 1
    $\begingroup$ If you want us to focus on the case where $k$ is larger than the cache size, it'd help to state that in the question (and clarify the model a bit more if you can -- is this a hardware circuit? parallel processing with multiple processors? does each processor have access to large sequential-access memory and a small random-access cache?). $\endgroup$ – D.W. Oct 20 '16 at 21:52
  • 1
    $\begingroup$ I think you'll get better answers if you are specific. Otherwise, you're forcing us to guess your requirements. You can still edit to clarify the relevant properties of the GPU (along the lines I sketched), without having to say it's for a GPU. Also, given your edit, please confirm whether we can assume $k \le n/2$. (If not, the first step may well be to set $k' = n-k$ and then find the $k'$th smallest element, which is equivalent to finding the $k$th largest element. Tell us in the question whether we have to deal with this corner case explicitly, or if we can assume $k \le n/2$.) $\endgroup$ – D.W. Oct 20 '16 at 21:57
1
$\begingroup$

If you're allowed to make multiple passes through the data, one efficient approach is to use QuickSelect to find the value of the $k$-th largest element, then follow with a linear scan that outputs all elements that are larger than it.

This is more or less a more carefully-worked out version of the kind of approach you seemed to be considering.

See also https://en.wikipedia.org/wiki/Selection_algorithm.


The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another possible approach would be to take a sorting network, which is a hardware circuit that sorts all of the values. Then, throw away all but the last $k$ outputs, and keep only the gates they depend on. You might be able to throw away a non-trivial fraction of the sorting network -- I haven't tried to work out how much. This would solve the partial sorting network, and could potentially be hardware-friendly.


The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another approach is to do something like merge sort, but where you only keep the top $k$ elements in each list at each stage. In other words, split your data so that each processor receives an equal number of items. Have each processor find the top $k$ of its elements (say, using a priority queue or any other method). Then merge lists recursively, where each merge operation merges two or more lists of size $k$ and outputs only the first (largest) $k$ elements of the result. This might work very well for out-of-cache (too-large-to-fit-in-main-memory) situations, or for parallel computing. If you can fit $B$ items in cache/memory, then each merge step merges $B/k$ lists, so the number of rounds is $\lg_{B/k} (n/B)$.

$\endgroup$
  • $\begingroup$ You want me to repeatedly pivot all of my data? :-( I know about QuickSelect, of course, but while it's theoretically nifty, I'm sure you can do much better in practice. And when I say better, I mean the constants in the O(...) notation. My suggestion, assuming it's valid, should give (1+o(1)) expected passes + f(k) complexity afterwards. $\endgroup$ – einpoklum Oct 20 '16 at 18:54
  • $\begingroup$ @einpoklum "I'm sure you can do much better in practice" -- not for selection, you can't. And you clearly do have to solve selection (with parameter $k$) as a subproblem, so I think D.W.'s answer may be very good. Incidentally, Quickselect is also quite tame w.r.t. caching. $\endgroup$ – Raphael Oct 20 '16 at 20:55
  • $\begingroup$ Median of medians is cache-oblivious; I assume Quickselect is as well. Partitioning is a side effect of the algorithm. $\endgroup$ – KWillets Oct 20 '16 at 21:29
  • $\begingroup$ The hardware is not nearly big enough to have a size-n network. Think of n as being less than an order of magnitude below the size of RAM. $\endgroup$ – einpoklum Oct 20 '16 at 21:44

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.