Java example source code file (QuantilesAlgorithm.java)

This example Java source code file (QuantilesAlgorithm.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

choose, collection, double, end, indexes, insert, map, math, override, partitioning, pointers, quantilesalgorithm, quickselect, sorting, target, util

The QuantilesAlgorithm.java Java example source code

/*
 * Copyright (C) 2014 The Guava Authors
 *
 * Licensed 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 com.google.common.math;

import com.google.common.collect.ImmutableMap;

import java.math.RoundingMode;
import java.util.Arrays;
import java.util.Collection;
import java.util.Map;

/**
 * Enumerates several algorithms providing equivalent functionality to {@link Quantiles}, for use in
 * {@link QuantilesBenchmark}. These algorithms each calculate either a single quantile or multiple
 * quantiles. All algorithms modify the dataset they are given (the cost of a copy to avoid this
 * will be constant across algorithms).
 *
 * @author Pete Gillin
 * @since 20.0
 */
enum QuantilesAlgorithm {

  /**
   * Sorts the dataset, and picks values from it. When computing multiple quantiles, we sort once
   * and pick multiple values.
   *
   * <p>This is basically equivalent to the legacy {@code com.google.math.Sample}, except that does
   * a copy whereas this is in-place.
   */
  SORTING {

    @Override
    double singleQuantile(int index, int scale, double[] dataset) {
      Arrays.sort(dataset);
      return singleQuantileFromSorted(index, scale, dataset);
    }

    @Override
    Map<Integer, Double> multipleQuantiles(
        Collection<Integer> indexes, int scale, double[] dataset) {
      Arrays.sort(dataset);
      ImmutableMap.Builder<Integer, Double> builder = ImmutableMap.builder();
      for (int index : indexes) {
        builder.put(index, singleQuantileFromSorted(index, scale, dataset));
      }
      return builder.build();
    }

    private double singleQuantileFromSorted(int index, int scale, double[] dataset) {
      long numerator = (long) index * (dataset.length - 1);
      int positionFloor = (int) LongMath.divide(numerator, scale, RoundingMode.DOWN);
      int remainder = (int) (numerator - positionFloor * scale);
      if (remainder == 0) {
        return dataset[positionFloor];
      } else {
        double positionFrac = (double) remainder / scale;
        return dataset[positionFloor]
            + positionFrac * (dataset[positionFloor + 1] - dataset[positionFloor]);
      }
    }
  },

  /**
   * Uses quickselect. When calculating multiple quantiles, each quickselect starts from scratch.
   *
   * <p>This is basically equivalent to the legacy {@code com.google.math.Rank}.
   */
  QUICKSELECT {

    @Override
    double singleQuantile(int index, int scale, double[] dataset) {
      long numerator = (long) index * (dataset.length - 1);
      int positionFloor = (int) LongMath.divide(numerator, scale, RoundingMode.DOWN);
      int remainder = (int) (numerator - positionFloor * scale);
      double percentileFloor = select(positionFloor, dataset);
      if (remainder == 0) {
        return percentileFloor;
      } else {
        double percentileCeiling = getMinValue(dataset, positionFloor + 1);
        double positionFrac = (double) remainder / scale;
        return percentileFloor
            + positionFrac * (percentileCeiling - percentileFloor);
      }
    }

    @Override
    Map<Integer, Double> multipleQuantiles(
        Collection<Integer> indexes, int scale, double[] dataset) {
      ImmutableMap.Builder<Integer, Double> builder = ImmutableMap.builder();
      for (int index : indexes) {
        builder.put(index, singleQuantile(index, scale, dataset));
      }
      return builder.build();
    }
  },

  /**
   * Uses {@link Quantiles}.
   */
  TARGET {

    @Override
    double singleQuantile(int index, int scale, double[] dataset) {
      return Quantiles.scale(scale).index(index).computeInPlace(dataset);
    }

    @Override
    Map<Integer, Double> multipleQuantiles(
        Collection<Integer> indexes, int scale, double[] dataset) {
      return Quantiles.scale(scale).indexes(indexes).computeInPlace(dataset);
    }
  },
  ;

  /**
   * Calculates a single quantile. Equivalent to
   * {@code Quantiles.scale(scale).index(index).computeInPlace(dataset)}.
   */
  abstract double singleQuantile(int index, int scale, double[] dataset);

  /**
   * Calculates multiple quantiles. Equivalent to
   * {@code Quantiles.scale(scale).indexes(indexes).computeInPlace(dataset)}.
   */
  abstract Map<Integer, Double> multipleQuantiles(
      Collection<Integer> indexes, int scale, double[] dataset);

  static double getMinValue(double[] array, int from) {
    // This is basically a copy of com.google.math.Rank#getMinValue, with a small change in the
    // method signature: we always search to the end of the array.
    int min = from;
    for (int i = from + 1; i < array.length; i++) {
      if (array[min] > array[i]) {
        min = i;
      }
    }
    return array[min];
  }

  static double select(int k, double[] array) {
    // This is basically a copy of com.google.math.Rank#select, with a small change in the method
    // signature: we make k 0-based rather than 1-based; and we drop from and to, and always work on
    // the whole array.
    int from = 0;
    int to = array.length - 1;

    while (true) {
      if (to <= from + 1) {
        // Two or less elements left.
        if (to == from + 1 && array[to] < array[from]) {
          // Exactly two elements left.
          swap(array, from, to);
        }
        return array[k];
      } else {
        int midIndex = (from + to) >>> 1;
        // Choose the median of the elements at the from, to and mid indexes,
        // and rearrange so that array[from]<=array[from+1], and
        // array[to] => array[from + 1].

        swap(array, midIndex, from + 1);

        if (array[from] > array[to]) {
          swap(array, from, to);
        }
        if (array[from + 1] > array[to]) {
          swap(array, from + 1, to);
        }
        if (array[from] > array[from + 1]) {
          swap(array, from, from + 1);
        }

        // Perform a partition with the selected median.
        int low = from + 1, high = to; // Indexes for partitioning.
        double partition = array[from + 1]; // Choose partitioning element.
        while (true) {
          // Skip the elements smaller than the partition.
          do {
            low++;
          } while (array[low] < partition);

          // Skip the elements larger than the partition.
          do {
            high--;
          } while (array[high] > partition);
          if (high < low) {
            break; // Pointers crossed. Partitioning complete.
          }
          swap(array, low, high); // End of innermost loop.
        }
        array[from + 1] = array[high]; // Insert partitioning element.
        array[high] = partition;

        // Continue the partition that contains the kth element.
        if (high >= k) {
          to = high - 1;
        }
        if (high <= k) {
          from = low;
        }
      }
    }
  }

  private static void swap(double[] array, int i, int j) {
    // This is a copy of com.google.math.Rank#swap.
    double temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}