You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Luc Maisonobe <Lu...@free.fr> on 2010/09/17 19:34:51 UTC
[math] speeding up percentile based statistics
Hi all,
During a recent face to face discussion with some commons-math users
from a large project, it appeared one implementation choice for
Percentile statistics was a huge performance bottleneck.
When the Percentile.evaluate method is called, the sample array is
copied and sorted. In one use case, 100 calls were made for each sample,
so the same array was sorted 100 times. In another use case, only one
call is made (typically to compute the median) but the user wondered why
the array should be completely sorted. In fact, using a selection
algorithm instead of a sorting algorithm would be sufficient.
I would like to have you opinion about providing a different evaluate
method that would process an array provided previously and use only
selections to provide the percentile. Consider for example the following
input array:
[ -6, 8, 4, -5, 0, 2, 7 ]
If we first as for the median, a selection algorithm may reorganize the
array as:
[ -6, 0, -5, 2, 8, 4, 7 ]
were the left part is smaller than the central element, the right part
is larger and hence the central element 2 is known to be the median.
Then we ask for another value, the 25% percentile. Since the object
already knows the smaller elements are in the left part, it can use a
select algorithm on the 3 elements left part and extract the value -5
without even trying to sort the upper part of the array.
What do you think ?
Luc
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Ted Dunning <te...@gmail.com>.
No. I think I missed you point.
My comment about code complexity still applies somewhat. Storing the state
of the sort and testing the corner cases can be difficult.
On Fri, Sep 17, 2010 at 12:19 PM, Luc Maisonobe <Lu...@free.fr>wrote:
> > Moreover, since sort is n log n without a radix sort, then the
> > increment selection algorithm can only win if 100 < log n which is pretty
> > unlikely.*
>
> I don't understand. Partition-based selection algorithms are basically
> partition-based sort algorithm where we recurse in only one of the
> partition once the pivot has been chosen. Subsequent calls therefore
> don't restart from an array of size n but from smaller sub-arrays, has
> the pivot can be saved (at least the top level ones). If at the end the
> number of selections is so high the array ends up to be completely
> sorted, the total cost is probably not much higher than what an initial
> sort would have done. It will be higher since their are some bookkeeping
> to do, but not so much higher I think. Doing one call corresponds to
> resuming the partial sort from the state resulting from previous calls.
>
> Did I miss something ?
Re: [math] speeding up percentile based statistics
Posted by Ted Dunning <te...@gmail.com>.
I just meant that with the nearly correct estimates from the first pass you
could do a more accurate job in the second pass, possibly by partitions,
possibly by just applying the incremental algorithm a second time. Because
it would have good density estimates from the first pass, it would
presumably have better estimates of the sample quantiles the second time
around.
On Fri, Sep 17, 2010 at 12:19 PM, Luc Maisonobe <Lu...@free.fr>wrote:
> > *- use the on-line algorithm mentioned above with two passes, one to
> > estimate the quantiles of interest, a second to refine the estimate using
> > the actual data. This allows the multiple probe method to be linear in
> time
> > and should give you exact sample quantiles. It doesn't help the repeated
> > probe problem.*
>
> I'm not sure I understand well. However, the on-line method by itself
> would be an interesting addition. It would allow quantiles computation
> with the Storeless versions of our classes.
>
Re: [math] speeding up percentile based statistics
Posted by Leanne Guy <Le...@unige.ch>.
On 9/27/10 09:55 PM, luc.maisonobe@free.fr wrote:
> ----- "Gilles Sadowski"<gi...@harfang.homelinux.org> a écrit :
>
>>> [...]
>>>>> ---CUT---
>>>>> double[] a = new double[] {1, 2, 3};
>>>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>>>> Percentile pA = new Percentile(a);
>>>>> Percentile pB = new Percentile(b);
>>>>>
>>>>> double r;
>>>>> r = pA.evaluate(50);
>>>>> r = pB.evaluate(50);
>>>>> r = pA.evaluate(50);
>>>>> r = pB.evaluate(50);
>>>>> ---CUT---
>>>>>
>>>>> That way, later calls can benefit from whatever preprocessing was
>> done in
>>>>> previous calls.
>>>>> The instance will always control all the information needed (e.g.
>> after a
>>>>> call to an "addValues" method) for the processing without the
>> need to rely
>>>>> on the user for calling "clearCache" whenever necessary.
>>>>>
>>>>>
>>>>> Gilles
>>>> +1
>>>> I think that is a really good idea and I agree on the points
>> made.
>>> This proposal is point 4. It breaks the UnivariateStatistic API and
>> it
>>> breaks what the user found interesting in this API, i.e. have a
>> general
>>> statistics framework where one statistic can be replaced by another
>> one.
>>> If you read again one of my earlier messages from today, we will
>> combine
>>> this method (i.e. evaluate without values) and the
>> UnivariateStatistics API.
>>> Perhaps we could add these new methods (i.e. addValues and evaluate
>>> without values) to UnivariateStatistics, but this can only be done
>> on 3.0.
>>
>> +1
>>
>> Is it urgent to complicate the code? If the API conflicts with a
>> necessary
>> efficiency improvement, why not postpone the change?
> I was trying to help Leanne as 3.0 is not going to be ready soon.
> I'm OK with a change in 3.0 as pushing these methods up to the interface is really the best solution.
>
Thanks Luc for your efforts to help. I'm of course still very interested
in seeing these changes
but I can wait until 3.0 so that the best solution can be implemented
Leanne
--
-----------------------------------------------------------------------
Leanne Guy
Variability Processing Group, Gaia Project, ESA
Observatoire de Geneve / ISDC Astrophysics Data Centre
Chemin d'Ecogia 16, CH-1290 Versoix, Switzerland
Email: leanne.guy-at-unige.ch
Tel: +41 22 379 2151 Fax: +41 (0)22 37 92 135
WWW: http://isdc.unige.ch/~leanne/ Skype: leanneobsge
-----------------------------------------------------------------------
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by lu...@free.fr.
----- "Gilles Sadowski" <gi...@harfang.homelinux.org> a écrit :
> > [...]
> > >>
> > >> ---CUT---
> > >> double[] a = new double[] {1, 2, 3};
> > >> double[] b = new double[] {1, 2, 3, 4, 5};
> > >> Percentile pA = new Percentile(a);
> > >> Percentile pB = new Percentile(b);
> > >>
> > >> double r;
> > >> r = pA.evaluate(50);
> > >> r = pB.evaluate(50);
> > >> r = pA.evaluate(50);
> > >> r = pB.evaluate(50);
> > >> ---CUT---
> > >>
> > >> That way, later calls can benefit from whatever preprocessing was
> done in
> > >> previous calls.
> > >> The instance will always control all the information needed (e.g.
> after a
> > >> call to an "addValues" method) for the processing without the
> need to rely
> > >> on the user for calling "clearCache" whenever necessary.
> > >>
> > >>
> > >> Gilles
> > >
> > > +1
> > > I think that is a really good idea and I agree on the points
> made.
> >
> > This proposal is point 4. It breaks the UnivariateStatistic API and
> it
> > breaks what the user found interesting in this API, i.e. have a
> general
> > statistics framework where one statistic can be replaced by another
> one.
> >
> > If you read again one of my earlier messages from today, we will
> combine
> > this method (i.e. evaluate without values) and the
> UnivariateStatistics API.
> >
> > Perhaps we could add these new methods (i.e. addValues and evaluate
> > without values) to UnivariateStatistics, but this can only be done
> on 3.0.
>
> +1
>
> Is it urgent to complicate the code? If the API conflicts with a
> necessary
> efficiency improvement, why not postpone the change?
I was trying to help Leanne as 3.0 is not going to be ready soon.
I'm OK with a change in 3.0 as pushing these methods up to the interface is really the best solution.
Luc
>
>
> Gilles
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
> [...]
> >>
> >> ---CUT---
> >> double[] a = new double[] {1, 2, 3};
> >> double[] b = new double[] {1, 2, 3, 4, 5};
> >> Percentile pA = new Percentile(a);
> >> Percentile pB = new Percentile(b);
> >>
> >> double r;
> >> r = pA.evaluate(50);
> >> r = pB.evaluate(50);
> >> r = pA.evaluate(50);
> >> r = pB.evaluate(50);
> >> ---CUT---
> >>
> >> That way, later calls can benefit from whatever preprocessing was done in
> >> previous calls.
> >> The instance will always control all the information needed (e.g. after a
> >> call to an "addValues" method) for the processing without the need to rely
> >> on the user for calling "clearCache" whenever necessary.
> >>
> >>
> >> Gilles
> >
> > +1
> > I think that is a really good idea and I agree on the points made.
>
> This proposal is point 4. It breaks the UnivariateStatistic API and it
> breaks what the user found interesting in this API, i.e. have a general
> statistics framework where one statistic can be replaced by another one.
>
> If you read again one of my earlier messages from today, we will combine
> this method (i.e. evaluate without values) and the UnivariateStatistics API.
>
> Perhaps we could add these new methods (i.e. addValues and evaluate
> without values) to UnivariateStatistics, but this can only be done on 3.0.
+1
Is it urgent to complicate the code? If the API conflicts with a necessary
efficiency improvement, why not postpone the change?
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Phil Steitz <ph...@gmail.com>.
On 9/26/10 1:27 PM, Mikkel Meyer Andersen wrote:
> 2010/9/26 Gilles Sadowski<gi...@harfang.homelinux.org>:
>>> [...]
>>>
>>> 1) do nothing to check the array is the same between calls and blindly
>>> assumes it IS the same. Users would really need to call clearCache
>>> when they provide a new array
>>> pros: very simple
>>> cons: error-prone for the user as it relies only on reading and
>>> understanding a documentation that would change with new version
>>>
>>> 2) check only array reference equality (with ==) to check the array
>>> is the same as the previous call or not. Users would need to call
>>> clearCache only if they use the same array but have changed its
>>> content.
>>> pros: trade-off between efficiency and reliability,
>>> handles most cases properly
>>> cons: may be wrong in corner cases
>>>
>>> 3) check array content using an hash code. Users would generally don't
>>> need to call clearCache at all so it would not be provided
>>> pros: works in all cases
>>> cons: add linear cost for array checking
>>>
>>> 4) remove the double[] values parameter from the API and use a separate
>>> addValues method, hence the class will reset its cache only when
>>> addValues is called
>>> pros: works in all cases
>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>
>>> My preference is choice 2.
>>>
>>> What do you think ?
>>
>> IIUC, the interface method ("evaluate") was designed around the assumption
>> that successive calls are independent: the array argument is not
>> encapsulated for further processing (e.g. caching).
>> IMO, the equality check and the "clearCache" method look like workarounds,
>> not a clean solution.
>> As an example, what if a user calls "evaluate" several times alternating on
>> two different arrays:
>>
>> ---CUT---
>> double[] a = new double[] {1, 2, 3};
>> double[] b = new double[] {1, 2, 3, 4, 5};
>> Percentile p = new Percentile();
>>
>> dourble r;
>> r = p.evaluate(a, 50);
>> r = p.evaluate(b, 50);
>> r = p.evaluate(a, 50);
>> r = p.evaluate(b, 50);
>>
>> // etc.
>> ---CUT---
>>
>> Doesn't this kind of use-case nullify the expected optimization?
>>
>> If the array is going to be reused, the user call should reflect that fact;
>> e.g. by passing the array in a constructor:
>>
>> ---CUT---
>> double[] a = new double[] {1, 2, 3};
>> double[] b = new double[] {1, 2, 3, 4, 5};
>> Percentile pA = new Percentile(a);
>> Percentile pB = new Percentile(b);
>>
>> double r;
>> r = pA.evaluate(50);
>> r = pB.evaluate(50);
>> r = pA.evaluate(50);
>> r = pB.evaluate(50);
>> ---CUT---
>>
>> That way, later calls can benefit from whatever preprocessing was done in
>> previous calls.
>> The instance will always control all the information needed (e.g. after a
>> call to an "addValues" method) for the processing without the need to rely
>> on the user for calling "clearCache" whenever necessary.
>>
>>
>> Gilles
>
> +1
> I think that is a really good idea and I agree on the points made.
>
Sorry, I missed Gilles response before responding myself with pretty
similar feedback. I like the constructor argument idea as well.
Phil
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Phil Steitz <ph...@gmail.com>.
On 10/3/10 3:55 PM, Luc Maisonobe wrote:
> Le 26/09/2010 21:34, Luc Maisonobe a écrit :
>> Le 26/09/2010 21:05, Phil Steitz a écrit :
>>> On 9/26/10 2:30 PM, Luc Maisonobe wrote:
>>>> Le 26/09/2010 19:27, Mikkel Meyer Andersen a écrit :
>>>>> 2010/9/26 Gilles Sadowski<gi...@harfang.homelinux.org>:
>>>>>>> [...]
>>>>>>>
>>>>>>> 1) do nothing to check the array is the same between calls and
>>>>>>> blindly
>>>>>>> assumes it IS the same. Users would really need to call
>>>>>>> clearCache
>>>>>>> when they provide a new array
>>>>>>> pros: very simple
>>>>>>> cons: error-prone for the user as it relies only on reading and
>>>>>>> understanding a documentation that would change with new version
>>>>>>>
>>>>>>> 2) check only array reference equality (with ==) to check the array
>>>>>>> is the same as the previous call or not. Users would need to call
>>>>>>> clearCache only if they use the same array but have changed its
>>>>>>> content.
>>>>>>> pros: trade-off between efficiency and reliability,
>>>>>>> handles most cases properly
>>>>>>> cons: may be wrong in corner cases
>>>>>>>
>>>>>>> 3) check array content using an hash code. Users would generally
>>>>>>> don't
>>>>>>> need to call clearCache at all so it would not be provided
>>>>>>> pros: works in all cases
>>>>>>> cons: add linear cost for array checking
>>>>>>>
>>>>>>> 4) remove the double[] values parameter from the API and use a
>>>>>>> separate
>>>>>>> addValues method, hence the class will reset its cache only when
>>>>>>> addValues is called
>>>>>>> pros: works in all cases
>>>>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>>>>
>>>>>>> My preference is choice 2.
>>>>>>>
>>>>>>> What do you think ?
>>>>>>
>>>>>> IIUC, the interface method ("evaluate") was designed around the
>>>>>> assumption
>>>>>> that successive calls are independent: the array argument is not
>>>>>> encapsulated for further processing (e.g. caching).
>>>>>> IMO, the equality check and the "clearCache" method look like
>>>>>> workarounds,
>>>>>> not a clean solution.
>>>>>> As an example, what if a user calls "evaluate" several times
>>>>>> alternating on
>>>>>> two different arrays:
>>>>>>
>>>>>> ---CUT---
>>>>>> double[] a = new double[] {1, 2, 3};
>>>>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>>>>> Percentile p = new Percentile();
>>>>>>
>>>>>> dourble r;
>>>>>> r = p.evaluate(a, 50);
>>>>>> r = p.evaluate(b, 50);
>>>>>> r = p.evaluate(a, 50);
>>>>>> r = p.evaluate(b, 50);
>>>>>>
>>>>>> // etc.
>>>>>> ---CUT---
>>>>>>
>>>>>> Doesn't this kind of use-case nullify the expected optimization?
>>>>>>
>>>>>> If the array is going to be reused, the user call should reflect
>>>>>> that fact;
>>>>>> e.g. by passing the array in a constructor:
>>>>>>
>>>>>> ---CUT---
>>>>>> double[] a = new double[] {1, 2, 3};
>>>>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>>>>> Percentile pA = new Percentile(a);
>>>>>> Percentile pB = new Percentile(b);
>>>>>>
>>>>>> double r;
>>>>>> r = pA.evaluate(50);
>>>>>> r = pB.evaluate(50);
>>>>>> r = pA.evaluate(50);
>>>>>> r = pB.evaluate(50);
>>>>>> ---CUT---
>>>>>>
>>>>>> That way, later calls can benefit from whatever preprocessing was
>>>>>> done in
>>>>>> previous calls.
>>>>>> The instance will always control all the information needed (e.g.
>>>>>> after a
>>>>>> call to an "addValues" method) for the processing without the need
>>>>>> to rely
>>>>>> on the user for calling "clearCache" whenever necessary.
>>>>>>
>>>>>>
>>>>>> Gilles
>>>>>
>>>>> +1
>>>>> I think that is a really good idea and I agree on the points made.
>>>>
>>>> This proposal is point 4. It breaks the UnivariateStatistic API and it
>>>> breaks what the user found interesting in this API, i.e. have a general
>>>> statistics framework where one statistic can be replaced by another one.
>>>>
>>>> If you read again one of my earlier messages from today, we will combine
>>>> this method (i.e. evaluate without values) and the
>>>> UnivariateStatistics API.
>>>>
>>>> Perhaps we could add these new methods (i.e. addValues and evaluate
>>>> without values) to UnivariateStatistics, but this can only be done on
>>>> 3.0.
>>>>
>>>
>>> We could add to AbstractUnivariateStatistics in 2.x and update the
>>> interface in 3.0, if we can work out and agree on the setData() idea in
>>> my last post. While only some statistics can benefit internally from
>>> caching, I think the setData idea is consistent with
>>> UnivariateStatistics, as this is the interface for stats that require
>>> the full set of data to be stored in memory.
>
> I am trying to set up the setData(double[] values) and setData(double[]
> values, int begin, int length) methods at AbstractUnivariateStatistics
> level. This adds a field to the abstract class, and this field must be
> copied by the various copy methods since it belongs to the instance
> state. Each statistic implements two copy method, an instance method
> which create a new instance and is declared by the top level
> UnivariateStatistics interface and a static one that overwrite an
> existing instance. They are all implemented by similar code, as shonw
> here for the Percentile case:
>
> public Percentile copy() {
> Percentile result = new Percentile();
> copy(this, result);
> return result;
> }
>
> public static void copy(Percentile source, Percentile dest) {
> dest.quantile = source.quantile;
> }
>
> How can I implement simply all these methods and make sure the stored
> data array in the abstract base class is copied too ?
>
> One method would be to add a static copy at abstract class level and
> change the static methods at class hierarchy leaf call this method. For
> Percentile, this would mean:
>
> public static void copy(Percentile source, Percentile dest) {
> AbstractUnivariateStatistics.copy(source, dest);
> dest.quantile = source.quantile;
> }
>
> I don't like this method much, it is too easy to forget calling the base
> class copy part. Preserving the static copy methods is important and if
> theses static methods work well, neither the instance copy methods nor
> the copy constructors need to be changed.
>
> So despite I don't like adding a static
> AbstractUnivariateStatistics.copy method, I think I will be forced to do it.
>
> Does anybody have a better solution ?
I don't know if this is any better, but it seems to me that you are
in any case going to need a getData method (unless the new data
field is protected), so you could provide a default impl of setData
and getData in AbstractUnivariateStatistics and then just use these
directly in copy
public static void copy(Percentile source, Percentile dest) {
dest.setData(source.getData());
dest.quantile = source.quantile;
}
I guess the first line above is your
AbstractUnivariateStatistics.copy method, so this is really no
different.
We do want to keep the copy stuff working. Maybe someone else has a
better idea...
Phil
>
> Luc
>
>>
>> This is fine for me.
>>
>> Luc
>>
>>>
>>> Phil
>>>> Luc
>>>>
>>>>>
>>>>> ---------------------------------------------------------------------
>>>>> 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
>>>>
>>>
>>>
>>> ---------------------------------------------------------------------
>>> 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
>>
>>
>
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 26/09/2010 21:34, Luc Maisonobe a écrit :
> Le 26/09/2010 21:05, Phil Steitz a écrit :
>> On 9/26/10 2:30 PM, Luc Maisonobe wrote:
>>> Le 26/09/2010 19:27, Mikkel Meyer Andersen a écrit :
>>>> 2010/9/26 Gilles Sadowski<gi...@harfang.homelinux.org>:
>>>>>> [...]
>>>>>>
>>>>>> 1) do nothing to check the array is the same between calls and
>>>>>> blindly
>>>>>> assumes it IS the same. Users would really need to call
>>>>>> clearCache
>>>>>> when they provide a new array
>>>>>> pros: very simple
>>>>>> cons: error-prone for the user as it relies only on reading and
>>>>>> understanding a documentation that would change with new version
>>>>>>
>>>>>> 2) check only array reference equality (with ==) to check the array
>>>>>> is the same as the previous call or not. Users would need to call
>>>>>> clearCache only if they use the same array but have changed its
>>>>>> content.
>>>>>> pros: trade-off between efficiency and reliability,
>>>>>> handles most cases properly
>>>>>> cons: may be wrong in corner cases
>>>>>>
>>>>>> 3) check array content using an hash code. Users would generally
>>>>>> don't
>>>>>> need to call clearCache at all so it would not be provided
>>>>>> pros: works in all cases
>>>>>> cons: add linear cost for array checking
>>>>>>
>>>>>> 4) remove the double[] values parameter from the API and use a
>>>>>> separate
>>>>>> addValues method, hence the class will reset its cache only when
>>>>>> addValues is called
>>>>>> pros: works in all cases
>>>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>>>
>>>>>> My preference is choice 2.
>>>>>>
>>>>>> What do you think ?
>>>>>
>>>>> IIUC, the interface method ("evaluate") was designed around the
>>>>> assumption
>>>>> that successive calls are independent: the array argument is not
>>>>> encapsulated for further processing (e.g. caching).
>>>>> IMO, the equality check and the "clearCache" method look like
>>>>> workarounds,
>>>>> not a clean solution.
>>>>> As an example, what if a user calls "evaluate" several times
>>>>> alternating on
>>>>> two different arrays:
>>>>>
>>>>> ---CUT---
>>>>> double[] a = new double[] {1, 2, 3};
>>>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>>>> Percentile p = new Percentile();
>>>>>
>>>>> dourble r;
>>>>> r = p.evaluate(a, 50);
>>>>> r = p.evaluate(b, 50);
>>>>> r = p.evaluate(a, 50);
>>>>> r = p.evaluate(b, 50);
>>>>>
>>>>> // etc.
>>>>> ---CUT---
>>>>>
>>>>> Doesn't this kind of use-case nullify the expected optimization?
>>>>>
>>>>> If the array is going to be reused, the user call should reflect
>>>>> that fact;
>>>>> e.g. by passing the array in a constructor:
>>>>>
>>>>> ---CUT---
>>>>> double[] a = new double[] {1, 2, 3};
>>>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>>>> Percentile pA = new Percentile(a);
>>>>> Percentile pB = new Percentile(b);
>>>>>
>>>>> double r;
>>>>> r = pA.evaluate(50);
>>>>> r = pB.evaluate(50);
>>>>> r = pA.evaluate(50);
>>>>> r = pB.evaluate(50);
>>>>> ---CUT---
>>>>>
>>>>> That way, later calls can benefit from whatever preprocessing was
>>>>> done in
>>>>> previous calls.
>>>>> The instance will always control all the information needed (e.g.
>>>>> after a
>>>>> call to an "addValues" method) for the processing without the need
>>>>> to rely
>>>>> on the user for calling "clearCache" whenever necessary.
>>>>>
>>>>>
>>>>> Gilles
>>>>
>>>> +1
>>>> I think that is a really good idea and I agree on the points made.
>>>
>>> This proposal is point 4. It breaks the UnivariateStatistic API and it
>>> breaks what the user found interesting in this API, i.e. have a general
>>> statistics framework where one statistic can be replaced by another one.
>>>
>>> If you read again one of my earlier messages from today, we will combine
>>> this method (i.e. evaluate without values) and the
>>> UnivariateStatistics API.
>>>
>>> Perhaps we could add these new methods (i.e. addValues and evaluate
>>> without values) to UnivariateStatistics, but this can only be done on
>>> 3.0.
>>>
>>
>> We could add to AbstractUnivariateStatistics in 2.x and update the
>> interface in 3.0, if we can work out and agree on the setData() idea in
>> my last post. While only some statistics can benefit internally from
>> caching, I think the setData idea is consistent with
>> UnivariateStatistics, as this is the interface for stats that require
>> the full set of data to be stored in memory.
I am trying to set up the setData(double[] values) and setData(double[]
values, int begin, int length) methods at AbstractUnivariateStatistics
level. This adds a field to the abstract class, and this field must be
copied by the various copy methods since it belongs to the instance
state. Each statistic implements two copy method, an instance method
which create a new instance and is declared by the top level
UnivariateStatistics interface and a static one that overwrite an
existing instance. They are all implemented by similar code, as shonw
here for the Percentile case:
public Percentile copy() {
Percentile result = new Percentile();
copy(this, result);
return result;
}
public static void copy(Percentile source, Percentile dest) {
dest.quantile = source.quantile;
}
How can I implement simply all these methods and make sure the stored
data array in the abstract base class is copied too ?
One method would be to add a static copy at abstract class level and
change the static methods at class hierarchy leaf call this method. For
Percentile, this would mean:
public static void copy(Percentile source, Percentile dest) {
AbstractUnivariateStatistics.copy(source, dest);
dest.quantile = source.quantile;
}
I don't like this method much, it is too easy to forget calling the base
class copy part. Preserving the static copy methods is important and if
theses static methods work well, neither the instance copy methods nor
the copy constructors need to be changed.
So despite I don't like adding a static
AbstractUnivariateStatistics.copy method, I think I will be forced to do it.
Does anybody have a better solution ?
Luc
>
> This is fine for me.
>
> Luc
>
>>
>> Phil
>>> Luc
>>>
>>>>
>>>> ---------------------------------------------------------------------
>>>> 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
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 26/09/2010 21:05, Phil Steitz a écrit :
> On 9/26/10 2:30 PM, Luc Maisonobe wrote:
>> Le 26/09/2010 19:27, Mikkel Meyer Andersen a écrit :
>>> 2010/9/26 Gilles Sadowski<gi...@harfang.homelinux.org>:
>>>>> [...]
>>>>>
>>>>> 1) do nothing to check the array is the same between calls and
>>>>> blindly
>>>>> assumes it IS the same. Users would really need to call
>>>>> clearCache
>>>>> when they provide a new array
>>>>> pros: very simple
>>>>> cons: error-prone for the user as it relies only on reading and
>>>>> understanding a documentation that would change with new version
>>>>>
>>>>> 2) check only array reference equality (with ==) to check the array
>>>>> is the same as the previous call or not. Users would need to call
>>>>> clearCache only if they use the same array but have changed its
>>>>> content.
>>>>> pros: trade-off between efficiency and reliability,
>>>>> handles most cases properly
>>>>> cons: may be wrong in corner cases
>>>>>
>>>>> 3) check array content using an hash code. Users would generally
>>>>> don't
>>>>> need to call clearCache at all so it would not be provided
>>>>> pros: works in all cases
>>>>> cons: add linear cost for array checking
>>>>>
>>>>> 4) remove the double[] values parameter from the API and use a
>>>>> separate
>>>>> addValues method, hence the class will reset its cache only when
>>>>> addValues is called
>>>>> pros: works in all cases
>>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>>
>>>>> My preference is choice 2.
>>>>>
>>>>> What do you think ?
>>>>
>>>> IIUC, the interface method ("evaluate") was designed around the
>>>> assumption
>>>> that successive calls are independent: the array argument is not
>>>> encapsulated for further processing (e.g. caching).
>>>> IMO, the equality check and the "clearCache" method look like
>>>> workarounds,
>>>> not a clean solution.
>>>> As an example, what if a user calls "evaluate" several times
>>>> alternating on
>>>> two different arrays:
>>>>
>>>> ---CUT---
>>>> double[] a = new double[] {1, 2, 3};
>>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>>> Percentile p = new Percentile();
>>>>
>>>> dourble r;
>>>> r = p.evaluate(a, 50);
>>>> r = p.evaluate(b, 50);
>>>> r = p.evaluate(a, 50);
>>>> r = p.evaluate(b, 50);
>>>>
>>>> // etc.
>>>> ---CUT---
>>>>
>>>> Doesn't this kind of use-case nullify the expected optimization?
>>>>
>>>> If the array is going to be reused, the user call should reflect
>>>> that fact;
>>>> e.g. by passing the array in a constructor:
>>>>
>>>> ---CUT---
>>>> double[] a = new double[] {1, 2, 3};
>>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>>> Percentile pA = new Percentile(a);
>>>> Percentile pB = new Percentile(b);
>>>>
>>>> double r;
>>>> r = pA.evaluate(50);
>>>> r = pB.evaluate(50);
>>>> r = pA.evaluate(50);
>>>> r = pB.evaluate(50);
>>>> ---CUT---
>>>>
>>>> That way, later calls can benefit from whatever preprocessing was
>>>> done in
>>>> previous calls.
>>>> The instance will always control all the information needed (e.g.
>>>> after a
>>>> call to an "addValues" method) for the processing without the need
>>>> to rely
>>>> on the user for calling "clearCache" whenever necessary.
>>>>
>>>>
>>>> Gilles
>>>
>>> +1
>>> I think that is a really good idea and I agree on the points made.
>>
>> This proposal is point 4. It breaks the UnivariateStatistic API and it
>> breaks what the user found interesting in this API, i.e. have a general
>> statistics framework where one statistic can be replaced by another one.
>>
>> If you read again one of my earlier messages from today, we will combine
>> this method (i.e. evaluate without values) and the
>> UnivariateStatistics API.
>>
>> Perhaps we could add these new methods (i.e. addValues and evaluate
>> without values) to UnivariateStatistics, but this can only be done on
>> 3.0.
>>
>
> We could add to AbstractUnivariateStatistics in 2.x and update the
> interface in 3.0, if we can work out and agree on the setData() idea in
> my last post. While only some statistics can benefit internally from
> caching, I think the setData idea is consistent with
> UnivariateStatistics, as this is the interface for stats that require
> the full set of data to be stored in memory.
This is fine for me.
Luc
>
> Phil
>> Luc
>>
>>>
>>> ---------------------------------------------------------------------
>>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Phil Steitz <ph...@gmail.com>.
On 9/26/10 2:30 PM, Luc Maisonobe wrote:
> Le 26/09/2010 19:27, Mikkel Meyer Andersen a écrit :
>> 2010/9/26 Gilles Sadowski<gi...@harfang.homelinux.org>:
>>>> [...]
>>>>
>>>> 1) do nothing to check the array is the same between calls and blindly
>>>> assumes it IS the same. Users would really need to call clearCache
>>>> when they provide a new array
>>>> pros: very simple
>>>> cons: error-prone for the user as it relies only on reading and
>>>> understanding a documentation that would change with new version
>>>>
>>>> 2) check only array reference equality (with ==) to check the array
>>>> is the same as the previous call or not. Users would need to call
>>>> clearCache only if they use the same array but have changed its
>>>> content.
>>>> pros: trade-off between efficiency and reliability,
>>>> handles most cases properly
>>>> cons: may be wrong in corner cases
>>>>
>>>> 3) check array content using an hash code. Users would generally don't
>>>> need to call clearCache at all so it would not be provided
>>>> pros: works in all cases
>>>> cons: add linear cost for array checking
>>>>
>>>> 4) remove the double[] values parameter from the API and use a separate
>>>> addValues method, hence the class will reset its cache only when
>>>> addValues is called
>>>> pros: works in all cases
>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>
>>>> My preference is choice 2.
>>>>
>>>> What do you think ?
>>>
>>> IIUC, the interface method ("evaluate") was designed around the assumption
>>> that successive calls are independent: the array argument is not
>>> encapsulated for further processing (e.g. caching).
>>> IMO, the equality check and the "clearCache" method look like workarounds,
>>> not a clean solution.
>>> As an example, what if a user calls "evaluate" several times alternating on
>>> two different arrays:
>>>
>>> ---CUT---
>>> double[] a = new double[] {1, 2, 3};
>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>> Percentile p = new Percentile();
>>>
>>> dourble r;
>>> r = p.evaluate(a, 50);
>>> r = p.evaluate(b, 50);
>>> r = p.evaluate(a, 50);
>>> r = p.evaluate(b, 50);
>>>
>>> // etc.
>>> ---CUT---
>>>
>>> Doesn't this kind of use-case nullify the expected optimization?
>>>
>>> If the array is going to be reused, the user call should reflect that fact;
>>> e.g. by passing the array in a constructor:
>>>
>>> ---CUT---
>>> double[] a = new double[] {1, 2, 3};
>>> double[] b = new double[] {1, 2, 3, 4, 5};
>>> Percentile pA = new Percentile(a);
>>> Percentile pB = new Percentile(b);
>>>
>>> double r;
>>> r = pA.evaluate(50);
>>> r = pB.evaluate(50);
>>> r = pA.evaluate(50);
>>> r = pB.evaluate(50);
>>> ---CUT---
>>>
>>> That way, later calls can benefit from whatever preprocessing was done in
>>> previous calls.
>>> The instance will always control all the information needed (e.g. after a
>>> call to an "addValues" method) for the processing without the need to rely
>>> on the user for calling "clearCache" whenever necessary.
>>>
>>>
>>> Gilles
>>
>> +1
>> I think that is a really good idea and I agree on the points made.
>
> This proposal is point 4. It breaks the UnivariateStatistic API and it
> breaks what the user found interesting in this API, i.e. have a general
> statistics framework where one statistic can be replaced by another one.
>
> If you read again one of my earlier messages from today, we will combine
> this method (i.e. evaluate without values) and the UnivariateStatistics API.
>
> Perhaps we could add these new methods (i.e. addValues and evaluate
> without values) to UnivariateStatistics, but this can only be done on 3.0.
>
We could add to AbstractUnivariateStatistics in 2.x and update the
interface in 3.0, if we can work out and agree on the setData() idea
in my last post. While only some statistics can benefit internally
from caching, I think the setData idea is consistent with
UnivariateStatistics, as this is the interface for stats that
require the full set of data to be stored in memory.
Phil
> Luc
>
>>
>> ---------------------------------------------------------------------
>> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 26/09/2010 19:27, Mikkel Meyer Andersen a écrit :
> 2010/9/26 Gilles Sadowski <gi...@harfang.homelinux.org>:
>>> [...]
>>>
>>> 1) do nothing to check the array is the same between calls and blindly
>>> assumes it IS the same. Users would really need to call clearCache
>>> when they provide a new array
>>> pros: very simple
>>> cons: error-prone for the user as it relies only on reading and
>>> understanding a documentation that would change with new version
>>>
>>> 2) check only array reference equality (with ==) to check the array
>>> is the same as the previous call or not. Users would need to call
>>> clearCache only if they use the same array but have changed its
>>> content.
>>> pros: trade-off between efficiency and reliability,
>>> handles most cases properly
>>> cons: may be wrong in corner cases
>>>
>>> 3) check array content using an hash code. Users would generally don't
>>> need to call clearCache at all so it would not be provided
>>> pros: works in all cases
>>> cons: add linear cost for array checking
>>>
>>> 4) remove the double[] values parameter from the API and use a separate
>>> addValues method, hence the class will reset its cache only when
>>> addValues is called
>>> pros: works in all cases
>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>
>>> My preference is choice 2.
>>>
>>> What do you think ?
>>
>> IIUC, the interface method ("evaluate") was designed around the assumption
>> that successive calls are independent: the array argument is not
>> encapsulated for further processing (e.g. caching).
>> IMO, the equality check and the "clearCache" method look like workarounds,
>> not a clean solution.
>> As an example, what if a user calls "evaluate" several times alternating on
>> two different arrays:
>>
>> ---CUT---
>> double[] a = new double[] {1, 2, 3};
>> double[] b = new double[] {1, 2, 3, 4, 5};
>> Percentile p = new Percentile();
>>
>> dourble r;
>> r = p.evaluate(a, 50);
>> r = p.evaluate(b, 50);
>> r = p.evaluate(a, 50);
>> r = p.evaluate(b, 50);
>>
>> // etc.
>> ---CUT---
>>
>> Doesn't this kind of use-case nullify the expected optimization?
>>
>> If the array is going to be reused, the user call should reflect that fact;
>> e.g. by passing the array in a constructor:
>>
>> ---CUT---
>> double[] a = new double[] {1, 2, 3};
>> double[] b = new double[] {1, 2, 3, 4, 5};
>> Percentile pA = new Percentile(a);
>> Percentile pB = new Percentile(b);
>>
>> double r;
>> r = pA.evaluate(50);
>> r = pB.evaluate(50);
>> r = pA.evaluate(50);
>> r = pB.evaluate(50);
>> ---CUT---
>>
>> That way, later calls can benefit from whatever preprocessing was done in
>> previous calls.
>> The instance will always control all the information needed (e.g. after a
>> call to an "addValues" method) for the processing without the need to rely
>> on the user for calling "clearCache" whenever necessary.
>>
>>
>> Gilles
>
> +1
> I think that is a really good idea and I agree on the points made.
This proposal is point 4. It breaks the UnivariateStatistic API and it
breaks what the user found interesting in this API, i.e. have a general
statistics framework where one statistic can be replaced by another one.
If you read again one of my earlier messages from today, we will combine
this method (i.e. evaluate without values) and the UnivariateStatistics API.
Perhaps we could add these new methods (i.e. addValues and evaluate
without values) to UnivariateStatistics, but this can only be done on 3.0.
Luc
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Mikkel Meyer Andersen <mi...@mikl.dk>.
2010/9/26 Gilles Sadowski <gi...@harfang.homelinux.org>:
>> [...]
>>
>> 1) do nothing to check the array is the same between calls and blindly
>> assumes it IS the same. Users would really need to call clearCache
>> when they provide a new array
>> pros: very simple
>> cons: error-prone for the user as it relies only on reading and
>> understanding a documentation that would change with new version
>>
>> 2) check only array reference equality (with ==) to check the array
>> is the same as the previous call or not. Users would need to call
>> clearCache only if they use the same array but have changed its
>> content.
>> pros: trade-off between efficiency and reliability,
>> handles most cases properly
>> cons: may be wrong in corner cases
>>
>> 3) check array content using an hash code. Users would generally don't
>> need to call clearCache at all so it would not be provided
>> pros: works in all cases
>> cons: add linear cost for array checking
>>
>> 4) remove the double[] values parameter from the API and use a separate
>> addValues method, hence the class will reset its cache only when
>> addValues is called
>> pros: works in all cases
>> cons: Percentile could not implement UnivariateStatistic anymore
>>
>> My preference is choice 2.
>>
>> What do you think ?
>
> IIUC, the interface method ("evaluate") was designed around the assumption
> that successive calls are independent: the array argument is not
> encapsulated for further processing (e.g. caching).
> IMO, the equality check and the "clearCache" method look like workarounds,
> not a clean solution.
> As an example, what if a user calls "evaluate" several times alternating on
> two different arrays:
>
> ---CUT---
> double[] a = new double[] {1, 2, 3};
> double[] b = new double[] {1, 2, 3, 4, 5};
> Percentile p = new Percentile();
>
> dourble r;
> r = p.evaluate(a, 50);
> r = p.evaluate(b, 50);
> r = p.evaluate(a, 50);
> r = p.evaluate(b, 50);
>
> // etc.
> ---CUT---
>
> Doesn't this kind of use-case nullify the expected optimization?
>
> If the array is going to be reused, the user call should reflect that fact;
> e.g. by passing the array in a constructor:
>
> ---CUT---
> double[] a = new double[] {1, 2, 3};
> double[] b = new double[] {1, 2, 3, 4, 5};
> Percentile pA = new Percentile(a);
> Percentile pB = new Percentile(b);
>
> double r;
> r = pA.evaluate(50);
> r = pB.evaluate(50);
> r = pA.evaluate(50);
> r = pB.evaluate(50);
> ---CUT---
>
> That way, later calls can benefit from whatever preprocessing was done in
> previous calls.
> The instance will always control all the information needed (e.g. after a
> call to an "addValues" method) for the processing without the need to rely
> on the user for calling "clearCache" whenever necessary.
>
>
> Gilles
+1
I think that is a really good idea and I agree on the points made.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
> [...]
>
> 1) do nothing to check the array is the same between calls and blindly
> assumes it IS the same. Users would really need to call clearCache
> when they provide a new array
> pros: very simple
> cons: error-prone for the user as it relies only on reading and
> understanding a documentation that would change with new version
>
> 2) check only array reference equality (with ==) to check the array
> is the same as the previous call or not. Users would need to call
> clearCache only if they use the same array but have changed its
> content.
> pros: trade-off between efficiency and reliability,
> handles most cases properly
> cons: may be wrong in corner cases
>
> 3) check array content using an hash code. Users would generally don't
> need to call clearCache at all so it would not be provided
> pros: works in all cases
> cons: add linear cost for array checking
>
> 4) remove the double[] values parameter from the API and use a separate
> addValues method, hence the class will reset its cache only when
> addValues is called
> pros: works in all cases
> cons: Percentile could not implement UnivariateStatistic anymore
>
> My preference is choice 2.
>
> What do you think ?
IIUC, the interface method ("evaluate") was designed around the assumption
that successive calls are independent: the array argument is not
encapsulated for further processing (e.g. caching).
IMO, the equality check and the "clearCache" method look like workarounds,
not a clean solution.
As an example, what if a user calls "evaluate" several times alternating on
two different arrays:
---CUT---
double[] a = new double[] {1, 2, 3};
double[] b = new double[] {1, 2, 3, 4, 5};
Percentile p = new Percentile();
dourble r;
r = p.evaluate(a, 50);
r = p.evaluate(b, 50);
r = p.evaluate(a, 50);
r = p.evaluate(b, 50);
// etc.
---CUT---
Doesn't this kind of use-case nullify the expected optimization?
If the array is going to be reused, the user call should reflect that fact;
e.g. by passing the array in a constructor:
---CUT---
double[] a = new double[] {1, 2, 3};
double[] b = new double[] {1, 2, 3, 4, 5};
Percentile pA = new Percentile(a);
Percentile pB = new Percentile(b);
double r;
r = pA.evaluate(50);
r = pB.evaluate(50);
r = pA.evaluate(50);
r = pB.evaluate(50);
---CUT---
That way, later calls can benefit from whatever preprocessing was done in
previous calls.
The instance will always control all the information needed (e.g. after a
call to an "addValues" method) for the processing without the need to rely
on the user for calling "clearCache" whenever necessary.
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Mikkel Meyer Andersen <mi...@mikl.dk>.
Hi,
Just a small pedantry correction:
Luc, you wrote:
> The evaluation that is only an approximation is the on-line algorithm,
> because it does not keep all values in memory. However, even when
> everything is in memory one should be aware that the result of the
> computation is the sample quantile, not the quantile of the underlying
> distribution and it seems this statistic is biased (sound to me close to
> what happen with standard deviation, with the 1/n or 1/(n+1) factors).
I assume you mean 1/n and 1/(n-1). (The latter is used to get an
unbiased estimate of the variance.)
Besides that: interesting and relevant discussion.
Cheers, Mikkel.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 26/09/2010 20:24, Phil Steitz a écrit :
> On 9/26/10 12:51 PM, Luc Maisonobe wrote:
>> Le 26/09/2010 18:21, Ted Dunning a écrit :
>>> I was about to write this suggestion down.
>>>
>>> Instead, I will simply concur.
>>>
>>> +1
>>>
>>> The safe version can do the checksum or make a copy. Either is safe
>>> and the
>>> costs are similar (O(n) on every call and no memory or O(1) on every
>>> call
>>> after the first, O(n) memory).
>>
>> OK. Then I will have a copy of the data in the class and for each
>> evaluate method with a double[] values parameter there will also be a
>> method without this parameter that will run on the already provided
>> array. The implementations with the value parameter will have an
>> implementation roughly similar to:
>>
>> public double evaluate(final double[] values, final double p) {
>> checkCache(values);
>> return evaluate(p);
>> }
>>
>> private void checkCache(final double[] values) {
>> final int hash = Arrays.hashcode(values);
>> if ((values != originalValues) || (hash != originalHash)) {
>> clearCache();
>> originalValues = values;
>> originalHash = hash;
>> copiedValues = values.clone();
>> }
>> }
>>
>> Starting to work on it ...
>
> -0 on the approach. Be careful with
>
> 1) array offset arguments. The contract of evaluate(p) will have to be
> evaluation on the same segment of the same array used in the last call.
I didn't see this, thanks for the hint.
> 2) For DescriptiveStatistics, the cache will have to be cleared when
> values are added between calls, since getPercentile(p) is already
> defined for that class and needs to return the value based on the
> current dataset.
Yes.
>
> The -0 as opposed to +1 is because
>
> a) handling offsets is going to make checkCache more complicated
Just two more values to store. What would be copied is the array slice.
This mean keeping the same array but changing the offsets would
invalidate cache.
> b) while the probability of collision may be very low in practice, there
> is no guarantee that hash collisions won't occur (in fact, it is certain
> that they *can* occur) and the result could be *nasty*, especially given
> that we are not telling the user we are doing it.
Thinking about it again, we could replace hash by a complete equality
test, but this would need to keep two copies of the array (one in
original order and another one in reorganized order). It would even be
faster as not equal arrays are detected on the first different element.
The cost is memory consumption.
> c) users that pass copies of arrays on subsequent calls containing the
> same values will not get the benefit of the caching.
With an equality test, this problem would be solved too.
>
> It may be better to just add setData(double[]), setData(double[], start,
> end) and evaluate(p) (and evaluate()) methods and define the contract of
> evaluate(p) to refer to the data added in the setData methods. We could
> talk about extending AbstractUnivariateStatistic similarly, adding
> setData and evaluate methods similarly - possibly evaluate(start, end)
> as well.
I think it would be worth having these methods pushed up in the class
hierarchy. However, the top level interface could be changed only in 3.0.
Luc
>
> Phil
>>
>> Luc
>>
>>>
>>> I would tend toward the copy option.
>>>
>>> On Sun, Sep 26, 2010 at 8:39 AM, Mikkel Meyer Andersen<mi...@mikl.dk>
>>> wrote:
>>>
>>>> Hi,
>>>>
>>>> Why not simply make 3) the default, but also supply a
>>>> *IMSureWhatIMDoing-method only implementing 2) (it is so cheap that we
>>>> might as well do it instead of not doing any check at all). This means
>>>> that users who read the documentation can gain something when they
>>>> explicitly ask for it, while users who don't read the docs are still
>>>> safe.
>>>>
>>>> Cheers, Mikkel.
>>>>
>>>> 2010/9/26 Luc Maisonobe<Lu...@free.fr>:
>>>>> Le 23/09/2010 20:57, Luc Maisonobe a écrit :
>>>>>> Hi,
>>>>>>
>>>>>> Resuming this thread, as I will be soon able to work on this (I
>>>>>> hope).
>>>>>> I propose to start by solving
>>>>>> <https://issues.apache.org/jira/browse/MATH-417> using a simple
>>>>>> partition-based selection algorithm and preserving pivot information.
>>>>>> This would help both the single call use-case (we don't sort
>>>>>> everything)
>>>>>> and the multiple call case (we don't redo on subsequent calls work
>>>>>> already done in the first calls.
>>>>>
>>>>> The current API of the Percentile method is derived from
>>>>> AbstractUnivariateStatistic and provides several evaluate methods that
>>>>> have the data array as a parameter.
>>>>>
>>>>> This is compatible with the one-call use case without any semantic
>>>>> change, but does not fit the multiple-calls use case seamlessly.
>>>>>
>>>>> If we want to cache some work already done on the array between calls
>>>>> with different values of p (the percentile value), we have to check if
>>>>> the array is still the same as the cached one on which we have done
>>>>> some
>>>>> partitioning and saved some pivots. This can be done by storing a
>>>>> reference to the original array in addition to a copy of its content
>>>>> (which we reorganize) and with an "if (values == originalValues)"
>>>>> statement. This would however not protect against changes in the array
>>>>> elements themselves done by the user between calls. A better
>>>>> protection
>>>>> could be to compute a hash code of the array content and compare it to
>>>>> the original one at each call. However, this would add a linear cost.
>>>>> The user who encountered the performances problems added an addValues
>>>>> method to set up the array once and simply ignored the values
>>>>> passed as
>>>>> an argument to the evaluate methods. This breaks the semantics of the
>>>> API.
>>>>>
>>>>> So I see four choices about partitioning caching and would like to
>>>>> have
>>>>> people express which one they prefer. A clearCache or similar public
>>>>> method would be made available to users to ensure clean computation if
>>>>> the caching mechanism gets on their way.
>>>>>
>>>>> 1) do nothing to check the array is the same between calls and
>>>>> blindly
>>>>> assumes it IS the same. Users would really need to call clearCache
>>>>> when they provide a new array
>>>>> pros: very simple
>>>>> cons: error-prone for the user as it relies only on reading and
>>>>> understanding a documentation that would change with new version
>>>>>
>>>>> 2) check only array reference equality (with ==) to check the array
>>>>> is the same as the previous call or not. Users would need to call
>>>>> clearCache only if they use the same array but have changed its
>>>>> content.
>>>>> pros: trade-off between efficiency and reliability,
>>>>> handles most cases properly
>>>>> cons: may be wrong in corner cases
>>>>>
>>>>> 3) check array content using an hash code. Users would generally
>>>>> don't
>>>>> need to call clearCache at all so it would not be provided
>>>>> pros: works in all cases
>>>>> cons: add linear cost for array checking
>>>>>
>>>>> 4) remove the double[] values parameter from the API and use a
>>>>> separate
>>>>> addValues method, hence the class will reset its cache only when
>>>>> addValues is called
>>>>> pros: works in all cases
>>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>>
>>>>> My preference is choice 2.
>>>>>
>>>>> What do you think ?
>>>>>
>>>>> Luc
>>>>>
>>>>>>
>>>>>> 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.
>>>>>>
>>>>>> Another possibility would be to have an additional method that would
>>>>>> compute percentiles for several thresholds at once, but this would
>>>>>> require returning an array of results and I think it would be
>>>>>> difficult
>>>>>> to mix with other statistics (mainly the DescriptiveStatistics.apply
>>>>>> method, which is used by the users I talked to).
>>>>>>
>>>>>> Would this meet everyone concerns ?
>>>>>> Luc
>>>>>>
>>>>>>
>>>>>> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
>>>>>>> Ted,
>>>>>>>
>>>>>>>> O(n), not n
>>>>>>>>
>>>>>>>> Expected case is n + n/2 + n/4 ...< 2n
>>>>>>>
>>>>>>> Yes, that I am already more incline to buy.
>>>>>>>
>>>>>>> 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
>>>>>>
>>>>>
>>>>>
>>>>> ---------------------------------------------------------------------
>>>>> 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
>>>>
>>>>
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Phil Steitz <ph...@gmail.com>.
On 9/26/10 12:51 PM, Luc Maisonobe wrote:
> Le 26/09/2010 18:21, Ted Dunning a écrit :
>> I was about to write this suggestion down.
>>
>> Instead, I will simply concur.
>>
>> +1
>>
>> The safe version can do the checksum or make a copy. Either is safe and the
>> costs are similar (O(n) on every call and no memory or O(1) on every call
>> after the first, O(n) memory).
>
> OK. Then I will have a copy of the data in the class and for each
> evaluate method with a double[] values parameter there will also be a
> method without this parameter that will run on the already provided
> array. The implementations with the value parameter will have an
> implementation roughly similar to:
>
> public double evaluate(final double[] values, final double p) {
> checkCache(values);
> return evaluate(p);
> }
>
> private void checkCache(final double[] values) {
> final int hash = Arrays.hashcode(values);
> if ((values != originalValues) || (hash != originalHash)) {
> clearCache();
> originalValues = values;
> originalHash = hash;
> copiedValues = values.clone();
> }
> }
>
> Starting to work on it ...
-0 on the approach. Be careful with
1) array offset arguments. The contract of evaluate(p) will have to
be evaluation on the same segment of the same array used in the last
call.
2) For DescriptiveStatistics, the cache will have to be cleared when
values are added between calls, since getPercentile(p) is already
defined for that class and needs to return the value based on the
current dataset.
The -0 as opposed to +1 is because
a) handling offsets is going to make checkCache more complicated
b) while the probability of collision may be very low in practice,
there is no guarantee that hash collisions won't occur (in fact, it
is certain that they *can* occur) and the result could be *nasty*,
especially given that we are not telling the user we are doing it.
c) users that pass copies of arrays on subsequent calls containing
the same values will not get the benefit of the caching.
It may be better to just add setData(double[]), setData(double[],
start, end) and evaluate(p) (and evaluate()) methods and define the
contract of evaluate(p) to refer to the data added in the setData
methods. We could talk about extending AbstractUnivariateStatistic
similarly, adding setData and evaluate methods similarly - possibly
evaluate(start, end) as well.
Phil
>
> Luc
>
>>
>> I would tend toward the copy option.
>>
>> On Sun, Sep 26, 2010 at 8:39 AM, Mikkel Meyer Andersen<mi...@mikl.dk> wrote:
>>
>>> Hi,
>>>
>>> Why not simply make 3) the default, but also supply a
>>> *IMSureWhatIMDoing-method only implementing 2) (it is so cheap that we
>>> might as well do it instead of not doing any check at all). This means
>>> that users who read the documentation can gain something when they
>>> explicitly ask for it, while users who don't read the docs are still
>>> safe.
>>>
>>> Cheers, Mikkel.
>>>
>>> 2010/9/26 Luc Maisonobe<Lu...@free.fr>:
>>>> Le 23/09/2010 20:57, Luc Maisonobe a écrit :
>>>>> Hi,
>>>>>
>>>>> Resuming this thread, as I will be soon able to work on this (I hope).
>>>>> I propose to start by solving
>>>>> <https://issues.apache.org/jira/browse/MATH-417> using a simple
>>>>> partition-based selection algorithm and preserving pivot information.
>>>>> This would help both the single call use-case (we don't sort everything)
>>>>> and the multiple call case (we don't redo on subsequent calls work
>>>>> already done in the first calls.
>>>>
>>>> The current API of the Percentile method is derived from
>>>> AbstractUnivariateStatistic and provides several evaluate methods that
>>>> have the data array as a parameter.
>>>>
>>>> This is compatible with the one-call use case without any semantic
>>>> change, but does not fit the multiple-calls use case seamlessly.
>>>>
>>>> If we want to cache some work already done on the array between calls
>>>> with different values of p (the percentile value), we have to check if
>>>> the array is still the same as the cached one on which we have done some
>>>> partitioning and saved some pivots. This can be done by storing a
>>>> reference to the original array in addition to a copy of its content
>>>> (which we reorganize) and with an "if (values == originalValues)"
>>>> statement. This would however not protect against changes in the array
>>>> elements themselves done by the user between calls. A better protection
>>>> could be to compute a hash code of the array content and compare it to
>>>> the original one at each call. However, this would add a linear cost.
>>>> The user who encountered the performances problems added an addValues
>>>> method to set up the array once and simply ignored the values passed as
>>>> an argument to the evaluate methods. This breaks the semantics of the
>>> API.
>>>>
>>>> So I see four choices about partitioning caching and would like to have
>>>> people express which one they prefer. A clearCache or similar public
>>>> method would be made available to users to ensure clean computation if
>>>> the caching mechanism gets on their way.
>>>>
>>>> 1) do nothing to check the array is the same between calls and blindly
>>>> assumes it IS the same. Users would really need to call clearCache
>>>> when they provide a new array
>>>> pros: very simple
>>>> cons: error-prone for the user as it relies only on reading and
>>>> understanding a documentation that would change with new version
>>>>
>>>> 2) check only array reference equality (with ==) to check the array
>>>> is the same as the previous call or not. Users would need to call
>>>> clearCache only if they use the same array but have changed its
>>>> content.
>>>> pros: trade-off between efficiency and reliability,
>>>> handles most cases properly
>>>> cons: may be wrong in corner cases
>>>>
>>>> 3) check array content using an hash code. Users would generally don't
>>>> need to call clearCache at all so it would not be provided
>>>> pros: works in all cases
>>>> cons: add linear cost for array checking
>>>>
>>>> 4) remove the double[] values parameter from the API and use a separate
>>>> addValues method, hence the class will reset its cache only when
>>>> addValues is called
>>>> pros: works in all cases
>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>
>>>> My preference is choice 2.
>>>>
>>>> What do you think ?
>>>>
>>>> Luc
>>>>
>>>>>
>>>>> 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.
>>>>>
>>>>> Another possibility would be to have an additional method that would
>>>>> compute percentiles for several thresholds at once, but this would
>>>>> require returning an array of results and I think it would be difficult
>>>>> to mix with other statistics (mainly the DescriptiveStatistics.apply
>>>>> method, which is used by the users I talked to).
>>>>>
>>>>> Would this meet everyone concerns ?
>>>>> Luc
>>>>>
>>>>>
>>>>> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
>>>>>> Ted,
>>>>>>
>>>>>>> O(n), not n
>>>>>>>
>>>>>>> Expected case is n + n/2 + n/4 ...< 2n
>>>>>>
>>>>>> Yes, that I am already more incline to buy.
>>>>>>
>>>>>> 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
>>>>>
>>>>
>>>>
>>>> ---------------------------------------------------------------------
>>>> 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
>>>
>>>
>>
>
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 26/09/2010 18:55, Mikkel Meyer Andersen a écrit :
> I don't see any season for computing hash value if pointers don't match.
If pointers don't match, the two arrays are obviously different, but wen
still need to compute the hash to cache it for the check on next call.
Luc
> Den 2010 9 26 18:52 skrev "Luc Maisonobe" <Lu...@free.fr>:
>> Le 26/09/2010 18:21, Ted Dunning a écrit :
>>> I was about to write this suggestion down.
>>>
>>> Instead, I will simply concur.
>>>
>>> +1
>>>
>>> The safe version can do the checksum or make a copy. Either is safe and
> the
>>> costs are similar (O(n) on every call and no memory or O(1) on every call
>>> after the first, O(n) memory).
>>
>> OK. Then I will have a copy of the data in the class and for each
>> evaluate method with a double[] values parameter there will also be a
>> method without this parameter that will run on the already provided
>> array. The implementations with the value parameter will have an
>> implementation roughly similar to:
>>
>> public double evaluate(final double[] values, final double p) {
>> checkCache(values);
>> return evaluate(p);
>> }
>>
>> private void checkCache(final double[] values) {
>> final int hash = Arrays.hashcode(values);
>> if ((values != originalValues) || (hash != originalHash)) {
>> clearCache();
>> originalValues = values;
>> originalHash = hash;
>> copiedValues = values.clone();
>> }
>> }
>>
>> Starting to work on it ...
>>
>> Luc
>>
>>>
>>> I would tend toward the copy option.
>>>
>>> On Sun, Sep 26, 2010 at 8:39 AM, Mikkel Meyer Andersen <mi...@mikl.dk>
> wrote:
>>>
>>>> Hi,
>>>>
>>>> Why not simply make 3) the default, but also supply a
>>>> *IMSureWhatIMDoing-method only implementing 2) (it is so cheap that we
>>>> might as well do it instead of not doing any check at all). This means
>>>> that users who read the documentation can gain something when they
>>>> explicitly ask for it, while users who don't read the docs are still
>>>> safe.
>>>>
>>>> Cheers, Mikkel.
>>>>
>>>> 2010/9/26 Luc Maisonobe <Lu...@free.fr>:
>>>>> Le 23/09/2010 20:57, Luc Maisonobe a écrit :
>>>>>> Hi,
>>>>>>
>>>>>> Resuming this thread, as I will be soon able to work on this (I hope).
>>>>>> I propose to start by solving
>>>>>> <https://issues.apache.org/jira/browse/MATH-417> using a simple
>>>>>> partition-based selection algorithm and preserving pivot information.
>>>>>> This would help both the single call use-case (we don't sort
> everything)
>>>>>> and the multiple call case (we don't redo on subsequent calls work
>>>>>> already done in the first calls.
>>>>>
>>>>> The current API of the Percentile method is derived from
>>>>> AbstractUnivariateStatistic and provides several evaluate methods that
>>>>> have the data array as a parameter.
>>>>>
>>>>> This is compatible with the one-call use case without any semantic
>>>>> change, but does not fit the multiple-calls use case seamlessly.
>>>>>
>>>>> If we want to cache some work already done on the array between calls
>>>>> with different values of p (the percentile value), we have to check if
>>>>> the array is still the same as the cached one on which we have done
> some
>>>>> partitioning and saved some pivots. This can be done by storing a
>>>>> reference to the original array in addition to a copy of its content
>>>>> (which we reorganize) and with an "if (values == originalValues)"
>>>>> statement. This would however not protect against changes in the array
>>>>> elements themselves done by the user between calls. A better protection
>>>>> could be to compute a hash code of the array content and compare it to
>>>>> the original one at each call. However, this would add a linear cost.
>>>>> The user who encountered the performances problems added an addValues
>>>>> method to set up the array once and simply ignored the values passed as
>>>>> an argument to the evaluate methods. This breaks the semantics of the
>>>> API.
>>>>>
>>>>> So I see four choices about partitioning caching and would like to have
>>>>> people express which one they prefer. A clearCache or similar public
>>>>> method would be made available to users to ensure clean computation if
>>>>> the caching mechanism gets on their way.
>>>>>
>>>>> 1) do nothing to check the array is the same between calls and blindly
>>>>> assumes it IS the same. Users would really need to call clearCache
>>>>> when they provide a new array
>>>>> pros: very simple
>>>>> cons: error-prone for the user as it relies only on reading and
>>>>> understanding a documentation that would change with new version
>>>>>
>>>>> 2) check only array reference equality (with ==) to check the array
>>>>> is the same as the previous call or not. Users would need to call
>>>>> clearCache only if they use the same array but have changed its
>>>>> content.
>>>>> pros: trade-off between efficiency and reliability,
>>>>> handles most cases properly
>>>>> cons: may be wrong in corner cases
>>>>>
>>>>> 3) check array content using an hash code. Users would generally don't
>>>>> need to call clearCache at all so it would not be provided
>>>>> pros: works in all cases
>>>>> cons: add linear cost for array checking
>>>>>
>>>>> 4) remove the double[] values parameter from the API and use a separate
>>>>> addValues method, hence the class will reset its cache only when
>>>>> addValues is called
>>>>> pros: works in all cases
>>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>>
>>>>> My preference is choice 2.
>>>>>
>>>>> What do you think ?
>>>>>
>>>>> Luc
>>>>>
>>>>>>
>>>>>> 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.
>>>>>>
>>>>>> Another possibility would be to have an additional method that would
>>>>>> compute percentiles for several thresholds at once, but this would
>>>>>> require returning an array of results and I think it would be
> difficult
>>>>>> to mix with other statistics (mainly the DescriptiveStatistics.apply
>>>>>> method, which is used by the users I talked to).
>>>>>>
>>>>>> Would this meet everyone concerns ?
>>>>>> Luc
>>>>>>
>>>>>>
>>>>>> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
>>>>>>> Ted,
>>>>>>>
>>>>>>>> O(n), not n
>>>>>>>>
>>>>>>>> Expected case is n + n/2 + n/4 ... < 2n
>>>>>>>
>>>>>>> Yes, that I am already more incline to buy.
>>>>>>>
>>>>>>> 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
>>>>>>
>>>>>
>>>>>
>>>>> ---------------------------------------------------------------------
>>>>> 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
>>>>
>>>>
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
Re: [math] speeding up percentile based statistics
Posted by Mikkel Meyer Andersen <mi...@mikl.dk>.
I don't see any season for computing hash value if pointers don't match.
Den 2010 9 26 18:52 skrev "Luc Maisonobe" <Lu...@free.fr>:
> Le 26/09/2010 18:21, Ted Dunning a écrit :
>> I was about to write this suggestion down.
>>
>> Instead, I will simply concur.
>>
>> +1
>>
>> The safe version can do the checksum or make a copy. Either is safe and
the
>> costs are similar (O(n) on every call and no memory or O(1) on every call
>> after the first, O(n) memory).
>
> OK. Then I will have a copy of the data in the class and for each
> evaluate method with a double[] values parameter there will also be a
> method without this parameter that will run on the already provided
> array. The implementations with the value parameter will have an
> implementation roughly similar to:
>
> public double evaluate(final double[] values, final double p) {
> checkCache(values);
> return evaluate(p);
> }
>
> private void checkCache(final double[] values) {
> final int hash = Arrays.hashcode(values);
> if ((values != originalValues) || (hash != originalHash)) {
> clearCache();
> originalValues = values;
> originalHash = hash;
> copiedValues = values.clone();
> }
> }
>
> Starting to work on it ...
>
> Luc
>
>>
>> I would tend toward the copy option.
>>
>> On Sun, Sep 26, 2010 at 8:39 AM, Mikkel Meyer Andersen <mi...@mikl.dk>
wrote:
>>
>>> Hi,
>>>
>>> Why not simply make 3) the default, but also supply a
>>> *IMSureWhatIMDoing-method only implementing 2) (it is so cheap that we
>>> might as well do it instead of not doing any check at all). This means
>>> that users who read the documentation can gain something when they
>>> explicitly ask for it, while users who don't read the docs are still
>>> safe.
>>>
>>> Cheers, Mikkel.
>>>
>>> 2010/9/26 Luc Maisonobe <Lu...@free.fr>:
>>>> Le 23/09/2010 20:57, Luc Maisonobe a écrit :
>>>>> Hi,
>>>>>
>>>>> Resuming this thread, as I will be soon able to work on this (I hope).
>>>>> I propose to start by solving
>>>>> <https://issues.apache.org/jira/browse/MATH-417> using a simple
>>>>> partition-based selection algorithm and preserving pivot information.
>>>>> This would help both the single call use-case (we don't sort
everything)
>>>>> and the multiple call case (we don't redo on subsequent calls work
>>>>> already done in the first calls.
>>>>
>>>> The current API of the Percentile method is derived from
>>>> AbstractUnivariateStatistic and provides several evaluate methods that
>>>> have the data array as a parameter.
>>>>
>>>> This is compatible with the one-call use case without any semantic
>>>> change, but does not fit the multiple-calls use case seamlessly.
>>>>
>>>> If we want to cache some work already done on the array between calls
>>>> with different values of p (the percentile value), we have to check if
>>>> the array is still the same as the cached one on which we have done
some
>>>> partitioning and saved some pivots. This can be done by storing a
>>>> reference to the original array in addition to a copy of its content
>>>> (which we reorganize) and with an "if (values == originalValues)"
>>>> statement. This would however not protect against changes in the array
>>>> elements themselves done by the user between calls. A better protection
>>>> could be to compute a hash code of the array content and compare it to
>>>> the original one at each call. However, this would add a linear cost.
>>>> The user who encountered the performances problems added an addValues
>>>> method to set up the array once and simply ignored the values passed as
>>>> an argument to the evaluate methods. This breaks the semantics of the
>>> API.
>>>>
>>>> So I see four choices about partitioning caching and would like to have
>>>> people express which one they prefer. A clearCache or similar public
>>>> method would be made available to users to ensure clean computation if
>>>> the caching mechanism gets on their way.
>>>>
>>>> 1) do nothing to check the array is the same between calls and blindly
>>>> assumes it IS the same. Users would really need to call clearCache
>>>> when they provide a new array
>>>> pros: very simple
>>>> cons: error-prone for the user as it relies only on reading and
>>>> understanding a documentation that would change with new version
>>>>
>>>> 2) check only array reference equality (with ==) to check the array
>>>> is the same as the previous call or not. Users would need to call
>>>> clearCache only if they use the same array but have changed its
>>>> content.
>>>> pros: trade-off between efficiency and reliability,
>>>> handles most cases properly
>>>> cons: may be wrong in corner cases
>>>>
>>>> 3) check array content using an hash code. Users would generally don't
>>>> need to call clearCache at all so it would not be provided
>>>> pros: works in all cases
>>>> cons: add linear cost for array checking
>>>>
>>>> 4) remove the double[] values parameter from the API and use a separate
>>>> addValues method, hence the class will reset its cache only when
>>>> addValues is called
>>>> pros: works in all cases
>>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>>
>>>> My preference is choice 2.
>>>>
>>>> What do you think ?
>>>>
>>>> Luc
>>>>
>>>>>
>>>>> 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.
>>>>>
>>>>> Another possibility would be to have an additional method that would
>>>>> compute percentiles for several thresholds at once, but this would
>>>>> require returning an array of results and I think it would be
difficult
>>>>> to mix with other statistics (mainly the DescriptiveStatistics.apply
>>>>> method, which is used by the users I talked to).
>>>>>
>>>>> Would this meet everyone concerns ?
>>>>> Luc
>>>>>
>>>>>
>>>>> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
>>>>>> Ted,
>>>>>>
>>>>>>> O(n), not n
>>>>>>>
>>>>>>> Expected case is n + n/2 + n/4 ... < 2n
>>>>>>
>>>>>> Yes, that I am already more incline to buy.
>>>>>>
>>>>>> 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
>>>>>
>>>>
>>>>
>>>> ---------------------------------------------------------------------
>>>> 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
>>>
>>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 26/09/2010 18:21, Ted Dunning a écrit :
> I was about to write this suggestion down.
>
> Instead, I will simply concur.
>
> +1
>
> The safe version can do the checksum or make a copy. Either is safe and the
> costs are similar (O(n) on every call and no memory or O(1) on every call
> after the first, O(n) memory).
OK. Then I will have a copy of the data in the class and for each
evaluate method with a double[] values parameter there will also be a
method without this parameter that will run on the already provided
array. The implementations with the value parameter will have an
implementation roughly similar to:
public double evaluate(final double[] values, final double p) {
checkCache(values);
return evaluate(p);
}
private void checkCache(final double[] values) {
final int hash = Arrays.hashcode(values);
if ((values != originalValues) || (hash != originalHash)) {
clearCache();
originalValues = values;
originalHash = hash;
copiedValues = values.clone();
}
}
Starting to work on it ...
Luc
>
> I would tend toward the copy option.
>
> On Sun, Sep 26, 2010 at 8:39 AM, Mikkel Meyer Andersen <mi...@mikl.dk> wrote:
>
>> Hi,
>>
>> Why not simply make 3) the default, but also supply a
>> *IMSureWhatIMDoing-method only implementing 2) (it is so cheap that we
>> might as well do it instead of not doing any check at all). This means
>> that users who read the documentation can gain something when they
>> explicitly ask for it, while users who don't read the docs are still
>> safe.
>>
>> Cheers, Mikkel.
>>
>> 2010/9/26 Luc Maisonobe <Lu...@free.fr>:
>>> Le 23/09/2010 20:57, Luc Maisonobe a écrit :
>>>> Hi,
>>>>
>>>> Resuming this thread, as I will be soon able to work on this (I hope).
>>>> I propose to start by solving
>>>> <https://issues.apache.org/jira/browse/MATH-417> using a simple
>>>> partition-based selection algorithm and preserving pivot information.
>>>> This would help both the single call use-case (we don't sort everything)
>>>> and the multiple call case (we don't redo on subsequent calls work
>>>> already done in the first calls.
>>>
>>> The current API of the Percentile method is derived from
>>> AbstractUnivariateStatistic and provides several evaluate methods that
>>> have the data array as a parameter.
>>>
>>> This is compatible with the one-call use case without any semantic
>>> change, but does not fit the multiple-calls use case seamlessly.
>>>
>>> If we want to cache some work already done on the array between calls
>>> with different values of p (the percentile value), we have to check if
>>> the array is still the same as the cached one on which we have done some
>>> partitioning and saved some pivots. This can be done by storing a
>>> reference to the original array in addition to a copy of its content
>>> (which we reorganize) and with an "if (values == originalValues)"
>>> statement. This would however not protect against changes in the array
>>> elements themselves done by the user between calls. A better protection
>>> could be to compute a hash code of the array content and compare it to
>>> the original one at each call. However, this would add a linear cost.
>>> The user who encountered the performances problems added an addValues
>>> method to set up the array once and simply ignored the values passed as
>>> an argument to the evaluate methods. This breaks the semantics of the
>> API.
>>>
>>> So I see four choices about partitioning caching and would like to have
>>> people express which one they prefer. A clearCache or similar public
>>> method would be made available to users to ensure clean computation if
>>> the caching mechanism gets on their way.
>>>
>>> 1) do nothing to check the array is the same between calls and blindly
>>> assumes it IS the same. Users would really need to call clearCache
>>> when they provide a new array
>>> pros: very simple
>>> cons: error-prone for the user as it relies only on reading and
>>> understanding a documentation that would change with new version
>>>
>>> 2) check only array reference equality (with ==) to check the array
>>> is the same as the previous call or not. Users would need to call
>>> clearCache only if they use the same array but have changed its
>>> content.
>>> pros: trade-off between efficiency and reliability,
>>> handles most cases properly
>>> cons: may be wrong in corner cases
>>>
>>> 3) check array content using an hash code. Users would generally don't
>>> need to call clearCache at all so it would not be provided
>>> pros: works in all cases
>>> cons: add linear cost for array checking
>>>
>>> 4) remove the double[] values parameter from the API and use a separate
>>> addValues method, hence the class will reset its cache only when
>>> addValues is called
>>> pros: works in all cases
>>> cons: Percentile could not implement UnivariateStatistic anymore
>>>
>>> My preference is choice 2.
>>>
>>> What do you think ?
>>>
>>> Luc
>>>
>>>>
>>>> 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.
>>>>
>>>> Another possibility would be to have an additional method that would
>>>> compute percentiles for several thresholds at once, but this would
>>>> require returning an array of results and I think it would be difficult
>>>> to mix with other statistics (mainly the DescriptiveStatistics.apply
>>>> method, which is used by the users I talked to).
>>>>
>>>> Would this meet everyone concerns ?
>>>> Luc
>>>>
>>>>
>>>> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
>>>>> Ted,
>>>>>
>>>>>> O(n), not n
>>>>>>
>>>>>> Expected case is n + n/2 + n/4 ... < 2n
>>>>>
>>>>> Yes, that I am already more incline to buy.
>>>>>
>>>>> 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
>>>>
>>>
>>>
>>> ---------------------------------------------------------------------
>>> 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
>>
>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Ted Dunning <te...@gmail.com>.
I was about to write this suggestion down.
Instead, I will simply concur.
+1
The safe version can do the checksum or make a copy. Either is safe and the
costs are similar (O(n) on every call and no memory or O(1) on every call
after the first, O(n) memory).
I would tend toward the copy option.
On Sun, Sep 26, 2010 at 8:39 AM, Mikkel Meyer Andersen <mi...@mikl.dk> wrote:
> Hi,
>
> Why not simply make 3) the default, but also supply a
> *IMSureWhatIMDoing-method only implementing 2) (it is so cheap that we
> might as well do it instead of not doing any check at all). This means
> that users who read the documentation can gain something when they
> explicitly ask for it, while users who don't read the docs are still
> safe.
>
> Cheers, Mikkel.
>
> 2010/9/26 Luc Maisonobe <Lu...@free.fr>:
> > Le 23/09/2010 20:57, Luc Maisonobe a écrit :
> >> Hi,
> >>
> >> Resuming this thread, as I will be soon able to work on this (I hope).
> >> I propose to start by solving
> >> <https://issues.apache.org/jira/browse/MATH-417> using a simple
> >> partition-based selection algorithm and preserving pivot information.
> >> This would help both the single call use-case (we don't sort everything)
> >> and the multiple call case (we don't redo on subsequent calls work
> >> already done in the first calls.
> >
> > The current API of the Percentile method is derived from
> > AbstractUnivariateStatistic and provides several evaluate methods that
> > have the data array as a parameter.
> >
> > This is compatible with the one-call use case without any semantic
> > change, but does not fit the multiple-calls use case seamlessly.
> >
> > If we want to cache some work already done on the array between calls
> > with different values of p (the percentile value), we have to check if
> > the array is still the same as the cached one on which we have done some
> > partitioning and saved some pivots. This can be done by storing a
> > reference to the original array in addition to a copy of its content
> > (which we reorganize) and with an "if (values == originalValues)"
> > statement. This would however not protect against changes in the array
> > elements themselves done by the user between calls. A better protection
> > could be to compute a hash code of the array content and compare it to
> > the original one at each call. However, this would add a linear cost.
> > The user who encountered the performances problems added an addValues
> > method to set up the array once and simply ignored the values passed as
> > an argument to the evaluate methods. This breaks the semantics of the
> API.
> >
> > So I see four choices about partitioning caching and would like to have
> > people express which one they prefer. A clearCache or similar public
> > method would be made available to users to ensure clean computation if
> > the caching mechanism gets on their way.
> >
> > 1) do nothing to check the array is the same between calls and blindly
> > assumes it IS the same. Users would really need to call clearCache
> > when they provide a new array
> > pros: very simple
> > cons: error-prone for the user as it relies only on reading and
> > understanding a documentation that would change with new version
> >
> > 2) check only array reference equality (with ==) to check the array
> > is the same as the previous call or not. Users would need to call
> > clearCache only if they use the same array but have changed its
> > content.
> > pros: trade-off between efficiency and reliability,
> > handles most cases properly
> > cons: may be wrong in corner cases
> >
> > 3) check array content using an hash code. Users would generally don't
> > need to call clearCache at all so it would not be provided
> > pros: works in all cases
> > cons: add linear cost for array checking
> >
> > 4) remove the double[] values parameter from the API and use a separate
> > addValues method, hence the class will reset its cache only when
> > addValues is called
> > pros: works in all cases
> > cons: Percentile could not implement UnivariateStatistic anymore
> >
> > My preference is choice 2.
> >
> > What do you think ?
> >
> > Luc
> >
> >>
> >> 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.
> >>
> >> Another possibility would be to have an additional method that would
> >> compute percentiles for several thresholds at once, but this would
> >> require returning an array of results and I think it would be difficult
> >> to mix with other statistics (mainly the DescriptiveStatistics.apply
> >> method, which is used by the users I talked to).
> >>
> >> Would this meet everyone concerns ?
> >> Luc
> >>
> >>
> >> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
> >>> Ted,
> >>>
> >>>> O(n), not n
> >>>>
> >>>> Expected case is n + n/2 + n/4 ... < 2n
> >>>
> >>> Yes, that I am already more incline to buy.
> >>>
> >>> 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
> >>
> >
> >
> > ---------------------------------------------------------------------
> > 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
>
>
Re: [math] speeding up percentile based statistics
Posted by Mikkel Meyer Andersen <mi...@mikl.dk>.
Hi,
Why not simply make 3) the default, but also supply a
*IMSureWhatIMDoing-method only implementing 2) (it is so cheap that we
might as well do it instead of not doing any check at all). This means
that users who read the documentation can gain something when they
explicitly ask for it, while users who don't read the docs are still
safe.
Cheers, Mikkel.
2010/9/26 Luc Maisonobe <Lu...@free.fr>:
> Le 23/09/2010 20:57, Luc Maisonobe a écrit :
>> Hi,
>>
>> Resuming this thread, as I will be soon able to work on this (I hope).
>> I propose to start by solving
>> <https://issues.apache.org/jira/browse/MATH-417> using a simple
>> partition-based selection algorithm and preserving pivot information.
>> This would help both the single call use-case (we don't sort everything)
>> and the multiple call case (we don't redo on subsequent calls work
>> already done in the first calls.
>
> The current API of the Percentile method is derived from
> AbstractUnivariateStatistic and provides several evaluate methods that
> have the data array as a parameter.
>
> This is compatible with the one-call use case without any semantic
> change, but does not fit the multiple-calls use case seamlessly.
>
> If we want to cache some work already done on the array between calls
> with different values of p (the percentile value), we have to check if
> the array is still the same as the cached one on which we have done some
> partitioning and saved some pivots. This can be done by storing a
> reference to the original array in addition to a copy of its content
> (which we reorganize) and with an "if (values == originalValues)"
> statement. This would however not protect against changes in the array
> elements themselves done by the user between calls. A better protection
> could be to compute a hash code of the array content and compare it to
> the original one at each call. However, this would add a linear cost.
> The user who encountered the performances problems added an addValues
> method to set up the array once and simply ignored the values passed as
> an argument to the evaluate methods. This breaks the semantics of the API.
>
> So I see four choices about partitioning caching and would like to have
> people express which one they prefer. A clearCache or similar public
> method would be made available to users to ensure clean computation if
> the caching mechanism gets on their way.
>
> 1) do nothing to check the array is the same between calls and blindly
> assumes it IS the same. Users would really need to call clearCache
> when they provide a new array
> pros: very simple
> cons: error-prone for the user as it relies only on reading and
> understanding a documentation that would change with new version
>
> 2) check only array reference equality (with ==) to check the array
> is the same as the previous call or not. Users would need to call
> clearCache only if they use the same array but have changed its
> content.
> pros: trade-off between efficiency and reliability,
> handles most cases properly
> cons: may be wrong in corner cases
>
> 3) check array content using an hash code. Users would generally don't
> need to call clearCache at all so it would not be provided
> pros: works in all cases
> cons: add linear cost for array checking
>
> 4) remove the double[] values parameter from the API and use a separate
> addValues method, hence the class will reset its cache only when
> addValues is called
> pros: works in all cases
> cons: Percentile could not implement UnivariateStatistic anymore
>
> My preference is choice 2.
>
> What do you think ?
>
> Luc
>
>>
>> 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.
>>
>> Another possibility would be to have an additional method that would
>> compute percentiles for several thresholds at once, but this would
>> require returning an array of results and I think it would be difficult
>> to mix with other statistics (mainly the DescriptiveStatistics.apply
>> method, which is used by the users I talked to).
>>
>> Would this meet everyone concerns ?
>> Luc
>>
>>
>> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
>>> Ted,
>>>
>>>> O(n), not n
>>>>
>>>> Expected case is n + n/2 + n/4 ... < 2n
>>>
>>> Yes, that I am already more incline to buy.
>>>
>>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 23/09/2010 20:57, Luc Maisonobe a écrit :
> Hi,
>
> Resuming this thread, as I will be soon able to work on this (I hope).
> I propose to start by solving
> <https://issues.apache.org/jira/browse/MATH-417> using a simple
> partition-based selection algorithm and preserving pivot information.
> This would help both the single call use-case (we don't sort everything)
> and the multiple call case (we don't redo on subsequent calls work
> already done in the first calls.
The current API of the Percentile method is derived from
AbstractUnivariateStatistic and provides several evaluate methods that
have the data array as a parameter.
This is compatible with the one-call use case without any semantic
change, but does not fit the multiple-calls use case seamlessly.
If we want to cache some work already done on the array between calls
with different values of p (the percentile value), we have to check if
the array is still the same as the cached one on which we have done some
partitioning and saved some pivots. This can be done by storing a
reference to the original array in addition to a copy of its content
(which we reorganize) and with an "if (values == originalValues)"
statement. This would however not protect against changes in the array
elements themselves done by the user between calls. A better protection
could be to compute a hash code of the array content and compare it to
the original one at each call. However, this would add a linear cost.
The user who encountered the performances problems added an addValues
method to set up the array once and simply ignored the values passed as
an argument to the evaluate methods. This breaks the semantics of the API.
So I see four choices about partitioning caching and would like to have
people express which one they prefer. A clearCache or similar public
method would be made available to users to ensure clean computation if
the caching mechanism gets on their way.
1) do nothing to check the array is the same between calls and blindly
assumes it IS the same. Users would really need to call clearCache
when they provide a new array
pros: very simple
cons: error-prone for the user as it relies only on reading and
understanding a documentation that would change with new version
2) check only array reference equality (with ==) to check the array
is the same as the previous call or not. Users would need to call
clearCache only if they use the same array but have changed its
content.
pros: trade-off between efficiency and reliability,
handles most cases properly
cons: may be wrong in corner cases
3) check array content using an hash code. Users would generally don't
need to call clearCache at all so it would not be provided
pros: works in all cases
cons: add linear cost for array checking
4) remove the double[] values parameter from the API and use a separate
addValues method, hence the class will reset its cache only when
addValues is called
pros: works in all cases
cons: Percentile could not implement UnivariateStatistic anymore
My preference is choice 2.
What do you think ?
Luc
>
> 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.
>
> Another possibility would be to have an additional method that would
> compute percentiles for several thresholds at once, but this would
> require returning an array of results and I think it would be difficult
> to mix with other statistics (mainly the DescriptiveStatistics.apply
> method, which is used by the users I talked to).
>
> Would this meet everyone concerns ?
> Luc
>
>
> Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
>> Ted,
>>
>>> O(n), not n
>>>
>>> Expected case is n + n/2 + n/4 ... < 2n
>>
>> Yes, that I am already more incline to buy.
>>
>> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
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 <Lu...@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
Re: [math] speeding up percentile based statistics
Posted by Ted Dunning <te...@gmail.com>.
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.
On Thu, Sep 23, 2010 at 11:57 AM, Luc Maisonobe <Lu...@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.
>
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Hi,
Resuming this thread, as I will be soon able to work on this (I hope).
I propose to start by solving
<https://issues.apache.org/jira/browse/MATH-417> using a simple
partition-based selection algorithm and preserving pivot information.
This would help both the single call use-case (we don't sort everything)
and the multiple call case (we don't redo on subsequent calls work
already done in the first calls.
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.
Another possibility would be to have an additional method that would
compute percentiles for several thresholds at once, but this would
require returning an array of results and I think it would be difficult
to mix with other statistics (mainly the DescriptiveStatistics.apply
method, which is used by the users I talked to).
Would this meet everyone concerns ?
Luc
Le 18/09/2010 21:50, Dimitri Pourbaix a écrit :
> Ted,
>
>> O(n), not n
>>
>> Expected case is n + n/2 + n/4 ... < 2n
>
> Yes, that I am already more incline to buy.
>
> 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
Re: [math] speeding up percentile based statistics
Posted by Dimitri Pourbaix <po...@astro.ulb.ac.be>.
Ted,
> O(n), not n
>
> Expected case is n + n/2 + n/4 ... < 2n
Yes, that I am already more incline to buy.
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
Re: [math] speeding up percentile based statistics
Posted by Ted Dunning <te...@gmail.com>.
O(n), not n
Expected case is n + n/2 + n/4 ... < 2n
On Sat, Sep 18, 2010 at 12:05 PM, Luc Maisonobe <Lu...@free.fr>wrote:
> 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
>
>
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
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
Re: [math] speeding up percentile based statistics
Posted by Dimitri Pourbaix <po...@astro.ulb.ac.be>.
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).
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
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 18/09/2010 20:01, Dimitri Pourbaix a écrit :
> Hi,
>
> If I understand correctly, the argument against the present implementation
> is that if several percentiles are requested, they all require the sorting
> of the array.
Yes.
> 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.
The evaluation that is only an approximation is the on-line algorithm,
because it does not keep all values in memory. However, even when
everything is in memory one should be aware that the result of the
computation is the sample quantile, not the quantile of the underlying
distribution and it seems this statistic is biased (sound to me close to
what happen with standard deviation, with the 1/n or 1/(n+1) factors).
> There is a compromise which would satisfy both sides, is not
> there? What about sorting and storing the sorted version of the array,
> once for all at the constructor level? That is what one would do anyway
> if speed was an issue (in one application, I need 5, 50, and 95-percentile
> of the same aray and sort it only once!).
This is what the user did, for 100 percentile evaluations for each sample.
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
Re: [math] speeding up percentile based statistics
Posted by Dimitri Pourbaix <po...@astro.ulb.ac.be>.
Hi,
If I understand correctly, the argument against the present implementation
is that if several percentiles are requested, they all require the sorting
of the array. On the other hand, the speed-up version would no longer
be mathematically correct, as a rough approximate of the pivot would be
adopted. There is a compromise which would satisfy both sides, is not
there? What about sorting and storing the sorted version of the array,
once for all at the constructor level? That is what one would do anyway
if speed was an issue (in one application, I need 5, 50, and 95-percentile
of the same aray and sort it only once!).
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
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 18/09/2010 17:39, Luc Maisonobe a écrit :
> Le 18/09/2010 17:36, Phil Steitz a écrit :
>> On 9/18/10 10:24 AM, Luc Maisonobe wrote:
>>> Le 18/09/2010 16:16, Phil Steitz a écrit :
>>>> On 9/17/10 3:19 PM, Luc Maisonobe wrote:
>>>>> Le 17/09/2010 19:55, Ted Dunning a écrit :
>>>>>> There are also on-line percentile estimation methods that require
>>>>>> only a
>>>>>> single pass over the data in order to get good estimates of several
>>>>>> quantile
>>>>>> at the same time.
>>>>>>
>>>>>> If you are interested in getting an estimate of some quantile of the
>>>>>> underlying distribution that generated your data then these on-line
>>>>>> methods
>>>>>> will give you an estimate that is very nearly as accurate as sorting
>>>>>> your
>>>>>> sample. Sorting gives you the exact quantiles of your sample, but
>>>>>> only an
>>>>>> estimate of the quantiles of your underlying distribution.
>>>>>>
>>>>>> There is a simplified implementation of this in Mahout along with
>>>>>> test cases
>>>>>> that demonstrate reasonable accuracy.
>>>>>>
>>>>>> These techniques are well described in the article: *Incremental
>>>>>> Quantile
>>>>>> Estimation for Massive
>>>>>> Tracking<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580>
>>>>>>
>>>>>>
>>>>>> *
>>>>>> *
>>>>>> *
>>>>>> *(available at
>>>>>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580 )*
>>>>>
>>>>> Thanks for the pointer, it looks interesting.
>>>>>
>>>>>> *
>>>>>> *
>>>>>> *Regarding the incremental selection method to find multiple
>>>>>> quantiles, I
>>>>>> think that you save a little bit if you are looking for a few
>>>>>> quantiles, but
>>>>>> the added complexity and special cases are going to make testing
>>>>>> difficult.
>>>>>> Wouldn't it be better to use one of the following strategies:*
>>>>>> *
>>>>>> *
>>>>>> *- keep a copy of the sorted data and if that copy is available, just
>>>>>> use
>>>>>> it. This cuts the cost of 100 quantiles probed incrementally to a
>>>>>> single
>>>>>> sort.
>>>>>
>>>>> This is exactly what this user did: put the sort out of the loop.
>>>>>
>>>>>> Moreover, since sort is n log n without a radix sort, then the
>>>>>> increment selection algorithm can only win if 100< log n which is
>>>>>> pretty
>>>>>> unlikely.*
>>>>>
>>>>> I don't understand. Partition-based selection algorithms are basically
>>>>> partition-based sort algorithm where we recurse in only one of the
>>>>> partition once the pivot has been chosen. Subsequent calls therefore
>>>>> don't restart from an array of size n but from smaller sub-arrays, has
>>>>> the pivot can be saved (at least the top level ones). If at the end the
>>>>> number of selections is so high the array ends up to be completely
>>>>> sorted, the total cost is probably not much higher than what an initial
>>>>> sort would have done. It will be higher since their are some
>>>>> bookkeeping
>>>>> to do, but not so much higher I think. Doing one call corresponds to
>>>>> resuming the partial sort from the state resulting from previous calls.
>>>>>
>>>>> Did I miss something ?
>>>>>
>>>>>
>>>>>> *
>>>>>> *
>>>>>> *- add a method to probe multiple quantiles at the same time. This
>>>>>> potentially uses less memory than the first approach, but is
>>>>>> dependent on
>>>>>> the user calling the right method.*
>>>>>
>>>>> Since there are different use case, having several methods seems
>>>>> fair. A
>>>>> multiple quantiles method is a good idea.
>>>>>
>>>>>> *
>>>>>> *
>>>>>> *- use the on-line algorithm mentioned above with two passes, one to
>>>>>> estimate the quantiles of interest, a second to refine the estimate
>>>>>> using
>>>>>> the actual data. This allows the multiple probe method to be linear
>>>>>> in time
>>>>>> and should give you exact sample quantiles. It doesn't help the
>>>>>> repeated
>>>>>> probe problem.*
>>>>>
>>>>> I'm not sure I understand well. However, the on-line method by itself
>>>>> would be an interesting addition. It would allow quantiles computation
>>>>> with the Storeless versions of our classes.
>>>>
>>>> +1 - definitely valuable for the storeless case.
>>>>
>>>> I need to think about this some more / see some patches; but my initial
>>>> reaction is that we can get a big bang from just doing what the user did
>>>> (caching the sorted array and inserting into it when addValue is called)
>>>> for the data-in-memory impls. I would suggest implementing that for for
>>>> Percentile itself (taking care to handle addValue and rolling windows
>>>> correctly) and DescriptiveStatistics;
>>>
>>> This would however handle only the multiple quantiles use case, not the
>>> case where only one quantile is computed that could be provided with a
>>> selection in O(n) rather than a sort in O(n ln(n)).
>>>
>>
>> Correct. Ideal would be to do the sort incrementally as you describe
>> for the data-in-memory impl. Would be tricky to implement in
>> Percentile, given array index parameters and the need to handle addValue
>> and window in DescriptiveStatistics; but this should be doable.
>>
>> Lets open 2 JIRAs for this - one straight performance improvement for
>> Percentile and the other for a storeless percentile estimator.
>
> OK. I'll open them in a few minutes.
The issues are <https://issues.apache.org/jira/browse/MATH-417> and
<https://issues.apache.org/jira/browse/MATH-418>. I have set the target
version to 2.2 for the first one to to 3.0 for the second one.
I'll give a look at the first one after finishing my current work
(implementing some new random generators).
Luc
>
> Luc
>
>>
>> Phil
>>
>>
>>> Luc
>>>
>>>> but add a new (storelesss)
>>>> statistic based on an incremental quantile estimation algorithm and make
>>>> this accessible via the storeless aggregate, SummaryStatistics. It
>>>> might be interesting to include this optionally with
>>>> DescriptiveStatistics as well, so that in the rolling window case you
>>>> could compare the current window distribution to the full sample.
>>>>
>>>> Phil
>>>>
>>>>
>>>>>
>>>>> Luc
>>>>>
>>>>>> *
>>>>>> *
>>>>>> On Fri, Sep 17, 2010 at 10:34 AM, Luc
>>>>>> Maisonobe<Lu...@free.fr>wrote:
>>>>>>
>>>>>>> Hi all,
>>>>>>>
>>>>>>> During a recent face to face discussion with some commons-math users
>>>>>>> from a large project, it appeared one implementation choice for
>>>>>>> Percentile statistics was a huge performance bottleneck.
>>>>>>>
>>>>>>> When the Percentile.evaluate method is called, the sample array is
>>>>>>> copied and sorted. In one use case, 100 calls were made for each
>>>>>>> sample,
>>>>>>> so the same array was sorted 100 times. In another use case, only one
>>>>>>> call is made (typically to compute the median) but the user wondered
>>>>>>> why
>>>>>>> the array should be completely sorted. In fact, using a selection
>>>>>>> algorithm instead of a sorting algorithm would be sufficient.
>>>>>>>
>>>>>>> I would like to have you opinion about providing a different evaluate
>>>>>>> method that would process an array provided previously and use only
>>>>>>> selections to provide the percentile. Consider for example the
>>>>>>> following
>>>>>>> input array:
>>>>>>>
>>>>>>> [ -6, 8, 4, -5, 0, 2, 7 ]
>>>>>>>
>>>>>>> If we first as for the median, a selection algorithm may
>>>>>>> reorganize the
>>>>>>> array as:
>>>>>>>
>>>>>>> [ -6, 0, -5, 2, 8, 4, 7 ]
>>>>>>>
>>>>>>> were the left part is smaller than the central element, the right
>>>>>>> part
>>>>>>> is larger and hence the central element 2 is known to be the median.
>>>>>>>
>>>>>>> Then we ask for another value, the 25% percentile. Since the object
>>>>>>> already knows the smaller elements are in the left part, it can use a
>>>>>>> select algorithm on the 3 elements left part and extract the value -5
>>>>>>> without even trying to sort the upper part of the array.
>>>>>>>
>>>>>>> What do you think ?
>>>>>>>
>>>>>>> Luc
>>>>>>>
>>>>>>> ---------------------------------------------------------------------
>>>>>>> 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
>>>>>
>>>>
>>>>
>>>> ---------------------------------------------------------------------
>>>> 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
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 18/09/2010 17:36, Phil Steitz a écrit :
> On 9/18/10 10:24 AM, Luc Maisonobe wrote:
>> Le 18/09/2010 16:16, Phil Steitz a écrit :
>>> On 9/17/10 3:19 PM, Luc Maisonobe wrote:
>>>> Le 17/09/2010 19:55, Ted Dunning a écrit :
>>>>> There are also on-line percentile estimation methods that require
>>>>> only a
>>>>> single pass over the data in order to get good estimates of several
>>>>> quantile
>>>>> at the same time.
>>>>>
>>>>> If you are interested in getting an estimate of some quantile of the
>>>>> underlying distribution that generated your data then these on-line
>>>>> methods
>>>>> will give you an estimate that is very nearly as accurate as sorting
>>>>> your
>>>>> sample. Sorting gives you the exact quantiles of your sample, but
>>>>> only an
>>>>> estimate of the quantiles of your underlying distribution.
>>>>>
>>>>> There is a simplified implementation of this in Mahout along with
>>>>> test cases
>>>>> that demonstrate reasonable accuracy.
>>>>>
>>>>> These techniques are well described in the article: *Incremental
>>>>> Quantile
>>>>> Estimation for Massive
>>>>> Tracking<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580>
>>>>>
>>>>>
>>>>> *
>>>>> *
>>>>> *
>>>>> *(available at
>>>>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580 )*
>>>>
>>>> Thanks for the pointer, it looks interesting.
>>>>
>>>>> *
>>>>> *
>>>>> *Regarding the incremental selection method to find multiple
>>>>> quantiles, I
>>>>> think that you save a little bit if you are looking for a few
>>>>> quantiles, but
>>>>> the added complexity and special cases are going to make testing
>>>>> difficult.
>>>>> Wouldn't it be better to use one of the following strategies:*
>>>>> *
>>>>> *
>>>>> *- keep a copy of the sorted data and if that copy is available, just
>>>>> use
>>>>> it. This cuts the cost of 100 quantiles probed incrementally to a
>>>>> single
>>>>> sort.
>>>>
>>>> This is exactly what this user did: put the sort out of the loop.
>>>>
>>>>> Moreover, since sort is n log n without a radix sort, then the
>>>>> increment selection algorithm can only win if 100< log n which is
>>>>> pretty
>>>>> unlikely.*
>>>>
>>>> I don't understand. Partition-based selection algorithms are basically
>>>> partition-based sort algorithm where we recurse in only one of the
>>>> partition once the pivot has been chosen. Subsequent calls therefore
>>>> don't restart from an array of size n but from smaller sub-arrays, has
>>>> the pivot can be saved (at least the top level ones). If at the end the
>>>> number of selections is so high the array ends up to be completely
>>>> sorted, the total cost is probably not much higher than what an initial
>>>> sort would have done. It will be higher since their are some
>>>> bookkeeping
>>>> to do, but not so much higher I think. Doing one call corresponds to
>>>> resuming the partial sort from the state resulting from previous calls.
>>>>
>>>> Did I miss something ?
>>>>
>>>>
>>>>> *
>>>>> *
>>>>> *- add a method to probe multiple quantiles at the same time. This
>>>>> potentially uses less memory than the first approach, but is
>>>>> dependent on
>>>>> the user calling the right method.*
>>>>
>>>> Since there are different use case, having several methods seems
>>>> fair. A
>>>> multiple quantiles method is a good idea.
>>>>
>>>>> *
>>>>> *
>>>>> *- use the on-line algorithm mentioned above with two passes, one to
>>>>> estimate the quantiles of interest, a second to refine the estimate
>>>>> using
>>>>> the actual data. This allows the multiple probe method to be linear
>>>>> in time
>>>>> and should give you exact sample quantiles. It doesn't help the
>>>>> repeated
>>>>> probe problem.*
>>>>
>>>> I'm not sure I understand well. However, the on-line method by itself
>>>> would be an interesting addition. It would allow quantiles computation
>>>> with the Storeless versions of our classes.
>>>
>>> +1 - definitely valuable for the storeless case.
>>>
>>> I need to think about this some more / see some patches; but my initial
>>> reaction is that we can get a big bang from just doing what the user did
>>> (caching the sorted array and inserting into it when addValue is called)
>>> for the data-in-memory impls. I would suggest implementing that for for
>>> Percentile itself (taking care to handle addValue and rolling windows
>>> correctly) and DescriptiveStatistics;
>>
>> This would however handle only the multiple quantiles use case, not the
>> case where only one quantile is computed that could be provided with a
>> selection in O(n) rather than a sort in O(n ln(n)).
>>
>
> Correct. Ideal would be to do the sort incrementally as you describe
> for the data-in-memory impl. Would be tricky to implement in
> Percentile, given array index parameters and the need to handle addValue
> and window in DescriptiveStatistics; but this should be doable.
>
> Lets open 2 JIRAs for this - one straight performance improvement for
> Percentile and the other for a storeless percentile estimator.
OK. I'll open them in a few minutes.
Luc
>
> Phil
>
>
>> Luc
>>
>>> but add a new (storelesss)
>>> statistic based on an incremental quantile estimation algorithm and make
>>> this accessible via the storeless aggregate, SummaryStatistics. It
>>> might be interesting to include this optionally with
>>> DescriptiveStatistics as well, so that in the rolling window case you
>>> could compare the current window distribution to the full sample.
>>>
>>> Phil
>>>
>>>
>>>>
>>>> Luc
>>>>
>>>>> *
>>>>> *
>>>>> On Fri, Sep 17, 2010 at 10:34 AM, Luc
>>>>> Maisonobe<Lu...@free.fr>wrote:
>>>>>
>>>>>> Hi all,
>>>>>>
>>>>>> During a recent face to face discussion with some commons-math users
>>>>>> from a large project, it appeared one implementation choice for
>>>>>> Percentile statistics was a huge performance bottleneck.
>>>>>>
>>>>>> When the Percentile.evaluate method is called, the sample array is
>>>>>> copied and sorted. In one use case, 100 calls were made for each
>>>>>> sample,
>>>>>> so the same array was sorted 100 times. In another use case, only one
>>>>>> call is made (typically to compute the median) but the user wondered
>>>>>> why
>>>>>> the array should be completely sorted. In fact, using a selection
>>>>>> algorithm instead of a sorting algorithm would be sufficient.
>>>>>>
>>>>>> I would like to have you opinion about providing a different evaluate
>>>>>> method that would process an array provided previously and use only
>>>>>> selections to provide the percentile. Consider for example the
>>>>>> following
>>>>>> input array:
>>>>>>
>>>>>> [ -6, 8, 4, -5, 0, 2, 7 ]
>>>>>>
>>>>>> If we first as for the median, a selection algorithm may
>>>>>> reorganize the
>>>>>> array as:
>>>>>>
>>>>>> [ -6, 0, -5, 2, 8, 4, 7 ]
>>>>>>
>>>>>> were the left part is smaller than the central element, the right
>>>>>> part
>>>>>> is larger and hence the central element 2 is known to be the median.
>>>>>>
>>>>>> Then we ask for another value, the 25% percentile. Since the object
>>>>>> already knows the smaller elements are in the left part, it can use a
>>>>>> select algorithm on the 3 elements left part and extract the value -5
>>>>>> without even trying to sort the upper part of the array.
>>>>>>
>>>>>> What do you think ?
>>>>>>
>>>>>> Luc
>>>>>>
>>>>>> ---------------------------------------------------------------------
>>>>>> 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
>>>>
>>>
>>>
>>> ---------------------------------------------------------------------
>>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Phil Steitz <ph...@gmail.com>.
On 9/18/10 10:24 AM, Luc Maisonobe wrote:
> Le 18/09/2010 16:16, Phil Steitz a écrit :
>> On 9/17/10 3:19 PM, Luc Maisonobe wrote:
>>> Le 17/09/2010 19:55, Ted Dunning a écrit :
>>>> There are also on-line percentile estimation methods that require only a
>>>> single pass over the data in order to get good estimates of several
>>>> quantile
>>>> at the same time.
>>>>
>>>> If you are interested in getting an estimate of some quantile of the
>>>> underlying distribution that generated your data then these on-line
>>>> methods
>>>> will give you an estimate that is very nearly as accurate as sorting
>>>> your
>>>> sample. Sorting gives you the exact quantiles of your sample, but
>>>> only an
>>>> estimate of the quantiles of your underlying distribution.
>>>>
>>>> There is a simplified implementation of this in Mahout along with
>>>> test cases
>>>> that demonstrate reasonable accuracy.
>>>>
>>>> These techniques are well described in the article: *Incremental
>>>> Quantile
>>>> Estimation for Massive
>>>> Tracking<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580>
>>>>
>>>> *
>>>> *
>>>> *
>>>> *(available at
>>>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580 )*
>>>
>>> Thanks for the pointer, it looks interesting.
>>>
>>>> *
>>>> *
>>>> *Regarding the incremental selection method to find multiple
>>>> quantiles, I
>>>> think that you save a little bit if you are looking for a few
>>>> quantiles, but
>>>> the added complexity and special cases are going to make testing
>>>> difficult.
>>>> Wouldn't it be better to use one of the following strategies:*
>>>> *
>>>> *
>>>> *- keep a copy of the sorted data and if that copy is available, just
>>>> use
>>>> it. This cuts the cost of 100 quantiles probed incrementally to a
>>>> single
>>>> sort.
>>>
>>> This is exactly what this user did: put the sort out of the loop.
>>>
>>>> Moreover, since sort is n log n without a radix sort, then the
>>>> increment selection algorithm can only win if 100< log n which is
>>>> pretty
>>>> unlikely.*
>>>
>>> I don't understand. Partition-based selection algorithms are basically
>>> partition-based sort algorithm where we recurse in only one of the
>>> partition once the pivot has been chosen. Subsequent calls therefore
>>> don't restart from an array of size n but from smaller sub-arrays, has
>>> the pivot can be saved (at least the top level ones). If at the end the
>>> number of selections is so high the array ends up to be completely
>>> sorted, the total cost is probably not much higher than what an initial
>>> sort would have done. It will be higher since their are some bookkeeping
>>> to do, but not so much higher I think. Doing one call corresponds to
>>> resuming the partial sort from the state resulting from previous calls.
>>>
>>> Did I miss something ?
>>>
>>>
>>>> *
>>>> *
>>>> *- add a method to probe multiple quantiles at the same time. This
>>>> potentially uses less memory than the first approach, but is
>>>> dependent on
>>>> the user calling the right method.*
>>>
>>> Since there are different use case, having several methods seems fair. A
>>> multiple quantiles method is a good idea.
>>>
>>>> *
>>>> *
>>>> *- use the on-line algorithm mentioned above with two passes, one to
>>>> estimate the quantiles of interest, a second to refine the estimate
>>>> using
>>>> the actual data. This allows the multiple probe method to be linear
>>>> in time
>>>> and should give you exact sample quantiles. It doesn't help the
>>>> repeated
>>>> probe problem.*
>>>
>>> I'm not sure I understand well. However, the on-line method by itself
>>> would be an interesting addition. It would allow quantiles computation
>>> with the Storeless versions of our classes.
>>
>> +1 - definitely valuable for the storeless case.
>>
>> I need to think about this some more / see some patches; but my initial
>> reaction is that we can get a big bang from just doing what the user did
>> (caching the sorted array and inserting into it when addValue is called)
>> for the data-in-memory impls. I would suggest implementing that for for
>> Percentile itself (taking care to handle addValue and rolling windows
>> correctly) and DescriptiveStatistics;
>
> This would however handle only the multiple quantiles use case, not the
> case where only one quantile is computed that could be provided with a
> selection in O(n) rather than a sort in O(n ln(n)).
>
Correct. Ideal would be to do the sort incrementally as you
describe for the data-in-memory impl. Would be tricky to implement
in Percentile, given array index parameters and the need to handle
addValue and window in DescriptiveStatistics; but this should be doable.
Lets open 2 JIRAs for this - one straight performance improvement
for Percentile and the other for a storeless percentile estimator.
Phil
> Luc
>
>> but add a new (storelesss)
>> statistic based on an incremental quantile estimation algorithm and make
>> this accessible via the storeless aggregate, SummaryStatistics. It
>> might be interesting to include this optionally with
>> DescriptiveStatistics as well, so that in the rolling window case you
>> could compare the current window distribution to the full sample.
>>
>> Phil
>>
>>
>>>
>>> Luc
>>>
>>>> *
>>>> *
>>>> On Fri, Sep 17, 2010 at 10:34 AM, Luc
>>>> Maisonobe<Lu...@free.fr>wrote:
>>>>
>>>>> Hi all,
>>>>>
>>>>> During a recent face to face discussion with some commons-math users
>>>>> from a large project, it appeared one implementation choice for
>>>>> Percentile statistics was a huge performance bottleneck.
>>>>>
>>>>> When the Percentile.evaluate method is called, the sample array is
>>>>> copied and sorted. In one use case, 100 calls were made for each
>>>>> sample,
>>>>> so the same array was sorted 100 times. In another use case, only one
>>>>> call is made (typically to compute the median) but the user wondered
>>>>> why
>>>>> the array should be completely sorted. In fact, using a selection
>>>>> algorithm instead of a sorting algorithm would be sufficient.
>>>>>
>>>>> I would like to have you opinion about providing a different evaluate
>>>>> method that would process an array provided previously and use only
>>>>> selections to provide the percentile. Consider for example the
>>>>> following
>>>>> input array:
>>>>>
>>>>> [ -6, 8, 4, -5, 0, 2, 7 ]
>>>>>
>>>>> If we first as for the median, a selection algorithm may reorganize the
>>>>> array as:
>>>>>
>>>>> [ -6, 0, -5, 2, 8, 4, 7 ]
>>>>>
>>>>> were the left part is smaller than the central element, the right part
>>>>> is larger and hence the central element 2 is known to be the median.
>>>>>
>>>>> Then we ask for another value, the 25% percentile. Since the object
>>>>> already knows the smaller elements are in the left part, it can use a
>>>>> select algorithm on the 3 elements left part and extract the value -5
>>>>> without even trying to sort the upper part of the array.
>>>>>
>>>>> What do you think ?
>>>>>
>>>>> Luc
>>>>>
>>>>> ---------------------------------------------------------------------
>>>>> 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
>>>
>>
>>
>> ---------------------------------------------------------------------
>> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 18/09/2010 16:16, Phil Steitz a écrit :
> On 9/17/10 3:19 PM, Luc Maisonobe wrote:
>> Le 17/09/2010 19:55, Ted Dunning a écrit :
>>> There are also on-line percentile estimation methods that require only a
>>> single pass over the data in order to get good estimates of several
>>> quantile
>>> at the same time.
>>>
>>> If you are interested in getting an estimate of some quantile of the
>>> underlying distribution that generated your data then these on-line
>>> methods
>>> will give you an estimate that is very nearly as accurate as sorting
>>> your
>>> sample. Sorting gives you the exact quantiles of your sample, but
>>> only an
>>> estimate of the quantiles of your underlying distribution.
>>>
>>> There is a simplified implementation of this in Mahout along with
>>> test cases
>>> that demonstrate reasonable accuracy.
>>>
>>> These techniques are well described in the article: *Incremental
>>> Quantile
>>> Estimation for Massive
>>> Tracking<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580>
>>>
>>> *
>>> *
>>> *
>>> *(available at
>>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580 )*
>>
>> Thanks for the pointer, it looks interesting.
>>
>>> *
>>> *
>>> *Regarding the incremental selection method to find multiple
>>> quantiles, I
>>> think that you save a little bit if you are looking for a few
>>> quantiles, but
>>> the added complexity and special cases are going to make testing
>>> difficult.
>>> Wouldn't it be better to use one of the following strategies:*
>>> *
>>> *
>>> *- keep a copy of the sorted data and if that copy is available, just
>>> use
>>> it. This cuts the cost of 100 quantiles probed incrementally to a
>>> single
>>> sort.
>>
>> This is exactly what this user did: put the sort out of the loop.
>>
>>> Moreover, since sort is n log n without a radix sort, then the
>>> increment selection algorithm can only win if 100< log n which is
>>> pretty
>>> unlikely.*
>>
>> I don't understand. Partition-based selection algorithms are basically
>> partition-based sort algorithm where we recurse in only one of the
>> partition once the pivot has been chosen. Subsequent calls therefore
>> don't restart from an array of size n but from smaller sub-arrays, has
>> the pivot can be saved (at least the top level ones). If at the end the
>> number of selections is so high the array ends up to be completely
>> sorted, the total cost is probably not much higher than what an initial
>> sort would have done. It will be higher since their are some bookkeeping
>> to do, but not so much higher I think. Doing one call corresponds to
>> resuming the partial sort from the state resulting from previous calls.
>>
>> Did I miss something ?
>>
>>
>>> *
>>> *
>>> *- add a method to probe multiple quantiles at the same time. This
>>> potentially uses less memory than the first approach, but is
>>> dependent on
>>> the user calling the right method.*
>>
>> Since there are different use case, having several methods seems fair. A
>> multiple quantiles method is a good idea.
>>
>>> *
>>> *
>>> *- use the on-line algorithm mentioned above with two passes, one to
>>> estimate the quantiles of interest, a second to refine the estimate
>>> using
>>> the actual data. This allows the multiple probe method to be linear
>>> in time
>>> and should give you exact sample quantiles. It doesn't help the
>>> repeated
>>> probe problem.*
>>
>> I'm not sure I understand well. However, the on-line method by itself
>> would be an interesting addition. It would allow quantiles computation
>> with the Storeless versions of our classes.
>
> +1 - definitely valuable for the storeless case.
>
> I need to think about this some more / see some patches; but my initial
> reaction is that we can get a big bang from just doing what the user did
> (caching the sorted array and inserting into it when addValue is called)
> for the data-in-memory impls. I would suggest implementing that for for
> Percentile itself (taking care to handle addValue and rolling windows
> correctly) and DescriptiveStatistics;
This would however handle only the multiple quantiles use case, not the
case where only one quantile is computed that could be provided with a
selection in O(n) rather than a sort in O(n ln(n)).
Luc
> but add a new (storelesss)
> statistic based on an incremental quantile estimation algorithm and make
> this accessible via the storeless aggregate, SummaryStatistics. It
> might be interesting to include this optionally with
> DescriptiveStatistics as well, so that in the rolling window case you
> could compare the current window distribution to the full sample.
>
> Phil
>
>
>>
>> Luc
>>
>>> *
>>> *
>>> On Fri, Sep 17, 2010 at 10:34 AM, Luc
>>> Maisonobe<Lu...@free.fr>wrote:
>>>
>>>> Hi all,
>>>>
>>>> During a recent face to face discussion with some commons-math users
>>>> from a large project, it appeared one implementation choice for
>>>> Percentile statistics was a huge performance bottleneck.
>>>>
>>>> When the Percentile.evaluate method is called, the sample array is
>>>> copied and sorted. In one use case, 100 calls were made for each
>>>> sample,
>>>> so the same array was sorted 100 times. In another use case, only one
>>>> call is made (typically to compute the median) but the user wondered
>>>> why
>>>> the array should be completely sorted. In fact, using a selection
>>>> algorithm instead of a sorting algorithm would be sufficient.
>>>>
>>>> I would like to have you opinion about providing a different evaluate
>>>> method that would process an array provided previously and use only
>>>> selections to provide the percentile. Consider for example the
>>>> following
>>>> input array:
>>>>
>>>> [ -6, 8, 4, -5, 0, 2, 7 ]
>>>>
>>>> If we first as for the median, a selection algorithm may reorganize the
>>>> array as:
>>>>
>>>> [ -6, 0, -5, 2, 8, 4, 7 ]
>>>>
>>>> were the left part is smaller than the central element, the right part
>>>> is larger and hence the central element 2 is known to be the median.
>>>>
>>>> Then we ask for another value, the 25% percentile. Since the object
>>>> already knows the smaller elements are in the left part, it can use a
>>>> select algorithm on the 3 elements left part and extract the value -5
>>>> without even trying to sort the upper part of the array.
>>>>
>>>> What do you think ?
>>>>
>>>> Luc
>>>>
>>>> ---------------------------------------------------------------------
>>>> 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
>>
>
>
> ---------------------------------------------------------------------
> 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
Re: [math] speeding up percentile based statistics
Posted by Phil Steitz <ph...@gmail.com>.
On 9/17/10 3:19 PM, Luc Maisonobe wrote:
> Le 17/09/2010 19:55, Ted Dunning a écrit :
>> There are also on-line percentile estimation methods that require only a
>> single pass over the data in order to get good estimates of several quantile
>> at the same time.
>>
>> If you are interested in getting an estimate of some quantile of the
>> underlying distribution that generated your data then these on-line methods
>> will give you an estimate that is very nearly as accurate as sorting your
>> sample. Sorting gives you the exact quantiles of your sample, but only an
>> estimate of the quantiles of your underlying distribution.
>>
>> There is a simplified implementation of this in Mahout along with test cases
>> that demonstrate reasonable accuracy.
>>
>> These techniques are well described in the article: *Incremental Quantile
>> Estimation for Massive
>> Tracking<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580>
>> *
>> *
>> *
>> *(available at
>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580 )*
>
> Thanks for the pointer, it looks interesting.
>
>> *
>> *
>> *Regarding the incremental selection method to find multiple quantiles, I
>> think that you save a little bit if you are looking for a few quantiles, but
>> the added complexity and special cases are going to make testing difficult.
>> Wouldn't it be better to use one of the following strategies:*
>> *
>> *
>> *- keep a copy of the sorted data and if that copy is available, just use
>> it. This cuts the cost of 100 quantiles probed incrementally to a single
>> sort.
>
> This is exactly what this user did: put the sort out of the loop.
>
>> Moreover, since sort is n log n without a radix sort, then the
>> increment selection algorithm can only win if 100< log n which is pretty
>> unlikely.*
>
> I don't understand. Partition-based selection algorithms are basically
> partition-based sort algorithm where we recurse in only one of the
> partition once the pivot has been chosen. Subsequent calls therefore
> don't restart from an array of size n but from smaller sub-arrays, has
> the pivot can be saved (at least the top level ones). If at the end the
> number of selections is so high the array ends up to be completely
> sorted, the total cost is probably not much higher than what an initial
> sort would have done. It will be higher since their are some bookkeeping
> to do, but not so much higher I think. Doing one call corresponds to
> resuming the partial sort from the state resulting from previous calls.
>
> Did I miss something ?
>
>
>> *
>> *
>> *- add a method to probe multiple quantiles at the same time. This
>> potentially uses less memory than the first approach, but is dependent on
>> the user calling the right method.*
>
> Since there are different use case, having several methods seems fair. A
> multiple quantiles method is a good idea.
>
>> *
>> *
>> *- use the on-line algorithm mentioned above with two passes, one to
>> estimate the quantiles of interest, a second to refine the estimate using
>> the actual data. This allows the multiple probe method to be linear in time
>> and should give you exact sample quantiles. It doesn't help the repeated
>> probe problem.*
>
> I'm not sure I understand well. However, the on-line method by itself
> would be an interesting addition. It would allow quantiles computation
> with the Storeless versions of our classes.
+1 - definitely valuable for the storeless case.
I need to think about this some more / see some patches; but my
initial reaction is that we can get a big bang from just doing what
the user did (caching the sorted array and inserting into it when
addValue is called) for the data-in-memory impls. I would suggest
implementing that for for Percentile itself (taking care to handle
addValue and rolling windows correctly) and DescriptiveStatistics;
but add a new (storelesss) statistic based on an incremental
quantile estimation algorithm and make this accessible via the
storeless aggregate, SummaryStatistics. It might be interesting to
include this optionally with DescriptiveStatistics as well, so that
in the rolling window case you could compare the current window
distribution to the full sample.
Phil
>
> Luc
>
>> *
>> *
>> On Fri, Sep 17, 2010 at 10:34 AM, Luc Maisonobe<Lu...@free.fr>wrote:
>>
>>> Hi all,
>>>
>>> During a recent face to face discussion with some commons-math users
>>> from a large project, it appeared one implementation choice for
>>> Percentile statistics was a huge performance bottleneck.
>>>
>>> When the Percentile.evaluate method is called, the sample array is
>>> copied and sorted. In one use case, 100 calls were made for each sample,
>>> so the same array was sorted 100 times. In another use case, only one
>>> call is made (typically to compute the median) but the user wondered why
>>> the array should be completely sorted. In fact, using a selection
>>> algorithm instead of a sorting algorithm would be sufficient.
>>>
>>> I would like to have you opinion about providing a different evaluate
>>> method that would process an array provided previously and use only
>>> selections to provide the percentile. Consider for example the following
>>> input array:
>>>
>>> [ -6, 8, 4, -5, 0, 2, 7 ]
>>>
>>> If we first as for the median, a selection algorithm may reorganize the
>>> array as:
>>>
>>> [ -6, 0, -5, 2, 8, 4, 7 ]
>>>
>>> were the left part is smaller than the central element, the right part
>>> is larger and hence the central element 2 is known to be the median.
>>>
>>> Then we ask for another value, the 25% percentile. Since the object
>>> already knows the smaller elements are in the left part, it can use a
>>> select algorithm on the 3 elements left part and extract the value -5
>>> without even trying to sort the upper part of the array.
>>>
>>> What do you think ?
>>>
>>> Luc
>>>
>>> ---------------------------------------------------------------------
>>> 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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] speeding up percentile based statistics
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 17/09/2010 19:55, Ted Dunning a écrit :
> There are also on-line percentile estimation methods that require only a
> single pass over the data in order to get good estimates of several quantile
> at the same time.
>
> If you are interested in getting an estimate of some quantile of the
> underlying distribution that generated your data then these on-line methods
> will give you an estimate that is very nearly as accurate as sorting your
> sample. Sorting gives you the exact quantiles of your sample, but only an
> estimate of the quantiles of your underlying distribution.
>
> There is a simplified implementation of this in Mahout along with test cases
> that demonstrate reasonable accuracy.
>
> These techniques are well described in the article: *Incremental Quantile
> Estimation for Massive
> Tracking<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580>
> *
> *
> *
> *(available at
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580 )*
Thanks for the pointer, it looks interesting.
> *
> *
> *Regarding the incremental selection method to find multiple quantiles, I
> think that you save a little bit if you are looking for a few quantiles, but
> the added complexity and special cases are going to make testing difficult.
> Wouldn't it be better to use one of the following strategies:*
> *
> *
> *- keep a copy of the sorted data and if that copy is available, just use
> it. This cuts the cost of 100 quantiles probed incrementally to a single
> sort.
This is exactly what this user did: put the sort out of the loop.
> Moreover, since sort is n log n without a radix sort, then the
> increment selection algorithm can only win if 100 < log n which is pretty
> unlikely.*
I don't understand. Partition-based selection algorithms are basically
partition-based sort algorithm where we recurse in only one of the
partition once the pivot has been chosen. Subsequent calls therefore
don't restart from an array of size n but from smaller sub-arrays, has
the pivot can be saved (at least the top level ones). If at the end the
number of selections is so high the array ends up to be completely
sorted, the total cost is probably not much higher than what an initial
sort would have done. It will be higher since their are some bookkeeping
to do, but not so much higher I think. Doing one call corresponds to
resuming the partial sort from the state resulting from previous calls.
Did I miss something ?
> *
> *
> *- add a method to probe multiple quantiles at the same time. This
> potentially uses less memory than the first approach, but is dependent on
> the user calling the right method.*
Since there are different use case, having several methods seems fair. A
multiple quantiles method is a good idea.
> *
> *
> *- use the on-line algorithm mentioned above with two passes, one to
> estimate the quantiles of interest, a second to refine the estimate using
> the actual data. This allows the multiple probe method to be linear in time
> and should give you exact sample quantiles. It doesn't help the repeated
> probe problem.*
I'm not sure I understand well. However, the on-line method by itself
would be an interesting addition. It would allow quantiles computation
with the Storeless versions of our classes.
Luc
> *
> *
> On Fri, Sep 17, 2010 at 10:34 AM, Luc Maisonobe <Lu...@free.fr>wrote:
>
>> Hi all,
>>
>> During a recent face to face discussion with some commons-math users
>> from a large project, it appeared one implementation choice for
>> Percentile statistics was a huge performance bottleneck.
>>
>> When the Percentile.evaluate method is called, the sample array is
>> copied and sorted. In one use case, 100 calls were made for each sample,
>> so the same array was sorted 100 times. In another use case, only one
>> call is made (typically to compute the median) but the user wondered why
>> the array should be completely sorted. In fact, using a selection
>> algorithm instead of a sorting algorithm would be sufficient.
>>
>> I would like to have you opinion about providing a different evaluate
>> method that would process an array provided previously and use only
>> selections to provide the percentile. Consider for example the following
>> input array:
>>
>> [ -6, 8, 4, -5, 0, 2, 7 ]
>>
>> If we first as for the median, a selection algorithm may reorganize the
>> array as:
>>
>> [ -6, 0, -5, 2, 8, 4, 7 ]
>>
>> were the left part is smaller than the central element, the right part
>> is larger and hence the central element 2 is known to be the median.
>>
>> Then we ask for another value, the 25% percentile. Since the object
>> already knows the smaller elements are in the left part, it can use a
>> select algorithm on the 3 elements left part and extract the value -5
>> without even trying to sort the upper part of the array.
>>
>> What do you think ?
>>
>> Luc
>>
>> ---------------------------------------------------------------------
>> 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
Re: [math] speeding up percentile based statistics
Posted by Ted Dunning <te...@gmail.com>.
There are also on-line percentile estimation methods that require only a
single pass over the data in order to get good estimates of several quantile
at the same time.
If you are interested in getting an estimate of some quantile of the
underlying distribution that generated your data then these on-line methods
will give you an estimate that is very nearly as accurate as sorting your
sample. Sorting gives you the exact quantiles of your sample, but only an
estimate of the quantiles of your underlying distribution.
There is a simplified implementation of this in Mahout along with test cases
that demonstrate reasonable accuracy.
These techniques are well described in the article: *Incremental Quantile
Estimation for Massive
Tracking<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580>
*
*
*
*(available at
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.1580 )*
*
*
*Regarding the incremental selection method to find multiple quantiles, I
think that you save a little bit if you are looking for a few quantiles, but
the added complexity and special cases are going to make testing difficult.
Wouldn't it be better to use one of the following strategies:*
*
*
*- keep a copy of the sorted data and if that copy is available, just use
it. This cuts the cost of 100 quantiles probed incrementally to a single
sort. Moreover, since sort is n log n without a radix sort, then the
increment selection algorithm can only win if 100 < log n which is pretty
unlikely.*
*
*
*- add a method to probe multiple quantiles at the same time. This
potentially uses less memory than the first approach, but is dependent on
the user calling the right method.*
*
*
*- use the on-line algorithm mentioned above with two passes, one to
estimate the quantiles of interest, a second to refine the estimate using
the actual data. This allows the multiple probe method to be linear in time
and should give you exact sample quantiles. It doesn't help the repeated
probe problem.*
*
*
On Fri, Sep 17, 2010 at 10:34 AM, Luc Maisonobe <Lu...@free.fr>wrote:
> Hi all,
>
> During a recent face to face discussion with some commons-math users
> from a large project, it appeared one implementation choice for
> Percentile statistics was a huge performance bottleneck.
>
> When the Percentile.evaluate method is called, the sample array is
> copied and sorted. In one use case, 100 calls were made for each sample,
> so the same array was sorted 100 times. In another use case, only one
> call is made (typically to compute the median) but the user wondered why
> the array should be completely sorted. In fact, using a selection
> algorithm instead of a sorting algorithm would be sufficient.
>
> I would like to have you opinion about providing a different evaluate
> method that would process an array provided previously and use only
> selections to provide the percentile. Consider for example the following
> input array:
>
> [ -6, 8, 4, -5, 0, 2, 7 ]
>
> If we first as for the median, a selection algorithm may reorganize the
> array as:
>
> [ -6, 0, -5, 2, 8, 4, 7 ]
>
> were the left part is smaller than the central element, the right part
> is larger and hence the central element 2 is known to be the median.
>
> Then we ask for another value, the 25% percentile. Since the object
> already knows the smaller elements are in the left part, it can use a
> select algorithm on the 3 elements left part and extract the value -5
> without even trying to sort the upper part of the array.
>
> What do you think ?
>
> Luc
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>