topN using a heap

[Timon Gehr via Digitalmars-d]

On 01/19/2016 12:39 AM, 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

https://en.wikipedia.org/wiki/Introselect