commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <>
Subject Re: [math] speeding up percentile based statistics
Date Sat, 18 Sep 2010 19:05:55 GMT
Le 18/09/2010 20:43, Dimitri Pourbaix a écrit :
> Luc,
>>> On the other hand, the speed-up version would no longer
>>> be mathematically correct, as a rough approximate of the pivot would be
>>> adopted.
>> No, the exact pivot is used. Its evaluation is only delayed. It would be
>> correct.
> Given a **general** array, I do not think one can identify the median in
> just n iterations (i.e. reading the array only once).

It is possible using Blum, Floyd, Pratt, Rivest and Tarjan, or David R.
Musser introselect algorithm (which uses BFPRT under the hood). See
<> for the original paper
Unfortunately, despite the paper says another paper will be devoted to
introselect I did not find it and suspect it was never published. The
Blum, Floyd, Pratt, Rivest and Tarjan algorithm ensure linear worst-case
behaviour is depicted here:

I'm not sure it is *really* needed to go to these lengths and have a
guaranteed linear worst case behavior in commons-math. An average linear
behavior and worst-case O(n^2) may be sufficient in many cases.

Also starting with Hoare selction algorithm and adding BFPRT in a later
version is always possible as Musser's algorithm simply switch from
Hoare to BFPRT when it detects arrays splitting are not sufficiently


> Dim.
> ----------------------------------------------------------------------------
> Dimitri Pourbaix                         *
> Institut d'Astronomie et d'Astrophysique *      Don't worry, be happy
> CP 226, office 2.N4.211, building NO     *         and CARPE DIEM.
> Universite Libre de Bruxelles            *
> Boulevard du Triomphe                    *      Tel : +32-2-650.35.71
>  B-1050 Bruxelles                        *      Fax : +32-2-650.42.26
>     *
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message