On Sunday, 17 January 2016 at 02:37:48 UTC, Timon Gehr wrote:
On 01/17/2016 03:09 AM, Andrei Alexandrescu wrote:
On 1/16/16 8:00 PM, Timon Gehr wrote:
The implementation falls back to topNHeap whenever k is
within the first
or last ~n/8 elements and therefore is Ω(n log n) on average.
Correct. The pedantic approach would be to only do that when k
is up to
log(n). -- Andrei
Ivan's analysis suggests that even something significantly
larger, like n/log(n)² might work as an upper bound for k.
I don't think that meeting the documented runtime bounds
amounts to pedantry. (Having linear average running time of
course does not even imply linear expected running time, as is
still written in the documentation.)
I'd suggest being able to switch between implementations.
Recall that, when sorting, we have SwapStrategy.stable which is,
well, stable, but additionally guarantees n log n with a larger
constant (MergeSort).
And we have SwapStrategy.unstable which uses Introsort, which, in
turn, has smaller constant on sane inputs.
Here, Andrei's suggestion is to also have two implementations,
let us call them TopNStrategy.quickSelect and TopNStrategy.heap.
The quickSelect one is O(n) on sane inputs but O(n^2) on an
artificial worst case.
The heap implementation is also O(n) when k is close to 0 or n,
but O(n log n) otherwise. What's important is that it is also
O(n log n) worst case.
The current proposal switches between strategies based on a
heuristic (k < n/8 or k > 7n/8 if I understand correctly), which
may not be the best strategy in all cases.
So, what can be done is to introduce TopNStrategy.auto which is
the default and uses the (current or better) heuristic to switch
between strategies, but also leave a way to explicitly select one
of the two strategies, just like one can do now with sort!(...,
SwapStrategy.whatWeExplicitlyWant).
All the code for both strategies is already there. Each strategy
has its benefits not covered by the other (quickSelect is faster
for k~n and sane inputs, heap is faster for k close to boundary
and special inputs). So, provide the default but let the user
choose.
Ivan Kazmenko.
