## 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!

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

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

:

int median(int a){
return
a[a<a?a<a?a<a?a<a?a<a?a<a?2:4:a<a?1:3:a<a?a<a?3:4:a<a?1:2:a<a?a<a?a<a?1:3:a<a?0:4:a<a?a<a?1:4:a<a?0:3:a<a?a<a?a<a?a<a?3:4:a<a?1:2:a<a?a<a?2:4:a<a?1:3:a<a?a<a?a<a?1:2:a<a?0:4:a<a?a<a?1:4:a<a?0:2:a<a?a<a?a<a?a<a?a<a?2:0:a<a?4:1:a<a?a<a?4:0:a<a?2:1:a<a?a<a?a<a?3:1:a<a?4:2:a<a?a<a?2:1:a<a?4:3:a<a?a<a?a<a?a<a?3:0:a<a?4:1:a<a?a<a?4:0:a<a?3:1:a<a?a<a?a<a?2:1:a<a?4:3:a<a?a<a?3:1:a<a?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.) 

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