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 Thu, 23 Sep 2010 23:13:27 GMT
Le 23/09/2010 22:38, Ted Dunning a écrit :
> If you use the median of three or five randomly selected points, the worst
> case/average case distinction is not going to come up.  You could even use
> the first, middle, end and two randomly selected points if you get nutty
> about it.

I intended to use median of three as it is a classical strategy. Of
course, Musser's "median of three killer" is always possible, but we
could wait for users complaints before handling it ...

Luc

> 
> On Thu, Sep 23, 2010 at 11:57 AM, Luc Maisonobe <Luc.Maisonobe@free.fr>wrote:
> 
>> Partition-based algorithms are O(n) in expected time but not in worst
>> case time. If end users ask for it later, we could improve again by
>> adding the Musser's introselect that guarantees O(n) behavior even in
>> worst case.
>>
> 


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


Mime
View raw message