topN using a heap

[Jon Degenhardt via Digitalmars-d]

On Tuesday, 19 January 2016 at 00:11:40 UTC, Andrei Alexandrescu 
wrote:
>
> So let me summarize what has happened:
>
> 1. topN was reportedly slow. It was using a random pivot. I 
> made it use getPivot (deterministic) instead of a random pivot 
> in https://github.com/D-Programming-Language/phobos/pull/3921. 
> getPivot is also what sort uses.
>
> [snip]
>
Not completely clear from this thread what the conclusion was wrt 
getting known topN performance issues addressed. From pull 
requests it appears identified fixes are in current release 
versions of the DMD/LDC. However, I hit significant issues on one 
of the first large data sets I tried. Not an artificial data, but 
one with very skewed distributions of values (a google ngram 
file).

Details here:  https://issues.dlang.org/show_bug.cgi?id=16517. 
Includes test program, url for the ngram file.

A brief summary - Data file is a TSV file with 3 numeric fields, 
a bit over 10 million values each with different distribution 
properties. Used both topN and sort get the median value. Since 
this was median, it topN for the mid-point value, not at one end 
or the other. (This is a specific callout for some of the issues 
identified.)

Timing comparison of sort and topN, times in milliseconds:

           sort      topN
Field 2:   289      1756
Field 3:   285    148793
Field 4:   273    668906

The above times are for LDC 1.1.0-beta2 (DMD 2.071.1). Similar 
behavior is seen for DMD 2.071.2. This makes topN pretty much 
unusable.