A few primitive algorithms got quite a bit quicker.

https://github.com/D-Programming-Language/phobos/pull/3921
https://github.com/D-Programming-Language/phobos/pull/3922

Destroy!

Andrei

On 01/12/2016 04:15 AM, Andrei Alexandrescu wrote:
> A few primitive algorithms got quite a bit quicker.
>
> https://github.com/D-Programming-Language/phobos/pull/3921
> https://github.com/D-Programming-Language/phobos/pull/3922
>
> Destroy!
>
> Andrei

Nice.

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

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



[1]:

int median(int[5] a){
    return a[a[0]<a[1]?a[2]<a[3]?a[0]<a[2]?a[1]<a[4]?a[1]<a[2]?a[2]<a[4]?2:4:a[1]<a[3]?1:3:a[2]<a[4]?a[3]<a[4]?3:4:a[1]<a[2]?1:2:a[3]<a[4]?a[0]<a[3]?a[1]<a[3]?1:3:a[0]<a[4]?0:4:a[0]<a[4]?a[1]<a[4]?1:4:a[0]<a[3]?0:3:a[0]<a[3]?a[1]<a[4]?a[1]<a[3]?a[3]<a[4]?3:4:a[1]<a[2]?1:2:a[3]<a[4]?a[2]<a[4]?2:4:a[1]<a[3]?1:3:a[2]<a[4]?a[0]<a[2]?a[1]<a[2]?1:2:a[0]<a[4]?0:4:a[0]<a[4]?a[1]<a[4]?1:4:a[0]<a[2]?0:2:a[2]<a[3]?a[0]<a[3]?a[2]<a[4]?a[0]<a[4]?a[0]<a[2]?2:0:a[1]<a[4]?4:1:a[0]<a[2]?a[0]<a[4]?4:0:a[1]<a[2]?2:1:a[1]<a[4]?a[3]<a[4]?a[1]<a[3]?3:1:a[2]<a[4]?4:2:a[1]<a[3]?a[1]<a[2]?2:1:a[3]<a[4]?4:3:a[0]<a[2]?a[3]<a[4]?a[0]<a[4]?a[0]<a[3]?3:0:a[1]<a[4]?4:1:a[0]<a[3]?a[0]<a[4]?4:0:a[1]<a[3]?3:1:a[1]<a[4]?a[2]<a[4]?a[1]<a[2]?2:1:a[3]<a[4]?4:3:a[1]<a[2]?a[1]<a[3]?3:1:a[2]<a[4]?4:2];
}

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

On Wednesday, 13 January 2016 at 03:38:45 UTC, Andrei Alexandrescu wrote:
> I tried a static rng but found out that pure functions call sort(). Overall I'm not that worried about attacks on sort().

So, sort() is still Introsort (O(n log n) worst case), but topN() can show quadratic performance?  Can a similar approach - fall back to just sorting in O(n log n) if we recurse too deep - be applied to topN() so that it is linear for sane inputs but O(n log n) in the worst case?

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