On Tuesday, 24 June 2014 at 16:03:26 UTC, Andrei Alexandrescu
wrote:
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
From what I know of partitioning algorithms, they're either
intrinsically stable or intrinsically unstable. Implementing an
algorithm with the attribute you described would likely come with
little benefit. I could be wrong, but this is my intuition.
