On 01/19/2016 09:26 PM, Timon Gehr wrote:
On 01/20/2016 02:20 AM, Andrei Alexandrescu wrote:
I've seldom have code write itself so beautifully. Which, of course,
means it needs to be destroyed.
https://github.com/D-Programming-Language/phobos/pull/3938 -- Andrei
This is not an implementation of the median of medians algorithm.
int[] bad(int n){
if(n<=5){ return iota(n).array; }
auto next=bad(n/5);
return next.map!(a=>[a-2,a-1,a,a+n,a+n+1]).join;
}
void main(){
import std.stdio;
auto a=bad(5^^10);
auto idx=medianOfMedians(a);
double notLarger=a.count!(x=>x<=a[idx])/(1.0*a.length);
writeln(notLarger); // 0.0100766
assert(notLarger>=0.3); // fail
}
The real algorithm works by computing an /exact/ median of the medians
and uses it as the pivot value for quickselect in order to compute the
precise median of the full array. In the given implementation, the
approximations accumulate with each recursive invocation and no constant
guarantees can be given on the percentile of the result.
Thanks. Urgh. So the approximate median part cannot be separated from
partitioning. It was suspiciously cute :o). Back to the drawing board.
-- Andrei
