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