You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by al...@apache.org on 2022/06/24 23:44:08 UTC
[datasketches-java] branch kll_inclusive updated: inclusive quantiles
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch kll_inclusive
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
The following commit(s) were added to refs/heads/kll_inclusive by this push:
new a9541e8c inclusive quantiles
a9541e8c is described below
commit a9541e8c44a7b69b840ce10a9a3c73358415d19d
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Fri Jun 24 16:44:03 2022 -0700
inclusive quantiles
---
.../org/apache/datasketches/QuantilesHelper.java | 4 +-
.../apache/datasketches/kll/KllDoublesHelper.java | 14 +++--
.../kll/KllDoublesQuantileCalculator.java | 4 +-
.../apache/datasketches/kll/KllDoublesSketch.java | 70 +++++++++++++++++++++-
.../apache/datasketches/kll/KllFloatsHelper.java | 13 ++--
.../kll/KllFloatsQuantileCalculator.java | 4 +-
.../apache/datasketches/kll/KllFloatsSketch.java | 70 +++++++++++++++++++++-
.../datasketches/quantiles/DoublesAuxiliary.java | 2 +-
.../datasketches/kll/KllDoublesSketchTest.java | 56 +++++++++++++++++
.../datasketches/kll/KllFloatsSketchTest.java | 56 +++++++++++++++++
10 files changed, 270 insertions(+), 23 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/QuantilesHelper.java b/src/main/java/org/apache/datasketches/QuantilesHelper.java
index f128a0d2..2146134a 100644
--- a/src/main/java/org/apache/datasketches/QuantilesHelper.java
+++ b/src/main/java/org/apache/datasketches/QuantilesHelper.java
@@ -30,11 +30,11 @@ public class QuantilesHelper {
* @param array of weights where first element is zero
* @return total weight
*/ //used by classic Quantiles and KLL
- public static long convertToPrecedingCummulative(final long[] array) {
+ public static long convertToPrecedingCummulative(final long[] array, final boolean inclusive) {
long subtotal = 0;
for (int i = 0; i < array.length; i++) {
final long newSubtotal = subtotal + array[i];
- array[i] = subtotal;
+ array[i] = inclusive ? newSubtotal : subtotal;
subtotal = newSubtotal;
}
return subtotal;
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index bc3a1a9e..ceaeeb55 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -93,7 +93,7 @@ final class KllDoublesHelper {
return buckets;
}
- static double getDoublesQuantile(final KllSketch mine, final double fraction) {
+ static double getDoublesQuantile(final KllSketch mine, final double fraction, final boolean inclusive) {
if (mine.isEmpty()) { return Double.NaN; }
if (fraction < 0.0 || fraction > 1.0) {
throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
@@ -101,11 +101,11 @@ final class KllDoublesHelper {
//These two assumptions make KLL compatible with the previous classic Quantiles Sketch
if (fraction == 0.0) { return mine.getMinDoubleValue(); }
if (fraction == 1.0) { return mine.getMaxDoubleValue(); }
- final KllDoublesQuantileCalculator quant = KllDoublesHelper.getDoublesQuantileCalculator(mine);
+ final KllDoublesQuantileCalculator quant = KllDoublesHelper.getDoublesQuantileCalculator(mine, inclusive);
return quant.getQuantile(fraction);
}
- static double[] getDoublesQuantiles(final KllSketch mine, final double[] fractions) {
+ static double[] getDoublesQuantiles(final KllSketch mine, final double[] fractions, final boolean inclusive) {
if (mine.isEmpty()) { return null; }
KllDoublesQuantileCalculator quant = null;
final double[] quantiles = new double[fractions.length];
@@ -118,7 +118,7 @@ final class KllDoublesHelper {
else if (fraction == 1.0) { quantiles[i] = mine.getMaxDoubleValue(); }
else {
if (quant == null) {
- quant = KllDoublesHelper.getDoublesQuantileCalculator(mine);
+ quant = KllDoublesHelper.getDoublesQuantileCalculator(mine, inclusive);
}
quantiles[i] = quant.getQuantile(fraction);
}
@@ -433,14 +433,16 @@ final class KllDoublesHelper {
return new int[] {numLevels, targetItemCount, currentItemCount};
}
- private static KllDoublesQuantileCalculator getDoublesQuantileCalculator(final KllSketch mine) {
+ private static KllDoublesQuantileCalculator getDoublesQuantileCalculator(final KllSketch mine,
+ final boolean inclusive) {
final int[] myLevelsArr = mine.getLevelsArray();
final double[] myDoubleItemsArr = mine.getDoubleItemsArray();
if (!mine.isLevelZeroSorted()) {
Arrays.sort(myDoubleItemsArr, myLevelsArr[0], myLevelsArr[1]);
if (!mine.hasMemory()) { mine.setLevelZeroSorted(true); }
}
- return new KllDoublesQuantileCalculator(myDoubleItemsArr, myLevelsArr, mine.getNumLevels(), mine.getN());
+ return new KllDoublesQuantileCalculator(myDoubleItemsArr, myLevelsArr, mine.getNumLevels(), mine.getN(),
+ inclusive);
}
private static void incrementDoublesBucketsSortedLevel(
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.java b/src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.java
index 7870002f..3368afea 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.java
@@ -38,7 +38,7 @@ final class KllDoublesQuantileCalculator {
// assumes that all levels are sorted including level 0
KllDoublesQuantileCalculator(final double[] items, final int[] levels, final int numLevels,
- final long n) {
+ final long n, final boolean inclusive) {
n_ = n;
final int numItems = levels[numLevels] - levels[0];
items_ = new double[numItems];
@@ -46,7 +46,7 @@ final class KllDoublesQuantileCalculator {
levels_ = new int[numLevels + 1];
populateFromSketch(items, levels, numLevels, numItems);
blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
- QuantilesHelper.convertToPrecedingCummulative(weights_);
+ QuantilesHelper.convertToPrecedingCummulative(weights_, inclusive);
}
//For testing only. Allows testing of getQuantile without a sketch.
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index 10c0b1a0..cc9ccbef 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -242,7 +242,30 @@ public abstract class KllDoublesSketch extends KllSketch {
* @return the approximation to the value at the given fraction
*/
public double getQuantile(final double fraction) {
- return KllDoublesHelper.getDoublesQuantile(this, fraction);
+ return KllDoublesHelper.getDoublesQuantile(this, fraction, false);
+ }
+
+ /**
+ * Returns an approximation to the value of the data item
+ * that would be preceded by the given fraction of a hypothetical sorted
+ * version of the input stream so far.
+ *
+ * <p>We note that this method has a fairly large overhead (microseconds instead of nanoseconds)
+ * so it should not be called multiple times to get different quantiles from the same
+ * sketch. Instead use getQuantiles(), which pays the overhead only once.
+ *
+ * <p>If the sketch is empty this returns NaN.
+ *
+ * @param fraction the specified fractional position in the hypothetical sorted stream.
+ * These are also called normalized ranks or fractional ranks.
+ * If fraction = 0.0, the true minimum value of the stream is returned.
+ * If fraction = 1.0, the true maximum value of the stream is returned.
+ *
+ * @param inclusive if true, the given fraction (rank) is considered inclusive
+ * @return the approximation to the value at the given fraction
+ */
+ public double getQuantile(final double fraction, final boolean inclusive) {
+ return KllDoublesHelper.getDoublesQuantile(this, fraction, inclusive);
}
/**
@@ -275,7 +298,30 @@ public abstract class KllDoublesSketch extends KllSketch {
* array.
*/
public double[] getQuantiles(final double[] fractions) {
- return KllDoublesHelper.getDoublesQuantiles(this, fractions);
+ return KllDoublesHelper.getDoublesQuantiles(this, fractions, false);
+ }
+
+ /**
+ * This is a more efficient multiple-query version of getQuantile().
+ *
+ * <p>This returns an array that could have been generated by using getQuantile() with many
+ * different fractional ranks, but would be very inefficient.
+ * This method incurs the internal set-up overhead once and obtains multiple quantile values in
+ * a single query. It is strongly recommend that this method be used instead of multiple calls
+ * to getQuantile().
+ *
+ * <p>If the sketch is empty this returns null.
+ *
+ * @param fractions given array of fractional positions in the hypothetical sorted stream.
+ * These are also called normalized ranks or fractional ranks.
+ * These fractions must be in the interval [0.0, 1.0], inclusive.
+ *
+ * @param inclusive if true, the given fractions (ranks) are considered inclusive
+ * @return array of approximations to the given fractions in the same order as given fractions
+ * array.
+ */
+ public double[] getQuantiles(final double[] fractions, final boolean inclusive) {
+ return KllDoublesHelper.getDoublesQuantiles(this, fractions, inclusive);
}
/**
@@ -297,6 +343,26 @@ public abstract class KllDoublesSketch extends KllSketch {
return getQuantiles(org.apache.datasketches.Util.evenlySpaced(0.0, 1.0, numEvenlySpaced));
}
+ /**
+ * This is also a more efficient multiple-query version of getQuantile() and allows the caller to
+ * specify the number of evenly spaced fractional ranks.
+ *
+ * <p>If the sketch is empty this returns null.
+ *
+ * @param numEvenlySpaced an integer that specifies the number of evenly spaced fractional ranks.
+ * This must be a positive integer greater than 0. A value of 1 will return the min value.
+ * A value of 2 will return the min and the max value. A value of 3 will return the min,
+ * the median and the max value, etc.
+ *
+ * @param inclusive if true, the fractional ranks are considered inclusive
+ * @return array of approximations to the given fractions in the same order as given fractions
+ * array.
+ */
+ public double[] getQuantiles(final int numEvenlySpaced, final boolean inclusive) {
+ if (isEmpty()) { return null; }
+ return getQuantiles(org.apache.datasketches.Util.evenlySpaced(0.0, 1.0, numEvenlySpaced), inclusive);
+ }
+
/**
* Gets the upper bound of the value interval in which the true quantile of the given rank
* exists with a confidence of at least 99%.
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
index 3492405e..ee2b7486 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
@@ -93,7 +93,7 @@ final class KllFloatsHelper {
return buckets;
}
- static float getFloatsQuantile(final KllSketch mine, final double fraction) {
+ static float getFloatsQuantile(final KllSketch mine, final double fraction, final boolean inclusive) {
if (mine.isEmpty()) { return Float.NaN; }
if (fraction < 0.0 || fraction > 1.0) {
throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
@@ -101,11 +101,11 @@ final class KllFloatsHelper {
//These two assumptions make KLL compatible with the previous classic Quantiles Sketch
if (fraction == 0.0) { return mine.getMinFloatValue(); }
if (fraction == 1.0) { return mine.getMaxFloatValue(); }
- final KllFloatsQuantileCalculator quant = KllFloatsHelper.getFloatsQuantileCalculator(mine);
+ final KllFloatsQuantileCalculator quant = KllFloatsHelper.getFloatsQuantileCalculator(mine, inclusive);
return quant.getQuantile(fraction);
}
- static float[] getFloatsQuantiles(final KllSketch mine, final double[] fractions) {
+ static float[] getFloatsQuantiles(final KllSketch mine, final double[] fractions, final boolean inclusive) {
if (mine.isEmpty()) { return null; }
KllFloatsQuantileCalculator quant = null;
final float[] quantiles = new float[fractions.length];
@@ -118,7 +118,7 @@ final class KllFloatsHelper {
else if (fraction == 1.0) { quantiles[i] = mine.getMaxFloatValue(); }
else {
if (quant == null) {
- quant = KllFloatsHelper.getFloatsQuantileCalculator(mine);
+ quant = KllFloatsHelper.getFloatsQuantileCalculator(mine, inclusive);
}
quantiles[i] = quant.getQuantile(fraction);
}
@@ -433,14 +433,15 @@ final class KllFloatsHelper {
return new int[] {numLevels, targetItemCount, currentItemCount};
}
- private static KllFloatsQuantileCalculator getFloatsQuantileCalculator(final KllSketch mine) {
+ private static KllFloatsQuantileCalculator getFloatsQuantileCalculator(final KllSketch mine,
+ final boolean inclusive) {
final int[] myLevelsArr = mine.getLevelsArray();
final float[] myFloatItemsArr = mine.getFloatItemsArray();
if (!mine.isLevelZeroSorted()) {
Arrays.sort(myFloatItemsArr, myLevelsArr[0], myLevelsArr[1]);
if (!mine.hasMemory()) { mine.setLevelZeroSorted(true); }
}
- return new KllFloatsQuantileCalculator(myFloatItemsArr, myLevelsArr, mine.getNumLevels(), mine.getN());
+ return new KllFloatsQuantileCalculator(myFloatItemsArr, myLevelsArr, mine.getNumLevels(), mine.getN(), inclusive);
}
private static void incrementFloatBucketsSortedLevel(
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsQuantileCalculator.java b/src/main/java/org/apache/datasketches/kll/KllFloatsQuantileCalculator.java
index 87539fc0..761e8dd0 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsQuantileCalculator.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsQuantileCalculator.java
@@ -38,7 +38,7 @@ final class KllFloatsQuantileCalculator {
// assumes that all levels are sorted including level 0
KllFloatsQuantileCalculator(final float[] items, final int[] levels, final int numLevels,
- final long n) {
+ final long n, final boolean inclusive) {
n_ = n;
final int numItems = levels[numLevels] - levels[0];
items_ = new float[numItems];
@@ -46,7 +46,7 @@ final class KllFloatsQuantileCalculator {
levels_ = new int[numLevels + 1];
populateFromSketch(items, levels, numLevels, numItems);
blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
- QuantilesHelper.convertToPrecedingCummulative(weights_);
+ QuantilesHelper.convertToPrecedingCummulative(weights_, inclusive);
}
//For testing only. Allows testing of getQuantile without a sketch.
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
index 48664b0b..39772de3 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
@@ -242,7 +242,30 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return the approximation to the value at the given fraction
*/
public float getQuantile(final double fraction) {
- return KllFloatsHelper.getFloatsQuantile(this, fraction);
+ return KllFloatsHelper.getFloatsQuantile(this, fraction, false);
+ }
+
+ /**
+ * Returns an approximation to the value of the data item
+ * that would be preceded by the given fraction of a hypothetical sorted
+ * version of the input stream so far.
+ *
+ * <p>We note that this method has a fairly large overhead (microseconds instead of nanoseconds)
+ * so it should not be called multiple times to get different quantiles from the same
+ * sketch. Instead use getQuantiles(), which pays the overhead only once.
+ *
+ * <p>If the sketch is empty this returns NaN.
+ *
+ * @param fraction the specified fractional position in the hypothetical sorted stream.
+ * These are also called normalized ranks or fractional ranks.
+ * If fraction = 0.0, the true minimum value of the stream is returned.
+ * If fraction = 1.0, the true maximum value of the stream is returned.
+ *
+ * @param inclusive if true, the given fraction (rank) is considered inclusive
+ * @return the approximation to the value at the given fraction
+ */
+ public float getQuantile(final double fraction, final boolean inclusive) {
+ return KllFloatsHelper.getFloatsQuantile(this, fraction, inclusive);
}
/**
@@ -275,7 +298,30 @@ public abstract class KllFloatsSketch extends KllSketch {
* array.
*/
public float[] getQuantiles(final double[] fractions) {
- return KllFloatsHelper.getFloatsQuantiles(this, fractions);
+ return KllFloatsHelper.getFloatsQuantiles(this, fractions, false);
+ }
+
+ /**
+ * This is a more efficient multiple-query version of getQuantile().
+ *
+ * <p>This returns an array that could have been generated by using getQuantile() with many
+ * different fractional ranks, but would be very inefficient.
+ * This method incurs the internal set-up overhead once and obtains multiple quantile values in
+ * a single query. It is strongly recommend that this method be used instead of multiple calls
+ * to getQuantile().
+ *
+ * <p>If the sketch is empty this returns null.
+ *
+ * @param fractions given array of fractional positions in the hypothetical sorted stream.
+ * These are also called normalized ranks or fractional ranks.
+ * These fractions must be in the interval [0.0, 1.0], inclusive.
+ *
+ * @param inclusive if true, the given fractions (ranks) are considered inclusive
+ * @return array of approximations to the given fractions in the same order as given fractions
+ * array.
+ */
+ public float[] getQuantiles(final double[] fractions, final boolean inclusive) {
+ return KllFloatsHelper.getFloatsQuantiles(this, fractions, inclusive);
}
/**
@@ -297,6 +343,26 @@ public abstract class KllFloatsSketch extends KllSketch {
return getQuantiles(org.apache.datasketches.Util.evenlySpaced(0.0, 1.0, numEvenlySpaced));
}
+ /**
+ * This is also a more efficient multiple-query version of getQuantile() and allows the caller to
+ * specify the number of evenly spaced fractional ranks.
+ *
+ * <p>If the sketch is empty this returns null.
+ *
+ * @param numEvenlySpaced an integer that specifies the number of evenly spaced fractional ranks.
+ * This must be a positive integer greater than 0. A value of 1 will return the min value.
+ * A value of 2 will return the min and the max value. A value of 3 will return the min,
+ * the median and the max value, etc.
+ *
+ * @param inclusive if true, the fractional ranks are considered inclusive
+ * @return array of approximations to the given fractions in the same order as given fractions
+ * array.
+ */
+ public float[] getQuantiles(final int numEvenlySpaced, final boolean inclusive) {
+ if (isEmpty()) { return null; }
+ return getQuantiles(org.apache.datasketches.Util.evenlySpaced(0.0, 1.0, numEvenlySpaced), inclusive);
+ }
+
/**
* Gets the upper bound of the value interval in which the true quantile of the given rank
* exists with a confidence of at least 99%.
diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesAuxiliary.java b/src/main/java/org/apache/datasketches/quantiles/DoublesAuxiliary.java
index 307917d1..344d9c14 100644
--- a/src/main/java/org/apache/datasketches/quantiles/DoublesAuxiliary.java
+++ b/src/main/java/org/apache/datasketches/quantiles/DoublesAuxiliary.java
@@ -60,7 +60,7 @@ final class DoublesAuxiliary {
// taking advantage of the already sorted blocks of length k
blockyTandemMergeSort(itemsArr, cumWtsArr, numSamples, k);
- final long total = QuantilesHelper.convertToPrecedingCummulative(cumWtsArr);
+ final long total = QuantilesHelper.convertToPrecedingCummulative(cumWtsArr, false);
assert total == n;
auxN_ = n;
diff --git a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
index 3b8cb97b..1744ab41 100644
--- a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
@@ -88,6 +88,62 @@ public class KllDoublesSketchTest {
assertEquals(sketch.getQuantile(0.5), 1.0);
}
+ @Test
+ public void tenItems() {
+ final KllDoublesSketch sketch = KllDoublesSketch.newHeapInstance();
+ for (int i = 1; i <= 10; i++) { sketch.update(i); }
+ assertFalse(sketch.isEmpty());
+ assertEquals(sketch.getN(), 10);
+ assertEquals(sketch.getNumRetained(), 10);
+ for (int i = 1; i <= 10; i++) {
+ assertEquals(sketch.getRank(i), (i - 1) / 10.0);
+ assertEquals(sketch.getRank(i, false), (i - 1) / 10.0);
+ assertEquals(sketch.getRank(i, true), (i) / 10.0);
+ }
+ // inclusive = false (default)
+ assertEquals(sketch.getQuantile(0), 1); // always min value
+ assertEquals(sketch.getQuantile(0.1), 2);
+ assertEquals(sketch.getQuantile(0.2), 3);
+ assertEquals(sketch.getQuantile(0.3), 4);
+ assertEquals(sketch.getQuantile(0.4), 5);
+ assertEquals(sketch.getQuantile(0.5), 6);
+ assertEquals(sketch.getQuantile(0.6), 7);
+ assertEquals(sketch.getQuantile(0.7), 8);
+ assertEquals(sketch.getQuantile(0.8), 9);
+ assertEquals(sketch.getQuantile(0.9), 10);
+ assertEquals(sketch.getQuantile(1), 10); // always max value
+ // inclusive = true
+ assertEquals(sketch.getQuantile(0, true), 1); // always min value
+ assertEquals(sketch.getQuantile(0.1, true), 1);
+ assertEquals(sketch.getQuantile(0.2, true), 2);
+ assertEquals(sketch.getQuantile(0.3, true), 3);
+ assertEquals(sketch.getQuantile(0.4, true), 4);
+ assertEquals(sketch.getQuantile(0.5, true), 5);
+ assertEquals(sketch.getQuantile(0.6, true), 6);
+ assertEquals(sketch.getQuantile(0.7, true), 7);
+ assertEquals(sketch.getQuantile(0.8, true), 8);
+ assertEquals(sketch.getQuantile(0.9, true), 9);
+ assertEquals(sketch.getQuantile(1, true), 10); // always max value
+
+ // getQuantile() and getQuantiles() equivalence
+ {
+ // inclusive = false (default)
+ final double[] quantiles =
+ sketch.getQuantiles(new double[] {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1});
+ for (int i = 0; i <= 10; i++) {
+ assertEquals(sketch.getQuantile(i / 10.0), quantiles[i]);
+ }
+ }
+ {
+ // inclusive = true
+ final double[] quantiles =
+ sketch.getQuantiles(new double[] {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}, true);
+ for (int i = 0; i <= 10; i++) {
+ assertEquals(sketch.getQuantile(i / 10.0, true), quantiles[i]);
+ }
+ }
+ }
+
@Test
public void manyItemsEstimationMode() {
final KllDoublesSketch sketch = KllDoublesSketch.newHeapInstance();
diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
index 17244d21..9ead0adf 100644
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
@@ -89,6 +89,62 @@ public class KllFloatsSketchTest {
assertEquals(sketch.getQuantile(0.5), 1f);
}
+ @Test
+ public void tenItems() {
+ final KllFloatsSketch sketch = KllFloatsSketch.newHeapInstance();
+ for (int i = 1; i <= 10; i++) { sketch.update(i); }
+ assertFalse(sketch.isEmpty());
+ assertEquals(sketch.getN(), 10);
+ assertEquals(sketch.getNumRetained(), 10);
+ for (int i = 1; i <= 10; i++) {
+ assertEquals(sketch.getRank(i), (i - 1) / 10.0);
+ assertEquals(sketch.getRank(i, false), (i - 1) / 10.0);
+ assertEquals(sketch.getRank(i, true), (i) / 10.0);
+ }
+ // inclusive = false (default)
+ assertEquals(sketch.getQuantile(0), 1); // always min value
+ assertEquals(sketch.getQuantile(0.1), 2);
+ assertEquals(sketch.getQuantile(0.2), 3);
+ assertEquals(sketch.getQuantile(0.3), 4);
+ assertEquals(sketch.getQuantile(0.4), 5);
+ assertEquals(sketch.getQuantile(0.5), 6);
+ assertEquals(sketch.getQuantile(0.6), 7);
+ assertEquals(sketch.getQuantile(0.7), 8);
+ assertEquals(sketch.getQuantile(0.8), 9);
+ assertEquals(sketch.getQuantile(0.9), 10);
+ assertEquals(sketch.getQuantile(1), 10); // always max value
+ // inclusive = true
+ assertEquals(sketch.getQuantile(0, true), 1); // always min value
+ assertEquals(sketch.getQuantile(0.1, true), 1);
+ assertEquals(sketch.getQuantile(0.2, true), 2);
+ assertEquals(sketch.getQuantile(0.3, true), 3);
+ assertEquals(sketch.getQuantile(0.4, true), 4);
+ assertEquals(sketch.getQuantile(0.5, true), 5);
+ assertEquals(sketch.getQuantile(0.6, true), 6);
+ assertEquals(sketch.getQuantile(0.7, true), 7);
+ assertEquals(sketch.getQuantile(0.8, true), 8);
+ assertEquals(sketch.getQuantile(0.9, true), 9);
+ assertEquals(sketch.getQuantile(1, true), 10); // always max value
+
+ // getQuantile() and getQuantiles() equivalence
+ {
+ // inclusive = false (default)
+ final float[] quantiles =
+ sketch.getQuantiles(new double[] {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1});
+ for (int i = 0; i <= 10; i++) {
+ assertEquals(sketch.getQuantile(i / 10.0), quantiles[i]);
+ }
+ }
+ {
+ // inclusive = true
+ final float[] quantiles =
+ sketch.getQuantiles(new double[] {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}, true);
+ for (int i = 0; i <= 10; i++) {
+ assertEquals(sketch.getQuantile(i / 10.0, true), quantiles[i]);
+ }
+ }
+ }
+
@Test
public void manyItemsEstimationMode() {
final KllFloatsSketch sketch = KllFloatsSketch.newHeapInstance();
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org