On 6/23/14, 3:47 PM, Xinok wrote:
I've managed to build a small laundry list the past couple days, so why
not add another item? I've been tasked with implementing a
"deterministic topN", but I also noticed that topN is lacking a stable
implementation, so this seemed like an ideal opportunity to kill two
birds with one stone. However, for me, it begged the question:
What exactly does stable topN imply?
A stable sort only implies that equal elements retain their original
order. However, topN is a partitioning function whose pivot is unknown
beforehand. To me, it would make more sense that not just equal elements
but ALL elements retain their original order in their respective
partitions.
However, to accomplish the above, the Nth element would need to be
discovered before any other elements are reordered. This suggests making
a full copy of the range to search for the Nth element. The unstable
topN could be applied to the copy to discover the Nth element, then the
stable partition function could finish the job with the correct pivot.
What do you all think? Do you agree with my definition of stable topN?
Do you know of a better algorithm/approach for implementing this function?
There's a notion of "semiStable" in std.algorithm that you may use for
further refining topN guarantees.
I'd say use semiStable for stability among the top N items (seeing as
those are the most interesting), and stable for stability of all items.
Andrei
