topN using a heap

[Andrei Alexandrescu via Digitalmars-d]

On 09/21/2016 01:37 PM, Jon Degenhardt wrote:
> On Wednesday, 21 September 2016 at 14:58:27 UTC, Andrei Alexandrescu wrote:
>> On 9/21/16 4:16 AM, Jon Degenhardt wrote:
>>> 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.
>>
>> I have it on my list to move https://arxiv.org/abs/1606.00484 into
>> Phobos. Thanks for the data! -- Andrei
>
> Very good, thanks. It'll be interesting to see how this algorithm does
> on this data set.

Preliminary results indicate that QuickselectAdaptive is about 10x 
faster than sort, net of data reading overheads, on the second-field 
data set. I'll proceed with submitting the algorithm in Phobos. -- Andrei