You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "leerho (via GitHub)" <gi...@apache.org> on 2024/04/16 05:40:38 UTC
[PR] Implemented fix for min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
leerho opened a new pull request, #547:
URL: https://github.com/apache/datasketches-java/pull/547
Also fixed a problem I discovered in the deserialization for Boolean quantiles, but it would also have shown up with other types. The data was ok, but the max value would have been incorrect.
Also fixed some problems with some of the tests.
Along the way I also replaced "back-slash-n" with platform independent "LS" in the files I touched.
Also moved some functions like getCDF(..) and getPMF(...) into parent interfaces as default functions. Now the three parent interfaces for Doubles SV, Floats SV and Items SV are all code-parallel.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568009457
##########
src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java:
##########
@@ -34,24 +35,36 @@ public final class DoublesSketchSortedView implements DoublesSortedView {
private final double[] quantiles;
private final long[] cumWeights; //cumulative natural weights
private final long totalN;
- private final double maxItem;
- private final double minItem;
/**
* Construct from elements, also used in testing.
* @param quantiles sorted array of quantiles
* @param cumWeights sorted, monotonically increasing cumulative weights.
- * @param totalN the total number of items presented to the sketch.
- * @param maxItem of type double
- * @param minItem of type double
+ * @param sk the underlying quantile sketch.
*/
- public DoublesSketchSortedView(final double[] quantiles, final long[] cumWeights, final long totalN,
- final double maxItem, final double minItem) {
- this.quantiles = quantiles;
- this.cumWeights = cumWeights;
+ public DoublesSketchSortedView(
+ final double[] quantiles,
+ final long[] cumWeights,
+ final QuantilesDoublesAPI sk) {
+ final DoublesPair dPair =
+ IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, sk.getMaxItem(), sk.getMinItem());
+ this.quantiles = dPair.quantiles;
+ this.cumWeights = dPair.cumWeights;
+ this.totalN = sk.getN();
+ }
+
+ //Used for testing
Review Comment:
Constructors like this are ... not great. We should really be trying to find ways to test w/o special constructors like this. Not gonna "require changes" because of it, but just noting it.
##########
src/main/java/org/apache/datasketches/kll/KllItemsSketch.java:
##########
@@ -422,49 +422,50 @@ private final ItemsSketchSortedView<T> refreshSortedView() {
@SuppressWarnings({"rawtypes"})
private final class CreateSortedView {
T[] quantiles;
- long[] cumWeights;
+ long[] cumWeights; //The new cumWeights array
ItemsSketchSortedView<T> getSV() {
- if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
- if (getN() == 0) { throw new SketchesArgumentException(EMPTY_MSG); }
+ if (isEmpty() || getN() == 0) { throw new SketchesArgumentException(EMPTY_MSG); }
final T[] srcQuantiles = getTotalItemsArray();
- final int[] srcLevels = levelsArr;
+ final int[] srcLevelsArr = levelsArr;
final int srcNumLevels = getNumLevels();
if (!isLevelZeroSorted()) {
- Arrays.sort(srcQuantiles, srcLevels[0], srcLevels[1], comparator);
+ Arrays.sort(srcQuantiles, srcLevelsArr[0], srcLevelsArr[1], comparator);
if (!hasMemory()) { setLevelZeroSorted(true); }
}
final int numQuantiles = getNumRetained();
quantiles = (T[]) Array.newInstance(serDe.getClassOfT(), numQuantiles);
cumWeights = new long[numQuantiles];
- populateFromSketch(srcQuantiles, srcLevels, srcNumLevels, numQuantiles);
+ populateFromSketch(srcQuantiles, srcLevelsArr, srcNumLevels, numQuantiles);
final QuantilesGenericAPI<T> sk = KllItemsSketch.this;
return new ItemsSketchSortedView(quantiles, cumWeights, sk);
}
- private void populateFromSketch(final Object[] srcQuantiles, final int[] srcLevels,
+ private void populateFromSketch(final Object[] srcQuantiles, final int[] srcLevelsArr,
final int srcNumLevels, final int numItems) {
- final int[] myLevels = new int[srcNumLevels + 1];
- final int offset = srcLevels[0];
- System.arraycopy(srcQuantiles, offset, quantiles, 0, numItems);
+ //Remove free space from both itemsArray and levels array
+ final int[] myLevelsArr = new int[srcLevelsArr.length];
Review Comment:
unclear why using this instead of srcNumLevels+1 as before, but gonna trust it's fine either way
##########
src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java:
##########
@@ -127,7 +145,17 @@ public interface GenericSortedView<T> extends PartitioningFeature<T>, SketchPar
* @return a PMF array of m+1 probability masses as doubles on the interval [0.0, 1.0].
* @throws IllegalArgumentException if sketch is empty.
*/
- double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ //double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
Review Comment:
remove commented-out line?
##########
src/test/java/org/apache/datasketches/kll/KllMiscItemsTest.java:
##########
@@ -34,22 +34,17 @@
import org.apache.datasketches.common.ArrayOfStringsSerDe;
import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.common.Util;
-import org.apache.datasketches.kll.KllSketch.SketchType;
-import org.apache.datasketches.quantilescommon.GenericSortedViewIterator;
-import org.apache.datasketches.quantilescommon.ItemsSketchSortedView;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
-import org.apache.datasketches.quantilescommon.DoublesSortedViewIterator;
-import org.apache.datasketches.quantilescommon.GenericSortedView;
import org.apache.datasketches.quantilescommon.GenericSortedViewIterator;
+import org.apache.datasketches.quantilescommon.ItemsSketchSortedView;
import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-@SuppressWarnings("unused")
+//@SuppressWarnings("unused")
Review Comment:
remove commented out line if not needed?
##########
src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java:
##########
@@ -127,7 +145,17 @@ public interface GenericSortedView<T> extends PartitioningFeature<T>, SketchPar
* @return a PMF array of m+1 probability masses as doubles on the interval [0.0, 1.0].
* @throws IllegalArgumentException if sketch is empty.
*/
- double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ //double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ default double[] getPMF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {
+ if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
+ GenericSortedView.validateItems(splitPoints, getComparator());
+ final double[] buckets = getCDF(splitPoints, searchCrit);
+ final int len = buckets.length;
+ for (int i = len; i-- > 1; ) {
Review Comment:
can just use `int i = buckets.length` here. clearly not wrong, but not necessary to define `len` :)
##########
src/main/java/org/apache/datasketches/quantilescommon/IncludeMinMax.java:
##########
@@ -0,0 +1,179 @@
+/*
+ * 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.quantilescommon;
+
+import java.lang.reflect.Array;
+import java.util.Comparator;
+
+/**
+ * This class reinserts the min and max values into the sorted view arrays as required.
+ */
+public class IncludeMinMax {
+
+ public static class DoublesPair {
+ public double[] quantiles;
+ public long[] cumWeights;
+
+ public DoublesPair(final double[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static class FloatsPair {
+ public float[] quantiles;
+ public long[] cumWeights;
+
+ public FloatsPair(final float[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static class ItemsPair<T> {
+ public T[] quantiles;
+ public long[] cumWeights;
+
+ public ItemsPair(final T[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static DoublesPair includeDoublesMinMax(
+ final double[] quantilesIn,
+ final long[] cumWeightsIn,
+ final double maxItem,
+ final double minItem) {
+ final int lenIn = cumWeightsIn.length;
+ final boolean adjLow = quantilesIn[0] != minItem; //if true, adjust the low end
+ final boolean adjHigh = quantilesIn[lenIn - 1] != maxItem; //if true, adjust the high end
+ int adjLen = lenIn; //this will be the length of the local copies of quantiles and cumWeights
+ adjLen += adjLow ? 1 : 0;
+ adjLen += adjHigh ? 1 : 0;
+ final double[] adjQuantiles;
+ final long[] adjCumWeights;
+ if (adjLen > lenIn) { //is any adjustment required at all?
+ adjQuantiles = new double[adjLen];
+ adjCumWeights = new long[adjLen];
+ final int offset = adjLow ? 1 : 0;
+ System.arraycopy(quantilesIn, 0, adjQuantiles, offset, lenIn);
+ System.arraycopy(cumWeightsIn,0, adjCumWeights, offset, lenIn);
+
+ //Adjust the low end if required.
Review Comment:
asked on slack and we don't need to adjust the next item's weight cuz it's already cumulative here. but can we add a short comment about that for future reference?
##########
src/test/java/org/apache/datasketches/quantilescommon/IncludeMinMaxTest.java:
##########
@@ -0,0 +1,199 @@
+/*
+ * 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.quantilescommon;
+
+import static org.apache.datasketches.common.Util.LS;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.DoublesPair;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.FloatsPair;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.ItemsPair;
+import static org.testng.Assert.assertEquals;
+
+import java.util.Comparator;
+
+import org.testng.annotations.Test;
+
+/**
+ * Checks the IncludeMinMax process
+ */
+public final class IncludeMinMaxTest {
+
+ @Test
+ public static void checkDoublesEndsAdjustment() {
+ final double[] quantiles = {2, 4, 6, 7};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final double maxItem = 8;
+ final double minItem = 1;
+ final DoublesPair dPair = IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, maxItem, minItem);
+ final double[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10.1f %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
Review Comment:
i think it'd be good to assert that the adjQuantiles array is 2 longer than the original quantiles array in here, too.
The printfs might be convient when debugging but they're basically no-ops in tests (and I treat them as such when reviewing). We want to make sure we assert on the expected
end-user behavior. And in this case, that's that the arrays are longer because we add in min and max.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568112636
##########
src/test/java/org/apache/datasketches/quantilescommon/IncludeMinMaxTest.java:
##########
@@ -0,0 +1,199 @@
+/*
+ * 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.quantilescommon;
+
+import static org.apache.datasketches.common.Util.LS;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.DoublesPair;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.FloatsPair;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.ItemsPair;
+import static org.testng.Assert.assertEquals;
+
+import java.util.Comparator;
+
+import org.testng.annotations.Test;
+
+/**
+ * Checks the IncludeMinMax process
+ */
+public final class IncludeMinMaxTest {
+
+ @Test
+ public static void checkDoublesEndsAdjustment() {
+ final double[] quantiles = {2, 4, 6, 7};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final double maxItem = 8;
+ final double minItem = 1;
+ final DoublesPair dPair = IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, maxItem, minItem);
+ final double[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10.1f %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
Review Comment:
Done.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho merged PR #547:
URL: https://github.com/apache/datasketches-java/pull/547
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568104361
##########
src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java:
##########
@@ -34,24 +35,36 @@ public final class DoublesSketchSortedView implements DoublesSortedView {
private final double[] quantiles;
private final long[] cumWeights; //cumulative natural weights
private final long totalN;
- private final double maxItem;
- private final double minItem;
/**
* Construct from elements, also used in testing.
* @param quantiles sorted array of quantiles
* @param cumWeights sorted, monotonically increasing cumulative weights.
- * @param totalN the total number of items presented to the sketch.
- * @param maxItem of type double
- * @param minItem of type double
+ * @param sk the underlying quantile sketch.
*/
- public DoublesSketchSortedView(final double[] quantiles, final long[] cumWeights, final long totalN,
- final double maxItem, final double minItem) {
- this.quantiles = quantiles;
- this.cumWeights = cumWeights;
+ public DoublesSketchSortedView(
+ final double[] quantiles,
+ final long[] cumWeights,
+ final QuantilesDoublesAPI sk) {
+ final DoublesPair dPair =
+ IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, sk.getMaxItem(), sk.getMinItem());
+ this.quantiles = dPair.quantiles;
+ this.cumWeights = dPair.cumWeights;
+ this.totalN = sk.getN();
+ }
+
+ //Used for testing
Review Comment:
Some of the tests would be very difficult to reproduce without this.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568105530
##########
src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java:
##########
@@ -127,7 +145,17 @@ public interface GenericSortedView<T> extends PartitioningFeature<T>, SketchPar
* @return a PMF array of m+1 probability masses as doubles on the interval [0.0, 1.0].
* @throws IllegalArgumentException if sketch is empty.
*/
- double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ //double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
Review Comment:
Yep, will fix.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568108645
##########
src/test/java/org/apache/datasketches/kll/KllMiscItemsTest.java:
##########
@@ -34,22 +34,17 @@
import org.apache.datasketches.common.ArrayOfStringsSerDe;
import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.common.Util;
-import org.apache.datasketches.kll.KllSketch.SketchType;
-import org.apache.datasketches.quantilescommon.GenericSortedViewIterator;
-import org.apache.datasketches.quantilescommon.ItemsSketchSortedView;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
-import org.apache.datasketches.quantilescommon.DoublesSortedViewIterator;
-import org.apache.datasketches.quantilescommon.GenericSortedView;
import org.apache.datasketches.quantilescommon.GenericSortedViewIterator;
+import org.apache.datasketches.quantilescommon.ItemsSketchSortedView;
import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-@SuppressWarnings("unused")
+//@SuppressWarnings("unused")
Review Comment:
Yep. Done.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568106406
##########
src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java:
##########
@@ -127,7 +145,17 @@ public interface GenericSortedView<T> extends PartitioningFeature<T>, SketchPar
* @return a PMF array of m+1 probability masses as doubles on the interval [0.0, 1.0].
* @throws IllegalArgumentException if sketch is empty.
*/
- double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ //double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ default double[] getPMF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {
+ if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
+ GenericSortedView.validateItems(splitPoints, getComparator());
+ final double[] buckets = getCDF(splitPoints, searchCrit);
+ final int len = buckets.length;
+ for (int i = len; i-- > 1; ) {
Review Comment:
Yep, will fix.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented fix for min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#issuecomment-2059585143
**Changes by file:**
**/kll/**
**KllDirectCompactItemsSketch**
- Fix for getMaxItem
**KllDoublesSketch**
- Propagation of new SV constructor signature
**KllFloatsSketch**
- Propagation of new SV constructor signature
**KllHeapDoublesSketch**
- Removed //TODO
**KllItemsSketch**
- Fixed a problem in toString(...)
**KllMemoryValidate**
- add code doc for better understanding
**/quantiles/**
**DoublesSketch**
- Propagation of new SV constructor signature
**ItemsUtil**
- Removed obsolete code comment
**/quantilescommon/**
**DoublesSketchSortedView**
- Revised the main constructor to include Min/Max fix.
- Added separate test constructor also with Min/Max fix
- Removed unneeded class members for min/max
**FloatsSketchSortedView**
- Revised the main constructor to include Min/Max fix.
- Added separate test constructor also with Min/Max fix
- Removed unneeded class members for min/max
**GenericSortedView**
- Moved getCDF() and getPMF() from ItemsSketchSortedView to here as an interface default implementation. This is consitent with how floats and dobles are implemented.
**IncludeMinMax**
- A new class that consolidates all new include Min and Max code for floats, doubles and item in one place.
**ItemsSketchSortedView**
- Revised the main constructor to include Min/Max fix.
- Added separate test constructor also with Min/Max fix
- Removed unneeded class members for min/max
**/req/**
**ReqSketch**
- Propagation of new SV constructor signature
**/test/...**
**/kll/**
**KllDirectCompactItemsSketch**
- Minor restructuring and added diagnostic print statements
**KllMiscDoublesTest**
- Redesigned a test to accommodate new min/max adjustments
- Apply "/n" to "LS" corrections
**KllMiscFloatsTest**
- Redesigned a test to accommodate new min/max adjustments
- Apply "/n" to "LS" corrections
**KllMiscItemsTest**
- Redesigned a test to accommodate new min/max adjustments
- Apply "/n" to "LS" corrections
**/quantilescommon/**
**IncludeMinMaxTest**
- tests for the new IncludeMinMax class
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#issuecomment-2059661088
> We changed the behavior of the sorted view to ensure the min and max values are always represented, which, we believe, will provide a more practical information to users of these distributions without distorting the resulting data. -- @jmalkin
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568103222
##########
src/main/java/org/apache/datasketches/kll/KllItemsSketch.java:
##########
@@ -422,49 +422,50 @@ private final ItemsSketchSortedView<T> refreshSortedView() {
@SuppressWarnings({"rawtypes"})
private final class CreateSortedView {
T[] quantiles;
- long[] cumWeights;
+ long[] cumWeights; //The new cumWeights array
ItemsSketchSortedView<T> getSV() {
- if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
- if (getN() == 0) { throw new SketchesArgumentException(EMPTY_MSG); }
+ if (isEmpty() || getN() == 0) { throw new SketchesArgumentException(EMPTY_MSG); }
final T[] srcQuantiles = getTotalItemsArray();
- final int[] srcLevels = levelsArr;
+ final int[] srcLevelsArr = levelsArr;
final int srcNumLevels = getNumLevels();
if (!isLevelZeroSorted()) {
- Arrays.sort(srcQuantiles, srcLevels[0], srcLevels[1], comparator);
+ Arrays.sort(srcQuantiles, srcLevelsArr[0], srcLevelsArr[1], comparator);
if (!hasMemory()) { setLevelZeroSorted(true); }
}
final int numQuantiles = getNumRetained();
quantiles = (T[]) Array.newInstance(serDe.getClassOfT(), numQuantiles);
cumWeights = new long[numQuantiles];
- populateFromSketch(srcQuantiles, srcLevels, srcNumLevels, numQuantiles);
+ populateFromSketch(srcQuantiles, srcLevelsArr, srcNumLevels, numQuantiles);
final QuantilesGenericAPI<T> sk = KllItemsSketch.this;
return new ItemsSketchSortedView(quantiles, cumWeights, sk);
}
- private void populateFromSketch(final Object[] srcQuantiles, final int[] srcLevels,
+ private void populateFromSketch(final Object[] srcQuantiles, final int[] srcLevelsArr,
final int srcNumLevels, final int numItems) {
- final int[] myLevels = new int[srcNumLevels + 1];
- final int offset = srcLevels[0];
- System.arraycopy(srcQuantiles, offset, quantiles, 0, numItems);
+ //Remove free space from both itemsArray and levels array
+ final int[] myLevelsArr = new int[srcLevelsArr.length];
Review Comment:
Without studying closely, the `srcNumLevels + 1` makes it seem like we are increasing the size of the levelsArr, when we are not. It is the same size as the original, but with different offsets.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Implemented Inclusion of min/max for Floats, Doubles and Items Sorted Views. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #547:
URL: https://github.com/apache/datasketches-java/pull/547#discussion_r1568107761
##########
src/main/java/org/apache/datasketches/quantilescommon/IncludeMinMax.java:
##########
@@ -0,0 +1,179 @@
+/*
+ * 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.quantilescommon;
+
+import java.lang.reflect.Array;
+import java.util.Comparator;
+
+/**
+ * This class reinserts the min and max values into the sorted view arrays as required.
+ */
+public class IncludeMinMax {
+
+ public static class DoublesPair {
+ public double[] quantiles;
+ public long[] cumWeights;
+
+ public DoublesPair(final double[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static class FloatsPair {
+ public float[] quantiles;
+ public long[] cumWeights;
+
+ public FloatsPair(final float[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static class ItemsPair<T> {
+ public T[] quantiles;
+ public long[] cumWeights;
+
+ public ItemsPair(final T[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static DoublesPair includeDoublesMinMax(
+ final double[] quantilesIn,
+ final long[] cumWeightsIn,
+ final double maxItem,
+ final double minItem) {
+ final int lenIn = cumWeightsIn.length;
+ final boolean adjLow = quantilesIn[0] != minItem; //if true, adjust the low end
+ final boolean adjHigh = quantilesIn[lenIn - 1] != maxItem; //if true, adjust the high end
+ int adjLen = lenIn; //this will be the length of the local copies of quantiles and cumWeights
+ adjLen += adjLow ? 1 : 0;
+ adjLen += adjHigh ? 1 : 0;
+ final double[] adjQuantiles;
+ final long[] adjCumWeights;
+ if (adjLen > lenIn) { //is any adjustment required at all?
+ adjQuantiles = new double[adjLen];
+ adjCumWeights = new long[adjLen];
+ final int offset = adjLow ? 1 : 0;
+ System.arraycopy(quantilesIn, 0, adjQuantiles, offset, lenIn);
+ System.arraycopy(cumWeightsIn,0, adjCumWeights, offset, lenIn);
+
+ //Adjust the low end if required.
Review Comment:
Yep. done.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org