Re: [OT] Lower and upper median of 4

[Timon Gehr via Digitalmars-d]

On 26.11.2016 23:16, Timon Gehr wrote:
On 26.11.2016 22:36, Timon Gehr wrote:


Thanks! Sorry, I forgot to mention partitioning around the lower/upper
median is also needed. It seems that changes the tradeoff space. --
Andrei

Did you see the suggestion to make the leanLeft/leanRight cases
symmetric, such that both use at most 4 branches?

Code:

void medianOf(bool leanRight,T)(ref T[4] r, size_t a, size_t b, size_t
c, size_t d){
    assert(a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d);
    if(r[c]<r[a]) swap(r[a],r[c]);
    if(r[d]<r[b]) swap(r[b],r[d]);
    if(leanRight?r[d]<r[c]:r[b]<r[a]){
        swap(r[c],r[d]);
        swap(r[a],r[b]);
    }
    if(r[c]<r[b]) swap(r[b],r[c]);
    if(leanRight) assert(r[a]<=r[c]&&r[b]<=r[c]&&r[c]<=r[d]);
    else assert(r[a]<=r[b]&&r[b]<=r[c]&&r[b]<=r[d]);
}


Slightly larger code, but uses fewer swaps:

void medianOf(bool leanRight,T)(ref T[4] r, size_t a, size_t b, size_t 
c, size_t d){
    assert(a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d);
    if(r[c]<r[a]) swap(r[a],r[c]);
    if(r[d]<r[b]) swap(r[b],r[d]);
    static if(leanRight){
        if(r[d]<r[c]){
            swap(r[c],r[d]);
            if(r[c]<r[a]) swap(r[a],r[c]);
        }else if(r[c]<r[b]) swap(r[b],r[c]);
        assert(r[a]<=r[c]&&r[b]<=r[c]&&r[c]<=r[d]);
    }else{
        if(r[b]<r[a]){
            swap(r[a],r[b]);
            if(r[d]<r[b]) swap(r[b],r[d]);
        }else if(r[c]<r[b]) swap(r[b],r[c]);
        assert(r[a]<=r[b]&&r[b]<=r[c]&&r[b]<=r[d]);
    }
}

The best strategy is probably to exhaustively enumerate all 
Pareto-optimal algorithms and to benchmark them automatically within the 
larger algorithm.