org.apache.commons.math.stat.descriptive.rank

## Class Percentile

- java.lang.Object
- - org.apache.commons.math.stat.descriptive.AbstractUnivariateStatistic
  - - org.apache.commons.math.stat.descriptive.rank.Percentile

All Implemented Interfaces:
  java.io.Serializable, UnivariateStatistic

Direct Known Subclasses:
  Median

    public class Percentile
    extends AbstractUnivariateStatistic
    implements java.io.Serializable

Provides percentile computation.

There are several commonly used methods for estimating percentiles (a.k.a. quantiles) based on sample data. For large samples, the different methods agree closely, but when sample sizes are small, different methods will give significantly different results. The algorithm implemented here works as follows:

1. Let `n` be the length of the (sorted) array and `0 < p <= 100` be the desired percentile.
2. If `n = 1` return the unique array element (regardless of the value of `p`); otherwise
3. Compute the estimated percentile position `pos = p * (n + 1) / 100` and the difference, `d` between `pos` and `floor(pos)` (i.e. the fractional part of `pos`). If `pos >= n` return the largest element in the array; otherwise
4. Let `lower` be the element in position `floor(pos)` in the array and let `upper` be the next element in the array. Return `lower + d * (upper - lower)`

To compute percentiles, the data must be at least partially ordered. Input arrays are copied and recursively partitioned using an ordering definition. The ordering used by `Arrays.sort(double[])` is the one determined by `Double.compareTo(Double)`. This ordering makes `Double.NaN` larger than any other value (including `Double.POSITIVE_INFINITY`). Therefore, for example, the median (50th percentile) of `{0, 1, 2, 3, 4, Double.NaN}` evaluates to `2.5.`

Since percentile estimation usually involves interpolation between array elements, arrays containing `NaN` or infinite values will often result in `NaN`or infinite values returned.``

Since 2.2, Percentile implementation uses only selection instead of complete sorting and caches selection algorithm state between calls to the various `evaluate` methods when several percentiles are to be computed on the same data. This greatly improves efficiency, both for single percentile and multiple percentiles computations. However, it also induces a need to be sure the data at one call to `evaluate` is the same as the data with the cached algorithm state from the previous calls. Percentile does this by checking the array reference itself and a checksum of its content by default. If the user already knows he calls `evaluate` on an immutable array, he can save the checking time by calling the `evaluate` methods that do not

Note that this implementation is not synchronized. If multiple threads access an instance of this class concurrently, and at least one of the threads invokes the `increment()` or `clear()` method, it must be synchronized externally.

Version:
  $Revision: 1006299 $ $Date: 2010-10-10 16:47:17 +0200 (dim. 10 oct. 2010) $
See Also:
  Serialized Form

### Field Summary

Fields
`private int[]` `cachedPivots` Cached pivots.
`private static int` `MAX_CACHED_LEVELS` Maximum number of partitioning pivots cached (each level double the number of pivots).
`private static int` `MIN_SELECT_SIZE` Minimum size under which we use a simple insertion sort rather than Hoare's select.
`private double` `quantile` Determines what percentile is computed when evaluate() is activated with no quantile argument
`private static long` `serialVersionUID` Serializable version identifier

### Constructor Summary

Constructors
Constructor and Description
`Percentile()` Constructs a Percentile with a default quantile value of 50.0.
`Percentile(double p)` Constructs a Percentile with the specific quantile value.
`Percentile(Percentile original)` Copy constructor, creates a new `Percentile` identical to the `original`

### Method Summary

