commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <Luc.Maison...@free.fr>
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
<http://www.cs.rpi.edu/~musser/gp/introsort.ps> 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:
<http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm>.

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

Luc


> 
> 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
> http://sb9.astro.ulb.ac.be/~pourbaix     * mailto:pourbaix@astro.ulb.ac.be
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
> 


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message