You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by le...@apache.org on 2019/10/16 16:07:18 UTC
[incubator-datasketches-characterization] branch master updated
(3dbfc72 -> 75837ea)
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-characterization.git.
from 3dbfc72 Reformat
new 0659fdd Change moment sketch dependency to jar.
new 75837ea cleanup Druid HLL, Histogram, Quantiles testing.
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
pom.xml | 69 +-
.../hll/DruidHllAccuracyProfile.java | 5 +-
.../hll/DruidHllMergeAccuracyProfile.java | 5 +-
.../hll/druidhll/ByteBitLookup.java | 288 ----
.../hll/druidhll/HyperLogLogCollector.java | 792 ---------
.../hll/druidhll/HyperLogLogHash.java | 65 -
.../druidhll/VersionOneHyperLogLogCollector.java | 142 --
.../druidhll/VersionZeroHyperLogLogCollector.java | 120 --
.../hll/druidhll/package-info.java | 10 -
.../quantiles/DruidAppHistStreamAProfile.java | 4 +-
.../quantiles/MSketchStreamAProfile.java | 3 +-
.../druidhistogram/ApproximateHistogram.java | 1704 --------------------
.../quantiles/druidhistogram/ArrayUtils.java | 65 -
.../quantiles/druidhistogram/Histogram.java | 102 --
.../quantiles/druidhistogram/package-info.java | 10 -
.../quantiles/momentsketch/DMaxentLoss.java | 136 --
.../quantiles/momentsketch/MathUtil.java | 172 --
.../momentsketch/MomentSketchWrapper.java | 179 --
.../quantiles/momentsketch/MomentSolver.java | 189 ---
.../quantiles/momentsketch/MomentStruct.java | 113 --
.../quantiles/momentsketch/SimpleMomentSketch.java | 111 --
.../optimizer/FunctionWithHessian.java | 28 -
.../momentsketch/optimizer/GenericOptimizer.java | 15 -
.../momentsketch/optimizer/NewtonOptimizer.java | 160 --
.../momentsketch/optimizer/QuadraticPotential.java | 77 -
.../momentsketch/optimizer/package-info.java | 10 -
.../quantiles/momentsketch/package-info.java | 10 -
.../quantiles/momentsketch/DMaxentLossTest.java | 53 -
.../quantiles/momentsketch/MathUtilTest.java | 32 -
.../quantiles/momentsketch/MomentSolverTest.java | 104 --
.../momentsketch/SimpleMomentSketchTest.java | 28 -
.../optimizer/NewtonOptimizerTest.java | 23 -
.../optimizer/QuadraticPotentialTest.java | 21 -
33 files changed, 37 insertions(+), 4808 deletions(-)
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/hll/druidhll/ByteBitLookup.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogCollector.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogHash.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionOneHyperLogLogCollector.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionZeroHyperLogLogCollector.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/hll/druidhll/package-info.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ApproximateHistogram.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ArrayUtils.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/Histogram.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/package-info.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLoss.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtil.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolver.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentStruct.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketch.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/FunctionWithHessian.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/GenericOptimizer.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizer.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotential.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/package-info.java
delete mode 100644 src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java
delete mode 100644 src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLossTest.java
delete mode 100644 src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtilTest.java
delete mode 100644 src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolverTest.java
delete mode 100644 src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketchTest.java
delete mode 100644 src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizerTest.java
delete mode 100644 src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotentialTest.java
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-characterization] 01/02: Change moment
sketch dependency to jar.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-characterization.git
commit 0659fdd84af7c1b189f4dc811193cd972a36d689
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Oct 15 13:53:59 2019 -0700
Change moment sketch dependency to jar.
---
.../quantiles/momentsketch/DMaxentLoss.java | 136 ---------------
.../quantiles/momentsketch/MathUtil.java | 172 -------------------
.../momentsketch/MomentSketchWrapper.java | 6 +-
.../quantiles/momentsketch/MomentSolver.java | 189 ---------------------
.../quantiles/momentsketch/MomentStruct.java | 113 ------------
.../quantiles/momentsketch/SimpleMomentSketch.java | 111 ------------
.../optimizer/FunctionWithHessian.java | 28 ---
.../momentsketch/optimizer/GenericOptimizer.java | 15 --
.../momentsketch/optimizer/NewtonOptimizer.java | 160 -----------------
.../momentsketch/optimizer/QuadraticPotential.java | 77 ---------
.../momentsketch/optimizer/package-info.java | 10 --
.../quantiles/momentsketch/package-info.java | 18 +-
.../quantiles/momentsketch/DMaxentLossTest.java | 53 ------
.../quantiles/momentsketch/MathUtilTest.java | 32 ----
.../quantiles/momentsketch/MomentSolverTest.java | 104 ------------
.../momentsketch/SimpleMomentSketchTest.java | 28 ---
.../optimizer/NewtonOptimizerTest.java | 23 ---
.../optimizer/QuadraticPotentialTest.java | 21 ---
18 files changed, 21 insertions(+), 1275 deletions(-)
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLoss.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLoss.java
deleted file mode 100644
index a36240f..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLoss.java
+++ /dev/null
@@ -1,136 +0,0 @@
-
-package com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-
-import org.apache.commons.math3.util.FastMath;
-
-import com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer.FunctionWithHessian;
-
-/**
- * Maximum entropy loss function we can optimize using Newton's method
- * to estimate underlying distributions from their moments.
- *
- * This loss operates over distributions with a gridded support.
- */
-public class DMaxentLoss implements FunctionWithHessian {
- protected int dim;
- // Number of grid points
- protected int nGrid;
- // Number of moments
- protected double[] d_mus;
-
- // Grid point support of the distribution
- protected double[] xs;
- // Cached chebyshev polynomial values at grid points
- protected double[][] cpVals;
-
- // Coefficients for expression weights using chebyshev polynomials
- protected double[] lambd;
- protected double[] weights;
- protected double[] mus;
- protected double[] grad;
- protected double[][] hess;
-
- public DMaxentLoss(
- double[] d_mus,
- int nGrid) {
- dim = d_mus.length;
- this.nGrid = nGrid;
- this.d_mus = d_mus;
-
- xs = new double[nGrid];
- for (int i = 0; i < nGrid; i++) {
- xs[i] = ((i * 2.0) / (nGrid - 1)) - 1.0;
- }
-
- cpVals = new double[2 * dim][nGrid];
- for (int i = 0; i < nGrid; i++) {
- cpVals[0][i] = 1.0;
- cpVals[1][i] = xs[i];
- }
- for (int j = 2; j < (2 * dim); j++) {
- for (int i = 0; i < nGrid; i++) {
- cpVals[j][i] = (2 * xs[i] * cpVals[j - 1][i]) - cpVals[j - 2][i];
- }
- }
-
- int k = dim;
- weights = new double[nGrid];
- mus = new double[2 * k];
- grad = new double[k];
- hess = new double[k][k];
- }
-
- public void setLambd(double[] newLambd) {
- lambd = newLambd;
- }
-
- @Override
- public void computeOnlyValue(double[] point, double tol) {
- computeAll(point, tol);
- }
-
- @Override
- public void computeAll(double[] point, double tol) {
- setLambd(point);
- for (int i = 0; i < nGrid; i++) {
- double sum = 0.0;
- for (int j = 0; j < dim; j++) {
- sum += lambd[j] * cpVals[j][i];
- }
- weights[i] = FastMath.exp(sum);
- }
- for (int i = 0; i < (2 * dim); i++) {
- double sum = 0.0;
- for (int j = 0; j < nGrid; j++) {
- sum += cpVals[i][j] * weights[j];
- }
- mus[i] = sum;
- }
- for (int i = 0; i < dim; i++) {
- grad[i] = mus[i] - d_mus[i];
- }
-
- for (int i = 0; i < dim; i++) {
- for (int j = 0; j < dim; j++) {
- hess[i][j] = .5 * (mus[i + j] + mus[FastMath.abs(i - j)]);
- }
- }
- }
-
- public double[] getWeights() {
- return weights;
- }
-
- @Override
- public int dim() {
- return dim;
- }
-
- @Override
- public double getValue() {
- double sum = 0.0;
- int k = d_mus.length;
- for (int i = 0; i < k; i++) {
- sum += lambd[i] * d_mus[i];
- }
- return mus[0] - sum;
- }
-
- @Override
- public double[] getGradient() {
- return grad;
- }
-
- @Override
- public double[][] getHessian() {
- return hess;
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtil.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtil.java
deleted file mode 100644
index d554af2..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtil.java
+++ /dev/null
@@ -1,172 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-
-public class MathUtil {
- public static long[][] getBinomials(int m) {
- long[][] binoms = new long[m + 1][m + 1];
- for (int i = 0; i <= m; i++) {
- binoms[i][0] = 1;
- for (int j = 1; j <= i; j++) {
- binoms[i][j] = binoms[i - 1][j - 1] + binoms[i - 1][j];
- }
- }
- return binoms;
- }
-
- public static int[][] getChebyCoefficients(int k) {
- int[][] chebyCoeffs = new int[k + 1][k + 1];
- chebyCoeffs[0][0] = 1;
- if (k == 0) {
- return chebyCoeffs;
- }
- chebyCoeffs[1][1] = 1;
- for (int i = 2; i <= k; i++) {
- int[] c1 = chebyCoeffs[i - 1];
- int[] c2 = chebyCoeffs[i - 2];
- chebyCoeffs[i][0] = -c2[0];
- for (int j = 1; j <= i; j++) {
- chebyCoeffs[i][j] = (2 * c1[j - 1]) - c2[j];
- }
- }
- return chebyCoeffs;
- }
-
- /**
- * Calculate power sums for shifted values x' = (x-xc)/r
- *
- * @param powerSums original power sums
- * @param r scaling factor
- * @param xc translation value
- * @return shifted and scaled power sums
- */
- public static double[] shiftPowerSum(
- double[] powerSums,
- double r,
- double xc) {
- int k = powerSums.length - 1;
- double[] scaledPowerSums = new double[k + 1];
- // (-xc)**i
- double[] nxcPowers = new double[k + 1];
- // r**(-i)
- double[] rNegPowers = new double[k + 1];
- nxcPowers[0] = 1;
- rNegPowers[0] = 1;
- for (int i = 1; i <= k; i++) {
- nxcPowers[i] = nxcPowers[i - 1] * (-xc);
- rNegPowers[i] = rNegPowers[i - 1] / r;
- }
- long[][] mBinoms = MathUtil.getBinomials(k);
- for (int m = 0; m <= k; m++) {
- double sum = 0.0;
- for (int j = 0; j <= m; j++) {
- sum += mBinoms[m][j] * nxcPowers[m - j] * powerSums[j];
- }
- scaledPowerSums[m] = rNegPowers[m] * sum;
- }
- return scaledPowerSums;
- }
-
- public static double[] powerSumsToZerodMoments(
- double[] powerSums,
- double min,
- double max) {
- double r = (max - min) / 2;
- double xc = (max + min) / 2;
- double[] scaledPowerSums = MathUtil.shiftPowerSum(
- powerSums, r, xc);
- double count = scaledPowerSums[0];
- for (int i = 0; i < powerSums.length; i++) {
- scaledPowerSums[i] /= count;
- }
- return scaledPowerSums;
- }
-
- public static double[] powerSumsToChebyMoments(
- double min,
- double max,
- double[] powerSums) {
- int k = powerSums.length - 1;
- double r = (max - min) / 2;
- double xc = (max + min) / 2;
- // First rescale the variables so that they lie in [-1,1]
- double[] scaledPowerSums = MathUtil.shiftPowerSum(
- powerSums, r, xc);
-
- double count = powerSums[0];
- int[][] cCoeffs = MathUtil.getChebyCoefficients(k);
- // Then convert from power sums to chebyshev moments
- double[] scaledChebyMoments = new double[k + 1];
- for (int i = 0; i <= k; i++) {
- double sum = 0.0;
- for (int j = 0; j <= i; j++) {
- sum += cCoeffs[i][j] * scaledPowerSums[j];
- }
- scaledChebyMoments[i] = sum / count;
- }
-
- return scaledChebyMoments;
- }
-
- public static double arrayMean(double[] xs) {
- double sum = 0.0;
- for (double x : xs) {
- sum += x;
- }
- return sum / xs.length;
- }
-
- public static void calcPowers(double x, double[] powers) {
- int n = powers.length;
- double curPow = 1.0;
- for (int i = 0; i < n; i++) {
- powers[i] = curPow;
- curPow *= x;
- }
- return;
- }
-
- public static double entropy(double[] ps) {
- double h = 0.0;
- for (double p : ps) {
- if (p > 0.0) {
- h -= p * Math.log(p);
- }
- }
- return h;
- }
-
- public static double getMSE(double[] error) {
- double sum = 0.0;
- for (int i = 0; i < error.length; i++) {
- sum += error[i] * error[i];
- }
- return sum / error.length;
- }
-
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java
index c5da8a7..5f5d0c8 100644
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java
+++ b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java
@@ -30,6 +30,10 @@ package com.yahoo.sketches.characterization.quantiles.momentsketch;
import java.nio.ByteBuffer;
+import com.github.stanfordfuturedata.momentsketch.MomentSolver;
+import com.github.stanfordfuturedata.momentsketch.MomentStruct;
+
+
/**
* Class for wrapping the operations of the moments sketch for use in
* the moment sketch aggregator
@@ -114,7 +118,7 @@ public class MomentSketchWrapper {
/**
* Estimates quantiles given the statistics in a moments sketch.
- *
+ *
* @param fractions real values between [0,1] for which we want to estimate quantiles
*
* @return estimated quantiles.
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolver.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolver.java
deleted file mode 100644
index 6be1b81..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolver.java
+++ /dev/null
@@ -1,189 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-//CHECKSTYLE.OFF: EmptyLineSeparator
-
-import com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer.GenericOptimizer;
-import com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer.NewtonOptimizer;
-
-/**
- * Interface for estimating quantiles given the statistics in a MomentStruct.
- */
-public class MomentSolver {
- private double[] c_moments;
- private double xCenter, xScale;
- private double xMin, xMax;
-
- private int gridSize = 1024;
- private int maxIter = 15;
- private boolean verbose = false;
-
- private double[] xs;
- private double[] lambd;
- private double[] weights;
-
- public MomentSolver(
- MomentStruct ms) {
- xMin = ms.min;
- xMax = ms.max;
- xCenter = (xMax + xMin) / 2;
- xScale = (xMax - xMin) / 2;
- c_moments = MathUtil.powerSumsToChebyMoments(
- xMin, xMax, ms.power_sums);
- }
-
- /**
- * By increasing the number of grid points the estimates will be more precise
- * but more expensive to compute. Accuracy is still limited by the number of
- * known moments. Usually 1024 is a safe default.
- *
- * @param gs number of grid points
- */
- public void setGridSize(int gs) {
- gridSize = gs;
- }
-
- /**
- *
- * @param maxIter maximum number of steps of optimization
- */
- public void setMaxIter(int maxIter) {
- this.maxIter = maxIter;
- }
-
- public void setVerbose(boolean flag) {
- verbose = flag;
- }
-
- /**
- * Run an optimization routine to solve for the best-fit distribution
- * given the statistics in a moments sketch. Call solve() before attempting
- * to extract quantiles using getQuantile(p).
- */
- public void solve() {
- int n = gridSize;
- DMaxentLoss P = new DMaxentLoss(c_moments, gridSize);
-
- double[] l0 = new double[c_moments.length];
- l0[0] = Math.log(1.0 / n);
- for (int i = 1; i < l0.length; i++) {
- l0[i] = 0;
- }
- GenericOptimizer optimizer = new NewtonOptimizer(P);
- optimizer.setVerbose(verbose);
- optimizer.setMaxIter(maxIter);
-
- lambd = optimizer.solve(l0, 1e-6);
- P.computeAll(lambd, 0.0);
- weights = P.getWeights();
-
- xs = new double[gridSize];
- for (int i = 0; i < gridSize; i++) {
- double scaledX = ((i * 2.0) / (gridSize - 1)) - 1.0;
- xs[i] = (scaledX * xScale) + xCenter;
- }
- }
-
- public double[] getQuantiles(double ps[]) {
- double[] cdf = new double[gridSize];
- cdf[0] = 0.0;
- for (int i = 1; i < gridSize; i++) {
- cdf[i] = cdf[i - 1] + weights[i];
- }
-
- double[] qs = new double[ps.length];
- for (int i = 0; i < ps.length; i++) {
- double p = ps[i];
- int leftIdx = 0;
- int rightIdx = gridSize - 1;
- if (p <= cdf[leftIdx]) {
- qs[i] = xs[leftIdx];
- continue;
- }
- if (cdf[rightIdx] <= p) {
- qs[i] = xs[rightIdx];
- continue;
- }
- while (true) {
- if ((rightIdx - leftIdx) <= 1) {
- qs[i] = xs[rightIdx];
- break;
- }
- int midIdx = (leftIdx + rightIdx) / 2;
- if (p <= cdf[midIdx]) {
- rightIdx = midIdx;
- } else {
- leftIdx = midIdx;
- }
- }
- }
- return qs;
- }
-
- /**
- * @param p desired quantile p in [0,1]
- * @return the estimated quantile
- */
- public double getQuantile(double p) {
- double[] cdf = new double[gridSize];
- cdf[0] = 0.0;
- for (int i = 1; i < gridSize; i++) {
- cdf[i] = cdf[i - 1] + weights[i];
- }
-
- //double lastRank = 0.0;
- double curRank = 0.0;
-
- int targetIdx = gridSize - 1;
- for (int curIdx = 0; curIdx < gridSize; curIdx++) {
- //lastRank = curRank;
- curRank = cdf[curIdx];
- if (curRank >= p) {
- targetIdx = curIdx;
- break;
- }
- }
-
- double q = xs[targetIdx];
- return q;
- }
-
- /**
- * @return grid points used in estimating the data distribution
- */
- public double[] getXs() {
- return xs;
- }
-
- /**
- * @return estimated distribution of data across grid points
- */
- public double[] getWeights() {
- return weights;
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentStruct.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentStruct.java
deleted file mode 100644
index e7a1b77..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentStruct.java
+++ /dev/null
@@ -1,113 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-//CHECKSTYLE.OFF: EmptyLineSeparator
-
-import java.util.Arrays;
-
-/**
- * Structure for storing the statistics in a Moments Sketch.
- *
- * Unlike in the paper we only store power sums here and omit log moments.
- * When the data can be skewed or have outliers one should preprocess the data using either
- * a log transform or an arcsinh transform beforehand.
- */
-public class MomentStruct {
- public double[] power_sums;
- public double min, max;
-
- /**
- * Initialize a sketch with pre-computed statistics
- *
- * @param pSums sums of powers of data values sum x^i starting with the count i=0
- * @param min the minimum observed value
- * @param max the maximum observed value
- */
- public MomentStruct(
- double[] pSums, double min, double max) {
- power_sums = pSums;
- this.min = min;
- this.max = max;
- }
-
- /**
- * @param k number of moments to track. [2,20] is the useful range.
- */
- public MomentStruct(
- int k) {
- power_sums = new double[k];
- min = Double.MAX_VALUE;
- max = -Double.MAX_VALUE;
- }
-
- /**
- * @param x value to add to the sketch
- */
- public void add(double x) {
- if (x < min) {
- min = x;
- }
- if (x > max) {
- max = x;
- }
- double curPow = 1.0;
- int k = power_sums.length;
- for (int i = 0; i < k; i++) {
- power_sums[i] += curPow;
- curPow *= x;
- }
- }
-
- public void add(double[] xVals) {
- for (double x : xVals) {
- add(x);
- }
- }
-
- /**
- * @param other existing moment sketch structure to aggregate into current structure
- */
- public void merge(MomentStruct other) {
- if (other.min < min) {
- min = other.min;
- }
- if (other.max > max) {
- max = other.max;
- }
- int k = power_sums.length;
- for (int i = 0; i < k; i++) {
- power_sums[i] += other.power_sums[i];
- }
- }
-
- @Override
- public String toString() {
- return String.format("%g:%g:%s", min, max, Arrays.toString(power_sums));
- }
-
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketch.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketch.java
deleted file mode 100644
index 74ec340..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketch.java
+++ /dev/null
@@ -1,111 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-//CHECKSTYLE.OFF: EmptyLineSeparator
-
-/**
- * Example wrapper class for exposing an approximate quantiles sketch API
- * Uses the MomentSolver and MomentStruct internally and optionally compressed
- * the input range using arcsinh.
- */
-public class SimpleMomentSketch {
- public MomentStruct data;
- // Whether we use arcsinh to compress the range
- public boolean useArcSinh = true;
-
- public SimpleMomentSketch(
- int k) {
- data = new MomentStruct(k);
- }
-
- public SimpleMomentSketch(
- MomentStruct data) {
- this.data = data;
- }
-
- public void setCompressed(boolean flag) {
- useArcSinh = flag;
- }
-
- public boolean getCompressed() {
- return useArcSinh;
- }
-
- public int getK() {
- return data.power_sums.length;
- }
-
- public double[] getPowerSums() {
- return data.power_sums;
- }
-
- public double getMin() {
- return data.min;
- }
-
- public double getMax() {
- return data.max;
- }
-
- public void add(double rawX) {
- double x = rawX;
- if (useArcSinh) {
- x = Math.log(rawX + Math.sqrt(1 + (rawX * rawX)));
- }
- data.add(x);
- }
-
- public void merge(SimpleMomentSketch other) {
- data.merge(other.data);
- }
-
- public MomentSolver getSolver() {
- MomentSolver ms = new MomentSolver(data);
- return ms;
- }
-
- public double[] getQuantiles(double[] fractions) {
- MomentSolver ms = new MomentSolver(data);
- ms.setGridSize(1024);
- ms.setMaxIter(15);
- ms.solve();
-
- double[] quantiles = new double[fractions.length];
- for (int i = 0; i < fractions.length; i++) {
- double rawQuantile = ms.getQuantile(fractions[i]);
- quantiles[i] = Math.sinh(rawQuantile);
- }
-
- return quantiles;
- }
-
- @Override
- public String toString() {
- return data.toString();
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/FunctionWithHessian.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/FunctionWithHessian.java
deleted file mode 100644
index fb7f387..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/FunctionWithHessian.java
+++ /dev/null
@@ -1,28 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-//CHECKSTYLE.OFF: EmptyLineSeparator
-
-/**
- * Describes a function which can be optimized using Newton's method.
- */
-public interface FunctionWithHessian {
- void computeOnlyValue(double[] point, double tol);
-
- void computeAll(double[] point, double tol);
-
- int dim();
-
- double getValue();
-
- double[] getGradient();
-
- // Returns in row-major order
- double[][] getHessian();
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/GenericOptimizer.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/GenericOptimizer.java
deleted file mode 100644
index e7098a2..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/GenericOptimizer.java
+++ /dev/null
@@ -1,15 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer;
-
-public interface GenericOptimizer {
- void setVerbose(boolean flag);
-
- void setMaxIter(int maxIter);
-
- boolean isConverged();
-
- int getStepCount();
-
- FunctionWithHessian getP();
-
- double[] solve(double[] start, double gradTol);
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizer.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizer.java
deleted file mode 100644
index 4b5aab3..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizer.java
+++ /dev/null
@@ -1,160 +0,0 @@
-
-package com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-//CHECKSTYLE.OFF: EmptyLineSeparator
-//CHECKSTYLE.OFF: CommentsIndentation
-
-import org.apache.commons.math3.linear.Array2DRowRealMatrix;
-import org.apache.commons.math3.linear.ArrayRealVector;
-import org.apache.commons.math3.linear.CholeskyDecomposition;
-import org.apache.commons.math3.linear.RealMatrix;
-import org.apache.commons.math3.linear.RealVector;
-import org.apache.commons.math3.linear.SingularValueDecomposition;
-
-import com.yahoo.sketches.characterization.quantiles.momentsketch.MathUtil;
-
-/**
- * Minimizes a convex function using damped Newton's method.
- */
-public class NewtonOptimizer implements GenericOptimizer {
- protected FunctionWithHessian P;
- protected int maxIter;
-
- protected int stepCount;
- protected boolean converged;
- protected int dampedStepCount;
-
- private double alpha = .3;
- private double beta = .25;
- private boolean verbose = false;
-
- public NewtonOptimizer(FunctionWithHessian P) {
- this.P = P;
- maxIter = 200;
- stepCount = 0;
- dampedStepCount = 0;
- converged = false;
- }
-
- @Override
- public void setVerbose(boolean flag) {
- verbose = flag;
- }
-
- @Override
- public void setMaxIter(int maxIter) {
- this.maxIter = maxIter;
- }
-
- @Override
- public int getStepCount() {
- return stepCount;
- }
-
- @Override
- public boolean isConverged() {
- return converged;
- }
-
- public int getDampedStepCount() {
- return dampedStepCount;
- }
-
- @Override
- public FunctionWithHessian getP() {
- return P;
- }
-
- @Override
- public double[] solve(double[] start, double gradTol) {
- int k = P.dim();
-
- double[] x = start.clone();
-
- int step;
- double requiredPrecision = gradTol / 10;
- P.computeAll(x, requiredPrecision);
-
- double gradTol2 = gradTol * gradTol;
- converged = false;
-
- for (step = 0; step < maxIter; step++) {
- double PVal = P.getValue();
- double[] grad = P.getGradient();
- double[][] hess = P.getHessian();
- double mse = MathUtil.getMSE(grad);
- if (verbose) {
- System.out.println(String.format("Step: %3d GradRMSE: %10.5g P: %10.5g", step, Math.sqrt(mse), PVal));
- }
- if (mse < gradTol2) {
- converged = true;
- break;
- }
- RealMatrix hhMat = new Array2DRowRealMatrix(hess, false);
- RealVector stepVector;
- try {
- CholeskyDecomposition d = new CholeskyDecomposition(
- hhMat,
- 0,
- 0);
- stepVector = d.getSolver().solve(new ArrayRealVector(grad));
- } catch (Exception e) {
- // Cholesky is faster but fall back to SVD if it doesn't work
- SingularValueDecomposition d = new SingularValueDecomposition(hhMat);
- stepVector = d.getSolver().solve(new ArrayRealVector(grad));
- }
- // SingularValueDecomposition d = new SingularValueDecomposition(hhMat);
- // System.out.println("cond: "+d.getConditionNumber());
- stepVector.mapMultiplyToSelf(-1.0);
-
- double dfdx = 0.0;
- for (int i = 0; i < k; i++) {
- dfdx += stepVector.getEntry(i) * grad[i];
- }
-
- double stepScaleFactor = 1.0;
- double[] newX = new double[k];
- for (int i = 0; i < k; i++) {
- newX[i] = x[i] + (stepScaleFactor * stepVector.getEntry(i));
- }
- // Warning: this overwrites grad and hess
- P.computeAll(newX, requiredPrecision);
-
- // do not look for damped steps if we are near stationary point
- if ((dfdx * dfdx) > gradTol2) {
- while (true) {
- double f1 = P.getValue();
- double delta = (PVal + (alpha * stepScaleFactor * dfdx)) - f1;
- if ((delta >= -gradTol) || (stepScaleFactor < 1e-3)) {
- break;
- } else {
- stepScaleFactor *= beta;
- }
- for (int i = 0; i < k; i++) {
- newX[i] = x[i] + (stepScaleFactor * stepVector.getEntry(i));
- }
- P.computeAll(newX, requiredPrecision);
- }
- }
- if (stepScaleFactor < 1.0) {
- dampedStepCount++;
- }
- if (verbose) {
- if (stepScaleFactor < 1.0) {
- System.out.println("Step Size: " + stepScaleFactor);
- }
- }
- System.arraycopy(newX, 0, x, 0, k);
- }
- stepCount = step;
- return x;
-
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotential.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotential.java
deleted file mode 100644
index 03264ae..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotential.java
+++ /dev/null
@@ -1,77 +0,0 @@
-
-package com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-//CHECKSTYLE.OFF: EmptyLineSeparator
-//CHECKSTYLE.OFF: CommentsIndentation
-
-/**
- * Simple quadratic function for use in tests.
- */
-public class QuadraticPotential implements FunctionWithHessian {
- private int k;
- private double Pval;
- private double[] Pgrad;
- private double[][] Phess;
-
- public QuadraticPotential(int k) {
- this.k = k;
- Pgrad = new double[k];
- Phess = new double[k][k];
- }
-
- @Override
- public void computeOnlyValue(double[] point, double tol) {
- double sum = 0;
- for (int i = 0; i < point.length; i++) {
- sum += point[i] * point[i];
- }
- Pval = sum;
- }
-
- @Override
- public void computeAll(double[] point, double tol) {
- double sum = 0;
- for (int i = 0; i < point.length; i++) {
- sum += point[i] * point[i];
- }
- Pval = sum;
-
- for (int i = 0; i < point.length; i++) {
- Pgrad[i] = 2 * point[i];
- for (int j = 0; j < point.length; j++) {
- if (j == i) {
- Phess[i][j] = 2;
- } else {
- Phess[i][j] = 0.0;
- }
- }
- }
- }
-
- @Override
- public int dim() {
- return k;
- }
-
- @Override
- public double getValue() {
- return Pval;
- }
-
- @Override
- public double[] getGradient() {
- return Pgrad;
- }
-
- @Override
- public double[][] getHessian() {
- return Phess;
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/package-info.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/package-info.java
deleted file mode 100644
index 4fca70d..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/package-info.java
+++ /dev/null
@@ -1,10 +0,0 @@
-/*
- * Copyright 2019, Yahoo! Inc. Licensed under the terms of the
- * Apache License 2.0. See LICENSE file at the project root for terms.
- */
-
-/**
- * @author Lee Rhodes
- */
-
-package com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer;
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java
index 20691ff..74e0f33 100644
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java
+++ b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java
@@ -1,6 +1,20 @@
/*
- * Copyright 2019, Yahoo! Inc. Licensed under the terms of the
- * Apache License 2.0. See LICENSE file at the project root for terms.
+ * 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.
*/
/**
diff --git a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLossTest.java b/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLossTest.java
deleted file mode 100644
index 05a5261..0000000
--- a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/DMaxentLossTest.java
+++ /dev/null
@@ -1,53 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-import com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer.GenericOptimizer;
-import com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer.NewtonOptimizer;
-import org.junit.Test;
-
-import static org.junit.Assert.*;
-
-public class DMaxentLossTest {
-
- @Test
- public void testTrivial() {
- double m_values[] = {1.0, 0, -1.0/3, 0, -1.0/15, 0, -1.0/35};
- double l_values[] = {0.0, 0, 0, 0, 0, 0, 0};
- double tol = 1e-10;
- DMaxentLoss P = new DMaxentLoss(m_values, 21);
- P.computeAll(l_values, tol);
- assertEquals(m_values.length, P.getGradient().length);
- }
-
- @Test
- public void testSimple() {
- double n = 20;
- double l0Val = Math.log(1.0/n);
- double[] d_mus = {
- 1. , -0.06277785, -0.4079572 , -0.26898716, -0.1348974 ,
- 0.34909762, 0.28072058, -0.00188146, -0.27568291, -0.17049106
- };
- DMaxentLoss P = new DMaxentLoss(
- d_mus,
- 21
- );
-
- double[] l0 = new double[d_mus.length];
- l0[0] = l0Val;
- for (int i = 1 ; i < l0.length; i++) {
- l0[i] = 0;
- }
- GenericOptimizer optimizer = new NewtonOptimizer(P);
- optimizer.setVerbose(false);
-
- //long startTime, endTime;
- int numIter = 1;
- //startTime = System.nanoTime();
- for (int i = 0; i < numIter; i++) {
- l0 = optimizer.solve(l0, 1e-6);
- }
- //endTime = System.nanoTime();
- //double elapsed = (endTime - startTime) / (1.0*numIter);
-
- assertEquals(-3.6, l0[1], .5);
- }
-}
\ No newline at end of file
diff --git a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtilTest.java b/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtilTest.java
deleted file mode 100644
index 8993d04..0000000
--- a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MathUtilTest.java
+++ /dev/null
@@ -1,32 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-import org.junit.Test;
-
-import static org.junit.Assert.assertArrayEquals;
-import static org.junit.Assert.assertEquals;
-
-public class MathUtilTest {
-
- @Test
- public void testBinomial() {
- long[][] binoms = MathUtil.getBinomials(5);
- assertEquals(binoms[5][2], 10L);
- }
-
- @Test
- public void testChebyCoefficient() {
- int[][] cCoeffs = MathUtil.getChebyCoefficients(5);
- int[] expected = { 0, -3, 0, 4, 0, 0 };
- assertArrayEquals(expected, cCoeffs[3]);
- }
-
- @Test
- public void testConvertMoments() {
- // integers from 0...1000
- double[] uniformPowerSums = { 1001, 500500, 333833500, 250500250000L };
- double[] convertedChebyshevMoments = MathUtil.powerSumsToChebyMoments(0, 1000, uniformPowerSums);
-
- double[] expectedChebyshevMoments = { 1.0, 0, -.332, 0 };
- assertArrayEquals(expectedChebyshevMoments, convertedChebyshevMoments, 1e-14);
- }
-}
\ No newline at end of file
diff --git a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolverTest.java b/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolverTest.java
deleted file mode 100644
index 470546b..0000000
--- a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSolverTest.java
+++ /dev/null
@@ -1,104 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-import org.apache.commons.math3.stat.descriptive.rank.Percentile;
-import org.junit.Test;
-
-import static org.junit.Assert.*;
-
-public class MomentSolverTest {
-
- @Test
- public void testSimple() {
- double[] powerSums =
- { 200000.0, 304719.1420864805, 618596.450341607, 1361890.949909549, 3102323.794140877, 7200195.90117825, 16918271.75568709, 40122284.67435465, 95873463.0010957, 230593433.48962364
- };
- MomentStruct mData = new MomentStruct(
- powerSums,
- 2.0496528630116753e-05,
- 3.2187884808801686);
- MomentSolver ms = new MomentSolver(mData);
- ms.setGridSize(51);
- ms.solve();
- double q = ms.getQuantile(.9);
- assertEquals(2.46, q, .1);
- }
-
- @Test
- public void testFromRaw() {
- int n = 1000;
- double[] xVals = new double[n];
- for (int i = 0; i < n; i++) {
- xVals[i] = i;
- }
- MomentStruct mData = new MomentStruct(10);
- mData.add(xVals);
-
- MomentSolver ms = new MomentSolver(mData);
- ms.setGridSize(1024);
- ms.solve();
- double q = ms.getQuantile(.9);
-
- Percentile p = new Percentile();
- p.setData(xVals);
- double truep90 = p.evaluate(90.0);
- assertEquals(truep90, q, 1.0);
-
- double[] ps = { 0, .1, .5, .9, 1.0 };
- double[] qs = ms.getQuantiles(ps);
- assertEquals(0.0, qs[0], 1.0);
- assertEquals(truep90, qs[3], 1.0);
- }
-
- @Test
- public void testMilanLogData() {
- // Log transform works very well on milan data
- double minData = -12.96899970738978;
- double maxData = 8.979198088411168;
- double[] powerSums =
- { 24308139.0, 12420049.706757378, 293245315.4299223, 131886982.50259101, 6781335850.764435, -6571640034.562504, 253168798811.8452, -919129472417.1187, 14293827594309.152, -93264716269145.2, 1113140641657524.2, -9711395910128630.0, 1.085213731386595e+17, -1.0979641590548122e+18, 1.232426498322159e+19
- };
- MomentStruct mData = new MomentStruct(
- powerSums,
- minData,
- maxData);
- //long startTime = System.nanoTime();
-
- int numIter = 1000;
- MomentSolver ms = new MomentSolver(mData);
- ms.setGridSize(1024);
- for (int i = 0; i < numIter; i++) {
- ms.solve();
- }
-
- //long elapsed = System.nanoTime() - startTime;
- //double timePer = elapsed*1.0 / numIter;
- double q = Math.exp(ms.getQuantile(.90));
- assertTrue(q < 100);
- assertTrue(q > 90);
- double[] ps = { .9 };
- double[] qs = ms.getQuantiles(ps);
- assertTrue(Math.exp(qs[0]) > 90);
- assertTrue(Math.exp(qs[0]) < 100);
- }
-
- @Test
- public void testMilanArcsinhData() {
- // arcsinh transform can handle negative values but compresses small values
- // for the milan dataset.
- double minData = 2.331497699527218e-06;
- double maxData = 9.672345272940357;
- double[] powerSums =
- { 24308139.0, 54890011.69268947, 238580708.62136176, 1150204745.6709106, 5912306163.506206, 32001600745.32434, 181021599632.44467, 1064120737505.5359, 6471014895729.757, 40550499825482.09, 260983399634733.6, 1720144478337448.0, 1.1581465001793776e+16, 7.948216615871363e+16, 5.549795612843805e+17
- };
- MomentStruct mData = new MomentStruct(
- powerSums,
- minData,
- maxData);
- MomentSolver ms = new MomentSolver(mData);
- ms.setGridSize(10000);
- ms.solve();
- double q = Math.sinh(ms.getQuantile(.9));
- assertTrue(q < 100);
- assertTrue(q > 90);
- }
-}
\ No newline at end of file
diff --git a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketchTest.java b/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketchTest.java
deleted file mode 100644
index e72a9e7..0000000
--- a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/SimpleMomentSketchTest.java
+++ /dev/null
@@ -1,28 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-import org.junit.Test;
-
-import static org.junit.Assert.*;
-
-public class SimpleMomentSketchTest {
-
- @Test
- public void testSimple() {
- int n = 1000;
- double[] xVals = new double[n];
- for (int i = 0; i < n; i++) {
- xVals[i] = i;
- }
-
- SimpleMomentSketch ms = new SimpleMomentSketch(10);
- ms.setCompressed(true);
- for (double x : xVals) {
- ms.add(x);
- }
- double[] ps = { .5, .9 };
- double[] qs = ms.getQuantiles(ps);
-
- assertEquals(500, qs[0], 10);
- assertEquals(900, qs[1], 10);
- }
-}
\ No newline at end of file
diff --git a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizerTest.java b/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizerTest.java
deleted file mode 100644
index 5e186a4..0000000
--- a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/NewtonOptimizerTest.java
+++ /dev/null
@@ -1,23 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer;
-
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-
-public class NewtonOptimizerTest {
-
- @Test
- public void testQuadratic() {
- QuadraticPotential qp = new QuadraticPotential(2);
- NewtonOptimizer opt = new NewtonOptimizer(qp);
- double[] start = { 1.0, 2.0 };
- double[] solution = opt.solve(start, 1e-10);
- for (int i = 0; i < start.length; i++) {
- assertEquals(0.0, solution[i], 1e-10);
- }
- assertEquals(1, opt.getStepCount());
- assertEquals(0, opt.getDampedStepCount());
- assertTrue(opt.isConverged());
- }
-}
\ No newline at end of file
diff --git a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotentialTest.java b/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotentialTest.java
deleted file mode 100644
index 728f069..0000000
--- a/src/test/java/com/yahoo/sketches/characterization/quantiles/momentsketch/optimizer/QuadraticPotentialTest.java
+++ /dev/null
@@ -1,21 +0,0 @@
-package com.yahoo.sketches.characterization.quantiles.momentsketch.optimizer;
-
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-
-public class QuadraticPotentialTest {
-
- @Test
- public void testSimple() {
- QuadraticPotential qp = new QuadraticPotential(2);
- double[] x = { 1.0, 2.0 };
- qp.computeAll(x, 0.0);
- assertEquals(5, qp.getValue(), 1e-10);
-
- double[] xMin = { 0.0, 0.0 };
- qp.computeAll(xMin, 0.0);
- assertEquals(0, qp.getGradient()[1], 1e-10);
- }
-
-}
\ No newline at end of file
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-characterization] 02/02: cleanup Druid HLL,
Histogram, Quantiles testing.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-characterization.git
commit 75837ea17acc71b2f5198a6d12d957753e71817b
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Oct 16 09:07:00 2019 -0700
cleanup Druid HLL, Histogram, Quantiles testing.
Moved 3rd party code to jars.
---
pom.xml | 69 +-
.../hll/DruidHllAccuracyProfile.java | 5 +-
.../hll/DruidHllMergeAccuracyProfile.java | 5 +-
.../hll/druidhll/ByteBitLookup.java | 288 ----
.../hll/druidhll/HyperLogLogCollector.java | 792 ---------
.../hll/druidhll/HyperLogLogHash.java | 65 -
.../druidhll/VersionOneHyperLogLogCollector.java | 142 --
.../druidhll/VersionZeroHyperLogLogCollector.java | 120 --
.../hll/druidhll/package-info.java | 10 -
.../quantiles/DruidAppHistStreamAProfile.java | 4 +-
.../quantiles/MSketchStreamAProfile.java | 3 +-
.../druidhistogram/ApproximateHistogram.java | 1704 --------------------
.../quantiles/druidhistogram/ArrayUtils.java | 65 -
.../quantiles/druidhistogram/Histogram.java | 102 --
.../quantiles/druidhistogram/package-info.java | 10 -
.../momentsketch/MomentSketchWrapper.java | 183 ---
.../quantiles/momentsketch/package-info.java | 24 -
17 files changed, 37 insertions(+), 3554 deletions(-)
diff --git a/pom.xml b/pom.xml
index 98546dd..84ac910 100644
--- a/pom.xml
+++ b/pom.xml
@@ -58,13 +58,12 @@
<maven.compiler.target>${java.version}</maven.compiler.target>
<!-- Dependencies -->
- <memory.version>0.12.2</memory.version>
- <sketches-core.version>0.13.4</sketches-core.version>
- <guava.version>25.0-jre</guava.version>
+ <datasketches-memory.version>1.1.0-incubating</datasketches-memory.version>
+ <datasketches-java.version>1.1.0-incubating</datasketches-java.version>
<testng.version>6.14.3</testng.version>
- <slf4j-api.version>1.7.25</slf4j-api.version>
- <org-json.version>20180813</org-json.version>
-
+ <druid-momentsketch.version>0.16.0-incubating</druid-momentsketch.version>
+ <druid-histogram.version>0.16.0-incubating</druid-histogram.version>
+ <druid-hll.version>0.16.0-incubating</druid-hll.version>
<!-- Maven Plugins -->
<maven-assembly-plugin.version>3.1.0</maven-assembly-plugin.version>
<maven-clean-plugin.version>3.1.0</maven-clean-plugin.version>
@@ -126,44 +125,44 @@
<dependencies>
<!-- memory -->
<dependency>
- <groupId>com.yahoo.datasketches</groupId>
- <artifactId>memory</artifactId>
- <version>${memory.version}</version>
+ <groupId>org.apache.datasketches</groupId>
+ <artifactId>datasketches-memory</artifactId>
+ <version>${datasketches-memory.version}</version>
</dependency>
<!-- sketches-core -->
<dependency>
- <groupId>com.yahoo.datasketches</groupId>
- <artifactId>sketches-core</artifactId>
- <version>${sketches-core.version}</version>
+ <groupId>org.apache.datasketches</groupId>
+ <artifactId>datasketches-java</artifactId>
+ <version>${datasketches-java.version}</version>
</dependency>
- <!-- org.json -->
+ <!-- Druid HLL Sketch -->
<dependency>
- <groupId>org.json</groupId>
- <artifactId>json</artifactId>
- <version>${org-json.version}</version>
+ <groupId>org.apache.druid</groupId>
+ <artifactId>druid-hll</artifactId>
+ <version>${druid-hll.version}</version>
</dependency>
- <!-- Druid HLL -->
+ <!-- Druid Moment Sketch -->
<dependency>
- <groupId>com.google.guava</groupId>
- <artifactId>guava</artifactId>
- <version>${guava.version}</version>
+ <groupId>org.apache.druid.extensions.contrib</groupId>
+ <artifactId>druid-momentsketch</artifactId>
+ <version>${druid-momentsketch.version}</version>
</dependency>
-
- <!-- Moment Sketch -->
+
+ <!-- Druid Histogram -->
<dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-math3</artifactId>
- <version>3.6.1</version>
+ <groupId>org.apache.druid.extensions</groupId>
+ <artifactId>druid-histogram</artifactId>
+ <version>${druid-histogram.version}</version>
</dependency>
<!-- Test Scope -->
<dependency>
- <groupId>com.yahoo.datasketches</groupId>
- <artifactId>sketches-core</artifactId>
- <version>${sketches-core.version}</version>
+ <groupId>org.apache.datasketches</groupId>
+ <artifactId>datasketches-java</artifactId>
+ <version>${datasketches-java.version}</version>
<type>test-jar</type>
</dependency>
@@ -175,20 +174,6 @@
<scope>compile</scope>
</dependency>
- <!-- Moment Sketch -->
- <dependency>
- <groupId>junit</groupId>
- <artifactId>junit</artifactId>
- <version>4.12</version>
- <scope>test</scope>
- </dependency>
-
- <!-- logging -->
- <dependency>
- <groupId>org.slf4j</groupId>
- <artifactId>slf4j-api</artifactId>
- <version>${slf4j-api.version}</version>
- </dependency>
</dependencies>
<repositories>
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllAccuracyProfile.java b/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllAccuracyProfile.java
index 80e11bf..036ebca 100644
--- a/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllAccuracyProfile.java
+++ b/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllAccuracyProfile.java
@@ -5,9 +5,10 @@
package com.yahoo.sketches.characterization.hll;
+import org.apache.druid.hll.HyperLogLogCollector;
+import org.apache.druid.hll.HyperLogLogHash;
+
import com.yahoo.sketches.AccuracyStats;
-import com.yahoo.sketches.characterization.hll.druidhll.HyperLogLogCollector;
-import com.yahoo.sketches.characterization.hll.druidhll.HyperLogLogHash;
import com.yahoo.sketches.characterization.uniquecount.BaseAccuracyProfile;
public class DruidHllAccuracyProfile extends BaseAccuracyProfile {
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllMergeAccuracyProfile.java b/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllMergeAccuracyProfile.java
index 59b33b6..dfabd5a 100644
--- a/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllMergeAccuracyProfile.java
+++ b/src/main/java/com/yahoo/sketches/characterization/hll/DruidHllMergeAccuracyProfile.java
@@ -7,10 +7,11 @@ package com.yahoo.sketches.characterization.hll;
import java.util.Random;
+import org.apache.druid.hll.HyperLogLogCollector;
+import org.apache.druid.hll.HyperLogLogHash;
+
import com.yahoo.sketches.Job;
import com.yahoo.sketches.JobProfile;
-import com.yahoo.sketches.characterization.hll.druidhll.HyperLogLogCollector;
-import com.yahoo.sketches.characterization.hll.druidhll.HyperLogLogHash;
public class DruidHllMergeAccuracyProfile implements JobProfile {
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/ByteBitLookup.java b/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/ByteBitLookup.java
deleted file mode 100644
index a4e7367..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/ByteBitLookup.java
+++ /dev/null
@@ -1,288 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.hll.druidhll;
-
-/**
- */
-public class ByteBitLookup
-{
- public static final byte[] lookup;
-
- static {
- lookup = new byte[256];
-
- lookup[0] = 0;
- lookup[1] = 1;
- lookup[2] = 2;
- lookup[3] = 1;
- lookup[4] = 3;
- lookup[5] = 1;
- lookup[6] = 2;
- lookup[7] = 1;
- lookup[8] = 4;
- lookup[9] = 1;
- lookup[10] = 2;
- lookup[11] = 1;
- lookup[12] = 3;
- lookup[13] = 1;
- lookup[14] = 2;
- lookup[15] = 1;
- lookup[16] = 5;
- lookup[17] = 1;
- lookup[18] = 2;
- lookup[19] = 1;
- lookup[20] = 3;
- lookup[21] = 1;
- lookup[22] = 2;
- lookup[23] = 1;
- lookup[24] = 4;
- lookup[25] = 1;
- lookup[26] = 2;
- lookup[27] = 1;
- lookup[28] = 3;
- lookup[29] = 1;
- lookup[30] = 2;
- lookup[31] = 1;
- lookup[32] = 6;
- lookup[33] = 1;
- lookup[34] = 2;
- lookup[35] = 1;
- lookup[36] = 3;
- lookup[37] = 1;
- lookup[38] = 2;
- lookup[39] = 1;
- lookup[40] = 4;
- lookup[41] = 1;
- lookup[42] = 2;
- lookup[43] = 1;
- lookup[44] = 3;
- lookup[45] = 1;
- lookup[46] = 2;
- lookup[47] = 1;
- lookup[48] = 5;
- lookup[49] = 1;
- lookup[50] = 2;
- lookup[51] = 1;
- lookup[52] = 3;
- lookup[53] = 1;
- lookup[54] = 2;
- lookup[55] = 1;
- lookup[56] = 4;
- lookup[57] = 1;
- lookup[58] = 2;
- lookup[59] = 1;
- lookup[60] = 3;
- lookup[61] = 1;
- lookup[62] = 2;
- lookup[63] = 1;
- lookup[64] = 7;
- lookup[65] = 1;
- lookup[66] = 2;
- lookup[67] = 1;
- lookup[68] = 3;
- lookup[69] = 1;
- lookup[70] = 2;
- lookup[71] = 1;
- lookup[72] = 4;
- lookup[73] = 1;
- lookup[74] = 2;
- lookup[75] = 1;
- lookup[76] = 3;
- lookup[77] = 1;
- lookup[78] = 2;
- lookup[79] = 1;
- lookup[80] = 5;
- lookup[81] = 1;
- lookup[82] = 2;
- lookup[83] = 1;
- lookup[84] = 3;
- lookup[85] = 1;
- lookup[86] = 2;
- lookup[87] = 1;
- lookup[88] = 4;
- lookup[89] = 1;
- lookup[90] = 2;
- lookup[91] = 1;
- lookup[92] = 3;
- lookup[93] = 1;
- lookup[94] = 2;
- lookup[95] = 1;
- lookup[96] = 6;
- lookup[97] = 1;
- lookup[98] = 2;
- lookup[99] = 1;
- lookup[100] = 3;
- lookup[101] = 1;
- lookup[102] = 2;
- lookup[103] = 1;
- lookup[104] = 4;
- lookup[105] = 1;
- lookup[106] = 2;
- lookup[107] = 1;
- lookup[108] = 3;
- lookup[109] = 1;
- lookup[110] = 2;
- lookup[111] = 1;
- lookup[112] = 5;
- lookup[113] = 1;
- lookup[114] = 2;
- lookup[115] = 1;
- lookup[116] = 3;
- lookup[117] = 1;
- lookup[118] = 2;
- lookup[119] = 1;
- lookup[120] = 4;
- lookup[121] = 1;
- lookup[122] = 2;
- lookup[123] = 1;
- lookup[124] = 3;
- lookup[125] = 1;
- lookup[126] = 2;
- lookup[127] = 1;
- lookup[128] = 8;
- lookup[129] = 1;
- lookup[130] = 2;
- lookup[131] = 1;
- lookup[132] = 3;
- lookup[133] = 1;
- lookup[134] = 2;
- lookup[135] = 1;
- lookup[136] = 4;
- lookup[137] = 1;
- lookup[138] = 2;
- lookup[139] = 1;
- lookup[140] = 3;
- lookup[141] = 1;
- lookup[142] = 2;
- lookup[143] = 1;
- lookup[144] = 5;
- lookup[145] = 1;
- lookup[146] = 2;
- lookup[147] = 1;
- lookup[148] = 3;
- lookup[149] = 1;
- lookup[150] = 2;
- lookup[151] = 1;
- lookup[152] = 4;
- lookup[153] = 1;
- lookup[154] = 2;
- lookup[155] = 1;
- lookup[156] = 3;
- lookup[157] = 1;
- lookup[158] = 2;
- lookup[159] = 1;
- lookup[160] = 6;
- lookup[161] = 1;
- lookup[162] = 2;
- lookup[163] = 1;
- lookup[164] = 3;
- lookup[165] = 1;
- lookup[166] = 2;
- lookup[167] = 1;
- lookup[168] = 4;
- lookup[169] = 1;
- lookup[170] = 2;
- lookup[171] = 1;
- lookup[172] = 3;
- lookup[173] = 1;
- lookup[174] = 2;
- lookup[175] = 1;
- lookup[176] = 5;
- lookup[177] = 1;
- lookup[178] = 2;
- lookup[179] = 1;
- lookup[180] = 3;
- lookup[181] = 1;
- lookup[182] = 2;
- lookup[183] = 1;
- lookup[184] = 4;
- lookup[185] = 1;
- lookup[186] = 2;
- lookup[187] = 1;
- lookup[188] = 3;
- lookup[189] = 1;
- lookup[190] = 2;
- lookup[191] = 1;
- lookup[192] = 7;
- lookup[193] = 1;
- lookup[194] = 2;
- lookup[195] = 1;
- lookup[196] = 3;
- lookup[197] = 1;
- lookup[198] = 2;
- lookup[199] = 1;
- lookup[200] = 4;
- lookup[201] = 1;
- lookup[202] = 2;
- lookup[203] = 1;
- lookup[204] = 3;
- lookup[205] = 1;
- lookup[206] = 2;
- lookup[207] = 1;
- lookup[208] = 5;
- lookup[209] = 1;
- lookup[210] = 2;
- lookup[211] = 1;
- lookup[212] = 3;
- lookup[213] = 1;
- lookup[214] = 2;
- lookup[215] = 1;
- lookup[216] = 4;
- lookup[217] = 1;
- lookup[218] = 2;
- lookup[219] = 1;
- lookup[220] = 3;
- lookup[221] = 1;
- lookup[222] = 2;
- lookup[223] = 1;
- lookup[224] = 6;
- lookup[225] = 1;
- lookup[226] = 2;
- lookup[227] = 1;
- lookup[228] = 3;
- lookup[229] = 1;
- lookup[230] = 2;
- lookup[231] = 1;
- lookup[232] = 4;
- lookup[233] = 1;
- lookup[234] = 2;
- lookup[235] = 1;
- lookup[236] = 3;
- lookup[237] = 1;
- lookup[238] = 2;
- lookup[239] = 1;
- lookup[240] = 5;
- lookup[241] = 1;
- lookup[242] = 2;
- lookup[243] = 1;
- lookup[244] = 3;
- lookup[245] = 1;
- lookup[246] = 2;
- lookup[247] = 1;
- lookup[248] = 4;
- lookup[249] = 1;
- lookup[250] = 2;
- lookup[251] = 1;
- lookup[252] = 3;
- lookup[253] = 1;
- lookup[254] = 2;
- lookup[255] = 1;
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogCollector.java b/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogCollector.java
deleted file mode 100644
index a2d42ab..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogCollector.java
+++ /dev/null
@@ -1,792 +0,0 @@
-//Version 0.13.0
-/*
- * 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
- *
- * <p>http://www.apache.org/licenses/LICENSE-2.0
- *
- * <p>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.yahoo.sketches.characterization.hll.druidhll;
-
-import java.nio.ByteBuffer;
-
-/**
- * Implements the HyperLogLog cardinality estimator described in:
- *
- * <p>http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
- *
- * <p>Run this code to see a simple indication of expected errors based on different m values:
- *
- * <code>
- * for (int i = 1; i < 20; ++i) {
- * System.out.printf("i[%,d], val[%,d] => error[%f%%]%n", i, 2 << i,
- * 104 / Math.sqrt(2 << i));
- * }
- * </code>
- *
- * <p>This class is *not* multi-threaded. It can be passed among threads, but it is written with the
- * assumption that only one thread is ever calling methods on it.
- *
- * <p>If you have multiple threads calling methods on this concurrently, I hope you manage to get
- * correct behavior.
- *
- * <p>Note that despite the non-thread-safety of this class, it is actually currently used by
- * multiple threads during realtime indexing. HyperUniquesAggregator's "aggregate" and "get"
- * methods can be called simultaneously by OnheapIncrementalIndex, since its "doAggregate" and
- * "getMetricObjectValue" methods are not synchronized. So, watch out for that.
- */
-public abstract class HyperLogLogCollector implements Comparable<HyperLogLogCollector>
-{
- public static final int DENSE_THRESHOLD = 128;
- public static final int BITS_FOR_BUCKETS = 11;
- public static final int NUM_BUCKETS = 1 << BITS_FOR_BUCKETS; //2048
- public static final int NUM_BYTES_FOR_BUCKETS = NUM_BUCKETS / 2; //1024
-
- private static final double TWO_TO_THE_SIXTY_FOUR = Math.pow(2, 64);
- private static final double ALPHA = 0.7213 / (1 + (1.079 / NUM_BUCKETS)); //0.720920179
-
- public static final double LOW_CORRECTION_THRESHOLD = (5 * NUM_BUCKETS) / 2.0d; //5120
- public static final double HIGH_CORRECTION_THRESHOLD = TWO_TO_THE_SIXTY_FOUR / 30.0d; //6.14891E17
- public static final double CORRECTION_PARAMETER = ALPHA * NUM_BUCKETS * NUM_BUCKETS; //3023758.392
-
- private static final int bucketMask = 0x7ff;
- private static final int minBytesRequired = 10;
- private static final int bitsPerBucket = 4;
- private static final int range = (int) Math.pow(2, bitsPerBucket) - 1; //15
-
- private static final double[][] minNumRegisterLookup = new double[64][256];
-
- static {
- for (int registerOffset = 0; registerOffset < 64; ++registerOffset) {
- for (int register = 0; register < 256; ++register) {
- final int upper = ((register & 0xf0) >> 4) + registerOffset;
- final int lower = (register & 0x0f) + registerOffset;
- minNumRegisterLookup[registerOffset][register]
- = (1.0d / Math.pow(2, upper)) + (1.0d / Math.pow(2, lower));
- }
- }
- }
-
- // we have to keep track of the number of zeroes in each of the two halves of the byte register
- // (0, 1, or 2)
- private static final int[] numZeroLookup = new int[256];
-
- static {
- for (int i = 0; i < numZeroLookup.length; ++i) {
- numZeroLookup[i] = (((i & 0xf0) == 0) ? 1 : 0) + (((i & 0x0f) == 0) ? 1 : 0);
- }
- }
-
- // Methods to build the latest HLLC
- public static HyperLogLogCollector makeLatestCollector()
- {
- return new VersionOneHyperLogLogCollector();
- }
-
- /**
- * Create a wrapper object around an HLL sketch contained within a buffer. The position and limit
- * of the buffer may be changed; if you do not want this to happen, you can duplicate the buffer
- * before passing it in.
- *
- * <p>The mark and byte order of the buffer will not be modified.
- *
- * @param buffer buffer containing an HLL sketch starting at its position and ending at its limit
- *
- * @return HLLC wrapper object
- */
- @SuppressWarnings("deprecation")
- public static HyperLogLogCollector makeCollector(final ByteBuffer buffer)
- {
- final int remaining = buffer.remaining();
- if (((remaining % 3) == 0) || (remaining == 1027)) {
- return new VersionZeroHyperLogLogCollector(buffer);
- } else {
- return new VersionOneHyperLogLogCollector(buffer);
- }
- }
-
- /**
- * Creates new collector which shares others collector buffer
- * (by using {@link ByteBuffer#duplicate()})
- *
- * @param otherCollector collector which buffer will be shared
- * @return collector
- */
- public static HyperLogLogCollector makeCollectorSharingStorage(
- final HyperLogLogCollector otherCollector) {
- return makeCollector(otherCollector.getStorageBuffer().duplicate());
- }
-
- public static int getLatestNumBytesForDenseStorage() {
- return VersionOneHyperLogLogCollector.NUM_BYTES_FOR_DENSE_STORAGE;
- }
-
- /**
- *
- * @return byte array
- */
- public static byte[] makeEmptyVersionedByteArray() {
- final byte[] arr = new byte[getLatestNumBytesForDenseStorage()];
- arr[0] = VersionOneHyperLogLogCollector.VERSION;
- return arr;
- }
-
- /**
- * @param e blah
- * @param zeroCount blah
- * @return blah
- */
- public static double applyCorrection(double e, final int zeroCount) {
- e = CORRECTION_PARAMETER / e;
-
- if (e <= LOW_CORRECTION_THRESHOLD) {
- return zeroCount == 0 ? e : NUM_BUCKETS * Math.log(NUM_BUCKETS / (double) zeroCount);
- }
-
- if (e > HIGH_CORRECTION_THRESHOLD) {
- final double ratio = e / TWO_TO_THE_SIXTY_FOUR;
- if (ratio >= 1) {
- // handle very unlikely case that value is > 2^64
- return Double.POSITIVE_INFINITY;
- } else {
- return -TWO_TO_THE_SIXTY_FOUR * Math.log(1 - ratio);
- }
- }
-
- return e;
- }
-
- public static double estimateByteBuffer(final ByteBuffer buf) {
- return makeCollector(buf.duplicate()).estimateCardinality();
- }
-
- private static double estimateSparse(
- final ByteBuffer buf,
- final byte minNum,
- final byte overflowValue,
- final short overflowPosition,
- final boolean isUpperNibble) {
- final ByteBuffer copy = buf.asReadOnlyBuffer();
- double e = 0.0d;
- int zeroCount = NUM_BUCKETS - (2 * (buf.remaining() / 3));
- while (copy.hasRemaining()) {
- final short position = copy.getShort();
- final int register = copy.get() & 0xff;
- if ((overflowValue != 0) && (position == overflowPosition)) {
- int upperNibble = ((register & 0xf0) >>> bitsPerBucket) + minNum;
- int lowerNibble = (register & 0x0f) + minNum;
- if (isUpperNibble) {
- upperNibble = Math.max(upperNibble, overflowValue);
- } else {
- lowerNibble = Math.max(lowerNibble, overflowValue);
- }
- e += (1.0d / Math.pow(2, upperNibble)) + (1.0d / Math.pow(2, lowerNibble));
- zeroCount += (((upperNibble & 0xf0) == 0) ? 1 : 0) + (((lowerNibble & 0x0f) == 0) ? 1 : 0);
- } else {
- e += minNumRegisterLookup[minNum][register];
- zeroCount += numZeroLookup[register];
- }
- }
-
- e += zeroCount;
- return applyCorrection(e, zeroCount);
- }
-
- private static double estimateDense(
- final ByteBuffer buf,
- final byte minNum,
- final byte overflowValue,
- final short overflowPosition,
- final boolean isUpperNibble) {
- final ByteBuffer copy = buf.asReadOnlyBuffer();
- double e = 0.0d;
- int zeroCount = 0;
- int position = 0;
- while (copy.hasRemaining()) {
- final int register = copy.get() & 0xff;
- if ((overflowValue != 0) && (position == overflowPosition)) {
- int upperNibble = ((register & 0xf0) >>> bitsPerBucket) + minNum;
- int lowerNibble = (register & 0x0f) + minNum;
- if (isUpperNibble) {
- upperNibble = Math.max(upperNibble, overflowValue);
- } else {
- lowerNibble = Math.max(lowerNibble, overflowValue);
- }
- e += (1.0d / Math.pow(2, upperNibble)) + (1.0d / Math.pow(2, lowerNibble));
- zeroCount += (((upperNibble & 0xf0) == 0) ? 1 : 0) + (((lowerNibble & 0x0f) == 0) ? 1 : 0);
- } else {
- e += minNumRegisterLookup[minNum][register];
- zeroCount += numZeroLookup[register];
- }
- position++;
- }
-
- return applyCorrection(e, zeroCount);
- }
-
- /**
- * Checks if the payload for the given ByteBuffer is sparse or not.
- * The given buffer must be positioned at getPayloadBytePosition() prior to calling isSparse
- */
- private static boolean isSparse(final ByteBuffer buffer) {
- return buffer.remaining() != NUM_BYTES_FOR_BUCKETS;
- }
-
- private ByteBuffer storageBuffer;
- private int initPosition;
- private Double estimatedCardinality;
-
- /**
- * @param byteBuffer blah
- */
- public HyperLogLogCollector(final ByteBuffer byteBuffer) {
- storageBuffer = byteBuffer;
- initPosition = byteBuffer.position();
- estimatedCardinality = null;
- }
-
- public abstract byte getVersion();
-
- public abstract void setVersion(ByteBuffer buffer);
-
- public abstract byte getRegisterOffset();
-
- public abstract void setRegisterOffset(byte registerOffset);
-
- public abstract void setRegisterOffset(ByteBuffer buffer, byte registerOffset);
-
- public abstract short getNumNonZeroRegisters();
-
- public abstract void setNumNonZeroRegisters(short numNonZeroRegisters);
-
- public abstract void setNumNonZeroRegisters(ByteBuffer buffer, short numNonZeroRegisters);
-
- public abstract byte getMaxOverflowValue();
-
- public abstract void setMaxOverflowValue(byte value);
-
- public abstract void setMaxOverflowValue(ByteBuffer buffer, byte value);
-
- public abstract short getMaxOverflowRegister();
-
- public abstract void setMaxOverflowRegister(short register);
-
- public abstract void setMaxOverflowRegister(ByteBuffer buffer, short register);
-
- public abstract int getNumHeaderBytes();
-
- public abstract int getNumBytesForDenseStorage();
-
- public abstract int getPayloadBytePosition();
-
- public abstract int getPayloadBytePosition(ByteBuffer buffer);
-
- protected int getInitPosition() {
- return initPosition;
- }
-
- protected ByteBuffer getStorageBuffer() {
- return storageBuffer;
- }
-
- /**
- * @param hashedValue must be >= 10 bytes!
- */
- public void add(final byte[] hashedValue) {
- if (hashedValue.length < minBytesRequired) {
- throw new IAE("Insufficient bytes, need[%d] got [%d]", minBytesRequired, hashedValue.length);
- }
-
- estimatedCardinality = null;
-
- final ByteBuffer buffer = ByteBuffer.wrap(hashedValue);
-
- final short bucket = (short) (buffer.getShort(hashedValue.length - 2) & bucketMask);
-
- byte positionOf1 = 0;
-
- for (int i = 0; i < 8; ++i) {
- final byte lookupVal = ByteBitLookup.lookup[hashedValue[i] & 0XFF];
- switch (lookupVal) {
- case 0:
- positionOf1 += (byte) 8;
- continue;
- default:
- positionOf1 += lookupVal;
- i = 8;
- break;
- }
- }
-
- add(bucket, positionOf1);
- }
-
- /**
- * @param bucket blah
- * @param positionOf1 blah
- */
- public void add(final short bucket, final byte positionOf1) {
- if (storageBuffer.isReadOnly()) {
- convertToMutableByteBuffer();
- }
-
- final byte registerOffset = getRegisterOffset();
-
- // discard everything outside of the range we care about
- if (positionOf1 <= registerOffset) {
- return;
- } else if (positionOf1 > (registerOffset + range)) {
- final byte currMax = getMaxOverflowValue();
- if (positionOf1 > currMax) {
- if (currMax <= (registerOffset + range)) {
- // this could be optimized by having an add without sanity checks
- add(getMaxOverflowRegister(), currMax);
- }
- setMaxOverflowValue(positionOf1);
- setMaxOverflowRegister(bucket);
- }
- return;
- }
-
- // whatever value we add must be stored in 4 bits
- final short numNonZeroRegisters
- = addNibbleRegister(bucket, (byte) ((0xff & positionOf1) - registerOffset));
- setNumNonZeroRegisters(numNonZeroRegisters);
- if (numNonZeroRegisters == NUM_BUCKETS) {
- setRegisterOffset((byte) (registerOffset + 1));
- setNumNonZeroRegisters(decrementBuckets());
- }
- }
-
- /**
- * @param other blah
- * @return blah
- */
- public HyperLogLogCollector fold(HyperLogLogCollector other) {
- if ((other == null) || (other.storageBuffer.remaining() == 0)) {
- return this;
- }
-
- if (storageBuffer.isReadOnly()) {
- convertToMutableByteBuffer();
- }
-
- if (storageBuffer.remaining() != getNumBytesForDenseStorage()) {
- convertToDenseStorage();
- }
-
- estimatedCardinality = null;
-
- if (getRegisterOffset() < other.getRegisterOffset()) {
- // "Swap" the buffers so that we are folding into the one with the higher offset
- final ByteBuffer tmpBuffer = ByteBuffer.allocate(storageBuffer.remaining());
- tmpBuffer.put(storageBuffer.asReadOnlyBuffer());
- tmpBuffer.clear();
-
- storageBuffer.duplicate().put(other.storageBuffer.asReadOnlyBuffer());
-
- other = HyperLogLogCollector.makeCollector(tmpBuffer);
- }
-
- final ByteBuffer otherBuffer = other.storageBuffer;
-
- // Save position and restore later to avoid allocations due to duplicating the otherBuffer object.
- final int otherPosition = otherBuffer.position();
-
- try {
- final byte otherOffset = other.getRegisterOffset();
-
- final byte myOffset = getRegisterOffset();
- short numNonZero = getNumNonZeroRegisters();
-
- final int offsetDiff = myOffset - otherOffset;
- if (offsetDiff < 0) {
- throw new ISE("offsetDiff[%d] < 0, shouldn't happen because of swap.", offsetDiff);
- }
-
- final int myPayloadStart = getPayloadBytePosition();
- otherBuffer.position(other.getPayloadBytePosition());
-
- if (isSparse(otherBuffer)) {
- while (otherBuffer.hasRemaining()) {
- final int payloadStartPosition = otherBuffer.getShort() - other.getNumHeaderBytes();
- numNonZero += mergeAndStoreByteRegister(
- storageBuffer,
- myPayloadStart + payloadStartPosition,
- offsetDiff,
- otherBuffer.get()
- );
- }
- if (numNonZero == NUM_BUCKETS) {
- numNonZero = decrementBuckets();
- setRegisterOffset((byte) (myOffset + 1));
- setNumNonZeroRegisters(numNonZero);
- }
- } else { // dense
- int position = getPayloadBytePosition();
- while (otherBuffer.hasRemaining()) {
- numNonZero += mergeAndStoreByteRegister(
- storageBuffer,
- position,
- offsetDiff,
- otherBuffer.get()
- );
- position++;
- }
- if (numNonZero == NUM_BUCKETS) {
- numNonZero = decrementBuckets();
- setRegisterOffset((byte) (myOffset + 1));
- setNumNonZeroRegisters(numNonZero);
- }
- }
-
- // no need to call setRegisterOffset(myOffset) here,
- // since it gets updated every time myOffset is incremented
- setNumNonZeroRegisters(numNonZero);
-
- // this will add the max overflow and also recheck if offset needs to be shifted
- add(other.getMaxOverflowRegister(), other.getMaxOverflowValue());
-
- return this;
- }
- finally {
- otherBuffer.position(otherPosition);
- }
- }
-
- public HyperLogLogCollector fold(final ByteBuffer buffer) {
- return fold(makeCollector(buffer.duplicate()));
- }
-
- /**
- * @return blah
- */
- public ByteBuffer toByteBuffer() {
- final short numNonZeroRegisters = getNumNonZeroRegisters();
-
- // store sparsely
- if ((storageBuffer.remaining() == getNumBytesForDenseStorage())
- && (numNonZeroRegisters < DENSE_THRESHOLD)) {
- final ByteBuffer retVal =
- ByteBuffer.wrap(new byte[(numNonZeroRegisters * 3) + getNumHeaderBytes()]);
- setVersion(retVal);
- setRegisterOffset(retVal, getRegisterOffset());
- setNumNonZeroRegisters(retVal, numNonZeroRegisters);
- setMaxOverflowValue(retVal, getMaxOverflowValue());
- setMaxOverflowRegister(retVal, getMaxOverflowRegister());
-
- final int startPosition = getPayloadBytePosition();
- retVal.position(getPayloadBytePosition(retVal));
-
- final byte[] zipperBuffer = new byte[NUM_BYTES_FOR_BUCKETS];
- final ByteBuffer roStorageBuffer = storageBuffer.asReadOnlyBuffer();
- roStorageBuffer.position(startPosition);
- roStorageBuffer.get(zipperBuffer);
-
- for (int i = 0; i < NUM_BYTES_FOR_BUCKETS; ++i) {
- if (zipperBuffer[i] != 0) {
- final short val = (short) (0xffff & ((i + startPosition) - initPosition));
- retVal.putShort(val);
- retVal.put(zipperBuffer[i]);
- }
- }
- retVal.rewind();
- return retVal.asReadOnlyBuffer();
- }
-
- return storageBuffer.asReadOnlyBuffer();
- }
-
- /**
- * @return blah
- */
- //@JsonValue
- public byte[] toByteArray() {
- final ByteBuffer buffer = toByteBuffer();
- final byte[] theBytes = new byte[buffer.remaining()];
- buffer.get(theBytes);
-
- return theBytes;
- }
-
- public long estimateCardinalityRound() {
- return Math.round(estimateCardinality());
- }
-
- /**
- * @return the estimated cardinality
- */
- public double estimateCardinality() {
- if (estimatedCardinality == null) {
- final byte registerOffset = getRegisterOffset();
- final byte overflowValue = getMaxOverflowValue();
- final short overflowRegister = getMaxOverflowRegister();
- final short overflowPosition = (short) (overflowRegister >>> 1);
- final boolean isUpperNibble = ((overflowRegister & 0x1) == 0);
-
- storageBuffer.position(getPayloadBytePosition());
-
- if (isSparse(storageBuffer)) {
- estimatedCardinality = estimateSparse(
- storageBuffer,
- registerOffset,
- overflowValue,
- overflowPosition,
- isUpperNibble
- );
- } else {
- estimatedCardinality = estimateDense(
- storageBuffer,
- registerOffset,
- overflowValue,
- overflowPosition,
- isUpperNibble
- );
- }
-
- storageBuffer.position(initPosition);
- }
- return estimatedCardinality;
- }
-
- @SuppressWarnings("null")
- @Override
- public boolean equals(final Object o) {
- if (this == o) {
- return true;
- }
- if ((o == null) || (getClass() != o.getClass())) {
- return false;
- }
-
- ByteBuffer otherBuffer = ((HyperLogLogCollector) o).storageBuffer;
-
- if (storageBuffer != null ? false : otherBuffer != null) {
- return false;
- }
-
- if ((storageBuffer == null) && (otherBuffer == null)) {
- return true;
- }
-
- final ByteBuffer denseStorageBuffer;
- if (storageBuffer.remaining() != getNumBytesForDenseStorage()) {
- final HyperLogLogCollector denseCollector
- = HyperLogLogCollector.makeCollector(storageBuffer.duplicate());
- denseCollector.convertToDenseStorage();
- denseStorageBuffer = denseCollector.storageBuffer;
- } else {
- denseStorageBuffer = storageBuffer;
- }
-
- if (otherBuffer.remaining() != getNumBytesForDenseStorage()) {
- final HyperLogLogCollector otherCollector
- = HyperLogLogCollector.makeCollector(otherBuffer.duplicate());
- otherCollector.convertToDenseStorage();
- otherBuffer = otherCollector.storageBuffer;
- }
-
- return denseStorageBuffer.equals(otherBuffer);
- }
-
- @Override
- public int hashCode() {
- int result = storageBuffer != null ? storageBuffer.hashCode() : 0;
- result = (31 * result) + initPosition;
- return result;
- }
-
- @Override
- public String toString() {
- return "HyperLogLogCollector{"
- + "initPosition=" + initPosition
- + ", version=" + getVersion()
- + ", registerOffset=" + getRegisterOffset()
- + ", numNonZeroRegisters=" + getNumNonZeroRegisters()
- + ", maxOverflowValue=" + getMaxOverflowValue()
- + ", maxOverflowRegister=" + getMaxOverflowRegister()
- + '}';
- }
-
- private short decrementBuckets() {
- final int startPosition = getPayloadBytePosition();
- short count = 0;
- for (int i = startPosition; i < (startPosition + NUM_BYTES_FOR_BUCKETS); i++) {
- final byte val = (byte) (storageBuffer.get(i) - 0x11);
- if ((val & 0xf0) != 0) {
- ++count;
- }
- if ((val & 0x0f) != 0) {
- ++count;
- }
- storageBuffer.put(i, val);
- }
- return count;
- }
-
- private void convertToMutableByteBuffer() {
- final ByteBuffer tmpBuffer = ByteBuffer.allocate(storageBuffer.remaining());
- tmpBuffer.put(storageBuffer.asReadOnlyBuffer());
- tmpBuffer.position(0);
- storageBuffer = tmpBuffer;
- initPosition = 0;
- }
-
- private void convertToDenseStorage() {
- final ByteBuffer tmpBuffer = ByteBuffer.allocate(getNumBytesForDenseStorage());
- // put header
- setVersion(tmpBuffer);
- setRegisterOffset(tmpBuffer, getRegisterOffset());
- setNumNonZeroRegisters(tmpBuffer, getNumNonZeroRegisters());
- setMaxOverflowValue(tmpBuffer, getMaxOverflowValue());
- setMaxOverflowRegister(tmpBuffer, getMaxOverflowRegister());
-
- storageBuffer.position(getPayloadBytePosition());
- tmpBuffer.position(getPayloadBytePosition(tmpBuffer));
- // put payload
- while (storageBuffer.hasRemaining()) {
- tmpBuffer.put(storageBuffer.getShort(), storageBuffer.get());
- }
- tmpBuffer.rewind();
- storageBuffer = tmpBuffer;
- initPosition = 0;
- }
-
- private short addNibbleRegister(final short bucket, final byte positionOf1) {
- short numNonZeroRegs = getNumNonZeroRegisters();
-
- final int position = getPayloadBytePosition() + (short) (bucket >> 1);
- final boolean isUpperNibble = ((bucket & 0x1) == 0);
-
- final byte shiftedPositionOf1
- = (isUpperNibble) ? (byte) (positionOf1 << bitsPerBucket) : positionOf1;
-
- if (storageBuffer.remaining() != getNumBytesForDenseStorage()) {
- convertToDenseStorage();
- }
-
- final byte origVal = storageBuffer.get(position);
- final byte newValueMask = (isUpperNibble) ? (byte) 0xf0 : (byte) 0x0f;
- final byte originalValueMask = (byte) (newValueMask ^ 0xff);
-
- // if something was at zero, we have to increase the numNonZeroRegisters
- if (((origVal & newValueMask) == 0) && (shiftedPositionOf1 != 0)) {
- numNonZeroRegs++;
- }
-
- storageBuffer.put(
- position,
- (byte) (
- Math.max((origVal & newValueMask) & 0XFF, shiftedPositionOf1 & 0XFF)
- | (origVal & originalValueMask)
- )
- );
-
- return numNonZeroRegs;
- }
-
- /**
- * Returns the number of registers that are no longer zero after the value was added
- *
- * @param position The position into the byte buffer, this position represents two "registers"
- * @param offsetDiff The difference in offset between the byteToAdd and the current
- * HyperLogLogCollector
- * @param byteToAdd The byte to merge into the current HyperLogLogCollector
- */
- private static short mergeAndStoreByteRegister(
- final ByteBuffer storageBuffer,
- final int position,
- final int offsetDiff,
- final byte byteToAdd) {
- if (byteToAdd == 0) {
- return 0;
- }
-
- final byte currVal = storageBuffer.get(position);
-
- final int upperNibble = currVal & 0xf0;
- final int lowerNibble = currVal & 0x0f;
-
- // subtract the differences so that the nibbles align
- final int otherUpper = (byteToAdd & 0xf0) - (offsetDiff << bitsPerBucket);
- final int otherLower = (byteToAdd & 0x0f) - offsetDiff;
-
- final int newUpper = Math.max(upperNibble, otherUpper);
- final int newLower = Math.max(lowerNibble, otherLower);
-
- storageBuffer.put(position, (byte) ((newUpper | newLower) & 0xff));
-
- short numNoLongerZero = 0;
- if ((upperNibble == 0) && (newUpper > 0)) {
- ++numNoLongerZero;
- }
- if ((lowerNibble == 0) && (newLower > 0)) {
- ++numNoLongerZero;
- }
-
- return numNoLongerZero;
- }
-
- @Override
- public int compareTo(final HyperLogLogCollector other) {
- return Double.compare(estimateCardinality(), other.estimateCardinality());
- }
-
- //added these locally to eliminate external dependencies
- class IAE extends IllegalArgumentException {
- static final long serialVersionUID = 0;
-
- public IAE(final String formatText, final Object... arguments)
- {
- super(nonStrictFormat(formatText, arguments));
- }
-
- public IAE(final Throwable cause, final String formatText, final Object... arguments)
- {
- super(nonStrictFormat(formatText, arguments), cause);
- }
- }
-
- class ISE extends IllegalStateException {
- static final long serialVersionUID = 0;
-
- public ISE(final String formatText, final Object... arguments)
- {
- super(nonStrictFormat(formatText, arguments));
- }
-
- public ISE(final Throwable cause, final String formatText, final Object... arguments)
- {
- super(nonStrictFormat(formatText, arguments), cause);
- }
- }
-
- static String nonStrictFormat(final String message, final Object... formatArgs) {
- if ((formatArgs == null) || (formatArgs.length == 0)) {
- return message;
- }
- try {
- return String.format(java.util.Locale.ENGLISH, message, formatArgs);
- }
- catch (final java.util.IllegalFormatException e) {
- final StringBuilder bob = new StringBuilder(message);
- for (Object formatArg : formatArgs) {
- bob.append("; ").append(formatArg);
- }
- return bob.toString();
- }
- }
-
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogHash.java b/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogHash.java
deleted file mode 100644
index 5bbdcf7..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/HyperLogLogHash.java
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.hll.druidhll;
-
-import static java.nio.charset.StandardCharsets.UTF_8;
-
-import com.google.common.hash.HashFunction;
-import com.google.common.hash.Hashing;
-
-/**
- * Contains data hashing methods used before applying Hyper Log Log.
- *
- * <p>{@link HyperLogLogCollector#add(byte[])} requires hashed value on input.
- * This class makes it easier to achieve
- * consistent value hashing for both internal aggregation and external hashing for pre-computed
- * aggregation.
- *
- * <p>By default 128-bit murmur3 algorithm, x64 variant is used. Implementation is thread safe.
- *
- * <p>Caution! changing of implementation may cause improper cardinality estimation between data
- * hashed with different versions.
- */
-public class HyperLogLogHash
-{
- private static final HyperLogLogHash DEFAULT = new HyperLogLogHash(Hashing.murmur3_128());
-
- public static HyperLogLogHash getDefault()
- {
- return DEFAULT;
- }
-
- private final HashFunction hashFunction;
-
- public HyperLogLogHash(final HashFunction hashFunction)
- {
- this.hashFunction = hashFunction;
- }
-
- public byte[] hash(final byte[] rawValue)
- {
- return hashFunction.hashBytes(rawValue).asBytes();
- }
-
- public byte[] hash(final String rawValue)
- {
- return hash(rawValue.getBytes(UTF_8));
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionOneHyperLogLogCollector.java b/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionOneHyperLogLogCollector.java
deleted file mode 100644
index 2393411..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionOneHyperLogLogCollector.java
+++ /dev/null
@@ -1,142 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.hll.druidhll;
-
-import java.nio.ByteBuffer;
-
-public class VersionOneHyperLogLogCollector extends HyperLogLogCollector {
- /**
- * Header:
- * Byte 0: version
- * Byte 1: registerOffset
- * Byte 2-3: numNonZeroRegisters
- * Byte 4: maxOverflowValue
- * Byte 5-6: maxOverflowRegister
- */
- public static final byte VERSION = 0x1;
- public static final int REGISTER_OFFSET_BYTE = 1;
- public static final int NUM_NON_ZERO_REGISTERS_BYTE = 2; //and 3
- public static final int MAX_OVERFLOW_VALUE_BYTE = 4; //the exception value
- public static final int MAX_OVERFLOW_REGISTER_BYTE = 5; //and 6, the exception index register
- public static final int HEADER_NUM_BYTES = 7;
- public static final int NUM_BYTES_FOR_DENSE_STORAGE =
- NUM_BYTES_FOR_BUCKETS + HEADER_NUM_BYTES; //1024 + 7 = 1031
-
- private static final ByteBuffer defaultStorageBuffer = //initial header is 1 in first of 7 bytes
- ByteBuffer.wrap(new byte[]{VERSION, 0, 0, 0, 0, 0, 0}).asReadOnlyBuffer();
-
- VersionOneHyperLogLogCollector() {
- super(defaultStorageBuffer.duplicate());
- }
-
- VersionOneHyperLogLogCollector(final ByteBuffer buffer) {
- super(buffer);
- }
-
- @Override
- public byte getVersion() {
- return VERSION;
- }
-
- @Override
- public void setVersion(final ByteBuffer buffer) {
- buffer.put(buffer.position(), VERSION);
- }
-
- @Override
- public byte getRegisterOffset() {
- return getStorageBuffer().get(getInitPosition() + REGISTER_OFFSET_BYTE);
- }
-
- @Override
- public void setRegisterOffset(final byte registerOffset) {
- getStorageBuffer().put(getInitPosition() + REGISTER_OFFSET_BYTE, registerOffset);
- }
-
- @Override
- public void setRegisterOffset(final ByteBuffer buffer, final byte registerOffset) {
- buffer.put(buffer.position() + REGISTER_OFFSET_BYTE, registerOffset);
- }
-
- @Override
- public short getNumNonZeroRegisters() {
- return getStorageBuffer().getShort(getInitPosition() + NUM_NON_ZERO_REGISTERS_BYTE);
- }
-
- @Override
- public void setNumNonZeroRegisters(final short numNonZeroRegisters) {
- getStorageBuffer().putShort(getInitPosition() + NUM_NON_ZERO_REGISTERS_BYTE, numNonZeroRegisters);
- }
-
- @Override
- public void setNumNonZeroRegisters(final ByteBuffer buffer, final short numNonZeroRegisters) {
- buffer.putShort(buffer.position() + NUM_NON_ZERO_REGISTERS_BYTE, numNonZeroRegisters);
- }
-
- @Override
- public byte getMaxOverflowValue() {
- return getStorageBuffer().get(getInitPosition() + MAX_OVERFLOW_VALUE_BYTE);
- }
-
- @Override
- public void setMaxOverflowValue(final byte value) {
- getStorageBuffer().put(getInitPosition() + MAX_OVERFLOW_VALUE_BYTE, value);
- }
-
- @Override
- public void setMaxOverflowValue(final ByteBuffer buffer, final byte value) {
- buffer.put(buffer.position() + MAX_OVERFLOW_VALUE_BYTE, value);
- }
-
- @Override
- public short getMaxOverflowRegister() {
- return getStorageBuffer().getShort(getInitPosition() + MAX_OVERFLOW_REGISTER_BYTE);
- }
-
- @Override
- public void setMaxOverflowRegister(final short register) {
- getStorageBuffer().putShort(getInitPosition() + MAX_OVERFLOW_REGISTER_BYTE, register);
- }
-
- @Override
- public void setMaxOverflowRegister(final ByteBuffer buffer, final short register) {
- buffer.putShort(buffer.position() + MAX_OVERFLOW_REGISTER_BYTE, register);
- }
-
- @Override
- public int getNumHeaderBytes() {
- return HEADER_NUM_BYTES;
- }
-
- @Override
- public int getNumBytesForDenseStorage() {
- return NUM_BYTES_FOR_DENSE_STORAGE;
- }
-
- @Override
- public int getPayloadBytePosition() {
- return getInitPosition() + HEADER_NUM_BYTES;
- }
-
- @Override
- public int getPayloadBytePosition(final ByteBuffer buffer) {
- return buffer.position() + HEADER_NUM_BYTES;
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionZeroHyperLogLogCollector.java b/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionZeroHyperLogLogCollector.java
deleted file mode 100644
index 487665d..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/VersionZeroHyperLogLogCollector.java
+++ /dev/null
@@ -1,120 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.hll.druidhll;
-
-import java.nio.ByteBuffer;
-
-@Deprecated
-public class VersionZeroHyperLogLogCollector extends HyperLogLogCollector
-{
- /**
- * Header:
- * Byte 0: registerOffset
- * Byte 1-2: numNonZeroRegisters
- */
- public static final int NUM_NON_ZERO_REGISTERS_BYTE = 1;
- public static final int HEADER_NUM_BYTES = 3;
- public static final int NUM_BYTES_FOR_DENSE_STORAGE
- = NUM_BYTES_FOR_BUCKETS + HEADER_NUM_BYTES; //1024 + 3 = 1027
-
- VersionZeroHyperLogLogCollector(final ByteBuffer buffer) {
- super(buffer);
- }
-
- @Override
- public byte getVersion() {
- return 0;
- }
-
- @Override
- public void setVersion(final ByteBuffer buffer) { }
-
- @Override
- public byte getRegisterOffset() {
- return getStorageBuffer().get(getInitPosition());
- }
-
- @Override
- public void setRegisterOffset(final byte registerOffset) {
- getStorageBuffer().put(getInitPosition(), registerOffset);
- }
-
- @Override
- public void setRegisterOffset(final ByteBuffer buffer, final byte registerOffset) {
- buffer.put(buffer.position(), registerOffset);
- }
-
- @Override
- public short getNumNonZeroRegisters() {
- return getStorageBuffer().getShort(getInitPosition() + NUM_NON_ZERO_REGISTERS_BYTE);
- }
-
- @Override
- public void setNumNonZeroRegisters(final short numNonZeroRegisters) {
- getStorageBuffer().putShort(getInitPosition() + NUM_NON_ZERO_REGISTERS_BYTE, numNonZeroRegisters);
- }
-
- @Override
- public void setNumNonZeroRegisters(final ByteBuffer buffer, final short numNonZeroRegisters) {
- buffer.putShort(buffer.position() + NUM_NON_ZERO_REGISTERS_BYTE, numNonZeroRegisters);
- }
-
- @Override
- public byte getMaxOverflowValue() {
- return 0;
- }
-
- @Override
- public void setMaxOverflowValue(final byte value) { }
-
- @Override
- public void setMaxOverflowValue(final ByteBuffer buffer, final byte value) { }
-
- @Override
- public short getMaxOverflowRegister() {
- return 0;
- }
-
- @Override
- public void setMaxOverflowRegister(final short register) { }
-
- @Override
- public void setMaxOverflowRegister(final ByteBuffer buffer, final short register) { }
-
- @Override
- public int getNumHeaderBytes() {
- return HEADER_NUM_BYTES;
- }
-
- @Override
- public int getNumBytesForDenseStorage() {
- return NUM_BYTES_FOR_DENSE_STORAGE;
- }
-
- @Override
- public int getPayloadBytePosition() {
- return getInitPosition() + HEADER_NUM_BYTES;
- }
-
- @Override
- public int getPayloadBytePosition(final ByteBuffer buffer) {
- return buffer.position() + HEADER_NUM_BYTES;
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/package-info.java b/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/package-info.java
deleted file mode 100644
index eb578bd..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/hll/druidhll/package-info.java
+++ /dev/null
@@ -1,10 +0,0 @@
-/*
- * Copyright 2019, Yahoo! Inc. Licensed under the terms of the
- * Apache License 2.0. See LICENSE file at the project root for terms.
- */
-
-/**
- * @author Lee Rhodes
- */
-
-package com.yahoo.sketches.characterization.hll.druidhll;
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/DruidAppHistStreamAProfile.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/DruidAppHistStreamAProfile.java
index 7992636..39ab8e1 100644
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/DruidAppHistStreamAProfile.java
+++ b/src/main/java/com/yahoo/sketches/characterization/quantiles/DruidAppHistStreamAProfile.java
@@ -9,6 +9,8 @@ import static com.yahoo.sketches.characterization.quantiles.ProfileUtil.buildSpl
import java.io.File;
+import org.apache.druid.query.aggregation.histogram.ApproximateHistogram;
+import org.apache.druid.query.aggregation.histogram.Histogram;
import org.testng.annotations.Test;
import com.yahoo.sketches.Job;
@@ -17,8 +19,6 @@ import com.yahoo.sketches.LineReader;
import com.yahoo.sketches.ProcessLine;
import com.yahoo.sketches.Properties;
import com.yahoo.sketches.UnzipFiles;
-import com.yahoo.sketches.characterization.quantiles.druidhistogram.ApproximateHistogram;
-import com.yahoo.sketches.characterization.quantiles.druidhistogram.Histogram;
/**
* @author Lee Rhodes
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/MSketchStreamAProfile.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/MSketchStreamAProfile.java
index 1812425..b371e2f 100644
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/MSketchStreamAProfile.java
+++ b/src/main/java/com/yahoo/sketches/characterization/quantiles/MSketchStreamAProfile.java
@@ -9,13 +9,14 @@ import static java.lang.Math.rint;
import java.io.File;
+import org.apache.druid.query.aggregation.momentsketch.MomentSketchWrapper;
+
import com.yahoo.sketches.Job;
import com.yahoo.sketches.JobProfile;
import com.yahoo.sketches.LineReader;
import com.yahoo.sketches.ProcessLine;
import com.yahoo.sketches.Properties;
import com.yahoo.sketches.UnzipFiles;
-import com.yahoo.sketches.characterization.quantiles.momentsketch.MomentSketchWrapper;
/**
* @author Lee Rhodes
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ApproximateHistogram.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ApproximateHistogram.java
deleted file mode 100644
index bbcb804..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ApproximateHistogram.java
+++ /dev/null
@@ -1,1704 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.druidhistogram;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-
-import java.nio.ByteBuffer;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import com.google.common.base.Preconditions;
-import com.google.common.primitives.Floats;
-
-public class ApproximateHistogram
-{
- public static final int DEFAULT_HISTOGRAM_SIZE = 50;
- public static final int DEFAULT_BUCKET_SIZE = 7; //not used
-
- // max size of the histogram (number of bincount/position pairs)
- int size;
-
- public float[] positions;
- public long[] bins;
-
- // used bincount
- int binCount;
- // min value that's been put into histogram
- float min;
- float max;
- // total number of values that have been put into histogram
- transient long count;
-
- // lower limit to maintain resolution
- // cutoff above which we merge bins is the difference of the limits / (size - 3)
- // so we'll set size = 203, lower limit = 0, upper limit = 10.00 if we don't want
- // to merge differences < 0.05
- transient float lowerLimit;
- transient float upperLimit;
-
- // use sign bit to indicate approximate bin and remaining bits for bin count
- private static final long APPROX_FLAG_BIT = Long.MIN_VALUE;
- private static final long COUNT_BITS = Long.MAX_VALUE;
-
-
- @Override
- public boolean equals(Object o)
- {
- if (this == o) {
- return true;
- }
- if ((o == null) || (getClass() != o.getClass())) {
- return false;
- }
-
- ApproximateHistogram that = (ApproximateHistogram) o;
-
- if (size != that.size) {
- return false;
- }
- if (binCount != that.binCount) {
- return false;
- }
- if (Float.compare(that.max, max) != 0) {
- return false;
- }
- if (Float.compare(that.min, min) != 0) {
- return false;
- }
- for (int i = 0; i < binCount; ++i) {
- if (positions[i] != that.positions[i]) {
- return false;
- }
- }
- for (int i = 0; i < binCount; ++i) {
- if (bins[i] != that.bins[i]) {
- return false;
- }
- }
- return true;
- }
-
- @Override
- public int hashCode()
- {
- int result = size;
- result = (31 * result) + (positions != null ? ArrayUtils.hashCode(positions, 0, binCount) : 0);
- result = (31 * result) + (bins != null ? ArrayUtils.hashCode(bins, 0, binCount) : 0);
- result = (31 * result) + binCount;
- result = (31 * result) + (min != +0.0f ? Float.floatToIntBits(min) : 0);
- result = (31 * result) + (max != +0.0f ? Float.floatToIntBits(max) : 0);
- return result;
- }
-
-
- public ApproximateHistogram(
- int size,
- float[] positions,
- long[] bins,
- int binCount,
- float min,
- float max,
- long count,
- float lowerLimit,
- float upperLimit
- )
- {
- Preconditions.checkArgument(positions.length == bins.length, "position and bin array must have same size");
- Preconditions.checkArgument(binCount <= size, "binCount must be less or equal to size");
-
- this.size = size;
- this.positions = positions;
- this.bins = bins;
- this.binCount = binCount;
- this.min = min;
- this.max = max;
- this.count = count;
- this.lowerLimit = lowerLimit;
- this.upperLimit = upperLimit;
- }
-
- public ApproximateHistogram()
- {
- this(DEFAULT_HISTOGRAM_SIZE);
- }
-
- public ApproximateHistogram(int size)
- {
- this(
- size, //size
- new float[size], //positions
- new long[size], //bins
- 0, //binCount
- Float.POSITIVE_INFINITY, //min
- Float.NEGATIVE_INFINITY, //max
- 0, //count
- Float.NEGATIVE_INFINITY, //lowerLimit
- Float.POSITIVE_INFINITY //upperLimit
- );
- }
-
- public ApproximateHistogram(int size, float lowerLimit, float upperLimit)
- {
- this(
- size, //size
- new float[size], //positions
- new long[size], //bins
- 0, //binCount
- Float.POSITIVE_INFINITY, //min
- Float.NEGATIVE_INFINITY, //max
- 0, //count
- lowerLimit, //lowerLimit
- upperLimit //upperLimit
- );
- }
-
- public ApproximateHistogram(int binCount, float[] positions, long[] bins, float min, float max)
- {
- this(
- positions.length, //size
- positions, //positions
- bins, //bins
- binCount, //binCount
- min, //min
- max, //max
- sumBins(bins, binCount), //count
- Float.NEGATIVE_INFINITY, //lowerLimit
- Float.POSITIVE_INFINITY //upperLimit
- );
- }
-
- public long count()
- {
- return count;
- }
-
- public float min()
- {
- return min;
- }
-
- public float max()
- {
- return max;
- }
-
- public int binCount()
- {
- return binCount;
- }
-
- public float[] positions()
- {
- return Arrays.copyOfRange(positions, 0, binCount);
- }
-
- public long[] bins()
- {
- long[] counts = new long[binCount];
- for (int i = 0; i < binCount; ++i) {
- counts[i] = bins[i] & COUNT_BITS;
- }
- return counts;
- }
-
- @Override
- public String toString()
- {
- return "ApproximateHistogram{" +
- "size=" + size +
- ", lowerLimit=" + lowerLimit +
- ", upperLimit=" + upperLimit +
- ", positions=" + Arrays.toString(positions()) +
- ", bins=" + getBinsString() +
- ", binCount=" + binCount +
- ", min=" + min +
- ", max=" + max +
- ", count=" + count +
- '}';
- }
-
- public long getExactCount()
- {
- long exactCount = 0;
- for (int i = 0; i < binCount; ++i) {
- if ((bins[i] & APPROX_FLAG_BIT) == 0) {
- exactCount += (bins[i] & COUNT_BITS);
- }
- }
- return exactCount;
- }
-
- public float getMin()
- {
- return min;
- }
-
- public float getMax()
- {
- return max;
- }
-
- private static long sumBins(long[] bins, int binCount)
- {
- long count = 0;
- for (int i = 0; i < binCount; ++i) {
- count += bins[i] & COUNT_BITS;
- }
- return count;
- }
-
- /**
- * @return a string representation of the actual bin counts
- */
- protected String getBinsString()
- {
- StringBuilder s = new StringBuilder();
- s.append('[');
- for (int i = 0; i < bins.length; ++i) {
- if (i > 0) {
- s.append(", ");
- }
- if ((bins[i] & APPROX_FLAG_BIT) != 0) {
- s.append("*");
- }
- s.append(bins[i] & COUNT_BITS);
- }
- s.append(']');
- return s.toString();
- }
-
- public void setLowerLimit(float lowerLimit)
- {
- this.lowerLimit = lowerLimit;
- }
-
- public void setUpperLimit(float upperLimit)
- {
- this.upperLimit = upperLimit;
- }
-
- /**
- * Adds the given value to the histogram
- *
- * @param value the value to be added
- */
- public void offer(float value)
- {
- // update min/max
- if (value < min) {
- min = value;
- }
- if (value > max) {
- max = value;
- }
-
- // initial value
- if (binCount == 0) {
- positions[0] = value;
- bins[0] = 1;
- count++;
-
- binCount++;
- return;
- }
-
- final int index = Arrays.binarySearch(positions, 0, binCount, value);
-
- if (index >= 0) {
- // we have an exact match, simply increase the count, but keep the approximate flag
- bins[index] = (bins[index] & APPROX_FLAG_BIT) | ((bins[index] & COUNT_BITS) + 1);
- count++;
- return;
- }
-
- // otherwise merge the value into a new or existing bin at the following position
- final int insertAt = -(index + 1);
-
- if (binCount < size) {
- // we have a spare slot, put the value into a new bin
- shiftRight(insertAt, binCount);
-
- positions[insertAt] = value;
- bins[insertAt] = 1;
- count++;
-
- binCount++;
- return;
- }
-
- // no more slots available merge the new value into and existing bin
- // or merge existing bins before inserting the new one
-
- int minPos = minDeltaIndex();
- float minDelta = minPos >= 0 ? positions[minPos + 1] - positions[minPos] : Float.POSITIVE_INFINITY;
-
- // determine the distance of new value to the nearest bins
- final float deltaRight = insertAt < binCount ? positions[insertAt] - value : Float.POSITIVE_INFINITY;
- final float deltaLeft = insertAt > 0 ? value - positions[insertAt - 1] : Float.POSITIVE_INFINITY;
-
- boolean mergeValue = false;
- if (deltaRight < minDelta) {
- minDelta = deltaRight;
- minPos = insertAt;
- mergeValue = true;
- }
- if (deltaLeft < minDelta) {
- minPos = insertAt - 1;
- mergeValue = true;
- }
-
- if (mergeValue) {
- // merge new value into an existing bin and set approximate flag
- final long k = bins[minPos] & COUNT_BITS;
- positions[minPos] = ((positions[minPos] * k) + value) / (k + 1);
- bins[minPos] = (k + 1) | APPROX_FLAG_BIT;
- count++;
- } else {
- // merge the closest bins together and insert new value as a separate bin
- mergeInsert(minPos, insertAt, value, 1);
- }
- }
-
- protected int minDeltaIndex()
- {
- // determine minimum distance between existing bins
- float minDelta = Float.POSITIVE_INFINITY;
- int minPos = -1;
- for (int i = 0; i < (binCount - 1); ++i) {
- float delta = (positions[i + 1] - positions[i]);
- if (delta < minDelta) {
- minDelta = delta;
- minPos = i;
- }
- }
- return minPos;
- }
-
- /**
- * Merges the bin in the mergeAt position with the bin in position mergeAt+1
- * and simultaneously inserts the given bin (v,c) as a new bin at position insertAt
- *
- * @param mergeAt index of the bin to be merged
- * @param insertAt index to insert the new bin at
- * @param v bin position
- * @param c bin count
- */
- protected void mergeInsert(final int mergeAt, int insertAt, final float v, final long c)
- {
- final long k0 = (bins[mergeAt] & COUNT_BITS);
- final long k1 = (bins[mergeAt + 1] & COUNT_BITS);
- final long sum = k0 + k1;
-
- // merge bin at given position with the next bin and set approximate flag
- positions[mergeAt] = (float) ((((double) positions[mergeAt] * k0) + ((double) positions[mergeAt + 1] * k1)) / sum);
- bins[mergeAt] = sum | APPROX_FLAG_BIT;
-
- final int unusedIndex = mergeAt + 1;
-
- if (insertAt >= 0) {
- // use unused slot to shift array left or right and make space for the new bin to insert
- if (insertAt < unusedIndex) {
- shiftRight(insertAt, unusedIndex);
- } else if (insertAt >= unusedIndex) {
- shiftLeft(unusedIndex, insertAt - 1);
- insertAt--;
- }
- positions[insertAt] = v;
- bins[insertAt] = c;
- count++;
- } else {
- // simple merging of bins, shift everything left and free up the unused bin
- shiftLeft(unusedIndex, binCount - 1);
- binCount--;
- }
- }
-
- /**
- * Shifts the given range the histogram bins one slot to the right
- *
- * @param start index of the first bin to shift
- * @param end index of the rightmost bin to shift into
- */
- protected void shiftRight(int start, int end)
- {
- float prevVal = positions[start];
- long prevCnt = bins[start];
-
- for (int i = start + 1; i <= end; ++i) {
- float tmpVal = positions[i];
- long tmpCnt = bins[i];
-
- positions[i] = prevVal;
- bins[i] = prevCnt;
-
- prevVal = tmpVal;
- prevCnt = tmpCnt;
- }
- }
-
- /**
- * Shifts the given range of histogram bins one slot to the left
- *
- * @param start index of the leftmost empty bin to shift into
- * @param end index of the last bin to shift left
- */
- protected void shiftLeft(int start, int end)
- {
- for (int i = start; i < end; ++i) {
- positions[i] = positions[i + 1];
- bins[i] = bins[i + 1];
- }
- }
-
- public ApproximateHistogram fold(ApproximateHistogram h)
- {
- return fold(h, null, null, null);
- }
-
- public ApproximateHistogram fold(ApproximateHistogram h, float[] mergedPositions, long[] mergedBins, float[] deltas)
- {
- if (size == 0) {
- return copy(h);
- } else {
- return foldMin(h, mergedPositions, mergedBins, deltas);
- }
- }
-
- public ApproximateHistogram foldFast(ApproximateHistogram h)
- {
- return foldFast(h, null, null);
- }
-
- /**
- * @param h histogram to be merged into the current histogram
- * @param mergedPositions temporary buffer of size greater or equal to {@link #size}
- * @param mergedBins temporary buffer of size greater or equal to {@link #size}
- *
- * @return returns this histogram with h folded into it
- */
- public ApproximateHistogram foldFast(ApproximateHistogram h, float[] mergedPositions, long[] mergedBins)
- {
- if (size == 0) {
- return copy(h);
- } else {
- return foldRule(h, mergedPositions, mergedBins);
- }
- }
-
- /**
- * Copies histogram h into the current histogram.
- *
- * @param h ApproximateHistogram to copy
- *
- * @return this histogram
- */
- public ApproximateHistogram copy(ApproximateHistogram h)
- {
- if (h.size > size) {
- size = h.size;
- positions = new float[size];
- bins = new long[size];
- }
-
- System.arraycopy(h.positions, 0, positions, 0, h.binCount);
- System.arraycopy(h.bins, 0, bins, 0, h.binCount);
- min = h.min;
- max = h.max;
- binCount = h.binCount;
- count = h.count;
- return this;
- }
-
- //approximate histogram solution using min heap to store location of min deltas
- protected ApproximateHistogram foldMin(
- ApproximateHistogram h,
- float[] mergedPositions,
- long[] mergedBins,
- float[] deltas
- )
- {
- // find common min / max
- float mergedMin = min < h.min ? min : h.min;
- float mergedMax = max > h.max ? max : h.max;
- long mergedCount = count + h.count;
-
- int maxSize = binCount + h.binCount;
- int[] next = new int[maxSize];
- int[] prev = new int[maxSize];
-
- // use preallocated arrays if passed
- if ((mergedPositions == null) || (mergedBins == null) || (deltas == null)) {
- mergedPositions = new float[maxSize];
- mergedBins = new long[maxSize];
- deltas = new float[maxSize];
- } else {
- Preconditions.checkArgument(
- mergedPositions.length >= maxSize,
- "temp buffer [mergedPositions] too small: length must be at least [%s], got [%s]",
- maxSize,
- mergedPositions.length
- );
- Preconditions.checkArgument(
- mergedBins.length >= maxSize,
- "temp buffer [mergedBins] too small: length must be at least [%s], got [%s]",
- maxSize,
- mergedPositions.length
- );
- Preconditions.checkArgument(
- deltas.length >= maxSize,
- "temp buffer [deltas] too small: length must be at least [%s], got [%s]",
- maxSize,
- mergedPositions.length
- );
- }
-
- int mergedBinCount = combineBins(
- binCount,
- positions,
- bins,
- h.binCount,
- h.positions,
- h.bins,
- mergedPositions,
- mergedBins,
- deltas
- );
- if (mergedBinCount == 0) {
- return this;
- }
-
- // determine how many bins to merge
- int numMerge = mergedBinCount - size;
- if (numMerge < 0) {
- numMerge = 0;
- }
-
- // perform the required number of merges
- mergeBins(mergedBinCount, mergedPositions, mergedBins, deltas, numMerge, next, prev);
-
- // copy merged values
- int i = 0;
- int k = 0;
- while (i < mergedBinCount) {
- positions[k] = mergedPositions[i];
- bins[k] = mergedBins[i];
- ++k;
- i = next[i];
- }
- binCount = mergedBinCount - numMerge;
- min = mergedMin;
- max = mergedMax;
- count = mergedCount;
- return this;
- }
-
- protected ApproximateHistogram foldRule(ApproximateHistogram h, float[] mergedPositions, long[] mergedBins)
- {
- // ruleCombine bins requires at least one bin
- if (h.binCount == 0) {
- return this;
- }
-
- // find common min / max
- float mergedMin = min < h.min ? min : h.min;
- float mergedMax = max > h.max ? max : h.max;
- long mergedCount = count + h.count;
- min = mergedMin;
- max = mergedMax;
-
- // use preallocated arrays if passed
- if (mergedPositions == null) {
- mergedPositions = new float[size];
- mergedBins = new long[size];
- }
-
- int mergedBinCount;
- if ((binCount + h.binCount) <= size) {
- // no need to merge bins
- mergedBinCount = combineBins(
- binCount,
- positions,
- bins,
- h.binCount,
- h.positions,
- h.bins,
- mergedPositions,
- mergedBins,
- null
- );
- } else {
- mergedBinCount = ruleCombineBins(
- binCount,
- positions,
- bins,
- h.binCount,
- h.positions,
- h.bins,
- mergedPositions,
- mergedBins
- );
- }
- for (int i = 0; i < mergedBinCount; ++i) {
- positions[i] = mergedPositions[i];
- bins[i] = mergedBins[i];
- }
-
- binCount = mergedBinCount;
- count = mergedCount;
-
- return this;
- }
-
- protected int ruleCombineBins(
- int leftBinCount,
- float[] leftPositions,
- long[] leftBins,
- int rightBinCount,
- float[] rightPositions,
- long[] rightBins,
- float[] mergedPositions,
- long[] mergedBins
- )
- {
- final float cutoff;
- // assumes binCount is greater than one for both histograms
- // if upper and lower limits are set, we use the first and last used values of the arrays
- // for information below and above the limits, respectively
- if ((upperLimit != Float.POSITIVE_INFINITY) && (lowerLimit != Float.NEGATIVE_INFINITY)) {
- cutoff = (upperLimit - lowerLimit) / (size - 2 - 1);
- } else {
- if (upperLimit != Float.POSITIVE_INFINITY) {
- cutoff = (upperLimit - min) / (size - 2);
- } else if (lowerLimit != Float.NEGATIVE_INFINITY) {
- cutoff = (max - lowerLimit) / (size - 2);
- } else {
- cutoff = (max - min) / (size - 1);
- }
- }
-
- float lowerPosition = 0f;
- long lowerBin = 0;
- float upperPosition = 0f;
- long upperBin = 0;
-
- int j = 0;
- int k = 0;
- int pos = 0;
-
- // continuously merge the left histogram below the lower limit
- while (j != leftBinCount) {
- final float m1 = leftPositions[j];
- if (m1 < lowerLimit) {
- final long k1 = leftBins[j] & COUNT_BITS;
- float delta = (m1 - lowerPosition);
- final long k0 = lowerBin & COUNT_BITS;
- final long sum = k0 + k1;
- final float w = (float) k0 / (float) sum;
- lowerPosition = (-delta * w) + m1;
- // set approximate flag
- lowerBin = sum | APPROX_FLAG_BIT;
- ++j;
- } else {
- break;
- }
- }
-
- // continuously merge the right histogram below the lower limit
- while (k != rightBinCount) {
- final float m1 = rightPositions[k];
- if (m1 < lowerLimit) {
- final long k1 = rightBins[k] & COUNT_BITS;
- float delta = (m1 - lowerPosition);
- final long k0 = lowerBin & COUNT_BITS;
- final long sum = k0 + k1;
- final float w = (float) k0 / (float) sum;
- lowerPosition = (-delta * w) + m1;
- // set approximate flag
- lowerBin = sum | APPROX_FLAG_BIT;
- ++k;
- } else {
- break;
- }
- }
-
- // if there are values below the lower limit, store them in array position 0
- if ((lowerBin & COUNT_BITS) > 0) {
- mergedPositions[0] = lowerPosition;
- mergedBins[0] = lowerBin;
- pos = 1;
- }
-
- // if there are values below the lower limit, fill in array position 1
- // else array position 0
- while ((j != leftBinCount) || (k != rightBinCount)) {
- if ((j != leftBinCount) && ((k == rightBinCount) || (leftPositions[j] < rightPositions[k]))) {
- mergedPositions[pos] = leftPositions[j];
- mergedBins[pos] = leftBins[j];
- ++j;
- break;
- } else {
- mergedPositions[pos] = rightPositions[k];
- mergedBins[pos] = rightBins[k];
- ++k;
- break;
- }
- }
-
- while ((j != leftBinCount) || (k != rightBinCount)) {
- if ((j != leftBinCount) && ((k == rightBinCount) || (leftPositions[j] < rightPositions[k]))) {
- final float m1 = leftPositions[j];
- final long k1 = leftBins[j] & COUNT_BITS;
-
- // above the upper limit gets merged continuously in the left histogram
- if (m1 > upperLimit) {
- float delta = (m1 - upperPosition);
- final long k0 = upperBin & COUNT_BITS;
- final long sum = k0 + k1;
- final float w = (float) k0 / (float) sum;
- upperPosition = (-delta * w) + m1;
- // set approximate flag
- upperBin = sum | APPROX_FLAG_BIT;
- ++j;
- continue;
- }
-
- final float delta = (m1 - mergedPositions[pos]);
-
- if (delta <= cutoff) {
- final long k0 = mergedBins[pos] & COUNT_BITS;
- final long sum = k0 + k1;
- final float w = (float) k0 / (float) sum;
- mergedPositions[pos] = (-delta * w) + m1;
- // set approximate flag
- mergedBins[pos] = sum | APPROX_FLAG_BIT;
- } else {
- ++pos;
- mergedPositions[pos] = m1;
- mergedBins[pos] = k1;
- }
- ++j;
- } else {
- final float m1 = rightPositions[k];
- final long k1 = rightBins[k] & COUNT_BITS;
-
- // above the upper limit gets merged continuously in the right histogram
- if (m1 > upperLimit) {
- float delta = (m1 - upperPosition);
- final long k0 = upperBin & COUNT_BITS;
- final long sum = k0 + k1;
- final float w = (float) k0 / (float) sum;
- upperPosition = (-delta * w) + m1;
- // set approximate flag
- upperBin = sum | APPROX_FLAG_BIT;
- ++k;
- continue;
- }
-
- final float delta = (m1 - mergedPositions[pos]);
-
- if (delta <= cutoff) {
- final long k0 = mergedBins[pos] & COUNT_BITS;
- final long sum = k0 + k1;
- final float w = (float) k0 / (float) sum;
- mergedPositions[pos] = (-delta * w) + m1;
- mergedBins[pos] = sum | APPROX_FLAG_BIT;
- } else {
- ++pos;
- mergedPositions[pos] = m1;
- mergedBins[pos] = k1;
- }
- ++k;
- }
- }
-
- if ((upperBin & COUNT_BITS) > 0) {
- ++pos;
- mergedPositions[pos] = upperPosition;
- mergedBins[pos] = upperBin;
- }
-
- return pos + 1;
- }
-
-
- /**
- * mergeBins performs the given number of bin merge operations on the given histogram
- *
- * It repeatedly merges the two closest bins until it has performed the requested number of merge operations.
- * Merges are done in-place and unused bins have unknown state
- *
- * next / prev maintains a doubly-linked list of valid bin indices into the mergedBins array.
- *
- * Fast operation is achieved by building a min-heap of the deltas as opposed to repeatedly
- * scanning the array of deltas to find the minimum. A reverse index into the heap is maintained
- * to allow deleting and updating of specific deltas.
- *
- * next and prev arrays are used to maintain indices to the previous / next valid bin from a given bin index
- *
- * Its effect is equivalent to running the following code:
- *
- * <pre>
- * ApproximateHistogram merged = new ApproximateHistogram(mergedBinCount, mergedPositions, mergedBins);
- *
- * int targetSize = merged.binCount() - numMerge;
- * while (merged.binCount() > targetSize) {
- * merged.merge(merged.minDeltaIndex());
- * }
- * </pre>
- *
- * @param mergedBinCount
- * @param mergedPositions
- * @param mergedBins
- * @param deltas
- * @param numMerge
- * @param next
- * @param prev
- */
- private static void mergeBins(
- int mergedBinCount,
- float[] mergedPositions,
- long[] mergedBins,
- float[] deltas,
- int numMerge,
- int[] next,
- int[] prev
- )
- {
- // repeatedly search for two closest bins, merge them and update the corresponding deltas
-
- // maintain index to the last valid bin
- int lastValidIndex = mergedBinCount - 1;
-
- // initialize prev / next lookup arrays
- for (int i = 0; i < mergedBinCount; ++i) {
- next[i] = i + 1;
- }
- for (int i = 0; i < mergedBinCount; ++i) {
- prev[i] = i - 1;
- }
-
- // initialize min-heap of deltas and the reverse index into the heap
- int heapSize = mergedBinCount - 1;
- int[] heap = new int[heapSize];
- int[] reverseIndex = new int[heapSize];
- for (int i = 0; i < heapSize; ++i) {
- heap[i] = i;
- }
- for (int i = 0; i < heapSize; ++i) {
- reverseIndex[i] = i;
- }
-
- heapify(heap, reverseIndex, heapSize, deltas);
-
- {
- int i = 0;
- while (i < numMerge) {
- // find the smallest delta within the range used for bins
-
- // pick minimum delta index using min-heap
- int currentIndex = heap[0];
-
- final int nextIndex = next[currentIndex];
- final int prevIndex = prev[currentIndex];
-
- final long k0 = mergedBins[currentIndex] & COUNT_BITS;
- final long k1 = mergedBins[nextIndex] & COUNT_BITS;
- final float m0 = mergedPositions[currentIndex];
- final float m1 = mergedPositions[nextIndex];
- final float d1 = deltas[nextIndex];
-
- final long sum = k0 + k1;
- final float w = (float) k0 / (float) sum;
-
- // merge bin at given position with the next bin
- final float mm0 = ((m0 - m1) * w) + m1;
-
- mergedPositions[currentIndex] = mm0;
-
- mergedBins[currentIndex] = sum | APPROX_FLAG_BIT;
-
- // update deltas and min-heap
- if (nextIndex == lastValidIndex) {
- // merged bin is the last => remove the current bin delta from the heap
- heapSize = heapDelete(heap, reverseIndex, heapSize, reverseIndex[currentIndex], deltas);
- } else {
- // merged bin is not the last => remove the merged bin delta from the heap
- heapSize = heapDelete(heap, reverseIndex, heapSize, reverseIndex[nextIndex], deltas);
-
- // updated current delta
- deltas[currentIndex] = (m1 - mm0) + d1;
-
- // updated delta is necessarily larger than existing one, therefore we only need to push it down the heap
- siftDown(heap, reverseIndex, reverseIndex[currentIndex], heapSize - 1, deltas);
- }
-
- if (prevIndex >= 0) {
- // current bin is not the first, therefore update the previous bin delta
- deltas[prevIndex] = mm0 - mergedPositions[prevIndex];
-
- // updated previous bin delta is necessarily larger than its existing value => push down the heap
- siftDown(heap, reverseIndex, reverseIndex[prevIndex], heapSize - 1, deltas);
- }
-
- // update last valid index if we merged the last bin
- if (nextIndex == lastValidIndex) {
- lastValidIndex = currentIndex;
- }
-
- next[currentIndex] = next[nextIndex];
- if (nextIndex < lastValidIndex) {
- prev[next[nextIndex]] = currentIndex;
- }
-
- ++i;
- }
- }
- }
-
- /**
- * Builds a min-heap and a reverseIndex into the heap from the given array of values
- *
- * @param heap min-heap stored as indices into the array of values
- * @param reverseIndex reverse index from the array of values into the heap
- * @param count current size of the heap
- * @param values values to be stored in the heap
- */
- private static void heapify(int[] heap, int[] reverseIndex, int count, float[] values)
- {
- int start = (count - 2) / 2;
- while (start >= 0) {
- siftDown(heap, reverseIndex, start, count - 1, values);
- start--;
- }
- }
-
- /**
- * Rebalances the min-heap by pushing values from the top down and simultaneously updating the reverse index
- *
- * @param heap min-heap stored as indices into the array of values
- * @param reverseIndex reverse index from the array of values into the heap
- * @param start index to start re-balancing from
- * @param end index to stop re-balancing at
- * @param values values stored in the heap
- */
- private static void siftDown(int[] heap, int[] reverseIndex, int start, int end, float[] values)
- {
- int root = start;
- while (((root * 2) + 1) <= end) {
- int child = (root * 2) + 1;
- int swap = root;
- if (values[heap[swap]] > values[heap[child]]) {
- swap = child;
- }
- if (((child + 1) <= end) && (values[heap[swap]] > values[heap[child + 1]])) {
- swap = child + 1;
- }
- if (swap != root) {
- // swap
- int tmp = heap[swap];
- heap[swap] = heap[root];
- heap[root] = tmp;
-
- // heap index from delta index
- reverseIndex[heap[swap]] = swap;
- reverseIndex[heap[root]] = root;
-
- root = swap;
- } else {
- return;
- }
- }
- }
-
- /**
- * Deletes an item from the min-heap and updates the reverse index
- *
- * @param heap min-heap stored as indices into the array of values
- * @param reverseIndex reverse index from the array of values into the heap
- * @param count current size of the heap
- * @param heapIndex index of the item to be deleted
- * @param values values stored in the heap
- */
- private static int heapDelete(int[] heap, int[] reverseIndex, int count, int heapIndex, float[] values)
- {
- int end = count - 1;
-
- reverseIndex[heap[heapIndex]] = -1;
-
- heap[heapIndex] = heap[end];
- reverseIndex[heap[heapIndex]] = heapIndex;
-
- end--;
- siftDown(heap, reverseIndex, heapIndex, end, values);
- return count - 1;
- }
-
- /**
- * Combines two sets of histogram bins using merge-sort and computes the delta between consecutive bin positions.
- * Duplicate bins are merged together.
- *
- * @param leftBinCount
- * @param leftPositions
- * @param leftBins
- * @param rightBinCount
- * @param rightPositions
- * @param rightBins
- * @param mergedPositions array to store the combined bin positions (size must be at least leftBinCount + rightBinCount)
- * @param mergedBins array to store the combined bin counts (size must be at least leftBinCount + rightBinCount)
- * @param deltas deltas between consecutive bin positions in the merged bins (size must be at least leftBinCount + rightBinCount)
- *
- * @return the number of combined bins
- */
- private static int combineBins(
- int leftBinCount,
- float[] leftPositions,
- long[] leftBins,
- int rightBinCount,
- float[] rightPositions,
- long[] rightBins,
- float[] mergedPositions,
- long[] mergedBins,
- float[] deltas
- )
- {
- int i = 0;
- int j = 0;
- int k = 0;
- while ((j < leftBinCount) || (k < rightBinCount)) {
- if ((j < leftBinCount) && ((k == rightBinCount) || (leftPositions[j] < rightPositions[k]))) {
- mergedPositions[i] = leftPositions[j];
- mergedBins[i] = leftBins[j];
- ++j;
- } else if ((k < rightBinCount) && ((j == leftBinCount) || (leftPositions[j] > rightPositions[k]))) {
- mergedPositions[i] = rightPositions[k];
- mergedBins[i] = rightBins[k];
- ++k;
- } else {
- // combine overlapping bins
- mergedPositions[i] = leftPositions[j];
- mergedBins[i] = leftBins[j] + rightBins[k];
- ++j;
- ++k;
- }
- if ((deltas != null) && (i > 0)) {
- deltas[i - 1] = mergedPositions[i] - mergedPositions[i - 1];
- }
- ++i;
- }
- return i;
- }
-
- /**
- * Returns a byte-array representation of this ApproximateHistogram object
- *
- * @return byte array representation
- */
- //@JsonValue
- public byte[] toBytes()
- {
- ByteBuffer buf = ByteBuffer.allocate(getMinStorageSize());
- toBytes(buf);
- return buf.array();
- }
-
-
- public int getDenseStorageSize()
- {
- return (Integer.BYTES * 2) + (Float.BYTES * size) + (Long.BYTES * size) + (Float.BYTES * 2);
- }
-
- public int getSparseStorageSize()
- {
- return (Integer.BYTES * 2) + (Float.BYTES * binCount) + (Long.BYTES * binCount) + (Float.BYTES * 2);
- }
-
- public int getCompactStorageSize()
- {
- // ensures exactCount and (count - exactCount) can safely be cast to (int)
- Preconditions.checkState(canStoreCompact(), "Approximate histogram cannot be stored in compact form");
-
- final long exactCount = getExactCount();
- if (exactCount == count) {
- return Short.BYTES + 1 + (Float.BYTES * (int) exactCount);
- } else {
- return Short.BYTES
- + 1
- + (Float.BYTES * (int) exactCount)
- + 1
- + (Float.BYTES * (int) (count - exactCount))
- + (Float.BYTES * 2);
- }
- }
-
- public int getMaxStorageSize()
- {
- return getDenseStorageSize();
- }
-
- /**
- * Returns the minimum number of bytes required to store this ApproximateHistogram object
- *
- * @return required number of bytes
- */
- public int getMinStorageSize()
- {
- // sparse is always small than dense, so no need to check
- if (canStoreCompact() && (getCompactStorageSize() < getSparseStorageSize())) {
- return getCompactStorageSize();
- } else {
- return getSparseStorageSize();
- }
- }
-
- /**
- * Checks whether this approximate histogram can be stored in a compact form
- *
- * @return true if yes, false otherwise
- */
- public boolean canStoreCompact()
- {
- final long exactCount = getExactCount();
- return ((size <= Short.MAX_VALUE) && (exactCount <= Byte.MAX_VALUE) && ((count - exactCount) <= Byte.MAX_VALUE));
- }
-
- /**
- * Writes the representation of this ApproximateHistogram object to the given byte-buffer
- *
- * @param buf ByteBuffer to write the ApproximateHistogram to
- */
- public void toBytes(ByteBuffer buf)
- {
- if (canStoreCompact() && (getCompactStorageSize() < getSparseStorageSize())) {
- // store compact
- toBytesCompact(buf);
- } else {
- // store sparse
- toBytesSparse(buf);
- }
- }
-
- /**
- * Writes the dense representation of this ApproximateHistogram object to the given byte-buffer
- *
- * Requires 16 + 12 * size bytes of storage
- *
- * @param buf ByteBuffer to write the ApproximateHistogram to
- */
- public void toBytesDense(ByteBuffer buf)
- {
- buf.putInt(size);
- buf.putInt(binCount);
-
- buf.asFloatBuffer().put(positions);
- buf.position(buf.position() + (Float.BYTES * positions.length));
- buf.asLongBuffer().put(bins);
- buf.position(buf.position() + (Long.BYTES * bins.length));
-
- buf.putFloat(min);
- buf.putFloat(max);
- }
-
- /**
- * Writes the sparse representation of this ApproximateHistogram object to the given byte-buffer
- *
- * Requires 16 + 12 * binCount bytes of storage
- *
- * @param buf ByteBuffer to write the ApproximateHistogram to
- */
- public void toBytesSparse(ByteBuffer buf)
- {
- buf.putInt(size);
- buf.putInt(-1 * binCount); // use negative binCount to indicate sparse storage
- for (int i = 0; i < binCount; ++i) {
- buf.putFloat(positions[i]);
- }
- for (int i = 0; i < binCount; ++i) {
- buf.putLong(bins[i]);
- }
- buf.putFloat(min);
- buf.putFloat(max);
- }
-
- /**
- * Returns a compact byte-buffer representation of this ApproximateHistogram object
- * storing actual values as opposed to histogram bins
- *
- * Requires 3 + 4 * count bytes of storage with count <= 127
- *
- * @param buf ByteBuffer to write the ApproximateHistogram to
- */
- public void toBytesCompact(ByteBuffer buf)
- {
- Preconditions.checkState(canStoreCompact(), "Approximate histogram cannot be stored in compact form");
-
- buf.putShort((short) (-1 * size)); // use negative size to indicate compact storage
-
- final long exactCount = getExactCount();
- if (exactCount != count) {
- // use negative count to indicate approximate bins
- buf.put((byte) (-1 * (count - exactCount)));
-
- // store actual values instead of bins
- for (int i = 0; i < binCount; ++i) {
- // repeat each value bins[i] times for approximate bins
- if ((bins[i] & APPROX_FLAG_BIT) != 0) {
- for (int k = 0; k < (bins[i] & COUNT_BITS); ++k) {
- buf.putFloat(positions[i]);
- }
- }
- }
-
- // tack on min and max since they may be lost int the approximate bins
- buf.putFloat(min);
- buf.putFloat(max);
- }
-
- buf.put((byte) exactCount);
- // store actual values instead of bins
- for (int i = 0; i < binCount; ++i) {
- // repeat each value bins[i] times for exact bins
- if ((bins[i] & APPROX_FLAG_BIT) == 0) {
- for (int k = 0; k < (bins[i] & COUNT_BITS); ++k) {
- buf.putFloat(positions[i]);
- }
- }
- }
- }
-
- /**
- * Constructs an Approximate Histogram object from the given byte-array representation
- *
- * @param bytes byte array to construct an ApproximateHistogram from
- *
- * @return ApproximateHistogram constructed from the given byte array
- */
- public static ApproximateHistogram fromBytes(byte[] bytes)
- {
- ByteBuffer buf = ByteBuffer.wrap(bytes);
- return fromBytes(buf);
- }
-
- /**
- * Constructs an ApproximateHistogram object from the given dense byte-buffer representation
- *
- * @param buf ByteBuffer to construct an ApproximateHistogram from
- *
- * @return ApproximateHistogram constructed from the given ByteBuffer
- */
- public static ApproximateHistogram fromBytesDense(ByteBuffer buf)
- {
- int size = buf.getInt();
- int binCount = buf.getInt();
-
- float[] positions = new float[size];
- long[] bins = new long[size];
-
- buf.asFloatBuffer().get(positions);
- buf.position(buf.position() + (Float.BYTES * positions.length));
- buf.asLongBuffer().get(bins);
- buf.position(buf.position() + (Long.BYTES * bins.length));
-
- float min = buf.getFloat();
- float max = buf.getFloat();
-
- return new ApproximateHistogram(binCount, positions, bins, min, max);
- }
-
- /**
- * Constructs an ApproximateHistogram object from the given dense byte-buffer representation
- *
- * @param buf ByteBuffer to construct an ApproximateHistogram from
- *
- * @return ApproximateHistogram constructed from the given ByteBuffer
- */
- public static ApproximateHistogram fromBytesSparse(ByteBuffer buf)
- {
- int size = buf.getInt();
- int binCount = -1 * buf.getInt();
-
- float[] positions = new float[size];
- long[] bins = new long[size];
-
- for (int i = 0; i < binCount; ++i) {
- positions[i] = buf.getFloat();
- }
- for (int i = 0; i < binCount; ++i) {
- bins[i] = buf.getLong();
- }
-
- float min = buf.getFloat();
- float max = buf.getFloat();
-
- return new ApproximateHistogram(binCount, positions, bins, min, max);
- }
-
- /**
- * Constructs an ApproximateHistogram object from the given compact byte-buffer representation
- *
- * @param buf ByteBuffer to construct an ApproximateHistogram from
- *
- * @return ApproximateHistogram constructed from the given ByteBuffer
- */
- public static ApproximateHistogram fromBytesCompact(ByteBuffer buf)
- {
- short size = (short) (-1 * buf.getShort());
- byte count = buf.get();
-
- if (count >= 0) {
- // only exact bins
- ApproximateHistogram histogram = new ApproximateHistogram(size);
- for (int i = 0; i < count; ++i) {
- histogram.offer(buf.getFloat());
- }
- return histogram;
- } else {
- byte approxCount = (byte) (-1 * count);
-
- Map<Float, Long> approx = new HashMap<>();
-
- for (int i = 0; i < approxCount; ++i) {
- final float value = buf.getFloat();
- if (approx.containsKey(value)) {
- approx.put(value, approx.get(value) + 1);
- } else {
- approx.put(value, 1L);
- }
- }
-
- float min = buf.getFloat();
- float max = buf.getFloat();
-
- byte exactCount = buf.get();
-
- Map<Float, Long> exact = new HashMap<>();
-
- for (int i = 0; i < exactCount; ++i) {
- final float value = buf.getFloat();
- if (exact.containsKey(value)) {
- exact.put(value, exact.get(value) + 1);
- } else {
- exact.put(value, 1L);
- }
- }
-
- int binCount = exact.size() + approx.size();
-
- List<Float> pos = new ArrayList<>();
- pos.addAll(exact.keySet());
- pos.addAll(approx.keySet());
- Collections.sort(pos);
-
- float[] positions = new float[size];
- long[] bins = new long[size];
-
- for (int i = 0; i < pos.size(); ++i) {
- positions[i] = pos.get(i);
- }
-
- for (int i = 0; i < pos.size(); ++i) {
- final float value = pos.get(i);
- if (exact.containsKey(value)) {
- bins[i] = exact.get(value);
- } else {
- bins[i] = approx.get(value) | APPROX_FLAG_BIT;
- }
- }
-
- return new ApproximateHistogram(binCount, positions, bins, min, max);
- }
- }
-
- /**
- * Constructs an ApproximateHistogram object from the given byte-buffer representation
- *
- * @param buf ByteBuffer to construct an ApproximateHistogram from
- *
- * @return ApproximateHistogram constructed from the given ByteBuffer
- */
- public static ApproximateHistogram fromBytes(ByteBuffer buf)
- {
- // negative size indicates compact representation
- // this works regardless of whether we use int or short for the size since the leftmost bit is the sign bit
- if (buf.getShort(buf.position()) < 0) {
- return fromBytesCompact(buf);
- } else {
- // ignore size, determine if sparse or dense based on sign of binCount
- if (buf.getInt(buf.position() + Integer.BYTES) < 0) {
- return fromBytesSparse(buf);
- } else {
- return fromBytesDense(buf);
- }
- }
- }
-
- /**
- * Returns the approximate number of items less than or equal to b in the histogram
- *
- * @param b the cutoff
- *
- * @return the approximate number of items less than or equal to b
- */
- public double sum(final float b)
- {
- if (b < min) {
- return 0;
- }
- if (b >= max) {
- return count;
- }
-
- int index = Arrays.binarySearch(positions, 0, binCount, b);
- boolean exactMatch = index >= 0;
- index = exactMatch ? index : -(index + 1);
-
- // we want positions[index] <= b < positions[index+1]
- if (!exactMatch) {
- index--;
- }
-
- final boolean outerLeft = index < 0;
- final boolean outerRight = index >= (binCount - 1);
-
- final long m0 = outerLeft ? 0 : (bins[index] & COUNT_BITS);
- final long m1 = outerRight ? 0 : (bins[index + 1] & COUNT_BITS);
- final double p0 = outerLeft ? min : positions[index];
- final double p1 = outerRight ? max : positions[index + 1];
- final boolean exact0 = (!outerLeft && ((bins[index] & APPROX_FLAG_BIT) == 0));
- final boolean exact1 = (!outerRight && ((bins[index + 1] & APPROX_FLAG_BIT) == 0));
-
- // handle case when p0 = p1, which happens if the first bin = min or the last bin = max
- final double l = (p1 == p0) ? 0 : (b - p0) / (p1 - p0);
-
- // don't include exact counts in the trapezoid calculation
- long tm0 = m0;
- long tm1 = m1;
- if (exact0) {
- tm0 = 0;
- }
- if (exact1) {
- tm1 = 0;
- }
- final double mb = tm0 + ((tm1 - tm0) * l);
- double s = 0.5 * (tm0 + mb) * l;
-
- for (int i = 0; i < index; ++i) {
- s += (bins[i] & COUNT_BITS);
- }
-
- // add full bin count if left bin count is exact
- if (exact0) {
- return (s + m0);
- } else {
- // otherwise add only the left half of the bin
- return (s + (0.5 * m0));
- }
- }
-
- /**
- * Returns the approximate quantiles corresponding to the given probabilities.
- * probabilities = [.5f] returns [median]
- * probabilities = [.25f, .5f, .75f] returns the quartiles, [25%ile, median, 75%ile]
- *
- * @param probabilities array of probabilities
- *
- * @return an array of length probabilities.length representing the the approximate sample quantiles
- * corresponding to the given probabilities
- */
-
- public float[] getQuantiles(float[] probabilities)
- {
- for (float p : probabilities) {
- Preconditions.checkArgument((0 < p) && (p < 1), "quantile probabilities must be strictly between 0 and 1");
- }
-
- float[] quantiles = new float[probabilities.length];
- Arrays.fill(quantiles, Float.NaN);
-
- if (count() == 0) {
- return quantiles;
- }
-
- final long[] bins = bins();
-
- for (int j = 0; j < probabilities.length; ++j) {
- // Adapted from Ben-Haiv/Tom-Tov (Algorithm 4: Uniform Procedure)
- // Our histogram has a set of bins {(p1, m1), (p2, m2), ... (pB, mB)}
- // and properties of min and max saved during construction, such
- // that min <= p1 and pB <= max.
- //
- // When min < p1 or pB < max, these are special cases of using the
- // dummy bins (p0, 0) or (pB+1, 0) respectively, where p0 == min
- // and pB+1 == max.
- //
- // This histogram gives an ordered set of numbers {pi, pi+1, ..., pn},
- // such that min <= pi < pn <= max, and n is the sum({m1, ..., mB}).
- // We use s to determine which pairs of (pi, mi), (pi+1, mi+1) to
- // calculate our quantile from by computing sum([pi,mi]) < s < sum
- // ([pi+1, mi+1])
- final double s = probabilities[j] * count();
-
- int i = 0;
- int sum = 0;
- int k = 1;
- long count;
- while (k <= binCount()) {
- count = bins[k - 1];
- if ((sum + count) > s) {
- i = k - 1;
- break;
- } else {
- sum += count;
- }
- ++k;
- }
-
- if (i == 0) {
- // At the first bin, there are no points to the left of p (min)
- quantiles[j] = min();
- } else {
- final double d = s - sum;
- final double c = -2 * d;
- final long a = bins[i] - bins[i - 1];
- final long b = 2 * bins[i - 1];
- double z;
- if (a == 0) {
- z = -c / b;
- } else {
- z = (-b + Math.sqrt((b * b) - (4 * a * c))) / (2 * a);
- }
- final double uj = positions[i - 1] + ((positions[i] - positions[i - 1]) * z);
- // A given bin (p, m) has m/2 points to the left and right of p, and
- // uj could be one of those points. However, uj is still subject to:
- // [min] (p0, 0) < uj < (p, m) or
- // (p, m) < uj < (pB+1, 0) [max]
- quantiles[j] = ((float) uj < max()) ? (float) uj : max();
- }
- }
-
- return quantiles;
- }
-
- /**
- * Computes a visual representation of the approximate histogram with bins laid out according to the given breaks
- *
- * @param breaks breaks defining the histogram bins
- *
- * @return visual representation of the histogram
- */
- public Histogram toHistogram(final float[] breaks)
- {
- final double[] approximateBins = new double[breaks.length - 1];
-
- double prev = sum(breaks[0]);
- for (int i = 1; i < breaks.length; ++i) {
- double s = sum(breaks[i]);
- approximateBins[i - 1] = (float) (s - prev);
- prev = s;
- }
-
- return new Histogram(breaks, approximateBins);
- }
-
- /**
- * Computes a visual representation of the approximate histogram with a given number of equal-sized bins
- *
- * @param size number of equal-sized bins to divide the histogram into
- *
- * @return visual representation of the histogram
- */
- public Histogram toHistogram(int size)
- {
- Preconditions.checkArgument(size > 1, "histogram size must be greater than 1");
-
- float[] breaks = new float[size + 1];
- float delta = (max - min) / (size - 1);
- breaks[0] = min - delta;
- for (int i = 1; i < (breaks.length - 1); ++i) {
- breaks[i] = breaks[i - 1] + delta;
- }
- breaks[breaks.length - 1] = max;
- return toHistogram(breaks);
- }
-
- /**
- * Computes a visual representation given an initial breakpoint, offset, and a bucket size.
- *
- * @param bucketSize the size of each bucket
- * @param offset the location of one breakpoint
- *
- * @return visual representation of the histogram
- */
- public Histogram toHistogram(final float bucketSize, final float offset)
- {
- final float minFloor = ((float) Math.floor((min() - offset) / bucketSize) * bucketSize) + offset;
- final float lowerLimitFloor = ((float) Math.floor((lowerLimit - offset) / bucketSize) * bucketSize) + offset;
- final float firstBreak = Math.max(minFloor, lowerLimitFloor);
-
- final float maxCeil = ((float) Math.ceil((max() - offset) / bucketSize) * bucketSize) + offset;
- final float upperLimitCeil = ((float) Math.ceil((upperLimit - offset) / bucketSize) * bucketSize) + offset;
- final float lastBreak = Math.min(maxCeil, upperLimitCeil);
-
- final float cutoff = 0.1f;
-
- final ArrayList<Float> breaks = new ArrayList<>();
-
- // to deal with left inclusivity when the min is the same as a break
- final float bottomBreak = minFloor - bucketSize;
- if ((bottomBreak != firstBreak) && ((sum(firstBreak) - sum(bottomBreak)) > cutoff)) {
- breaks.add(bottomBreak);
- }
-
- float left = firstBreak;
- boolean leftSet = false;
-
- //the + bucketSize / 10 is because floating point addition is always slightly incorrect and so we need to account for that
- while ((left + bucketSize) <= (lastBreak + (bucketSize / 10))) {
- final float right = left + bucketSize;
-
- if ((sum(right) - sum(left)) > cutoff) {
- if (!leftSet) {
- breaks.add(left);
- }
- breaks.add(right);
- leftSet = true;
- } else {
- leftSet = false;
- }
-
- left = right;
- }
-
- if ((breaks.get(breaks.size() - 1) != maxCeil) && ((sum(maxCeil) - sum(breaks.get(breaks.size() - 1))) > cutoff)) {
- breaks.add(maxCeil);
- }
-
- return toHistogram(Floats.toArray(breaks));
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ArrayUtils.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ArrayUtils.java
deleted file mode 100644
index 9794b75..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/ArrayUtils.java
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.druidhistogram;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-
-public class ArrayUtils
-{
- public static int hashCode(long[] a, int fromIndex, int toIndex)
- {
- int hashCode = 1;
- int i = fromIndex;
- while (i < toIndex) {
- long v = a[i];
- hashCode = (31 * hashCode) + (int) (v ^ (v >>> 32));
- ++i;
- }
- return hashCode;
- }
-
- public static int hashCode(float[] a, int fromIndex, int toIndex)
- {
- int hashCode = 1;
- int i = fromIndex;
- while (i < toIndex) {
- hashCode = (31 * hashCode) + Float.floatToIntBits(a[i]);
- ++i;
- }
- return hashCode;
- }
-
- public static int hashCode(double[] a, int fromIndex, int toIndex)
- {
- int hashCode = 1;
- int i = fromIndex;
- while (i < toIndex) {
- long v = Double.doubleToLongBits(a[i]);
- hashCode = (31 * hashCode) + (int) (v ^ (v >>> 32));
- ++i;
- }
- return hashCode;
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/Histogram.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/Histogram.java
deleted file mode 100644
index 55cfa3f..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/Histogram.java
+++ /dev/null
@@ -1,102 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.druidhistogram;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-
-//import com.fasterxml.jackson.annotation.JsonProperty;
-
-import java.util.Arrays;
-
-public class Histogram
-{
- double[] breaks;
- double[] counts; //one less than breaks
-
- public Histogram(float[] breaks, double[] counts)
- {
- double[] retVal = new double[breaks.length];
- for (int i = 0; i < breaks.length; ++i) {
- retVal[i] = breaks[i];
- }
-
- this.breaks = retVal;
- this.counts = counts;
- }
-
- //@JsonProperty
- public double[] getBreaks()
- {
- return breaks;
- }
-
- //@JsonProperty
- public double[] getCounts()
- {
- return counts;
- }
-
- @Override
- public boolean equals(Object o)
- {
- if (this == o) {
- return true;
- }
- if ((o == null) || (getClass() != o.getClass())) {
- return false;
- }
-
- Histogram that = (Histogram) o;
-
- if (!Arrays.equals(getBreaks(), that.getBreaks())) {
- return false;
- }
- if (!Arrays.equals(getCounts(), that.getCounts())) {
- return false;
- }
- return true;
- }
-
- @Override
- public int hashCode()
- {
- int result = (getBreaks() != null ? ArrayUtils.hashCode(getBreaks(), 0, getBreaks().length) : 0);
- result = (31 * result) + (getCounts() != null ? ArrayUtils.hashCode(
- getCounts(),
- 0,
- getCounts().length
- ) : 0);
- return result;
- }
-
- @Override
- public String toString()
- {
- return "Histogram{" +
- "breaks=" + Arrays.toString(breaks) +
- ", counts=" + Arrays.toString(counts) +
- '}';
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/package-info.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/package-info.java
deleted file mode 100644
index 0957672..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/druidhistogram/package-info.java
+++ /dev/null
@@ -1,10 +0,0 @@
-/*
- * Copyright 2018, Yahoo! Inc. Licensed under the terms of the
- * Apache License 2.0. See LICENSE file at the project root for terms.
- */
-
-/**
- * @author Lee Rhodes
- */
-
-package com.yahoo.sketches.characterization.quantiles.druidhistogram;
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java
deleted file mode 100644
index 5f5d0c8..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/MomentSketchWrapper.java
+++ /dev/null
@@ -1,183 +0,0 @@
-/*
- * 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 com.yahoo.sketches.characterization.quantiles.momentsketch;
-
-//CHECKSTYLE.OFF: FinalLocalVariable
-//CHECKSTYLE.OFF: JavadocMethod
-//CHECKSTYLE.OFF: LineLength
-//CHECKSTYLE.OFF: OperatorWrap
-//CHECKSTYLE.OFF: NonEmptyAtclauseDescription
-//CHECKSTYLE.OFF: JavadocParagraph
-//CHECKSTYLE.OFF: WhitespaceAround
-//CHECKSTYLE.OFF: EmptyLineSeparator
-
-import java.nio.ByteBuffer;
-
-import com.github.stanfordfuturedata.momentsketch.MomentSolver;
-import com.github.stanfordfuturedata.momentsketch.MomentStruct;
-
-
-/**
- * Class for wrapping the operations of the moments sketch for use in
- * the moment sketch aggregator
- * {@link org.apache.druid.query.aggregation.momentsketch.aggregator.MomentSketchAggregatorFactory}.
- *
- * <p>
- * k controls the size and accuracy provided by the sketch.
- * The sinh function is used to compress the range of data to allow for more robust results
- * on skewed and long-tailed metrics, but slightly reducing accuracy on metrics with more uniform
- * distributions.
- */
-public class MomentSketchWrapper {
- // The MomentStruct object stores the relevant statistics about a metric distribution.
- protected MomentStruct data;
- // Whether we use arcsinh to compress the range
- protected boolean useArcSinh = true;
-
- public MomentSketchWrapper(int k) {
- data = new MomentStruct(k);
- }
-
- public MomentSketchWrapper(MomentStruct data) {
- this.data = data;
- }
-
- public void setCompressed(boolean flag) {
- useArcSinh = flag;
- }
-
- public boolean getCompressed() {
- return useArcSinh;
- }
-
- public int getK() {
- return data.power_sums.length;
- }
-
- public double[] getPowerSums() {
- return data.power_sums;
- }
-
- public double getMin() {
- if (useArcSinh) {
- return Math.sinh(data.min);
- } else {
- return data.min;
- }
- }
-
- public double getMax() {
- if (useArcSinh) {
- return Math.sinh(data.max);
- } else {
- return data.max;
- }
- }
-
- public void add(double rawX) {
- double x = rawX;
- if (useArcSinh) {
- // Since Java does not have a native arcsinh implementation we
- // compute it manually using the following formula.
- // This is the inverse operation of Math.sinh
- x = Math.log(rawX + Math.sqrt(1 + (rawX * rawX)));
- }
- data.add(x);
- }
-
- public void merge(MomentSketchWrapper other) {
- data.merge(other.data);
- }
-
- public byte[] toByteArray() {
- ByteBuffer bb = ByteBuffer.allocate((2 * Integer.BYTES) + ((data.power_sums.length + 2) * Double.BYTES));
- return toBytes(bb).array();
- }
-
- public MomentSolver getSolver() {
- MomentSolver ms = new MomentSolver(data);
- return ms;
- }
-
- /**
- * Estimates quantiles given the statistics in a moments sketch.
- *
- * @param fractions real values between [0,1] for which we want to estimate quantiles
- *
- * @return estimated quantiles.
- */
- public double[] getQuantiles(double[] fractions) {
- // The solver attempts to construct a distribution estimate which matches the
- // statistics tracked by the moments sketch. We can then read off quantile estimates
- // from the reconstructed distribution.
- // This operation can be relatively expensive (~1 ms) so we set the parameters from distribution
- // reconstruction to conservative values.
- MomentSolver ms = new MomentSolver(data);
- // Constants here are chosen to yield maximum precision while keeping solve times ~1ms on 2Ghz cpu
- // Grid size can be increased if longer solve times are acceptable
- ms.setGridSize(1024);
- ms.setMaxIter(15);
- ms.solve();
- double[] rawQuantiles = ms.getQuantiles(fractions);
- for (int i = 0; i < fractions.length; i++) {
- if (useArcSinh) {
- rawQuantiles[i] = Math.sinh(rawQuantiles[i]);
- }
- }
- return rawQuantiles;
- }
-
- public ByteBuffer toBytes(ByteBuffer bb) {
- int compressedInt = getCompressed() ? 1 : 0;
- bb.putInt(data.power_sums.length);
- bb.putInt(compressedInt);
- bb.putDouble(data.min);
- bb.putDouble(data.max);
- for (double x : data.power_sums) {
- bb.putDouble(x);
- }
- return bb;
- }
-
- public static MomentSketchWrapper fromBytes(ByteBuffer bb) {
- int k = bb.getInt();
- int compressedInt = bb.getInt();
- boolean compressed = (compressedInt > 0);
- MomentStruct m = new MomentStruct(k);
- m.min = bb.getDouble();
- m.max = bb.getDouble();
- for (int i = 0; i < k; i++) {
- m.power_sums[i] = bb.getDouble();
- }
- MomentSketchWrapper mw = new MomentSketchWrapper(m);
- mw.setCompressed(compressed);
- return mw;
- }
-
- public static MomentSketchWrapper fromByteArray(byte[] input) {
- ByteBuffer bb = ByteBuffer.wrap(input);
- return fromBytes(bb);
- }
-
- @Override
- public String toString() {
- return data.toString();
- }
-}
diff --git a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java b/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java
deleted file mode 100644
index 74e0f33..0000000
--- a/src/main/java/com/yahoo/sketches/characterization/quantiles/momentsketch/package-info.java
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * 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.
- */
-
-/**
- * @author Lee Rhodes
- */
-
-package com.yahoo.sketches.characterization.quantiles.momentsketch;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org