topN using a heap

[Ilya via Digitalmars-d]

On Tuesday, 19 January 2016 at 00:02:08 UTC, Timon Gehr wrote:
> On 01/19/2016 12:55 AM, Ilya wrote:
>> On Monday, 18 January 2016 at 23:53:53 UTC, Timon Gehr wrote:
>>> On 01/19/2016 12:50 AM, Ilya wrote:
>>>> ...
>>>>
>>>> 1. Yes, probability of hitting the worst case repeatedly is 
>>>> is
>>>> practically zero. But RNGs do not change this probability.
>>>> 2. It is possible to build attack for our RNGs, because they 
>>>> are
>>>> Pseudo-RNGs.
>>>> --Ilya
>>>
>>> You also need to predict the seed. How do you do that?
>>
>> We can not use unpredictable seed (like system clock) in pure 
>> functions.
>> --Ilya
>
> Clearly. The point is, there already was an impure 
> implementation of topN whose expected linear running time is 
> still specified in the documentation. The current 
> implementation does not fulfill this bound.

There is already implementation with predictable seed. Proof: 
https://github.com/D-Programming-Language/phobos/blob/master/std/random.d#L1151 --Ilya