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

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

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

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

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?

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.