001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.util;
019
020import org.apache.yetus.audience.InterfaceAudience;
021
022/**
023 * This class maintains mean and variation for any sequence of input provided to it. It is
024 * initialized with number of rolling periods which basically means the number of past inputs whose
025 * data will be considered to maintain mean and variation. It will use O(N) memory to maintain these
026 * statistics, where N is number of look up periods it was initialized with. If zero is passed
027 * during initialization then it will maintain mean and variance from the start. It will use O(1)
028 * memory only. But note that since it will maintain mean / variance from the start the statistics
029 * may behave like constants and may ignore short trends. All operations are O(1) except the
030 * initialization which is O(N).
031 */
032@InterfaceAudience.Private
033public class RollingStatCalculator {
034  private double currentSum;
035  private double currentSqrSum;
036  // Total number of data values whose statistic is currently present
037  private long numberOfDataValues;
038  private int rollingPeriod;
039  private int currentIndexPosition;
040  // to be used only if we have non-zero rolling period
041  private long[] dataValues;
042
043  /**
044   * Creates a RollingStatCalculator with given number of rolling periods. n
045   */
046  public RollingStatCalculator(int rollingPeriod) {
047    this.rollingPeriod = rollingPeriod;
048    this.dataValues = fillWithZeros(rollingPeriod);
049    this.currentSum = 0.0;
050    this.currentSqrSum = 0.0;
051    this.currentIndexPosition = 0;
052    this.numberOfDataValues = 0;
053  }
054
055  /**
056   * Inserts given data value to array of data values to be considered for statistics calculation n
057   */
058  public void insertDataValue(long data) {
059    // if current number of data points already equals rolling period and rolling period is
060    // non-zero then remove one data and update the statistics
061    if (numberOfDataValues >= rollingPeriod && rollingPeriod > 0) {
062      this.removeData(dataValues[currentIndexPosition]);
063    }
064    numberOfDataValues++;
065    currentSum = currentSum + (double) data;
066    currentSqrSum = currentSqrSum + ((double) data * data);
067    if (rollingPeriod > 0) {
068      dataValues[currentIndexPosition] = data;
069      currentIndexPosition = (currentIndexPosition + 1) % rollingPeriod;
070    }
071  }
072
073  /**
074   * Update the statistics after removing the given data value n
075   */
076  private void removeData(long data) {
077    currentSum = currentSum - (double) data;
078    currentSqrSum = currentSqrSum - ((double) data * data);
079    numberOfDataValues--;
080  }
081
082  /** Returns mean of the data values that are in the current list of data values */
083  public double getMean() {
084    return this.currentSum / (double) numberOfDataValues;
085  }
086
087  /** Returns deviation of the data values that are in the current list of data values */
088  public double getDeviation() {
089    double variance = (currentSqrSum - (currentSum * currentSum) / (double) (numberOfDataValues))
090      / numberOfDataValues;
091    return Math.sqrt(variance);
092  }
093
094  /**
095   * n * @return an array of given size initialized with zeros
096   */
097  private long[] fillWithZeros(int size) {
098    long[] zeros = new long[size];
099    for (int i = 0; i < size; i++) {
100      zeros[i] = 0L;
101    }
102    return zeros;
103  }
104}