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.