digitalmars.D - Today was a good day
- Andrei Alexandrescu (5/5) Jan 11 2016 A few primitive algorithms got quite a bit quicker.
- Timon Gehr (15/20) Jan 12 2016 Nice.
- Andrei Alexandrescu (5/13) Jan 12 2016 I tried a static rng but found out that pure functions call sort().
- Ivan Kazmenko (7/9) Jan 15 2016 So, sort() is still Introsort (O(n log n) worst case), but topN()
- Timon Gehr (4/13) Jan 16 2016 What I'm saying is that this implementation of topN does not satisfy the...
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 2016
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! AndreiNice. - 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 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
Jan 12 2016
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 2016
On 01/13/2016 04:38 AM, Andrei Alexandrescu wrote:On 01/12/2016 08:31 PM, Timon Gehr wrote: ...What I'm saying is that this implementation of topN does not satisfy the specification. The documentation and/or the implementation should be changed.- 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().
Jan 16 2016