| /* |
| * 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. |
| */ |
| 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. |
| */ |
| 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; |
| } |
| } |