Methods
`Percentile` `copy()` Returns a copy of the statistic with the same internal state.
`static void` `copy(Percentile source, Percentile dest)` Copies source to dest.
`double` `evaluate(double p)` Returns the result of evaluating the statistic over the stored data.
`double` `evaluate(double[] values, double p)` Returns an estimate of the `p`th percentile of the values in the `values` array.
`double` `evaluate(double[] values, int start, int length)` Returns an estimate of the `quantile`th percentile of the designated values in the `values` array.
`double` `evaluate(double[] values, int begin, int length, double p)` Returns an estimate of the `p`th percentile of the values in the `values` array, starting with the element in (0-based) position `begin` in the array and including `length` values.
`double` `getQuantile()` Returns the value of the quantile field (determines what percentile is computed when evaluate() is called with no quantile argument).
`private void` `insertionSort(double[] work, int begin, int end)` Sort in place a (small) array slice using insertion sort
`(package private) int` `medianOf3(double[] work, int begin, int end)` Select a pivot index as the median of three
`private int` `partition(double[] work, int begin, int end, int pivot)` Partition an array slice around a pivot
`private double` `select(double[] work, int[] pivotsHeap, int k)` Select the kth smallest element from work array
`void` `setData(double[] values)` Set the data array.
`void` `setData(double[] values, int begin, int length)` Set the data array.
`void` `setQuantile(double p)` Sets the value of the quantile field (determines what percentile is computed when evaluate() is called with no quantile argument).

### Methods inherited from class org.apache.commons.math.stat.descriptive.AbstractUnivariateStatistic

`evaluate, evaluate, getData, getDataRef, test, test`

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

### Field Detail

#### serialVersionUID

    private static final long serialVersionUID

Serializable version identifier

See Also:
  Constant Field Values

#### MIN_SELECT_SIZE

    private static final int MIN_SELECT_SIZE

Minimum size under which we use a simple insertion sort rather than Hoare's select.

See Also:
  Constant Field Values

#### MAX_CACHED_LEVELS

    private static final int MAX_CACHED_LEVELS

Maximum number of partitioning pivots cached (each level double the number of pivots).

See Also:
  Constant Field Values

#### quantile

    private double quantile

Determines what percentile is computed when evaluate() is activated with no quantile argument

#### cachedPivots

    private int[] cachedPivots

Cached pivots.

### Constructor Detail

#### Percentile

    public Percentile()

Constructs a Percentile with a default quantile value of 50.0.

#### Percentile

    public Percentile(double p)

Constructs a Percentile with the specific quantile value.

Parameters:
  `p` - the quantile
Throws:
  `java.lang.IllegalArgumentException` - if p is not greater than 0 and less than or equal to 100

#### Percentile

    public Percentile(Percentile original)

Copy constructor, creates a new `Percentile` identical to the `original`

Parameters:
  `original` - the `Percentile` instance to copy

### Method Detail

#### setData

    public void setData(double[] values)

Set the data array.

The stored value is a copy of the parameter array, not the array itself

Overrides:
  `setData` in class `AbstractUnivariateStatistic`
Parameters:
  `values` - data array to store (may be null to remove stored data)
See Also:
  `AbstractUnivariateStatistic.evaluate()`

#### setData

    public void setData(double[] values,
               int begin,
               int length)

Set the data array.

Overrides:
  `setData` in class `AbstractUnivariateStatistic`
Parameters:
  `values` - data array to store
  `begin` - the index of the first element to include
  `length` - the number of elements to include
See Also:
  `AbstractUnivariateStatistic.evaluate()`

#### evaluate

    public double evaluate(double p)

Returns the result of evaluating the statistic over the stored data.

The stored array is the one which was set by previous calls to

Parameters:
  `p` - the percentile value to compute
Returns:
  the value of the statistic applied to the stored data

#### evaluate

    public double evaluate(double[] values,
                  double p)

Returns an estimate of the `p`th percentile of the values in the `values` array.

Calls to this method do not modify the internal `quantile` state of this statistic.

- Returns `Double.NaN` if `values` has length `0`
- Returns (for any value of `p`) `values[0]` if `values` has length `1`
- Throws `IllegalArgumentException` if `values` is null or p is not a valid quantile value (p must be greater than 0 and less than or equal to 100)

See `Percentile` for a description of the percentile estimation algorithm used.

Parameters:
  `values` - input array of values
  `p` - the percentile value to compute
Returns:
  the percentile value or Double.NaN if the array is empty
Throws:
  `java.lang.IllegalArgumentException` - if `values` is null or p is invalid

#### evaluate

    public double evaluate(double[] values,
                  int start,
                  int length)

Returns an estimate of the `quantile`th percentile of the designated values in the `values` array. The quantile estimated is determined by the `quantile` property.

