topN using a heap

[Ivan Kazmenko 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:
>> 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.

Possible, but only if the seed and previous usage of victim 
program's global RNG are also known to the attacker... at which 
point the victim may well have a bigger problem than just 
quadratic topN.

> 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.

Is it feasible to have two overloads of sort and/or topN, one 
pure and the other with better complexity guarantees?

> 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.

Hmm.  Isn't using any pointers still breaking strong purity?  Say 
the GC moved our array, and it now has a different address.  A 
strongly pure function would order the elements exactly the same 
then.

The same goes about sorting, where the thing depending on pivot 
choice is the relative order of "equal" elements.

 From a theoretical standpoint (not taking current D purity rules 
into account), I'd say using a pointer (which may be modified by 
GC) is as pure as just allowing a static RNG (a global one, or 
even another instance dedicated specifically to sort/topN).

Ivan Kazmenko.