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/23 22:03:57 UTC
[datasketches-java] branch kll_inclusive created (now 5a64985c)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch kll_inclusive
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
at 5a64985c inclusive rank
This branch includes the following new commits:
new 5a64985c inclusive rank
The 1 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.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 01/01: inclusive rank
Posted by al...@apache.org.
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
commit 5a64985c1664f0cb631f8dc54b02c34af9c33a60
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Thu Jun 23 15:03:51 2022 -0700
inclusive rank
---
.../apache/datasketches/kll/KllDoublesHelper.java | 4 ++--
.../apache/datasketches/kll/KllDoublesSketch.java | 20 +++++++++++++++++++-
.../org/apache/datasketches/kll/KllFloatsHelper.java | 4 ++--
.../org/apache/datasketches/kll/KllFloatsSketch.java | 20 +++++++++++++++++++-
.../datasketches/kll/KllDoublesSketchTest.java | 4 ++++
.../apache/datasketches/kll/KllFloatsSketchTest.java | 4 ++++
6 files changed, 50 insertions(+), 6 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index 3f9e1368..bc3a1a9e 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -36,7 +36,7 @@ import org.apache.datasketches.SketchesArgumentException;
*/
final class KllDoublesHelper {
- static double getDoubleRank(final KllSketch mine, final double value) {
+ static double getDoubleRank(final KllSketch mine, final double value, final boolean inclusive) {
if (mine.isEmpty()) { return Double.NaN; }
int level = 0;
int weight = 1;
@@ -47,7 +47,7 @@ final class KllDoublesHelper {
final int fromIndex = myLevelsArr[level];
final int toIndex = myLevelsArr[level + 1]; // exclusive
for (int i = fromIndex; i < toIndex; i++) {
- if (myDoubleItemsArr[i] < value) {
+ if (inclusive ? value >= myDoubleItemsArr[i] : myDoubleItemsArr[i] < value) {
total += weight;
} else if (level > 0 || mine.isLevelZeroSorted()) {
break; // levels above 0 are sorted, no point comparing further
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index 6ef6a172..10c0b1a0 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -321,7 +321,25 @@ public abstract class KllDoublesSketch extends KllSketch {
* @return an approximate rank of the given value
*/
public double getRank(final double value) {
- return KllDoublesHelper.getDoubleRank(this, value);
+ return KllDoublesHelper.getDoubleRank(this, value, false);
+ }
+
+ /**
+ * Returns an approximation to the normalized (fractional) rank of the given value from 0 to 1,
+ * inclusive.
+ *
+ * <p>The resulting approximation has a probabilistic guarantee that can be obtained from the
+ * getNormalizedRankError(false) function.
+ *
+ * <p>If the sketch is empty this returns NaN.</p>
+ *
+ * @param value to be ranked
+ * @param inclusive if true the weight of the given value is included into the rank.
+ * Otherwise the rank equals the sum of the weights of all values that are less than the given value
+ * @return an approximate rank of the given value
+ */
+ public double getRank(final double value, final boolean inclusive) {
+ return KllDoublesHelper.getDoubleRank(this, value, inclusive);
}
/**
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
index 45dda8d0..3492405e 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
@@ -36,7 +36,7 @@ import org.apache.datasketches.SketchesArgumentException;
*/
final class KllFloatsHelper {
- static double getFloatRank(final KllSketch mine, final float value) {
+ static double getFloatRank(final KllSketch mine, final float value, final boolean inclusive) {
if (mine.isEmpty()) { return Double.NaN; }
int level = 0;
int weight = 1;
@@ -47,7 +47,7 @@ final class KllFloatsHelper {
final int fromIndex = myLevelsArr[level];
final int toIndex = myLevelsArr[level + 1]; // exclusive
for (int i = fromIndex; i < toIndex; i++) {
- if (myFloatItemsArr[i] < value) {
+ if (inclusive ? value >= myFloatItemsArr[i] : myFloatItemsArr[i] < value) {
total += weight;
} else if (level > 0 || mine.isLevelZeroSorted()) {
break; // levels above 0 are sorted, no point comparing further
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
index 7f0b0f10..48664b0b 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
@@ -321,7 +321,25 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return an approximate rank of the given value
*/
public double getRank(final float value) {
- return KllFloatsHelper.getFloatRank(this, value);
+ return KllFloatsHelper.getFloatRank(this, value, false);
+ }
+
+ /**
+ * Returns an approximation to the normalized (fractional) rank of the given value from 0 to 1,
+ * inclusive.
+ *
+ * <p>The resulting approximation has a probabilistic guarantee that can be obtained from the
+ * getNormalizedRankError(false) function.
+ *
+ * <p>If the sketch is empty this returns NaN.</p>
+ *
+ * @param value to be ranked
+ * @param inclusive if true the weight of the given value is included into the rank.
+ * Otherwise the rank equals the sum of the weights of all values that are less than the given value
+ * @return an approximate rank of the given value
+ */
+ public double getRank(final float value, final boolean inclusive) {
+ return KllFloatsHelper.getFloatRank(this, value, inclusive);
}
/**
diff --git a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
index b2e3eda1..3b8cb97b 100644
--- a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
@@ -79,6 +79,10 @@ public class KllDoublesSketchTest {
assertEquals(sketch.getNumRetained(), 1);
assertEquals(sketch.getRank(1), 0.0);
assertEquals(sketch.getRank(2), 1.0);
+ assertEquals(sketch.getRank(1, false), 0.0);
+ assertEquals(sketch.getRank(2, false), 1.0);
+ assertEquals(sketch.getRank(0, true), 0.0);
+ assertEquals(sketch.getRank(1, true), 1.0);
assertEquals(sketch.getMinValue(), 1.0);
assertEquals(sketch.getMaxValue(), 1.0);
assertEquals(sketch.getQuantile(0.5), 1.0);
diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
index 09bda87d..17244d21 100644
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
@@ -80,6 +80,10 @@ public class KllFloatsSketchTest {
assertEquals(sketch.getNumRetained(), 1);
assertEquals(sketch.getRank(1), 0.0);
assertEquals(sketch.getRank(2), 1.0);
+ assertEquals(sketch.getRank(1, false), 0.0);
+ assertEquals(sketch.getRank(2, false), 1.0);
+ assertEquals(sketch.getRank(0, true), 0.0);
+ assertEquals(sketch.getRank(1, true), 1.0);
assertEquals(sketch.getMinValue(), 1f);
assertEquals(sketch.getMaxValue(), 1f);
assertEquals(sketch.getQuantile(0.5), 1f);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org