topN using a heap

[Andrei Alexandrescu via Digitalmars-d]

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