Today was a good day
Timon Gehr via Digitalmars-d
digitalmars-d at puremagic.com
Sat Jan 16 07:57:19 PST 2016
On 01/13/2016 04:38 AM, Andrei Alexandrescu wrote:
> On 01/12/2016 08:31 PM, Timon Gehr wrote:
>> - 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().
What I'm saying is that this implementation of topN does not satisfy the
specification. The documentation and/or the implementation should be
More information about the Digitalmars-d