www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Today was a good day

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jan 11
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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]; }
Jan 12
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jan 12
next sibling parent Ivan Kazmenko <gassa mail.ru> writes:
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?
Jan 15
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jan 16