Today was a good day

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Tue Jan 12 19:38:45 PST 2016


On 01/12/2016 08:31 PM, Timon Gehr wrote:
> - This probably does not make a large difference, but one can find the
> median of five elements using only at most 6 comparisons. (And without
> moving the elements.) [1]

Moving the elements actually does help.

> - getPivot selects indices which depend deterministically on the range
> length. Therefore afaics it is now possible to create inputs that force
> quadratic runtime for topN. (E.g. an input can be crafted such that
> getPivot always picks the third-largest element in the range.) This
> violates the running time bound given in the documentation.

I tried a static rng but found out that pure functions call sort(). 
Overall I'm not that worried about attacks on sort().


Andrei


More information about the Digitalmars-d mailing list