| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.openejb.math.stat.descriptive.rank; |
| |
| import java.io.Serializable; |
| import java.util.Arrays; |
| |
| import org.apache.openejb.math.MathRuntimeException; |
| import org.apache.openejb.math.stat.descriptive.AbstractUnivariateStatistic; |
| |
| /** |
| * Provides percentile computation. |
| * <p> |
| * 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: |
| * <ol> |
| * <li>Let <code>n</code> be the length of the (sorted) array and |
| * <code>0 < p <= 100</code> be the desired percentile.</li> |
| * <li>If <code> n = 1 </code> return the unique array element (regardless of |
| * the value of <code>p</code>); otherwise </li> |
| * <li>Compute the estimated percentile position |
| * <code> pos = p * (n + 1) / 100</code> and the difference, <code>d</code> |
| * between <code>pos</code> and <code>floor(pos)</code> (i.e. the fractional |
| * part of <code>pos</code>). If <code>pos >= n</code> return the largest |
| * element in the array; otherwise</li> |
| * <li>Let <code>lower</code> be the element in position |
| * <code>floor(pos)</code> in the array and let <code>upper</code> be the |
| * next element in the array. Return <code>lower + d * (upper - lower)</code> |
| * </li> |
| * </ol></p> |
| * <p> |
| * To compute percentiles, the data must be (totally) ordered. Input arrays |
| * are copied and then sorted using {@link java.util.Arrays#sort(double[])}. |
| * The ordering used by <code>Arrays.sort(double[])</code> is the one determined |
| * by {@link java.lang.Double#compareTo(Double)}. This ordering makes |
| * <code>Double.NaN</code> larger than any other value (including |
| * <code>Double.POSITIVE_INFINITY</code>). Therefore, for example, the median |
| * (50th percentile) of |
| * <code>{0, 1, 2, 3, 4, Double.NaN}</code> evaluates to <code>2.5.</code></p> |
| * <p> |
| * Since percentile estimation usually involves interpolation between array |
| * elements, arrays containing <code>NaN</code> or infinite values will often |
| * result in <code>NaN<code> or infinite values returned.</p> |
| * <p> |
| * <strong>Note that this implementation is not synchronized.</strong> If |
| * multiple threads access an instance of this class concurrently, and at least |
| * one of the threads invokes the <code>increment()</code> or |
| * <code>clear()</code> method, it must be synchronized externally.</p> |
| * |
| * @version $Revision: 811685 $ $Date: 2009-09-05 10:36:48 -0700 (Sat, 05 Sep 2009) $ |
| */ |
| public class Percentile extends AbstractUnivariateStatistic implements Serializable { |
| |
| /** Serializable version identifier */ |
| private static final long serialVersionUID = -1231216485095130416L; |
| |
| /** Determines what percentile is computed when evaluate() is activated |
| * with no quantile argument */ |
| private double quantile = 0.0; |
| |
| /** |
| * Constructs a Percentile with a default quantile |
| * value of 50.0. |
| */ |
| public Percentile() { |
| this(50.0); |
| } |
| |
| /** |
| * Constructs a Percentile with the specific quantile value. |
| * @param p the quantile |
| * @throws IllegalArgumentException if p is not greater than 0 and less |
| * than or equal to 100 |
| */ |
| public Percentile(final double p) { |
| setQuantile(p); |
| } |
| |
| /** |
| * Copy constructor, creates a new {@code Percentile} identical |
| * to the {@code original} |
| * |
| * @param original the {@code Percentile} instance to copy |
| */ |
| public Percentile(Percentile original) { |
| copy(original, this); |
| } |
| |
| /** |
| * Returns an estimate of the <code>p</code>th percentile of the values |
| * in the <code>values</code> array. |
| * <p> |
| * Calls to this method do not modify the internal <code>quantile</code> |
| * state of this statistic.</p> |
| * <p> |
| * <ul> |
| * <li>Returns <code>Double.NaN</code> if <code>values</code> has length |
| * <code>0</code></li> |
| * <li>Returns (for any value of <code>p</code>) <code>values[0]</code> |
| * if <code>values</code> has length <code>1</code></li> |
| * <li>Throws <code>IllegalArgumentException</code> if <code>values</code> |
| * is null or p is not a valid quantile value (p must be greater than 0 |
| * and less than or equal to 100) </li> |
| * </ul></p> |
| * <p> |
| * See {@link Percentile} for a description of the percentile estimation |
| * algorithm used.</p> |
| * |
| * @param values input array of values |
| * @param p the percentile value to compute |
| * @return the percentile value or Double.NaN if the array is empty |
| * @throws IllegalArgumentException if <code>values</code> is null |
| * or p is invalid |
| */ |
| public double evaluate(final double[] values, final double p) { |
| test(values, 0, 0); |
| return evaluate(values, 0, values.length, p); |
| } |
| |
| /** |
| * Returns an estimate of the <code>quantile</code>th percentile of the |
| * designated values in the <code>values</code> array. The quantile |
| * estimated is determined by the <code>quantile</code> property. |
| * <p> |
| * <ul> |
| * <li>Returns <code>Double.NaN</code> if <code>length = 0</code></li> |
| * <li>Returns (for any value of <code>quantile</code>) |
| * <code>values[begin]</code> if <code>length = 1 </code></li> |
| * <li>Throws <code>IllegalArgumentException</code> if <code>values</code> |
| * is null, or <code>start</code> or <code>length</code> |
| * is invalid</li> |
| * </ul></p> |
| * <p> |
| * See {@link Percentile} for a description of the percentile estimation |
| * algorithm used.</p> |
| * |
| * @param values the input array |
| * @param start index of the first array element to include |
| * @param length the number of elements to include |
| * @return the percentile value |
| * @throws IllegalArgumentException if the parameters are not valid |
| * |
| */ |
| @Override |
| public double evaluate( final double[] values, final int start, final int length) { |
| return evaluate(values, start, length, quantile); |
| } |
| |
| /** |
| * Returns an estimate of the <code>p</code>th percentile of the values |
| * in the <code>values</code> array, starting with the element in (0-based) |
| * position <code>begin</code> in the array and including <code>length</code> |
| * values. |
| * <p> |
| * Calls to this method do not modify the internal <code>quantile</code> |
| * state of this statistic.</p> |
| * <p> |
| * <ul> |
| * <li>Returns <code>Double.NaN</code> if <code>length = 0</code></li> |
| * <li>Returns (for any value of <code>p</code>) <code>values[begin]</code> |
| * if <code>length = 1 </code></li> |
| * <li>Throws <code>IllegalArgumentException</code> if <code>values</code> |
| * is null , <code>begin</code> or <code>length</code> is invalid, or |
| * <code>p</code> is not a valid quantile value (p must be greater than 0 |
| * and less than or equal to 100)</li> |
| * </ul></p> |
| * <p> |
| * See {@link Percentile} for a description of the percentile estimation |
| * algorithm used.</p> |
| * |
| * @param values array of input values |
| * @param p the percentile to compute |
| * @param begin the first (0-based) element to include in the computation |
| * @param length the number of array elements to include |
| * @return the percentile value |
| * @throws IllegalArgumentException if the parameters are not valid or the |
| * input array is null |
| */ |
| public double evaluate(final double[] values, final int begin, |
| final int length, final double p) { |
| |
| test(values, begin, length); |
| |
| if ((p > 100) || (p <= 0)) { |
| throw MathRuntimeException.createIllegalArgumentException( |
| "out of bounds quantile value: {0}, must be in (0, 100]", p); |
| } |
| if (length == 0) { |
| return Double.NaN; |
| } |
| if (length == 1) { |
| return values[begin]; // always return single value for n = 1 |
| } |
| double n = length; |
| double pos = p * (n + 1) / 100; |
| double fpos = Math.floor(pos); |
| int intPos = (int) fpos; |
| double dif = pos - fpos; |
| double[] sorted = new double[length]; |
| System.arraycopy(values, begin, sorted, 0, length); |
| Arrays.sort(sorted); |
| |
| if (pos < 1) { |
| return sorted[0]; |
| } |
| if (pos >= n) { |
| return sorted[length - 1]; |
| } |
| double lower = sorted[intPos - 1]; |
| double upper = sorted[intPos]; |
| return lower + dif * (upper - lower); |
| } |
| |
| /** |
| * Returns the value of the quantile field (determines what percentile is |
| * computed when evaluate() is called with no quantile argument). |
| * |
| * @return quantile |
| */ |
| public double getQuantile() { |
| return quantile; |
| } |
| |
| /** |
| * Sets the value of the quantile field (determines what percentile is |
| * computed when evaluate() is called with no quantile argument). |
| * |
| * @param p a value between 0 < p <= 100 |
| * @throws IllegalArgumentException if p is not greater than 0 and less |
| * than or equal to 100 |
| */ |
| public void setQuantile(final double p) { |
| if (p <= 0 || p > 100) { |
| throw MathRuntimeException.createIllegalArgumentException( |
| "out of bounds quantile value: {0}, must be in (0, 100]", p); |
| } |
| quantile = p; |
| } |
| |
| /** |
| * {@inheritDoc} |
| */ |
| @Override |
| public Percentile copy() { |
| Percentile result = new Percentile(); |
| copy(this, result); |
| return result; |
| } |
| |
| /** |
| * Copies source to dest. |
| * <p>Neither source nor dest can be null.</p> |
| * |
| * @param source Percentile to copy |
| * @param dest Percentile to copy to |
| * @throws NullPointerException if either source or dest is null |
| */ |
| public static void copy(Percentile source, Percentile dest) { |
| dest.quantile = source.quantile; |
| } |
| |
| } |