- Returns `Double.NaN` if `length = 0`
- Returns (for any value of `quantile`) `values[begin]` if `length = 1`
- Throws `IllegalArgumentException` if `values` is null, or `start` or `length` is invalid

See `Percentile` for a description of the percentile estimation algorithm used.

Specified by:
  `evaluate` in interface `UnivariateStatistic`
Specified by:
  `evaluate` in class `AbstractUnivariateStatistic`
Parameters:
  `values` - the input array
  `start` - index of the first array element to include
  `length` - the number of elements to include
Returns:
  the percentile value
Throws:
  `java.lang.IllegalArgumentException` - if the parameters are not valid

#### evaluate

    public double evaluate(double[] values,
                  int begin,
                  int length,
                  double p)

Returns an estimate of the `p`th percentile of the values in the `values` array, starting with the element in (0-based) position `begin` in the array and including `length` values.

Calls to this method do not modify the internal `quantile` state of this statistic.

- Returns `Double.NaN` if `length = 0`
- Returns (for any value of `p`) `values[begin]` if `length = 1`
- Throws `IllegalArgumentException` if `values` is null , `begin` or `length` is invalid, or `p` is not a valid quantile value (p must be greater than 0 and less than or equal to 100)

See `Percentile` for a description of the percentile estimation algorithm used.

Parameters:
  `values` - array of input values
  `p` - the percentile to compute
  `begin` - the first (0-based) element to include in the computation
  `length` - the number of array elements to include
Returns:
  the percentile value
Throws:
  `java.lang.IllegalArgumentException` - if the parameters are not valid or the input array is null

#### select

    private double select(double[] work,
                int[] pivotsHeap,
                int k)

Select the kth smallest element from work array

Parameters:
  `work` - work array (will be reorganized during the call)
  `pivotsHeap` - set of pivot index corresponding to elements that are already at their sorted location, stored as an implicit heap (i.e. a sorted binary tree stored in a flat array, where the children of a node at index n are at indices 2n+1 for the left child and 2n+2 for the right child, with 0-based indices)
  `k` - index of the desired element
Returns:
  kth smallest element

#### medianOf3

    int medianOf3(double[] work,
                int begin,
                int end)

Select a pivot index as the median of three

Parameters:
  `work` - data array
  `begin` - index of the first element of the slice
  `end` - index after the last element of the slice
Returns:
  the index of the median element chosen between the first, the middle and the last element of the array slice

#### partition

    private int partition(double[] work,
                int begin,
                int end,
                int pivot)

Partition an array slice around a pivot

Partitioning exchanges array elements such that all elements smaller than pivot are before it and all elements larger than pivot are after it

Parameters:
  `work` - data array
  `begin` - index of the first element of the slice
  `end` - index after the last element of the slice
  `pivot` - initial index of the pivot
Returns:
  index of the pivot after partition

#### insertionSort

    private void insertionSort(double[] work,
                     int begin,
                     int end)

Sort in place a (small) array slice using insertion sort

Parameters:
  `work` - array to sort
  `begin` - index of the first element of the slice to sort
  `end` - index after the last element of the slice to sort

#### getQuantile

    public double getQuantile()

Returns the value of the quantile field (determines what percentile is computed when evaluate() is called with no quantile argument).

Returns:
  quantile

#### setQuantile

    public void setQuantile(double p)

Sets the value of the quantile field (determines what percentile is computed when evaluate() is called with no quantile argument).

Parameters:
  `p` - a value between 0 < p <= 100
Throws:
  `java.lang.IllegalArgumentException` - if p is not greater than 0 and less than or equal to 100

#### copy

    public Percentile copy()

Returns a copy of the statistic with the same internal state.

Specified by:
  `copy` in interface `UnivariateStatistic`
Specified by:
  `copy` in class `AbstractUnivariateStatistic`
Returns:
  a copy of the statistic

#### copy

    public static void copy(Percentile source,
            Percentile dest)

Copies source to dest.

Neither source nor dest can be null.

Parameters:
  `source` - Percentile to copy
  `dest` - Percentile to copy to
Throws:
  `java.lang.NullPointerException` - if either source or dest is null