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/07/15 22:54:36 UTC
[datasketches-java] branch quantiles_sketch_sorted_view updated: KllDoublesSketchSortedView
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch quantiles_sketch_sorted_view
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
The following commit(s) were added to refs/heads/quantiles_sketch_sorted_view by this push:
new 22cc1f81 KllDoublesSketchSortedView
22cc1f81 is described below
commit 22cc1f81fa672191838663c98d6390b0b3ac900b
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Fri Jul 15 15:54:30 2022 -0700
KllDoublesSketchSortedView
---
.../apache/datasketches/kll/KllDoublesHelper.java | 14 ++---
.../apache/datasketches/kll/KllDoublesSketch.java | 11 ++++
...ulator.java => KllDoublesSketchSortedView.java} | 30 ++++++----
.../kll/KllDoublesSketchSortedViewIterator.java | 68 ++++++++++++++++++++++
.../datasketches/kll/KllDoublesSketchTest.java | 54 +++++++++++++++++
5 files changed, 160 insertions(+), 17 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index 49bca2ec..af66ae9a 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -104,13 +104,13 @@ 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, inclusive);
+ final KllDoublesSketchSortedView quant = KllDoublesHelper.getDoublesSortedView(mine, true, inclusive);
return quant.getQuantile(fraction);
}
static double[] getDoublesQuantiles(final KllSketch mine, final double[] fractions, final boolean inclusive) {
if (mine.isEmpty()) { return null; }
- KllDoublesQuantileCalculator quant = null;
+ KllDoublesSketchSortedView quant = null;
final double[] quantiles = new double[fractions.length];
for (int i = 0; i < fractions.length; i++) {
final double fraction = fractions[i];
@@ -121,7 +121,7 @@ final class KllDoublesHelper {
else if (fraction == 1.0) { quantiles[i] = mine.getMaxDoubleValue(); }
else {
if (quant == null) {
- quant = KllDoublesHelper.getDoublesQuantileCalculator(mine, inclusive);
+ quant = KllDoublesHelper.getDoublesSortedView(mine, true, inclusive);
}
quantiles[i] = quant.getQuantile(fraction);
}
@@ -436,16 +436,16 @@ final class KllDoublesHelper {
return new int[] {numLevels, targetItemCount, currentItemCount};
}
- private static KllDoublesQuantileCalculator getDoublesQuantileCalculator(final KllSketch mine,
- final boolean inclusive) {
+ static KllDoublesSketchSortedView getDoublesSortedView(final KllSketch mine,
+ final boolean cumulative, 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(),
- inclusive);
+ return new KllDoublesSketchSortedView(myDoubleItemsArr, myLevelsArr, mine.getNumLevels(), mine.getN(),
+ cumulative, inclusive);
}
private static void incrementDoublesBucketsSortedLevel(
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index 0ee9b6f0..2aa4d9c1 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -408,6 +408,17 @@ public abstract class KllDoublesSketch extends KllSketch {
KllDoublesHelper.updateDouble(this, value);
}
+ /**
+ * Sorted view of the sketch.
+ * Complexity: linear merge of sorted levels plus sorting of the level 0.
+ * @param cumulative if true weights are cumulative
+ * @param inclusive if true cumulative weight of an item includes its own weight
+ * @return sorted view object
+ */
+ public KllDoublesSketchSortedView getSortedView(final boolean cumulative, final boolean inclusive) {
+ return KllDoublesHelper.getDoublesSortedView(this, cumulative, inclusive);
+ }
+
@Override //Artifact of inheritance
float[] getFloatItemsArray() { kllSketchThrow(MUST_NOT_CALL); return null; }
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
similarity index 88%
rename from src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.java
rename to src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
index 29252563..7428641c 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
@@ -22,13 +22,14 @@ package org.apache.datasketches.kll;
import java.util.Arrays;
import org.apache.datasketches.QuantilesHelper;
+import org.apache.datasketches.SketchesStateException;
/**
* Data structure for answering quantile queries based on the samples from KllSketch
* @author Kevin Lang
* @author Alexander Saydakov
*/
-final class KllDoublesQuantileCalculator {
+public final class KllDoublesSketchSortedView {
private final long n_;
private final double[] items_;
@@ -37,8 +38,8 @@ final class KllDoublesQuantileCalculator {
private int numLevels_;
// assumes that all levels are sorted including level 0
- KllDoublesQuantileCalculator(final double[] items, final int[] levels, final int numLevels,
- final long n, final boolean inclusive) {
+ KllDoublesSketchSortedView(final double[] items, final int[] levels, final int numLevels,
+ final long n, final boolean cumulative, final boolean inclusive) {
n_ = n;
final int numItems = levels[numLevels] - levels[0];
items_ = new double[numItems];
@@ -46,11 +47,13 @@ final class KllDoublesQuantileCalculator {
levels_ = new int[numLevels + 1];
populateFromSketch(items, levels, numLevels, numItems);
blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
- QuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
+ if (cumulative) {
+ QuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
+ }
}
//For testing only. Allows testing of getQuantile without a sketch.
- KllDoublesQuantileCalculator(final double[] items, final long[] weights, final long n) {
+ KllDoublesSketchSortedView(final double[] items, final long[] weights, final long n) {
n_ = n;
items_ = items;
weights_ = weights; //must be size of items + 1
@@ -58,6 +61,18 @@ final class KllDoublesQuantileCalculator {
numLevels_ = 0; //not used by test
}
+ public double getQuantile(final double rank) {
+ if (weights_[items_.length] != n_) {
+ throw new SketchesStateException("getQuantile must be used with cumulative view only");
+ }
+ final long pos = QuantilesHelper.posOfRank(rank, n_);
+ return approximatelyAnswerPositonalQuery(pos);
+ }
+
+ public KllDoublesSketchSortedViewIterator iterator() {
+ return new KllDoublesSketchSortedViewIterator(items_, weights_);
+ }
+
private static void blockyTandemMergeSort(final double[] items, final long[] weights,
final int[] levels, final int numLevels) {
if (numLevels == 1) { return; }
@@ -132,11 +147,6 @@ final class KllDoublesQuantileCalculator {
}
}
- double getQuantile(final double rank) {
- final long pos = QuantilesHelper.posOfRank(rank, n_);
- return approximatelyAnswerPositonalQuery(pos);
- }
-
private double approximatelyAnswerPositonalQuery(final long pos) {
assert pos >= 0;
assert pos < n_;
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedViewIterator.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedViewIterator.java
new file mode 100644
index 00000000..e2962658
--- /dev/null
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedViewIterator.java
@@ -0,0 +1,68 @@
+/*
+ * 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 org.apache.datasketches.kll;
+
+/**
+ * Iterator over KllDoublesSketchSortedView
+ */
+public class KllDoublesSketchSortedViewIterator {
+
+ private final double[] items_;
+ private final long[] weights_;
+ private int i_;
+
+ KllDoublesSketchSortedViewIterator(final double[] items, final long[] weights) {
+ items_ = items;
+ weights_ = weights;
+ i_ = -1;
+ }
+
+ /**
+ * Gets a value from the current entry.
+ * Don't call this before calling next() for the first time
+ * or after getting false from next().
+ * @return value from the current entry
+ */
+ public double getValue() {
+ return items_[i_];
+ }
+
+ /**
+ * Gets a weight for the value from the current entry.
+ * Don't call this before calling next() for the first time
+ * or after getting false from next().
+ * @return weight for the value from the current entry
+ */
+ public long getWeight() {
+ return weights_[i_];
+ }
+
+ /**
+ * Advancing the iterator and checking existence of the next entry
+ * is combined here for efficiency. This results in an undefined
+ * state of the iterator before the first call of this method.
+ * @return true if the next element exists
+ */
+ public boolean next() {
+ i_++;
+ return i_ < items_.length;
+ }
+
+}
diff --git a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
index 7ba7951a..55d03b04 100644
--- a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
@@ -27,6 +27,7 @@ import static org.testng.Assert.assertTrue;
import static org.testng.Assert.fail;
import org.apache.datasketches.SketchesArgumentException;
+import org.apache.datasketches.SketchesStateException;
import org.apache.datasketches.memory.DefaultMemoryRequestServer;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
@@ -525,4 +526,57 @@ public class KllDoublesSketchTest {
assertTrue(compactSize < updateSize);
}
+ @Test
+ public void sortedView() {
+ KllDoublesSketch sk = KllDoublesSketch.newHeapInstance();
+ sk.update(3);
+ sk.update(1);
+ sk.update(2);
+ { // non-cumulative (inclusive does not matter in this case)
+ KllDoublesSketchSortedView view = sk.getSortedView(false, false);
+ KllDoublesSketchSortedViewIterator it = view.iterator();
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 1);
+ assertEquals(it.getWeight(), 1);
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 2);
+ assertEquals(it.getWeight(), 1);
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 3);
+ assertEquals(it.getWeight(), 1);
+ assertEquals(it.next(), false);
+ try {
+ view.getQuantile(0);
+ fail();
+ } catch(SketchesStateException e) {}
+ }
+ { // cumulative, non-inclusive
+ KllDoublesSketchSortedView view = sk.getSortedView(true, false);
+ KllDoublesSketchSortedViewIterator it = view.iterator();
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 1);
+ assertEquals(it.getWeight(), 0);
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 2);
+ assertEquals(it.getWeight(), 1);
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 3);
+ assertEquals(it.getWeight(), 2);
+ assertEquals(it.next(), false);
+ }
+ { // cumulative, inclusive
+ KllDoublesSketchSortedView view = sk.getSortedView(true, true);
+ KllDoublesSketchSortedViewIterator it = view.iterator();
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 1);
+ assertEquals(it.getWeight(), 1);
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 2);
+ assertEquals(it.getWeight(), 2);
+ assertEquals(it.next(), true);
+ assertEquals(it.getValue(), 3);
+ assertEquals(it.getWeight(), 3);
+ assertEquals(it.next(), false);
+ }
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org