Stable topN?

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Tue Jun 24 09:03:27 PDT 2014


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


More information about the Digitalmars-d mailing list