topN using a heap

[Ilya via Digitalmars-d]

On Monday, 18 January 2016 at 23:39:02 UTC, Andrei Alexandrescu 
wrote:
> On 1/18/16 6:18 PM, Ilya wrote:
>> On Monday, 18 January 2016 at 20:45:56 UTC, Ivan Kazmenko 
>> wrote:
>>> On Monday, 18 January 2016 at 12:00:10 UTC, Ivan Kazmenko 
>>> wrote:
>>>> Here goes the test which shows quadratic behavior for the 
>>>> new version:
>>>> http://dpaste.dzfl.pl/e4b3bc26c3cf
>>>> (dpaste kills the slow code before it completes the task)
>>>
>>> Correction: this is the result of removing a uniform call in 
>>> pull
>>> 3921.  Since we are supposed to discuss the improvements 
>>> related to
>>> pull 3934 here, I created a separate entry for the issue:
>>> https://issues.dlang.org/show_bug.cgi?id=15583.
>>
>> A RNGs don't improve worst case. It only changes an 
>> permutation for
>> worst case. --Ilya
>
> Well it does improve things. The probability of hitting the 
> worst case repeatedly is practically zero, and it's impossible 
> to create an attack input.
>
> I'm not sure whether we should worry about this. Probably we do 
> because sort attacks are a press favorite.
>
> The nice thing about not relying on randomness is that pure 
> functions can call sort, topN etc.
>
> As a sort of a compromise I was thinking of seeding the RNG 
> with not only the length of the range, but also the integral 
> representation of the address of the first element. This would 
> still allow an attack if the input is always at the same 
> address.
>
>
> Thoughts?
>
> Andrei

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