Today was a good day

[Timon Gehr via Digitalmars-d]

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