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 2024/02/29 19:44:24 UTC
(datasketches-java) branch debug_issue_514 created (now 4ac77573)
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a change to branch debug_issue_514
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
at 4ac77573 Update the built in shuffle class.
This branch includes the following new commits:
new 67cf69f8 Adding some asserts for self-merging and long overruns.
new 4ac77573 Update the built in shuffle class.
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.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
(datasketches-java) 01/02: Adding some asserts for self-merging and long overruns.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch debug_issue_514
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 67cf69f80f76e1f498105d581a471d70d8ba2f9e
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Feb 28 15:31:27 2024 -0800
Adding some asserts for self-merging and long overruns.
---
.../org/apache/datasketches/kll/KllDoublesHelper.java | 7 +++++--
.../org/apache/datasketches/kll/KllDoublesSketch.java | 3 ++-
.../java/org/apache/datasketches/kll/KllHelper.java | 1 +
.../datasketches/quantilescommon/QuantilesAPI.java | 1 +
.../java/org/apache/datasketches/common/Shuffle.java | 18 ++++++++++++++++++
5 files changed, 27 insertions(+), 3 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index 88da49e3..8a5c98b9 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -123,8 +123,7 @@ final class KllDoublesHelper {
}
//assumes readOnly = false and UPDATABLE, called from KllDoublesSketch::merge
- static void mergeDoubleImpl(final KllDoublesSketch mySketch,
- final KllDoublesSketch otherDblSk) {
+ static void mergeDoubleImpl(final KllDoublesSketch mySketch, final KllDoublesSketch otherDblSk) {
if (otherDblSk.isEmpty()) { return; }
//capture my key mutable fields before doing any merging
@@ -133,6 +132,8 @@ final class KllDoublesHelper {
final double myMax = myEmpty ? Double.NaN : mySketch.getMaxItem();
final int myMinK = mySketch.getMinK();
final long finalN = mySketch.getN() + otherDblSk.getN();
+ assert finalN <= Long.MAX_VALUE && finalN >= 0 :
+ "The input count has exceeded the capacity of a long and the capability of this sketch.";
//buffers that are referenced multiple times
final int otherNumLevels = otherDblSk.getNumLevels();
@@ -400,6 +401,8 @@ final class KllDoublesHelper {
// If we are at the current top level, add an empty level above it for convenience,
// but do not increment numLevels until later
if (curLevel == (numLevels - 1)) {
+ assert curLevel + 2 < 60 :
+ "The number of levels has exceeded the capability of this sketch.";
inLevels[curLevel + 2] = inLevels[curLevel + 1];
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index 3cef8471..8883734c 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -276,7 +276,8 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou
@Override
public final void merge(final KllSketch other) {
if (readOnly || sketchStructure != UPDATABLE) { throw new SketchesArgumentException(TGT_IS_READ_ONLY_MSG); }
- final KllDoublesSketch othDblSk = (KllDoublesSketch)other; //check cast first
+ if (this == other) { throw new SketchesArgumentException(SELF_MERGE_MSG); }
+ final KllDoublesSketch othDblSk = (KllDoublesSketch)other;
if (othDblSk.isEmpty()) { return; } //then check empty
KllDoublesHelper.mergeDoubleImpl(this, othDblSk);
kllDoublesSV = null;
diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java
index f1d1df9b..ae829506 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java
@@ -632,6 +632,7 @@ final class KllHelper {
//grow levels arr by one and copy the old data to the new array, extra space at the top.
myNewLevelsArr = Arrays.copyOf(myCurLevelsArr, myCurNumLevels + 2);
assert myNewLevelsArr.length == myCurLevelsArr.length + 1;
+ assert myNewLevelsArr.length <= 60 : "The number of levels has exceeded the capability of this sketch.";
myNewNumLevels = myCurNumLevels + 1;
sketch.incNumLevels(); //increment for off-heap
} else {
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java b/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java
index 38502eca..f433519e 100644
--- a/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java
+++ b/src/main/java/org/apache/datasketches/quantilescommon/QuantilesAPI.java
@@ -209,6 +209,7 @@ public interface QuantilesAPI {
static String NOT_SINGLE_ITEM_MSG = "Sketch does not have just one item. ";
static String MEM_REQ_SVR_NULL_MSG = "MemoryRequestServer must not be null. ";
static String TGT_IS_READ_ONLY_MSG = "Target sketch is Read Only, cannot write. ";
+ static String SELF_MERGE_MSG = "A sketch cannot merge with itself. ";
/**
* Gets the user configured parameter k, which controls the accuracy of the sketch
diff --git a/src/test/java/org/apache/datasketches/common/Shuffle.java b/src/test/java/org/apache/datasketches/common/Shuffle.java
index 992d15ab..223e3486 100644
--- a/src/test/java/org/apache/datasketches/common/Shuffle.java
+++ b/src/test/java/org/apache/datasketches/common/Shuffle.java
@@ -99,4 +99,22 @@ public final class Shuffle {
array[i2] = value;
}
+ /**
+ * Shuffle the given input array of type T
+ * @param array input array
+ */
+ public static <T> void shuffle(final T[] array) {
+ final int arrLen = array.length;
+ for (int i = 0; i < arrLen; i++) {
+ final int r = rand.nextInt(i + 1);
+ swap(array, i, r);
+ }
+ }
+
+ private static<T> void swap(final T[] array, final int i1, final int i2) {
+ final T value = array[i1];
+ array[i1] = array[i2];
+ array[i2] = value;
+ }
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
(datasketches-java) 02/02: Update the built in shuffle class.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch debug_issue_514
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 4ac7757366e9ea1ab5a27530324d0dca2fd3ca41
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Feb 29 11:42:49 2024 -0800
Update the built in shuffle class.
Includes generic type arrays and also gives the option of providing a
user source of randomness derived from java.util.Random.
---
.../org/apache/datasketches/common/Shuffle.java | 67 ++++++++++++++++++----
1 file changed, 57 insertions(+), 10 deletions(-)
diff --git a/src/test/java/org/apache/datasketches/common/Shuffle.java b/src/test/java/org/apache/datasketches/common/Shuffle.java
index 223e3486..af6c4f8b 100644
--- a/src/test/java/org/apache/datasketches/common/Shuffle.java
+++ b/src/test/java/org/apache/datasketches/common/Shuffle.java
@@ -28,10 +28,19 @@ public final class Shuffle {
private static final Random rand = new Random();
/**
- * Shuffle the given input float array
- * @param array input array
+ * Shuffle the given input array using a default source of randomness.
+ * @param array the array to be shuffled.
*/
public static void shuffle(final float[] array) {
+ shuffle(array, rand);
+ }
+
+ /**
+ * Shuffle the given input array using the given source of randomness.
+ * @param array the array to be shuffled.
+ * @param rand the source of randomness used to shuffle the list.
+ */
+ public static void shuffle(final float[] array, final Random rand) {
final int arrLen = array.length;
for (int i = 0; i < arrLen; i++) {
final int r = rand.nextInt(i + 1);
@@ -46,10 +55,19 @@ public final class Shuffle {
}
/**
- * Shuffle the given input double array
- * @param array input array
+ * Shuffle the given input array using a default source of randomness.
+ * @param array the array to be shuffled.
*/
public static void shuffle(final double[] array) {
+ shuffle(array, rand);
+ }
+
+ /**
+ * Shuffle the given input array using the given source of randomness.
+ * @param array the array to be shuffled.
+ * @param rand the source of randomness used to shuffle the list.
+ */
+ public static void shuffle(final double[] array, final Random rand) {
final int arrLen = array.length;
for (int i = 0; i < arrLen; i++) {
final int r = rand.nextInt(i + 1);
@@ -64,10 +82,19 @@ public final class Shuffle {
}
/**
- * Shuffle the given input long array
- * @param array input array
+ * Shuffle the given input array using a default source of randomness.
+ * @param array the array to be shuffled.
*/
public static void shuffle(final long[] array) {
+ shuffle(array, rand);
+ }
+
+ /**
+ * Shuffle the given input array using the given source of randomness.
+ * @param array the array to be shuffled.
+ * @param rand the source of randomness used to shuffle the list.
+ */
+ public static void shuffle(final long[] array, final Random rand) {
final int arrLen = array.length;
for (int i = 0; i < arrLen; i++) {
final int r = rand.nextInt(i + 1);
@@ -82,10 +109,19 @@ public final class Shuffle {
}
/**
- * Shuffle the given input int array
- * @param array input array
+ * Shuffle the given input array using a default source of randomness.
+ * @param array the array to be shuffled.
*/
public static void shuffle(final int[] array) {
+ shuffle(array, rand);
+ }
+
+ /**
+ * Shuffle the given input array using the given source of randomness.
+ * @param array the array to be shuffled.
+ * @param rand the source of randomness used to shuffle the list.
+ */
+ public static void shuffle(final int[] array, final Random rand) {
final int arrLen = array.length;
for (int i = 0; i < arrLen; i++) {
final int r = rand.nextInt(i + 1);
@@ -100,10 +136,21 @@ public final class Shuffle {
}
/**
- * Shuffle the given input array of type T
- * @param array input array
+ * Shuffle the given input array using a default source of randomness.
+ * @param array the array to be shuffled.
+ * @param <T> the component type of the given array.
*/
public static <T> void shuffle(final T[] array) {
+ shuffle(array, rand);
+ }
+
+ /**
+ * Shuffle the given input array using the given source of randomness.
+ * @param array the array to be shuffled.
+ * @param rand the source of randomness used to shuffle the list.
+ * @param <T> the component type of the given array.
+ */
+ public static <T> void shuffle(final T[] array, final Random rand) {
final int arrLen = array.length;
for (int i = 0; i < arrLen; i++) {
final int r = rand.nextInt(i + 1);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org