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 2022/07/29 03:56:12 UTC
[datasketches-java] branch More_changes_to_REQ created (now 856926ff)
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a change to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
at 856926ff Update REQ to use the new QuantileSearchCriteria.
This branch includes the following new commits:
new 5e36107a minor renaming of "mine" to "sketch".
new e2fb4365 Renaming variables that were misnamed.
new 6e30aba5 Merge branch 'minor_changes_to_REQ' into Changes_to_kll
new 1ba33414 incremental changes 1
new 1436f378 Interim 2
new 889c820b Merge branch 'minor_changes_to_REQ' into Changes_to_kll
new 4a828111 Interim 3
new 856926ff Update REQ to use the new QuantileSearchCriteria.
The 8 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] 02/08: Renaming variables that were misnamed.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit e2fb436585f645ee9e92aa8d93771c7f672506ef
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Jul 25 10:50:30 2022 -0700
Renaming variables that were misnamed.
---
.../apache/datasketches/kll/KllDoublesHelper.java | 140 ++++++------
.../apache/datasketches/kll/KllFloatsHelper.java | 4 +-
.../org/apache/datasketches/kll/KllHelper.java | 242 ++++++++++-----------
.../apache/datasketches/kll/MiscFloatsTest.java | 4 +-
4 files changed, 195 insertions(+), 195 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index af66ae9a..a893e0e9 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -36,46 +36,46 @@ import org.apache.datasketches.SketchesArgumentException;
*/
final class KllDoublesHelper {
- static double getDoubleRank(final KllSketch mine, final double value, final boolean inclusive) {
- if (mine.isEmpty()) { return Double.NaN; }
+ static double getDoubleRank(final KllSketch sketch, final double value, final boolean inclusive) {
+ if (sketch.isEmpty()) { return Double.NaN; }
int level = 0;
int weight = 1;
long total = 0;
- final double[] myDoubleItemsArr = mine.getDoubleItemsArray();
- final int[] myLevelsArr = mine.getLevelsArray();
- while (level < mine.getNumLevels()) {
+ final double[] myDoubleItemsArr = sketch.getDoubleItemsArray();
+ final int[] myLevelsArr = sketch.getLevelsArray();
+ while (level < sketch.getNumLevels()) {
final int fromIndex = myLevelsArr[level];
final int toIndex = myLevelsArr[level + 1]; // exclusive
for (int i = fromIndex; i < toIndex; i++) {
if (inclusive ? myDoubleItemsArr[i] <= value : myDoubleItemsArr[i] < value) {
total += weight;
- } else if (level > 0 || mine.isLevelZeroSorted()) {
+ } else if (level > 0 || sketch.isLevelZeroSorted()) {
break; // levels above 0 are sorted, no point comparing further
}
}
level++;
weight *= 2;
}
- return (double) total / mine.getN();
+ return (double) total / sketch.getN();
}
- static double[] getDoublesPmfOrCdf(final KllSketch mine, final double[] splitPoints,
+ static double[] getDoublesPmfOrCdf(final KllSketch sketch, final double[] splitPoints,
final boolean isCdf, final boolean inclusive) {
- if (mine.isEmpty()) { return null; }
+ if (sketch.isEmpty()) { return null; }
validateDoubleValues(splitPoints);
final double[] buckets = new double[splitPoints.length + 1];
- final int myNumLevels = mine.getNumLevels();
- final int[] myLevelsArr = mine.getLevelsArray();
+ final int myNumLevels = sketch.getNumLevels();
+ final int[] myLevelsArr = sketch.getLevelsArray();
int level = 0;
int weight = 1;
while (level < myNumLevels) {
final int fromIndex = myLevelsArr[level];
final int toIndex = myLevelsArr[level + 1]; // exclusive
- if (level == 0 && !mine.isLevelZeroSorted()) {
- KllDoublesHelper.incrementDoublesBucketsUnsortedLevel(mine, fromIndex, toIndex, weight, splitPoints,
+ if (level == 0 && !sketch.isLevelZeroSorted()) {
+ KllDoublesHelper.incrementDoublesBucketsUnsortedLevel(sketch, fromIndex, toIndex, weight, splitPoints,
buckets, inclusive);
} else {
- KllDoublesHelper.incrementDoublesBucketsSortedLevel(mine, fromIndex, toIndex, weight, splitPoints,
+ KllDoublesHelper.incrementDoublesBucketsSortedLevel(sketch, fromIndex, toIndex, weight, splitPoints,
buckets, inclusive);
}
level++;
@@ -86,30 +86,30 @@ final class KllDoublesHelper {
double subtotal = 0;
for (int i = 0; i < buckets.length; i++) {
subtotal += buckets[i];
- buckets[i] = subtotal / mine.getN();
+ buckets[i] = subtotal / sketch.getN();
}
} else {
for (int i = 0; i < buckets.length; i++) {
- buckets[i] /= mine.getN();
+ buckets[i] /= sketch.getN();
}
}
return buckets;
}
- static double getDoublesQuantile(final KllSketch mine, final double fraction, final boolean inclusive) {
- if (mine.isEmpty()) { return Double.NaN; }
+ static double getDoublesQuantile(final KllSketch sketch, final double fraction, final boolean inclusive) {
+ if (sketch.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");
}
//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 KllDoublesSketchSortedView quant = KllDoublesHelper.getDoublesSortedView(mine, true, inclusive);
+ if (fraction == 0.0) { return sketch.getMinDoubleValue(); }
+ if (fraction == 1.0) { return sketch.getMaxDoubleValue(); }
+ final KllDoublesSketchSortedView quant = KllDoublesHelper.getDoublesSortedView(sketch, true, inclusive);
return quant.getQuantile(fraction);
}
- static double[] getDoublesQuantiles(final KllSketch mine, final double[] fractions, final boolean inclusive) {
- if (mine.isEmpty()) { return null; }
+ static double[] getDoublesQuantiles(final KllSketch sketch, final double[] fractions, final boolean inclusive) {
+ if (sketch.isEmpty()) { return null; }
KllDoublesSketchSortedView quant = null;
final double[] quantiles = new double[fractions.length];
for (int i = 0; i < fractions.length; i++) {
@@ -117,11 +117,11 @@ final class KllDoublesHelper {
if (fraction < 0.0 || fraction > 1.0) {
throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
}
- if (fraction == 0.0) { quantiles[i] = mine.getMinDoubleValue(); }
- else if (fraction == 1.0) { quantiles[i] = mine.getMaxDoubleValue(); }
+ if (fraction == 0.0) { quantiles[i] = sketch.getMinDoubleValue(); }
+ else if (fraction == 1.0) { quantiles[i] = sketch.getMaxDoubleValue(); }
else {
if (quant == null) {
- quant = KllDoublesHelper.getDoublesSortedView(mine, true, inclusive);
+ quant = KllDoublesHelper.getDoublesSortedView(sketch, true, inclusive);
}
quantiles[i] = quant.getQuantile(fraction);
}
@@ -129,38 +129,38 @@ final class KllDoublesHelper {
return quantiles;
}
- static void mergeDoubleImpl(final KllSketch mine, final KllSketch other) {
+ static void mergeDoubleImpl(final KllSketch sketch, final KllSketch other) {
if (other.isEmpty()) { return; }
- final long finalN = mine.getN() + other.getN();
+ final long finalN = sketch.getN() + other.getN();
final int otherNumLevels = other.getNumLevels();
final int[] otherLevelsArr = other.getLevelsArray();
final double[] otherDoubleItemsArr;
//capture my min & max, minK
- final double myMin = mine.getMinDoubleValue();
- final double myMax = mine.getMaxDoubleValue();
- final int myMinK = mine.getMinK();
+ final double myMin = sketch.getMinDoubleValue();
+ final double myMax = sketch.getMaxDoubleValue();
+ final int myMinK = sketch.getMinK();
//update this sketch with level0 items from the other sketch
if (other.isCompactSingleItem()) {
- updateDouble(mine, other.getDoubleSingleItem());
+ updateDouble(sketch, other.getDoubleSingleItem());
otherDoubleItemsArr = new double[0];
} else {
otherDoubleItemsArr = other.getDoubleItemsArray();
for (int i = otherLevelsArr[0]; i < otherLevelsArr[1]; i++) {
- KllDoublesHelper.updateDouble(mine, otherDoubleItemsArr[i]);
+ KllDoublesHelper.updateDouble(sketch, otherDoubleItemsArr[i]);
}
}
// after the level 0 update, we capture the state of levels and items arrays
- final int myCurNumLevels = mine.getNumLevels();
- final int[] myCurLevelsArr = mine.getLevelsArray();
- final double[] myCurDoubleItemsArr = mine.getDoubleItemsArray();
+ final int myCurNumLevels = sketch.getNumLevels();
+ final int[] myCurLevelsArr = sketch.getLevelsArray();
+ final double[] myCurDoubleItemsArr = sketch.getDoubleItemsArray();
int myNewNumLevels = myCurNumLevels;
int[] myNewLevelsArr = myCurLevelsArr;
double[] myNewDoubleItemsArr = myCurDoubleItemsArr;
if (otherNumLevels > 1 && !other.isCompactSingleItem()) { //now merge other levels if they exist
- final int tmpSpaceNeeded = mine.getNumRetained()
+ final int tmpSpaceNeeded = sketch.getNumRetained()
+ KllHelper.getNumRetainedAboveLevelZero(otherNumLevels, otherLevelsArr);
final double[] workbuf = new double[tmpSpaceNeeded];
final int ub = KllHelper.ubOnNumLevels(finalN);
@@ -174,8 +174,8 @@ final class KllDoublesHelper {
otherNumLevels, otherLevelsArr, otherDoubleItemsArr);
// notice that workbuf is being used as both the input and output
- final int[] result = generalDoublesCompress(mine.getK(), mine.getM(), provisionalNumLevels,
- workbuf, worklevels, workbuf, outlevels, mine.isLevelZeroSorted(), KllSketch.random);
+ final int[] result = generalDoublesCompress(sketch.getK(), sketch.getM(), provisionalNumLevels,
+ workbuf, worklevels, workbuf, outlevels, sketch.isLevelZeroSorted(), KllSketch.random);
final int targetItemCount = result[1]; //was finalCapacity. Max size given k, m, numLevels
final int curItemCount = result[2]; //was finalPop
@@ -206,28 +206,28 @@ final class KllDoublesHelper {
}
//MEMORY SPACE MANAGEMENT
- if (mine.updatableMemFormat) {
- mine.wmem = KllHelper.memorySpaceMgmt(mine, myNewLevelsArr.length, myNewDoubleItemsArr.length);
+ if (sketch.updatableMemFormat) {
+ sketch.wmem = KllHelper.memorySpaceMgmt(sketch, myNewLevelsArr.length, myNewDoubleItemsArr.length);
}
}
//Update Preamble:
- mine.setN(finalN);
+ sketch.setN(finalN);
if (other.isEstimationMode()) { //otherwise the merge brings over exact items.
- mine.setMinK(min(myMinK, other.getMinK()));
+ sketch.setMinK(min(myMinK, other.getMinK()));
}
//Update numLevels, levelsArray, items
- mine.setNumLevels(myNewNumLevels);
- mine.setLevelsArray(myNewLevelsArr);
- mine.setDoubleItemsArray(myNewDoubleItemsArr);
+ sketch.setNumLevels(myNewNumLevels);
+ sketch.setLevelsArray(myNewLevelsArr);
+ sketch.setDoubleItemsArray(myNewDoubleItemsArr);
//Update min, max values
final double otherMin = other.getMinDoubleValue();
final double otherMax = other.getMaxDoubleValue();
- mine.setMinDoubleValue(resolveDoubleMinValue(myMin, otherMin));
- mine.setMaxDoubleValue(resolveDoubleMaxValue(myMax, otherMax));
- assert KllHelper.sumTheSampleWeights(mine.getNumLevels(), mine.getLevelsArray()) == mine.getN();
+ sketch.setMinDoubleValue(resolveDoubleMinValue(myMin, otherMin));
+ sketch.setMaxDoubleValue(resolveDoubleMaxValue(myMax, otherMax));
+ assert KllHelper.sumTheSampleWeights(sketch.getNumLevels(), sketch.getLevelsArray()) == sketch.getN();
}
static void mergeSortedDoubleArrays(
@@ -299,20 +299,20 @@ final class KllDoublesHelper {
}
}
- static void updateDouble(final KllSketch mine, final double value) {
+ static void updateDouble(final KllSketch sketch, final double value) {
if (Double.isNaN(value)) { return; }
- final double prevMin = mine.getMinDoubleValue();
- final double prevMax = mine.getMaxDoubleValue();
- mine.setMinDoubleValue(resolveDoubleMinValue(prevMin, value));
- mine.setMaxDoubleValue(resolveDoubleMaxValue(prevMax, value));
- if (mine.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(mine); }
- final int myLevelsArrAtZero = mine.getLevelsArray()[0]; //LevelsArr could be expanded
- mine.incN();
- mine.setLevelZeroSorted(false);
+ final double prevMin = sketch.getMinDoubleValue();
+ final double prevMax = sketch.getMaxDoubleValue();
+ sketch.setMinDoubleValue(resolveDoubleMinValue(prevMin, value));
+ sketch.setMaxDoubleValue(resolveDoubleMaxValue(prevMax, value));
+ if (sketch.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(sketch); }
+ final int myLevelsArrAtZero = sketch.getLevelsArray()[0]; //LevelsArr could be expanded
+ sketch.incN();
+ sketch.setLevelZeroSorted(false);
final int nextPos = myLevelsArrAtZero - 1;
assert myLevelsArrAtZero >= 0;
- mine.setLevelsArrayAt(0, nextPos);
- mine.setDoubleItemsArrayAt(nextPos, value);
+ sketch.setLevelsArrayAt(0, nextPos);
+ sketch.setDoubleItemsArrayAt(nextPos, value);
}
/**
@@ -436,22 +436,22 @@ final class KllDoublesHelper {
return new int[] {numLevels, targetItemCount, currentItemCount};
}
- static KllDoublesSketchSortedView getDoublesSortedView(final KllSketch mine,
+ static KllDoublesSketchSortedView getDoublesSortedView(final KllSketch sketch,
final boolean cumulative, final boolean inclusive) {
- final int[] myLevelsArr = mine.getLevelsArray();
- final double[] myDoubleItemsArr = mine.getDoubleItemsArray();
- if (!mine.isLevelZeroSorted()) {
+ final int[] myLevelsArr = sketch.getLevelsArray();
+ final double[] myDoubleItemsArr = sketch.getDoubleItemsArray();
+ if (!sketch.isLevelZeroSorted()) {
Arrays.sort(myDoubleItemsArr, myLevelsArr[0], myLevelsArr[1]);
- if (!mine.hasMemory()) { mine.setLevelZeroSorted(true); }
+ if (!sketch.hasMemory()) { sketch.setLevelZeroSorted(true); }
}
- return new KllDoublesSketchSortedView(myDoubleItemsArr, myLevelsArr, mine.getNumLevels(), mine.getN(),
+ return new KllDoublesSketchSortedView(myDoubleItemsArr, myLevelsArr, sketch.getNumLevels(), sketch.getN(),
cumulative, inclusive);
}
private static void incrementDoublesBucketsSortedLevel(
- final KllSketch mine, final int fromIndex, final int toIndex, final int weight,
+ final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
final double[] splitPoints, final double[] buckets, final boolean inclusive) {
- final double[] myDoubleItemsArr = mine.getDoubleItemsArray();
+ final double[] myDoubleItemsArr = sketch.getDoubleItemsArray();
int i = fromIndex;
int j = 0;
while (i < toIndex && j < splitPoints.length) {
@@ -471,9 +471,9 @@ final class KllDoublesHelper {
}
private static void incrementDoublesBucketsUnsortedLevel(
- final KllSketch mine, final int fromIndex, final int toIndex, final int weight,
+ final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
final double[] splitPoints, final double[] buckets, final boolean inclusive) {
- final double[] myDoubleItemsArr = mine.getDoubleItemsArray();
+ final double[] myDoubleItemsArr = sketch.getDoubleItemsArray();
for (int i = fromIndex; i < toIndex; i++) {
int j;
for (j = 0; j < splitPoints.length; j++) {
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
index e11391a2..000700c3 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
@@ -101,8 +101,8 @@ final class KllFloatsHelper {
if (fraction < 0.0 || fraction > 1.0) {
throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
}
- final KllFloatsSketchSortedView quant = KllFloatsHelper.getFloatsSortedView(sketch, true, inclusive);
- return quant.getQuantile(fraction);
+ final KllFloatsSketchSortedView kllFSV = KllFloatsHelper.getFloatsSortedView(sketch, true, inclusive);
+ return kllFSV.getQuantile(fraction);
}
static float[] getFloatsQuantiles(final KllSketch sketch, final double[] fractions, final boolean inclusive) {
diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java
index 5655296a..94512e08 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java
@@ -137,20 +137,20 @@ final class KllHelper {
/**
* The following code is only valid in the special case of exactly reaching capacity while updating.
* It cannot be used while merging, while reducing k, or anything else.
- * @param mine the current sketch
+ * @param sketch the current sketch
*/
- static void compressWhileUpdatingSketch(final KllSketch mine) {
+ static void compressWhileUpdatingSketch(final KllSketch sketch) {
final int level =
- findLevelToCompact(mine.getK(), mine.getM(), mine.getNumLevels(), mine.getLevelsArray());
- if (level == mine.getNumLevels() - 1) {
+ findLevelToCompact(sketch.getK(), sketch.getM(), sketch.getNumLevels(), sketch.getLevelsArray());
+ if (level == sketch.getNumLevels() - 1) {
//The level to compact is the top level, thus we need to add a level.
//Be aware that this operation grows the items array,
//shifts the items data and the level boundaries of the data,
//and grows the levels array and increments numLevels_.
- KllHelper.addEmptyTopLevelToCompletelyFullSketch(mine);
+ KllHelper.addEmptyTopLevelToCompletelyFullSketch(sketch);
}
//after this point, the levelsArray will not be expanded, only modified.
- final int[] myLevelsArr = mine.getLevelsArray();
+ final int[] myLevelsArr = sketch.getLevelsArray();
final int rawBeg = myLevelsArr[level];
final int rawEnd = myLevelsArr[level + 1];
// +2 is OK because we already added a new top level if necessary
@@ -161,8 +161,8 @@ final class KllHelper {
final int adjPop = oddPop ? rawPop - 1 : rawPop;
final int halfAdjPop = adjPop / 2;
- if (mine.sketchType == DOUBLES_SKETCH) {
- final double[] myDoubleItemsArr = mine.getDoubleItemsArray();
+ if (sketch.sketchType == DOUBLES_SKETCH) {
+ final double[] myDoubleItemsArr = sketch.getDoubleItemsArray();
if (level == 0) { // level zero might not be sorted, so we must sort it if we wish to compact it
Arrays.sort(myDoubleItemsArr, adjBeg, adjBeg + adjPop);
}
@@ -177,13 +177,13 @@ final class KllHelper {
}
int newIndex = myLevelsArr[level + 1] - halfAdjPop; // adjust boundaries of the level above
- mine.setLevelsArrayAt(level + 1, newIndex);
+ sketch.setLevelsArrayAt(level + 1, newIndex);
if (oddPop) {
- mine.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item
+ sketch.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item
myDoubleItemsArr[myLevelsArr[level]] = myDoubleItemsArr[rawBeg]; // namely this leftover guy
} else {
- mine.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty
+ sketch.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty
}
// verify that we freed up halfAdjPop array slots just below the current level
@@ -197,12 +197,12 @@ final class KllHelper {
}
for (int lvl = 0; lvl < level; lvl++) {
newIndex = myLevelsArr[lvl] + halfAdjPop; //adjust boundary
- mine.setLevelsArrayAt(lvl, newIndex);
+ sketch.setLevelsArrayAt(lvl, newIndex);
}
- mine.setDoubleItemsArray(myDoubleItemsArr);
+ sketch.setDoubleItemsArray(myDoubleItemsArr);
}
else { //Float sketch
- final float[] myFloatItemsArr = mine.getFloatItemsArray();
+ final float[] myFloatItemsArr = sketch.getFloatItemsArray();
if (level == 0) { // level zero might not be sorted, so we must sort it if we wish to compact it
Arrays.sort(myFloatItemsArr, adjBeg, adjBeg + adjPop);
}
@@ -217,13 +217,13 @@ final class KllHelper {
}
int newIndex = myLevelsArr[level + 1] - halfAdjPop; // adjust boundaries of the level above
- mine.setLevelsArrayAt(level + 1, newIndex);
+ sketch.setLevelsArrayAt(level + 1, newIndex);
if (oddPop) {
- mine.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item
+ sketch.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item
myFloatItemsArr[myLevelsArr[level]] = myFloatItemsArr[rawBeg]; // namely this leftover guy
} else {
- mine.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty
+ sketch.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty
}
// verify that we freed up halfAdjPop array slots just below the current level
@@ -237,9 +237,9 @@ final class KllHelper {
}
for (int lvl = 0; lvl < level; lvl++) {
newIndex = myLevelsArr[lvl] + halfAdjPop; //adjust boundary
- mine.setLevelsArrayAt(lvl, newIndex);
+ sketch.setLevelsArrayAt(lvl, newIndex);
}
- mine.setFloatItemsArray(myFloatItemsArr);
+ sketch.setFloatItemsArray(myFloatItemsArr);
}
}
@@ -544,29 +544,29 @@ final class KllHelper {
return total;
}
- static byte[] toCompactByteArrayImpl(final KllSketch mine) {
- if (mine.isEmpty()) { return fastEmptyCompactByteArray(mine); }
- if (mine.isSingleItem()) { return fastSingleItemCompactByteArray(mine); }
- final byte[] byteArr = new byte[mine.getCurrentCompactSerializedSizeBytes()];
+ static byte[] toCompactByteArrayImpl(final KllSketch sketch) {
+ if (sketch.isEmpty()) { return fastEmptyCompactByteArray(sketch); }
+ if (sketch.isSingleItem()) { return fastSingleItemCompactByteArray(sketch); }
+ final byte[] byteArr = new byte[sketch.getCurrentCompactSerializedSizeBytes()];
final WritableMemory wmem = WritableMemory.writableWrap(byteArr);
- loadFirst8Bytes(mine, wmem, false);
- if (mine.getN() == 0) { return byteArr; } //empty
- final boolean doubleType = (mine.sketchType == DOUBLES_SKETCH);
+ loadFirst8Bytes(sketch, wmem, false);
+ if (sketch.getN() == 0) { return byteArr; } //empty
+ final boolean doubleType = (sketch.sketchType == DOUBLES_SKETCH);
//load data
int offset = DATA_START_ADR_SINGLE_ITEM;
- final int[] myLevelsArr = mine.getLevelsArray();
- if (mine.getN() == 1) { //single item
+ final int[] myLevelsArr = sketch.getLevelsArray();
+ if (sketch.getN() == 1) { //single item
if (doubleType) {
- wmem.putDouble(offset, mine.getDoubleItemsArray()[myLevelsArr[0]]);
+ wmem.putDouble(offset, sketch.getDoubleItemsArray()[myLevelsArr[0]]);
} else {
- wmem.putFloat(offset, mine.getFloatItemsArray()[myLevelsArr[0]]);
+ wmem.putFloat(offset, sketch.getFloatItemsArray()[myLevelsArr[0]]);
}
} else { // n > 1
//remainder of preamble after first 8 bytes
- setMemoryN(wmem, mine.getN());
- setMemoryMinK(wmem, mine.getMinK());
- setMemoryNumLevels(wmem, mine.getNumLevels());
+ setMemoryN(wmem, sketch.getN());
+ setMemoryMinK(wmem, sketch.getMinK());
+ setMemoryNumLevels(wmem, sketch.getNumLevels());
offset = DATA_START_ADR;
//LOAD LEVELS ARR the last integer in levels_ is NOT serialized
@@ -576,96 +576,96 @@ final class KllHelper {
//LOAD MIN, MAX VALUES FOLLOWED BY ITEMS ARRAY
if (doubleType) {
- wmem.putDouble(offset,mine. getMinDoubleValue());
+ wmem.putDouble(offset,sketch. getMinDoubleValue());
offset += Double.BYTES;
- wmem.putDouble(offset, mine.getMaxDoubleValue());
+ wmem.putDouble(offset, sketch.getMaxDoubleValue());
offset += Double.BYTES;
- wmem.putDoubleArray(offset, mine.getDoubleItemsArray(), myLevelsArr[0], mine.getNumRetained());
+ wmem.putDoubleArray(offset, sketch.getDoubleItemsArray(), myLevelsArr[0], sketch.getNumRetained());
} else {
- wmem.putFloat(offset, mine.getMinFloatValue());
+ wmem.putFloat(offset, sketch.getMinFloatValue());
offset += Float.BYTES;
- wmem.putFloat(offset, mine.getMaxFloatValue());
+ wmem.putFloat(offset, sketch.getMaxFloatValue());
offset += Float.BYTES;
- wmem.putFloatArray(offset, mine.getFloatItemsArray(), myLevelsArr[0], mine.getNumRetained());
+ wmem.putFloatArray(offset, sketch.getFloatItemsArray(), myLevelsArr[0], sketch.getNumRetained());
}
}
return byteArr;
}
- static byte[] fastEmptyCompactByteArray(final KllSketch mine) {
- final int doubleFlagBit = (mine.sketchType == DOUBLES_SKETCH) ? DOUBLES_SKETCH_BIT_MASK : 0;
+ static byte[] fastEmptyCompactByteArray(final KllSketch sketch) {
+ final int doubleFlagBit = (sketch.sketchType == DOUBLES_SKETCH) ? DOUBLES_SKETCH_BIT_MASK : 0;
final byte[] byteArr = new byte[8];
byteArr[0] = PREAMBLE_INTS_EMPTY_SINGLE; //2
byteArr[1] = SERIAL_VERSION_EMPTY_FULL; //1
byteArr[2] = KLL_FAMILY; //15
byteArr[3] = (byte) (EMPTY_BIT_MASK | doubleFlagBit);
- ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)mine.getK());
- byteArr[6] = (byte)mine.getM();
+ ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)sketch.getK());
+ byteArr[6] = (byte)sketch.getM();
return byteArr;
}
- static byte[] fastSingleItemCompactByteArray(final KllSketch mine) {
- final boolean doubleSketch = mine.sketchType == DOUBLES_SKETCH;
+ static byte[] fastSingleItemCompactByteArray(final KllSketch sketch) {
+ final boolean doubleSketch = sketch.sketchType == DOUBLES_SKETCH;
final int doubleFlagBit = doubleSketch ? DOUBLES_SKETCH_BIT_MASK : 0;
final byte[] byteArr = new byte[8 + (doubleSketch ? Double.BYTES : Float.BYTES)];
byteArr[0] = PREAMBLE_INTS_EMPTY_SINGLE; //2
byteArr[1] = SERIAL_VERSION_SINGLE; //2
byteArr[2] = KLL_FAMILY; //15
byteArr[3] = (byte) (SINGLE_ITEM_BIT_MASK | doubleFlagBit);
- ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)mine.getK());
- byteArr[6] = (byte)mine.getM();
+ ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)sketch.getK());
+ byteArr[6] = (byte)sketch.getM();
if (doubleSketch) {
- ByteArrayUtil.putDoubleLE(byteArr, DATA_START_ADR_SINGLE_ITEM, mine.getDoubleSingleItem());
+ ByteArrayUtil.putDoubleLE(byteArr, DATA_START_ADR_SINGLE_ITEM, sketch.getDoubleSingleItem());
} else {
- ByteArrayUtil.putFloatLE(byteArr, DATA_START_ADR_SINGLE_ITEM, mine.getFloatSingleItem());
+ ByteArrayUtil.putFloatLE(byteArr, DATA_START_ADR_SINGLE_ITEM, sketch.getFloatSingleItem());
}
return byteArr;
}
- static String toStringImpl(final KllSketch mine, final boolean withLevels, final boolean withData) {
- final boolean doubleType = (mine.sketchType == DOUBLES_SKETCH);
- final int k = mine.getK();
- final int m = mine.getM();
- final int numLevels = mine.getNumLevels();
- final int[] levelsArr = mine.getLevelsArray();
- final String epsPct = String.format("%.3f%%", mine.getNormalizedRankError(false) * 100);
- final String epsPMFPct = String.format("%.3f%%", mine.getNormalizedRankError(true) * 100);
+ static String toStringImpl(final KllSketch sketch, final boolean withLevels, final boolean withData) {
+ final boolean doubleType = (sketch.sketchType == DOUBLES_SKETCH);
+ final int k = sketch.getK();
+ final int m = sketch.getM();
+ final int numLevels = sketch.getNumLevels();
+ final int[] levelsArr = sketch.getLevelsArray();
+ final String epsPct = String.format("%.3f%%", sketch.getNormalizedRankError(false) * 100);
+ final String epsPMFPct = String.format("%.3f%%", sketch.getNormalizedRankError(true) * 100);
final StringBuilder sb = new StringBuilder();
- final String skType = (mine.updatableMemFormat ? "Direct" : "") + (doubleType ? "Doubles" : "Floats");
+ final String skType = (sketch.updatableMemFormat ? "Direct" : "") + (doubleType ? "Doubles" : "Floats");
sb.append(Util.LS).append("### Kll").append(skType).append("Sketch Summary:").append(Util.LS);
sb.append(" K : ").append(k).append(Util.LS);
- sb.append(" Dynamic min K : ").append(mine.getMinK()).append(Util.LS);
+ sb.append(" Dynamic min K : ").append(sketch.getMinK()).append(Util.LS);
sb.append(" M : ").append(m).append(Util.LS);
- sb.append(" N : ").append(mine.getN()).append(Util.LS);
+ sb.append(" N : ").append(sketch.getN()).append(Util.LS);
sb.append(" Epsilon : ").append(epsPct).append(Util.LS);
sb.append(" Epsison PMF : ").append(epsPMFPct).append(Util.LS);
- sb.append(" Empty : ").append(mine.isEmpty()).append(Util.LS);
- sb.append(" Estimation Mode : ").append(mine.isEstimationMode()).append(Util.LS);
+ sb.append(" Empty : ").append(sketch.isEmpty()).append(Util.LS);
+ sb.append(" Estimation Mode : ").append(sketch.isEstimationMode()).append(Util.LS);
sb.append(" Levels : ").append(numLevels).append(Util.LS);
- sb.append(" Level 0 Sorted : ").append(mine.isLevelZeroSorted()).append(Util.LS);
+ sb.append(" Level 0 Sorted : ").append(sketch.isLevelZeroSorted()).append(Util.LS);
sb.append(" Capacity Items : ").append(levelsArr[numLevels]).append(Util.LS);
- sb.append(" Retained Items : ").append(mine.getNumRetained()).append(Util.LS);
- if (mine.updatableMemFormat) {
- sb.append(" Updatable Storage Bytes: ").append(mine.getCurrentUpdatableSerializedSizeBytes()).append(Util.LS);
+ sb.append(" Retained Items : ").append(sketch.getNumRetained()).append(Util.LS);
+ if (sketch.updatableMemFormat) {
+ sb.append(" Updatable Storage Bytes: ").append(sketch.getCurrentUpdatableSerializedSizeBytes()).append(Util.LS);
} else {
- sb.append(" Compact Storage Bytes : ").append(mine.getCurrentCompactSerializedSizeBytes()).append(Util.LS);
+ sb.append(" Compact Storage Bytes : ").append(sketch.getCurrentCompactSerializedSizeBytes()).append(Util.LS);
}
if (doubleType) {
- sb.append(" Min Value : ").append(mine.getMinDoubleValue()).append(Util.LS);
- sb.append(" Max Value : ").append(mine.getMaxDoubleValue()).append(Util.LS);
+ sb.append(" Min Value : ").append(sketch.getMinDoubleValue()).append(Util.LS);
+ sb.append(" Max Value : ").append(sketch.getMaxDoubleValue()).append(Util.LS);
} else {
- sb.append(" Min Value : ").append(mine.getMinFloatValue()).append(Util.LS);
- sb.append(" Max Value : ").append(mine.getMaxFloatValue()).append(Util.LS);
+ sb.append(" Min Value : ").append(sketch.getMinFloatValue()).append(Util.LS);
+ sb.append(" Max Value : ").append(sketch.getMaxFloatValue()).append(Util.LS);
}
sb.append("### End sketch summary").append(Util.LS);
double[] myDoubleItemsArr = null;
float[] myFloatItemsArr = null;
if (doubleType) {
- myDoubleItemsArr = mine.getDoubleItemsArray();
+ myDoubleItemsArr = sketch.getDoubleItemsArray();
} else {
- myFloatItemsArr = mine.getFloatItemsArray();
+ myFloatItemsArr = sketch.getFloatItemsArray();
}
if (withLevels) {
sb.append(outputLevels(k, m, numLevels, levelsArr));
@@ -680,19 +680,19 @@ final class KllHelper {
* This method exists for testing purposes only. The resulting byteArray
* structure is an internal format and not supported for general transport
* or compatibility between systems and may be subject to change in the future.
- * @param mine the current sketch to be serialized.
+ * @param sketch the current sketch to be serialized.
* @return a byte array in an updatable form.
*/
- private static byte[] toUpdatableByteArrayFromUpdatableMemory(final KllSketch mine) {
- final boolean doubleType = (mine.sketchType == SketchType.DOUBLES_SKETCH);
- final int curBytes = mine.getCurrentUpdatableSerializedSizeBytes();
- final long n = mine.getN();
+ private static byte[] toUpdatableByteArrayFromUpdatableMemory(final KllSketch sketch) {
+ final boolean doubleType = (sketch.sketchType == SketchType.DOUBLES_SKETCH);
+ final int curBytes = sketch.getCurrentUpdatableSerializedSizeBytes();
+ final long n = sketch.getN();
final byte flags = (byte) (UPDATABLE_BIT_MASK
| ((n == 0) ? EMPTY_BIT_MASK : 0)
| ((n == 1) ? SINGLE_ITEM_BIT_MASK : 0)
| (doubleType ? DOUBLES_SKETCH_BIT_MASK : 0));
final byte[] byteArr = new byte[curBytes];
- mine.wmem.getByteArray(0, byteArr, 0, curBytes);
+ sketch.wmem.getByteArray(0, byteArr, 0, curBytes);
byteArr[FLAGS_BYTE_ADR] = flags;
return byteArr;
}
@@ -701,45 +701,45 @@ final class KllHelper {
* This method exists for testing purposes only. The resulting byteArray
* structure is an internal format and not supported for general transport
* or compatibility between systems and may be subject to change in the future.
- * @param mine the current sketch to be serialized.
+ * @param sketch the current sketch to be serialized.
* @return a byte array in an updatable form.
*/
- static byte[] toUpdatableByteArrayImpl(final KllSketch mine) {
- if (mine.hasMemory() && mine.updatableMemFormat) {
- return toUpdatableByteArrayFromUpdatableMemory(mine);
+ static byte[] toUpdatableByteArrayImpl(final KllSketch sketch) {
+ if (sketch.hasMemory() && sketch.updatableMemFormat) {
+ return toUpdatableByteArrayFromUpdatableMemory(sketch);
}
- final byte[] byteArr = new byte[mine.getCurrentUpdatableSerializedSizeBytes()];
+ final byte[] byteArr = new byte[sketch.getCurrentUpdatableSerializedSizeBytes()];
final WritableMemory wmem = WritableMemory.writableWrap(byteArr);
- loadFirst8Bytes(mine, wmem, true);
+ loadFirst8Bytes(sketch, wmem, true);
//remainder of preamble after first 8 bytes
- setMemoryN(wmem, mine.getN());
- setMemoryMinK(wmem, mine.getMinK());
- setMemoryNumLevels(wmem, mine.getNumLevels());
+ setMemoryN(wmem, sketch.getN());
+ setMemoryMinK(wmem, sketch.getMinK());
+ setMemoryNumLevels(wmem, sketch.getNumLevels());
//load data
- final boolean doubleType = (mine.sketchType == DOUBLES_SKETCH);
+ final boolean doubleType = (sketch.sketchType == DOUBLES_SKETCH);
int offset = DATA_START_ADR;
//LOAD LEVELS ARRAY the last integer in levels_ IS serialized
- final int[] myLevelsArr = mine.getLevelsArray();
+ final int[] myLevelsArr = sketch.getLevelsArray();
final int len = myLevelsArr.length;
wmem.putIntArray(offset, myLevelsArr, 0, len);
offset += len * Integer.BYTES;
//LOAD MIN, MAX VALUES FOLLOWED BY ITEMS ARRAY
if (doubleType) {
- wmem.putDouble(offset, mine.getMinDoubleValue());
+ wmem.putDouble(offset, sketch.getMinDoubleValue());
offset += Double.BYTES;
- wmem.putDouble(offset, mine.getMaxDoubleValue());
+ wmem.putDouble(offset, sketch.getMaxDoubleValue());
offset += Double.BYTES;
- final double[] doubleItemsArr = mine.getDoubleItemsArray();
+ final double[] doubleItemsArr = sketch.getDoubleItemsArray();
wmem.putDoubleArray(offset, doubleItemsArr, 0, doubleItemsArr.length);
} else {
- wmem.putFloat(offset, mine.getMinFloatValue());
+ wmem.putFloat(offset, sketch.getMinFloatValue());
offset += Float.BYTES;
- wmem.putFloat(offset,mine.getMaxFloatValue());
+ wmem.putFloat(offset,sketch.getMaxFloatValue());
offset += Float.BYTES;
- final float[] floatItemsArr = mine.getFloatItemsArray();
+ final float[] floatItemsArr = sketch.getFloatItemsArray();
wmem.putFloatArray(offset, floatItemsArr, 0, floatItemsArr.length);
}
return byteArr;
@@ -757,11 +757,11 @@ final class KllHelper {
/**
* This grows the levels arr by 1 (if needed) and increases the capacity of the items array
* at the bottom. Only numLevels, the levels array and the items array are affected.
- * @param mine the current sketch
+ * @param sketch the current sketch
*/
- private static void addEmptyTopLevelToCompletelyFullSketch(final KllSketch mine) {
- final int[] myCurLevelsArr = mine.getLevelsArray();
- final int myCurNumLevels = mine.getNumLevels();
+ private static void addEmptyTopLevelToCompletelyFullSketch(final KllSketch sketch) {
+ final int[] myCurLevelsArr = sketch.getLevelsArray();
+ final int myCurNumLevels = sketch.getNumLevels();
final int myCurTotalItemsCapacity = myCurLevelsArr[myCurNumLevels];
double minDouble = Double.NaN;
double maxDouble = Double.NaN;
@@ -778,21 +778,21 @@ final class KllHelper {
float[] myNewFloatItemsArr = null;
double[] myNewDoubleItemsArr = null;
- if (mine.sketchType == DOUBLES_SKETCH) {
- minDouble = mine.getMinDoubleValue();
- maxDouble = mine.getMaxDoubleValue();
- myCurDoubleItemsArr = mine.getDoubleItemsArray();
+ if (sketch.sketchType == DOUBLES_SKETCH) {
+ minDouble = sketch.getMinDoubleValue();
+ maxDouble = sketch.getMaxDoubleValue();
+ myCurDoubleItemsArr = sketch.getDoubleItemsArray();
//assert we are following a certain growth scheme
assert myCurDoubleItemsArr.length == myCurTotalItemsCapacity;
} else { //FLOATS_SKETCH
- minFloat = mine.getMinFloatValue();
- maxFloat = mine.getMaxFloatValue();
- myCurFloatItemsArr = mine.getFloatItemsArray();
+ minFloat = sketch.getMinFloatValue();
+ maxFloat = sketch.getMaxFloatValue();
+ myCurFloatItemsArr = sketch.getFloatItemsArray();
assert myCurFloatItemsArr.length == myCurTotalItemsCapacity;
}
assert myCurLevelsArr[0] == 0; //definition of full is part of the growth scheme
- final int deltaItemsCap = levelCapacity(mine.getK(), myCurNumLevels + 1, 0, mine.getM());
+ final int deltaItemsCap = levelCapacity(sketch.getK(), myCurNumLevels + 1, 0, sketch.getM());
myNewTotalItemsCapacity = myCurTotalItemsCapacity + deltaItemsCap;
// Check if growing the levels arr if required.
@@ -805,7 +805,7 @@ final class KllHelper {
myNewLevelsArr = Arrays.copyOf(myCurLevelsArr, myCurNumLevels + 2);
assert myNewLevelsArr.length == myCurLevelsArr.length + 1;
myNewNumLevels = myCurNumLevels + 1;
- mine.incNumLevels(); //increment the class member
+ sketch.incNumLevels(); //increment the class member
} else {
myNewLevelsArr = myCurLevelsArr;
myNewNumLevels = myCurNumLevels;
@@ -817,7 +817,7 @@ final class KllHelper {
myNewLevelsArr[myNewNumLevels] = myNewTotalItemsCapacity; // initialize the new "extra" index at the top
// GROW ITEMS ARRAY
- if (mine.sketchType == DOUBLES_SKETCH) {
+ if (sketch.sketchType == DOUBLES_SKETCH) {
myNewDoubleItemsArr = new double[myNewTotalItemsCapacity];
// copy and shift the current data into the new array
System.arraycopy(myCurDoubleItemsArr, 0, myNewDoubleItemsArr, deltaItemsCap, myCurTotalItemsCapacity);
@@ -828,20 +828,20 @@ final class KllHelper {
}
//MEMORY SPACE MANAGEMENT
- if (mine.updatableMemFormat) {
- mine.wmem = memorySpaceMgmt(mine, myNewLevelsArr.length, myNewTotalItemsCapacity);
+ if (sketch.updatableMemFormat) {
+ sketch.wmem = memorySpaceMgmt(sketch, myNewLevelsArr.length, myNewTotalItemsCapacity);
}
//update our sketch with new expanded spaces
- mine.setNumLevels(myNewNumLevels);
- mine.setLevelsArray(myNewLevelsArr);
- if (mine.sketchType == DOUBLES_SKETCH) {
- mine.setMinDoubleValue(minDouble);
- mine.setMaxDoubleValue(maxDouble);
- mine.setDoubleItemsArray(myNewDoubleItemsArr);
+ sketch.setNumLevels(myNewNumLevels);
+ sketch.setLevelsArray(myNewLevelsArr);
+ if (sketch.sketchType == DOUBLES_SKETCH) {
+ sketch.setMinDoubleValue(minDouble);
+ sketch.setMaxDoubleValue(maxDouble);
+ sketch.setDoubleItemsArray(myNewDoubleItemsArr);
} else { //Float sketch
- mine.setMinFloatValue(minFloat);
- mine.setMaxFloatValue(maxFloat);
- mine.setFloatItemsArray(myNewFloatItemsArr);
+ sketch.setMinFloatValue(minFloat);
+ sketch.setMaxFloatValue(maxFloat);
+ sketch.setFloatItemsArray(myNewFloatItemsArr);
}
}
diff --git a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
index 0b100e48..f0090486 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
@@ -149,7 +149,7 @@ public class MiscFloatsTest {
private static void show(final KllFloatsSketch sk, int limit) {
int i = (int) sk.getN();
- for ( ; i < limit; i++) { sk.update(i + 1); }
+ for ( ; i < limit; i++) { sk.update(i + 1); } //incremental update
println(sk.toString(true, true));
}
@@ -528,7 +528,7 @@ public class MiscFloatsTest {
* @param o value to print
*/
static void println(final Object o) {
- //System.out.println(o.toString()); //disable here
+ System.out.println(o.toString()); //disable here
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 05/08: Interim 2
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 1436f378a4a7c0cf97f9308386f2346f4f5956df
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Jul 26 10:45:07 2022 -0700
Interim 2
---
.../apache/datasketches/kll/KllFloatsHelper.java | 164 +----------------
.../apache/datasketches/kll/KllFloatsSketch.java | 24 +--
.../kll/KllFloatsSketchSortedView.java | 204 ++++++++++++++++++---
.../datasketches/kll/KllFloatsSketchTest.java | 1 +
4 files changed, 203 insertions(+), 190 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
index 000700c3..a29d9c89 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
@@ -27,8 +27,6 @@ import static org.apache.datasketches.Util.isOdd;
import java.util.Arrays;
import java.util.Random;
-import org.apache.datasketches.SketchesArgumentException;
-
/**
* Static methods to support KllFloatsSketch
* @author Kevin Lang
@@ -36,92 +34,8 @@ import org.apache.datasketches.SketchesArgumentException;
*/
final class KllFloatsHelper {
- static double getFloatRank(final KllSketch sketch, final float value, final boolean inclusive) {
- if (sketch.isEmpty()) { return Double.NaN; }
- int level = 0;
- int weight = 1;
- long total = 0;
- final float[] myFloatItemsArr = sketch.getFloatItemsArray();
- final int[] myLevelsArr = sketch.getLevelsArray();
- while (level < sketch.getNumLevels()) {
- final int fromIndex = myLevelsArr[level];
- final int toIndex = myLevelsArr[level + 1]; // exclusive
- for (int i = fromIndex; i < toIndex; i++) {
- if (inclusive ? myFloatItemsArr[i] <= value : myFloatItemsArr[i] < value) {
- total += weight;
- } else if (level > 0 || sketch.isLevelZeroSorted()) {
- break; // levels above 0 are sorted, no point comparing further
- }
- }
- level++;
- weight *= 2;
- }
- return (double) total / sketch.getN();
- }
-
- static double[] getFloatsPmfOrCdf(final KllSketch sketch, final float[] splitPoints,
- final boolean isCdf, final boolean inclusive) {
- if (sketch.isEmpty()) { return null; }
- validateFloatValues(splitPoints);
- final double[] buckets = new double[splitPoints.length + 1];
- final int myNumLevels = sketch.getNumLevels();
- final int[] myLevelsArr = sketch.getLevelsArray();
- int level = 0;
- int weight = 1;
- while (level < myNumLevels) {
- final int fromIndex = myLevelsArr[level];
- final int toIndex = myLevelsArr[level + 1]; // exclusive
- if (level == 0 && !sketch.isLevelZeroSorted()) {
- KllFloatsHelper.incrementFloatBucketsUnsortedLevel(sketch, fromIndex, toIndex, weight, splitPoints,
- buckets, inclusive);
- } else {
- KllFloatsHelper.incrementFloatBucketsSortedLevel(sketch, fromIndex, toIndex, weight, splitPoints,
- buckets, inclusive);
- }
- level++;
- weight *= 2;
- }
- // normalize and, if CDF, convert to cumulative
- if (isCdf) {
- double subtotal = 0;
- for (int i = 0; i < buckets.length; i++) {
- subtotal += buckets[i];
- buckets[i] = subtotal / sketch.getN();
- }
- } else {
- for (int i = 0; i < buckets.length; i++) {
- buckets[i] /= sketch.getN();
- }
- }
- return buckets;
- }
-
- static float getFloatsQuantile(final KllSketch sketch, final double fraction, final boolean inclusive) {
- if (sketch.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");
- }
- final KllFloatsSketchSortedView kllFSV = KllFloatsHelper.getFloatsSortedView(sketch, true, inclusive);
- return kllFSV.getQuantile(fraction);
- }
-
- static float[] getFloatsQuantiles(final KllSketch sketch, final double[] fractions, final boolean inclusive) {
- if (sketch.isEmpty()) { return null; }
- KllFloatsSketchSortedView kllFSV = null;
- final float[] quantiles = new float[fractions.length];
- for (int i = 0; i < fractions.length; i++) { //check if fraction are in [0, 1]
- final double fraction = fractions[i];
- if (fraction < 0.0 || fraction > 1.0) {
- throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
- }
- if (kllFSV == null) {
- kllFSV = KllFloatsHelper.getFloatsSortedView(sketch, true, inclusive);
- }
- quantiles[i] = kllFSV.getQuantile(fraction);
- }
- return quantiles;
- }
+ //Called from KllSketch
static void mergeFloatImpl(final KllSketch sketch, final KllSketch other) {
if (other.isEmpty()) { return; }
final long finalN = sketch.getN() + other.getN();
@@ -223,6 +137,7 @@ final class KllFloatsHelper {
assert KllHelper.sumTheSampleWeights(sketch.getNumLevels(), sketch.getLevelsArray()) == sketch.getN();
}
+ //Called from KllHelper and this.generalFloatsCompress(...), this.populateFloatWorkArrays(...)
static void mergeSortedFloatArrays(
final float[] bufA, final int startA, final int lenA,
final float[] bufB, final int startB, final int lenB,
@@ -260,7 +175,9 @@ final class KllFloatsHelper {
* @param start data start
* @param length items length
* @param random instance of Random
- */ //NOTE Validation Method: Need to modify to run.
+ */
+ //NOTE: Validation Method: Need to modify to run.
+ //Called from KllHelper, this.generalFloatsCompress(...)
static void randomlyHalveDownFloats(final float[] buf, final int start, final int length, final Random random) {
assert isEven(length);
final int half_length = length / 2;
@@ -279,7 +196,9 @@ final class KllFloatsHelper {
* @param start data start
* @param length items length
* @param random instance of Random
- */ //NOTE Validation Method: Need to modify to run.
+ */
+ //NOTE Validation Method: Need to modify to run.
+ //Called from KllHelper, this.generalFloatsCompress(...)
static void randomlyHalveUpFloats(final float[] buf, final int start, final int length, final Random random) {
assert isEven(length);
final int half_length = length / 2;
@@ -292,6 +211,7 @@ final class KllFloatsHelper {
}
}
+ //Called from KllFloatsSketch, this.mergeFloatImpl(...
static void updateFloat(final KllSketch sketch, final float value) {
if (Float.isNaN(value)) { return; }
final float prevMin = sketch.getMinFloatValue();
@@ -429,55 +349,6 @@ final class KllFloatsHelper {
return new int[] {numLevels, targetItemCount, currentItemCount};
}
- static KllFloatsSketchSortedView getFloatsSortedView(final KllSketch sketch,
- final boolean cumulative, final boolean inclusive) {
- final int[] skLevelsArr = sketch.getLevelsArray();
- final float[] skFloatItemsArr = sketch.getFloatItemsArray();
- if (!sketch.isLevelZeroSorted()) {
- Arrays.sort(skFloatItemsArr, skLevelsArr[0], skLevelsArr[1]);
- if (!sketch.hasMemory()) { sketch.setLevelZeroSorted(true); }
- }
- return new KllFloatsSketchSortedView(skFloatItemsArr, skLevelsArr, sketch.getNumLevels(), sketch.getN(),
- cumulative, inclusive);
- }
-
- private static void incrementFloatBucketsSortedLevel(
- final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
- final float[] splitPoints, final double[] buckets, final boolean inclusive) {
- final float[] myFloatItemsArr = sketch.getFloatItemsArray();
- int i = fromIndex;
- int j = 0;
- while (i < toIndex && j < splitPoints.length) {
- if (inclusive ? myFloatItemsArr[i] <= splitPoints[j]: myFloatItemsArr[i] < splitPoints[j]) {
- buckets[j] += weight; // this sample goes into this bucket
- i++; // move on to next sample and see whether it also goes into this bucket
- } else {
- j++; // no more samples for this bucket
- }
- }
- // now either i == toIndex (we are out of samples), or
- // j == numSplitPoints (we are out of buckets, but there are more samples remaining)
- // we only need to do something in the latter case
- if (j == splitPoints.length) {
- buckets[j] += weight * (toIndex - i);
- }
- }
-
- private static void incrementFloatBucketsUnsortedLevel(
- final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
- final float[] splitPoints, final double[] buckets, final boolean inclusive) {
- final float[] myFloatItemsArr = sketch.getFloatItemsArray();
- for (int i = fromIndex; i < toIndex; i++) {
- int j;
- for (j = 0; j < splitPoints.length; j++) {
- if (inclusive ? myFloatItemsArr[i] <= splitPoints[j] : myFloatItemsArr[i] < splitPoints[j]) {
- break;
- }
- }
- buckets[j] += weight;
- }
- }
-
private static void populateFloatWorkArrays(
final float[] workbuf, final int[] worklevels, final int provisionalNumLevels,
final int myCurNumLevels, final int[] myCurLevelsArr, final float[] myCurFloatItemsArr,
@@ -519,23 +390,6 @@ final class KllFloatsHelper {
return min(myMin, otherMin);
}
- /**
- * Checks the sequential validity of the given array of float values.
- * They must be unique, monotonically increasing and not NaN.
- * @param values the given array of values
- */
- private static void validateFloatValues(final float[] values) {
- for (int i = 0; i < values.length; i++) {
- if (!Float.isFinite(values[i])) {
- throw new SketchesArgumentException("Values must be finite");
- }
- if (i < values.length - 1 && values[i] >= values[i + 1]) {
- throw new SketchesArgumentException(
- "Values must be unique and monotonically increasing");
- }
- }
- }
-
/*
* Validation Method.
* The following must be enabled for use with the KllFloatsValidationTest,
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
index b49788af..53538e2d 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
@@ -181,7 +181,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* in positions 0 through j of the returned PMF array.
*/
public double[] getCDF(final float[] splitPoints, final boolean inclusive) {
- return KllFloatsHelper.getFloatsPmfOrCdf(this, splitPoints, true, inclusive);
+ return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, true, inclusive);
}
/**
@@ -190,7 +190,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return CDF
*/
public double[] getCDF(final float[] splitPoints) {
- return KllFloatsHelper.getFloatsPmfOrCdf(this, splitPoints, true, false);
+ return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, true, false);
}
/**
@@ -235,7 +235,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* splitPoint, with the exception that the last interval will include maximum value.
*/
public double[] getPMF(final float[] splitPoints, final boolean inclusive) {
- return KllFloatsHelper.getFloatsPmfOrCdf(this, splitPoints, false, inclusive);
+ return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, false, inclusive);
}
/**
@@ -244,7 +244,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return PMF
*/
public double[] getPMF(final float[] splitPoints) {
- return KllFloatsHelper.getFloatsPmfOrCdf(this, splitPoints, false, false);
+ return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, false, false);
}
/**
@@ -267,7 +267,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* @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);
+ return KllFloatsSketchSortedView.getFloatsQuantile(this, fraction, inclusive);
}
/**
@@ -276,7 +276,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return quantile
*/
public float getQuantile(final double fraction) {
- return KllFloatsHelper.getFloatsQuantile(this, fraction, false);
+ return KllFloatsSketchSortedView.getFloatsQuantile(this, fraction, false);
}
/**
@@ -310,7 +310,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* array.
*/
public float[] getQuantiles(final double[] fractions, final boolean inclusive) {
- return KllFloatsHelper.getFloatsQuantiles(this, fractions, inclusive);
+ return KllFloatsSketchSortedView.getFloatsQuantiles(this, fractions, inclusive);
}
/**
@@ -319,7 +319,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return quantiles
*/
public float[] getQuantiles(final double[] fractions) {
- return KllFloatsHelper.getFloatsQuantiles(this, fractions, false);
+ return KllFloatsSketchSortedView.getFloatsQuantiles(this, fractions, false);
}
/**
@@ -378,7 +378,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return an approximate rank of the given value
*/
public double getRank(final float value, final boolean inclusive) {
- return KllFloatsHelper.getFloatRank(this, value, inclusive);
+ return KllFloatsSketchSortedView.getFloatRank(this, value, inclusive);
}
/**
@@ -387,7 +387,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* @return fractional rank
*/
public double getRank(final float value) {
- return KllFloatsHelper.getFloatRank(this, value, false);
+ return KllFloatsSketchSortedView.getFloatRank(this, value, false);
}
/**
@@ -409,13 +409,13 @@ public abstract class KllFloatsSketch extends KllSketch {
/**
* Sorted view of the sketch.
- * Complexity: linear merge of sorted levels plus sorting of the level 0.
+ * Complexity: linear, single-pass 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 KllFloatsSketchSortedView getSortedView(final boolean cumulative, final boolean inclusive) {
- return KllFloatsHelper.getFloatsSortedView(this, cumulative, inclusive);
+ return KllFloatsSketchSortedView.getFloatsSortedView(this, cumulative, inclusive);
}
@Override //Artifact of inheritance
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
index e4824c8a..f3359da5 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
@@ -22,6 +22,7 @@ package org.apache.datasketches.kll;
import java.util.Arrays;
import org.apache.datasketches.QuantilesHelper;
+import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.SketchesStateException;
/**
@@ -52,6 +53,42 @@ public final class KllFloatsSketchSortedView {
}
}
+ private void populateFromSketch(final float[] srcItems, final int[] srcLevels,
+ final int numLevels, final int numItems) {
+ final int offset = srcLevels[0];
+ System.arraycopy(srcItems, offset, items_, 0, numItems);
+ int srcLevel = 0;
+ int dstLevel = 0;
+ long weight = 1;
+ while (srcLevel < numLevels) {
+ final int fromIndex = srcLevels[srcLevel] - offset;
+ final int toIndex = srcLevels[srcLevel + 1] - offset; // exclusive
+ if (fromIndex < toIndex) { // if equal, skip empty level
+ Arrays.fill(weights_, fromIndex, toIndex, weight);
+ levels_[dstLevel] = fromIndex;
+ levels_[dstLevel + 1] = toIndex;
+ dstLevel++;
+ }
+ srcLevel++;
+ weight *= 2;
+ }
+ weights_[numItems] = 0;
+ numLevels_ = dstLevel;
+ }
+
+ static KllFloatsSketchSortedView getFloatsSortedView(final KllSketch sketch,
+ final boolean cumulative, final boolean inclusive) {
+ final float[] skFloatItemsArr = sketch.getFloatItemsArray();
+ final int[] skLevelsArr = sketch.getLevelsArray();
+
+ if (!sketch.isLevelZeroSorted()) {
+ Arrays.sort(skFloatItemsArr, skLevelsArr[0], skLevelsArr[1]);
+ if (!sketch.hasMemory()) { sketch.setLevelZeroSorted(true); }
+ }
+ return new KllFloatsSketchSortedView(skFloatItemsArr, skLevelsArr, sketch.getNumLevels(), sketch.getN(),
+ cumulative, inclusive);
+ }
+
//For testing only. Allows testing of getQuantile without a sketch. NOT USED
KllFloatsSketchSortedView(final float[] items, final long[] weights, final long n) {
n_ = n;
@@ -73,6 +110,150 @@ public final class KllFloatsSketchSortedView {
return new KllFloatsSketchSortedViewIterator(items_, weights_);
}
+
+ //Called only from KllFloatsSketch
+ static double getFloatRank(final KllSketch sketch, final float value, final boolean inclusive) {
+ if (sketch.isEmpty()) { return Double.NaN; }
+ int level = 0;
+ int weight = 1;
+ long total = 0;
+ final float[] floatItemsArr = sketch.getFloatItemsArray();
+ final int[] levelsArr = sketch.getLevelsArray();
+ while (level < sketch.getNumLevels()) {
+ final int fromIndex = levelsArr[level];
+ final int toIndex = levelsArr[level + 1]; // exclusive
+ for (int i = fromIndex; i < toIndex; i++) {
+ if (inclusive ? floatItemsArr[i] <= value : floatItemsArr[i] < value) {
+ total += weight;
+ } else if (level > 0 || sketch.isLevelZeroSorted()) {
+ break; // levels above 0 are sorted, no point comparing further
+ }
+ }
+ level++;
+ weight *= 2;
+ }
+ return (double) total / sketch.getN();
+ }
+
+ //Called only from KllFloatsSketch
+ static double[] getFloatsPmfOrCdf(final KllSketch sketch, final float[] splitPoints,
+ final boolean isCdf, final boolean inclusive) {
+ if (sketch.isEmpty()) { return null; }
+ validateFloatValues(splitPoints);
+ final double[] buckets = new double[splitPoints.length + 1];
+ final int numLevels = sketch.getNumLevels();
+ final int[] levelsArr = sketch.getLevelsArray();
+ int level = 0;
+ int weight = 1;
+ while (level < numLevels) {
+ final int fromIndex = levelsArr[level];
+ final int toIndex = levelsArr[level + 1]; // exclusive
+ if (level == 0 && !sketch.isLevelZeroSorted()) {
+ incrementFloatBucketsUnsortedLevel(sketch, fromIndex, toIndex, weight, splitPoints, buckets, inclusive);
+ } else {
+ incrementFloatBucketsSortedLevel(sketch, fromIndex, toIndex, weight, splitPoints, buckets, inclusive);
+ }
+ level++;
+ weight *= 2;
+ }
+ // normalize and, if CDF, convert to cumulative
+ if (isCdf) {
+ double subtotal = 0;
+ for (int i = 0; i < buckets.length; i++) {
+ subtotal += buckets[i];
+ buckets[i] = subtotal / sketch.getN();
+ }
+ } else {
+ for (int i = 0; i < buckets.length; i++) {
+ buckets[i] /= sketch.getN();
+ }
+ }
+ return buckets;
+ }
+
+ /**
+ * Checks the sequential validity of the given array of float values.
+ * They must be unique, monotonically increasing and not NaN.
+ * @param values the given array of values
+ */
+ private static void validateFloatValues(final float[] values) {
+ for (int i = 0; i < values.length; i++) {
+ if (!Float.isFinite(values[i])) {
+ throw new SketchesArgumentException("Values must be finite");
+ }
+ if (i < values.length - 1 && values[i] >= values[i + 1]) {
+ throw new SketchesArgumentException(
+ "Values must be unique and monotonically increasing");
+ }
+ }
+ }
+
+ private static void incrementFloatBucketsSortedLevel(
+ final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
+ final float[] splitPoints, final double[] buckets, final boolean inclusive) {
+ final float[] floatItemsArr = sketch.getFloatItemsArray();
+ int i = fromIndex;
+ int j = 0;
+ while (i < toIndex && j < splitPoints.length) {
+ if (inclusive ? floatItemsArr[i] <= splitPoints[j]: floatItemsArr[i] < splitPoints[j]) {
+ buckets[j] += weight; // this sample goes into this bucket
+ i++; // move on to next sample and see whether it also goes into this bucket
+ } else {
+ j++; // no more samples for this bucket
+ }
+ }
+ // now either i == toIndex (we are out of samples), or
+ // j == numSplitPoints (we are out of buckets, but there are more samples remaining)
+ // we only need to do something in the latter case
+ if (j == splitPoints.length) {
+ buckets[j] += weight * (toIndex - i);
+ }
+ }
+
+ private static void incrementFloatBucketsUnsortedLevel(
+ final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
+ final float[] splitPoints, final double[] buckets, final boolean inclusive) {
+ final float[] floatItemsArr = sketch.getFloatItemsArray();
+ for (int i = fromIndex; i < toIndex; i++) {
+ int j;
+ for (j = 0; j < splitPoints.length; j++) {
+ if (inclusive ? floatItemsArr[i] <= splitPoints[j] : floatItemsArr[i] < splitPoints[j]) {
+ break;
+ }
+ }
+ buckets[j] += weight;
+ }
+ }
+
+ //Called only from KllFloatsSketch
+ static float getFloatsQuantile(final KllSketch sketch, final double fraction, final boolean inclusive) {
+ if (sketch.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");
+ }
+ final KllFloatsSketchSortedView kllFSV = KllFloatsSketchSortedView.getFloatsSortedView(sketch, true, inclusive);
+ return kllFSV.getQuantile(fraction);
+ }
+
+ //Called only from KllFloatsSketch
+ static float[] getFloatsQuantiles(final KllSketch sketch, final double[] fractions, final boolean inclusive) {
+ if (sketch.isEmpty()) { return null; }
+ KllFloatsSketchSortedView kllFSV = null;
+ final float[] quantiles = new float[fractions.length];
+ for (int i = 0; i < fractions.length; i++) { //check if fraction are in [0, 1]
+ final double fraction = fractions[i];
+ if (fraction < 0.0 || fraction > 1.0) {
+ throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
+ }
+ if (kllFSV == null) {
+ kllFSV = KllFloatsSketchSortedView.getFloatsSortedView(sketch, true, inclusive);
+ }
+ quantiles[i] = kllFSV.getQuantile(fraction);
+ }
+ return quantiles;
+ }
+
+
private static void blockyTandemMergeSort(final float[] items, final long[] weights,
final int[] levels, final int numLevels) {
if (numLevels == 1) { return; }
@@ -154,27 +335,4 @@ public final class KllFloatsSketchSortedView {
return items_[index];
}
- private void populateFromSketch(final float[] srcItems, final int[] srcLevels,
- final int numLevels, final int numItems) {
- final int offset = srcLevels[0];
- System.arraycopy(srcItems, offset, items_, 0, numItems);
- int srcLevel = 0;
- int dstLevel = 0;
- long weight = 1;
- while (srcLevel < numLevels) {
- final int fromIndex = srcLevels[srcLevel] - offset;
- final int toIndex = srcLevels[srcLevel + 1] - offset; // exclusive
- if (fromIndex < toIndex) { // if equal, skip empty level
- Arrays.fill(weights_, fromIndex, toIndex, weight);
- levels_[dstLevel] = fromIndex;
- levels_[dstLevel + 1] = toIndex;
- dstLevel++;
- }
- srcLevel++;
- weight *= 2;
- }
- weights_[numItems] = 0;
- numLevels_ = dstLevel;
- }
-
}
diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
index cb1951ff..073d562c 100644
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
@@ -94,6 +94,7 @@ public class KllFloatsSketchTest {
public void tenItems() {
final KllFloatsSketch sketch = KllFloatsSketch.newHeapInstance();
for (int i = 1; i <= 10; i++) { sketch.update(i); }
+ System.out.println(sketch.toString(true, true)); //TODO
assertFalse(sketch.isEmpty());
assertEquals(sketch.getN(), 10);
assertEquals(sketch.getNumRetained(), 10);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 08/08: Update REQ to use the new QuantileSearchCriteria.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 856926ff941c87a34b4c624a50fadf6c41c1eb29
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Jul 28 20:29:17 2022 -0700
Update REQ to use the new QuantileSearchCriteria.
---
.../org/apache/datasketches/InequalitySearch.java | 2 +
.../datasketches/QuantileSearchCriteria.java | 74 +++++++++++++
.../org/apache/datasketches/req/BaseReqSketch.java | 48 +++++----
.../org/apache/datasketches/req/FloatBuffer.java | 10 +-
.../org/apache/datasketches/req/ReqSketch.java | 34 +++---
.../datasketches/req/ReqSketchSortedView.java | 16 ++-
.../req/ReqSketchSortedViewIterator.java | 10 +-
.../datasketches/CrossCheckQuantilesTest.java | 117 +++++++++++----------
...loatBufferTest.java => ReqFloatBufferTest.java} | 18 ++--
.../datasketches/req/ReqSketchSortedViewTest.java | 11 +-
.../org/apache/datasketches/req/ReqSketchTest.java | 36 ++++---
11 files changed, 244 insertions(+), 132 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/InequalitySearch.java b/src/main/java/org/apache/datasketches/InequalitySearch.java
index 278a3383..19726697 100644
--- a/src/main/java/org/apache/datasketches/InequalitySearch.java
+++ b/src/main/java/org/apache/datasketches/InequalitySearch.java
@@ -37,6 +37,8 @@ import java.util.Objects;
* <p>Given a sorted array of values <i>arr[]</i> and the search key value <i>v</i>, the algorithms for
* the searching criteria are given with each enum criterion.</p>
*
+ * @see <a href="https://datasketches.apache.org/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">
+ * Sketching Quantiles and Ranks Tutorial</a>
* @author Lee Rhodes
*/
public enum InequalitySearch {
diff --git a/src/main/java/org/apache/datasketches/QuantileSearchCriteria.java b/src/main/java/org/apache/datasketches/QuantileSearchCriteria.java
new file mode 100644
index 00000000..c9335e92
--- /dev/null
+++ b/src/main/java/org/apache/datasketches/QuantileSearchCriteria.java
@@ -0,0 +1,74 @@
+/*
+ * 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;
+
+/**
+ * These criteria are used by all the quantiles algorithms in the library.
+ * <ul>
+ * <li><b>Definition of Non Inclusive <i>getRank(q)</i> search:</b><br>
+ * Given quantile <i>q</i>, return the rank, <i>r</i>, of the largest quantile that is strictly less than <i>q</i>.
+ * </li>
+ *
+ * <li><b>Definition of Inclusive <i>getRank(q)</i> search:</b><br>
+ * Given quantile <i>q</i>, return the rank, <i>r</i>, of the largest quantile that is less than or equal to <i>q</i>.
+ * </li>
+ *
+ * <li><b>Definition of Non Inclusive Search <i>getQuantile(r)</i> search:</b><br>
+ * Given rank <i>r</i>, return the quantile of the smallest rank that is strictly greater than <i>r</i>.
+ * </li>
+ *
+ * <li><b>Definition of Inclusive Search <i>getQuantile(r)</i> search:</b><br>
+ * Given rank <i>r</i>, return the quantile of the smallest rank that is strictly greater than or equal to <i>r</i>.
+ * </li>
+ * </ul>
+
+ * @see <a href="https://datasketches.apache.org/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">
+ * Sketching Quantiles and Ranks Tutorial</a>
+ *
+ * @author Lee Rhodes
+ */
+public enum QuantileSearchCriteria {
+
+ /**
+ * See definition of Non Inclusive above.
+ *
+ * <p>For a non inclusive, strict getQuantile(rank) type search, If the given rank is equal to 1.0,
+ * there is no quantile that satisfies this criterion,
+ * the getQuantile(rank) method will return a NaN.</p>
+ */
+ NON_INCLUSIVE_STRICT,
+
+ /**
+ * See definition of Non Inclusive above.
+ *
+ * <p>For a non inclusive, getQuantile(rank) type search, If the given rank is is equal to 1.0,
+ * there is no quantile that satisfies this criterion, however,
+ * the method will return the largest quantile value retained by the sketch as a convenience.</p>
+ *
+ * <p>This is not strictly mathematically correct, but very convenient as it most often what we expect.</p>
+ */
+ NON_INCLUSIVE,
+
+ /**
+ * See definition of Inclusive above.
+ */
+ INCLUSIVE
+}
+
diff --git a/src/main/java/org/apache/datasketches/req/BaseReqSketch.java b/src/main/java/org/apache/datasketches/req/BaseReqSketch.java
index 10b51420..3538bd6b 100644
--- a/src/main/java/org/apache/datasketches/req/BaseReqSketch.java
+++ b/src/main/java/org/apache/datasketches/req/BaseReqSketch.java
@@ -19,14 +19,26 @@
package org.apache.datasketches.req;
+import org.apache.datasketches.QuantileSearchCriteria;
+
/**
* This abstract class provides a single place to define and document the public API
* for the Relative Error Quantiles Sketch.
*
+ * @see <a href="https://datasketches.apache.org/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">
+ * Sketching Quantiles and Ranks Tutorial</a>
+ *
* @author Lee Rhodes
*/
abstract class BaseReqSketch {
+ /**
+ * Same as {@link #getCDF(float[], QuantileSearchCriteria) getCDF(float[] splitPoints, QuantileSearchCriteria)}
+ * @param splitPoints splitPoints
+ * @return CDF
+ */
+ public abstract double[] getCDF(float[] splitPoints);
+
/**
* Returns an approximation to the Cumulative Distribution Function (CDF), which is the
* cumulative analog of the PMF, of the input stream given a set of splitPoint (values).
@@ -40,24 +52,17 @@ abstract class BaseReqSketch {
* that divide the real number line into <i>m+1</i> consecutive disjoint intervals.
* The definition of an "interval" is inclusive of the left splitPoint (or minimum value) and
* exclusive of the right splitPoint, with the exception that the last interval will include
- * the maximum value.
+ * the largest value retained by the sketch.
* It is not necessary to include either the min or max values in these split points.
*
- * @param inclusive if true the weight of a given value is included into its rank.
+ * @param inclusive if true, the weight of a given value is included into its rank.
*
* @return an array of m+1 double values, which are a consecutive approximation to the CDF
* of the input stream given the splitPoints. The value at array position j of the returned
* CDF array is the sum of the returned values in positions 0 through j of the returned PMF
* array.
*/
- public abstract double[] getCDF(float[] splitPoints, boolean inclusive);
-
- /**
- * Same as {@link #getCDF(float[], boolean) getCDF(float[] splitPoints, isLessThanOrEqual())}
- * @param splitPoints splitPoints
- * @return CDF
- */
- public abstract double[] getCDF(float[] splitPoints);
+ public abstract double[] getCDF(float[] splitPoints, QuantileSearchCriteria inclusive);
/**
* If true, the high ranks are prioritized for better accuracy. Otherwise
@@ -119,12 +124,12 @@ abstract class BaseReqSketch {
* @return an array of m+1 doubles each of which is an approximation
* to the fraction of the input stream values (the mass) that fall into one of those intervals.
* The definition of an "interval" is inclusive of the left splitPoint and exclusive of the right
- * splitPoint, with the exception that the last interval will include maximum value.
+ * splitPoint, with the exception that the last interval will include the largest value retained by the sketch.
*/
- public abstract double[] getPMF(float[] splitPoints, boolean inclusive);
+ public abstract double[] getPMF(float[] splitPoints, QuantileSearchCriteria inclusive);
/**
- * Same as {@link #getPMF(float[], boolean) getPMF(float[] splitPoints, isLessThanOrEqual())}
+ * Same as {@link #getPMF(float[], QuantileSearchCriteria) getPMF(float[] splitPoints, QuantileSearchCriteria)}
* @param splitPoints splitPoints
* @return PMF
*/
@@ -137,10 +142,10 @@ abstract class BaseReqSketch {
* @param inclusive if true, the given rank is considered inclusive.
* @return the approximate quantile given the normalized rank.
*/
- public abstract float getQuantile(double normRank, boolean inclusive);
+ public abstract float getQuantile(double normRank, QuantileSearchCriteria inclusive);
/**
- * Same as {@link #getQuantile(double, boolean) getQuantile(double fraction, isLessThanOrEqual())}
+ * Same as {@link #getQuantile(double, QuantileSearchCriteria) getQuantile(double fraction, QuantileSearchCriteria)}
* @param normRank fractional rank
* @return quantile
*/
@@ -153,10 +158,11 @@ abstract class BaseReqSketch {
* @return the array of quantiles that correspond to the given array of normalized ranks.
* See <i>getQuantile(double)</i>
*/
- public abstract float[] getQuantiles(double[] normRanks, boolean inclusive);
+ public abstract float[] getQuantiles(double[] normRanks, QuantileSearchCriteria inclusive);
/**
- * Same as {@link #getQuantiles(double[], boolean) getQuantiles(double[] fractions, isLessThanOrEqual())}
+ * Same as {@link #getQuantiles(double[], QuantileSearchCriteria)
+ * getQuantiles(double[] fractions, QuantileSearchCriteria)}
* @param normRanks normalized ranks
* @return quantiles
*/
@@ -170,10 +176,10 @@ abstract class BaseReqSketch {
* @param inclusive if true the weight of the given value is included into its rank.
* @return the normalized rank of the given value in the stream.
*/
- public abstract double getRank(float value, boolean inclusive);
+ public abstract double getRank(float value, QuantileSearchCriteria inclusive);
/**
- * Same as {@link #getRank(float, boolean) getRank(float value, isLessThanOrEqual())}
+ * Same as {@link #getRank(float, QuantileSearchCriteria) getRank(float value, QuantileSearchCriteria)}
* @param value value to be ranked
* @return normalized rank
*/
@@ -194,10 +200,10 @@ abstract class BaseReqSketch {
* @return the array of normalized ranks that correspond to the given array of values.
* See <i>getRank(float)</i>
*/
- public abstract double[] getRanks(float[] values, boolean inclusive);
+ public abstract double[] getRanks(float[] values, QuantileSearchCriteria inclusive);
/**
- * Same as {@link #getRanks(float[], boolean) getRanks(float[] values, isLessThanOrEqual())}
+ * Same as {@link #getRanks(float[], QuantileSearchCriteria) getRanks(float[] values, QuantileSearchCriteria)}
* @param values the given array of values to be ranked
* @return array of normalized ranks
*/
diff --git a/src/main/java/org/apache/datasketches/req/FloatBuffer.java b/src/main/java/org/apache/datasketches/req/FloatBuffer.java
index 6d86316c..a3246d88 100755
--- a/src/main/java/org/apache/datasketches/req/FloatBuffer.java
+++ b/src/main/java/org/apache/datasketches/req/FloatBuffer.java
@@ -21,6 +21,10 @@ package org.apache.datasketches.req;
import java.util.Arrays;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+
+import org.apache.datasketches.QuantileSearchCriteria;
+
import org.apache.datasketches.InequalitySearch;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.WritableBuffer;
@@ -202,10 +206,10 @@ class FloatBuffer {
* Returns the count of items based on the given criteria.
* Also used in test.
* @param value the given value
- * @param ltEq the chosen criterion: LT or LE
+ * @param inclusive the chosen criterion: LT, LT Strict, or LE
* @return count of items based on the given criterion.
*/
- int getCountWithCriterion(final float value, final boolean ltEq) {
+ int getCountWithCriterion(final float value, final QuantileSearchCriteria inclusive) {
assert !Float.isNaN(value) : "Float values must not be NaN.";
if (!sorted_) { sort(); } //we must be sorted!
int low = 0; //Initialized to space at top
@@ -214,7 +218,7 @@ class FloatBuffer {
low = capacity_ - count_;
high = capacity_ - 1;
}
- final InequalitySearch crit = ltEq ? InequalitySearch.LE : InequalitySearch.LT;
+ final InequalitySearch crit = (inclusive == INCLUSIVE) ? InequalitySearch.LE : InequalitySearch.LT;
final int index = InequalitySearch.find(arr_, low, high, value, crit);
return index == -1 ? 0 : index - low + 1;
}
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketch.java b/src/main/java/org/apache/datasketches/req/ReqSketch.java
index 22328099..f17668af 100644
--- a/src/main/java/org/apache/datasketches/req/ReqSketch.java
+++ b/src/main/java/org/apache/datasketches/req/ReqSketch.java
@@ -19,10 +19,14 @@
package org.apache.datasketches.req;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE;
+
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import org.apache.datasketches.QuantileSearchCriteria;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;
@@ -230,11 +234,11 @@ public class ReqSketch extends BaseReqSketch {
@Override
public double[] getCDF(final float[] splitPoints) {
- return getCDF(splitPoints, ltEq);
+ return getCDF(splitPoints, QuantileSearchCriteria.NON_INCLUSIVE);
}
@Override
- public double[] getCDF(final float[] splitPoints, final boolean inclusive) {
+ public double[] getCDF(final float[] splitPoints, final QuantileSearchCriteria inclusive) {
if (isEmpty()) { return null; }
final int numBkts = splitPoints.length + 1;
final double[] outArr = new double[numBkts];
@@ -267,11 +271,11 @@ public class ReqSketch extends BaseReqSketch {
@Override
public double[] getPMF(final float[] splitPoints) {
- return getPMF(splitPoints, ltEq);
+ return getPMF(splitPoints, ltEq == true ? INCLUSIVE : NON_INCLUSIVE);
}
@Override
- public double[] getPMF(final float[] splitPoints, final boolean inclusive) {
+ public double[] getPMF(final float[] splitPoints, final QuantileSearchCriteria inclusive) {
if (isEmpty()) { return null; }
final int numBkts = splitPoints.length + 1;
final double[] outArr = new double[numBkts];
@@ -285,11 +289,11 @@ public class ReqSketch extends BaseReqSketch {
@Override
public float getQuantile(final double normRank) {
- return getQuantile(normRank, ltEq);
+ return getQuantile(normRank, ltEq == true ? INCLUSIVE : NON_INCLUSIVE );
}
@Override
- public float getQuantile(final double normRank, final boolean inclusive) {
+ public float getQuantile(final double normRank, final QuantileSearchCriteria inclusive) {
if (isEmpty()) { return Float.NaN; }
if (normRank < 0 || normRank > 1.0) {
throw new SketchesArgumentException(
@@ -303,11 +307,11 @@ public class ReqSketch extends BaseReqSketch {
@Override
public float[] getQuantiles(final double[] normRanks) {
- return getQuantiles(normRanks, ltEq);
+ return getQuantiles(normRanks, ltEq == true ? INCLUSIVE : NON_INCLUSIVE);
}
@Override
- public float[] getQuantiles(final double[] normRanks, final boolean inclusive) {
+ public float[] getQuantiles(final double[] normRanks, final QuantileSearchCriteria inclusive) {
if (isEmpty()) { return null; }
final int len = normRanks.length;
final float[] qArr = new float[len];
@@ -319,11 +323,11 @@ public class ReqSketch extends BaseReqSketch {
@Override
public double getRank(final float value) {
- return getRank(value, ltEq);
+ return getRank(value, ltEq == true ? INCLUSIVE : NON_INCLUSIVE);
}
@Override
- public double getRank(final float value, final boolean inclusive) {
+ public double getRank(final float value, final QuantileSearchCriteria inclusive) {
if (isEmpty()) { return Double.NaN; }
final long nnCount = getCount(value, inclusive);
return (double)nnCount / totalN;
@@ -336,11 +340,11 @@ public class ReqSketch extends BaseReqSketch {
@Override
public double[] getRanks(final float[] values) {
- return getRanks(values, ltEq);
+ return getRanks(values, ltEq == true ? INCLUSIVE : NON_INCLUSIVE);
}
@Override
- public double[] getRanks(final float[] values, final boolean inclusive) {
+ public double[] getRanks(final float[] values, final QuantileSearchCriteria inclusive) {
if (isEmpty()) { return null; }
final int numValues = values.length;
final double[] retArr = new double[numValues];
@@ -586,7 +590,7 @@ public class ReqSketch extends BaseReqSketch {
if (reqDebug != null) { reqDebug.emitCompressDone(); }
}
- private long getCount(final float value, final boolean inclusive) {
+ private long getCount(final float value, final QuantileSearchCriteria inclusive) {
if (isEmpty()) { return 0; }
final int numComp = compactors.size();
long cumNnr = 0;
@@ -599,7 +603,7 @@ public class ReqSketch extends BaseReqSketch {
return cumNnr;
}
- private long[] getCounts(final float[] values, final boolean inclusive) {
+ private long[] getCounts(final float[] values, final QuantileSearchCriteria inclusive) {
final int numValues = values.length;
final int numComp = compactors.size();
final long[] cumNnrArr = new long[numValues];
@@ -621,7 +625,7 @@ public class ReqSketch extends BaseReqSketch {
* @param inclusive if true the weight of a given value is included into its rank
* @return a CDF in raw counts
*/
- private long[] getPMForCDF(final float[] splits, final boolean inclusive) {
+ private long[] getPMForCDF(final float[] splits, final QuantileSearchCriteria inclusive) {
validateSplits(splits);
final int numSplits = splits.length;
final long[] splitCounts = getCounts(splits, inclusive);
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketchSortedView.java b/src/main/java/org/apache/datasketches/req/ReqSketchSortedView.java
index 4ee07afd..96af7a44 100644
--- a/src/main/java/org/apache/datasketches/req/ReqSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/req/ReqSketchSortedView.java
@@ -19,10 +19,15 @@
package org.apache.datasketches.req;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE_STRICT;
+
import java.util.Arrays;
import java.util.List;
import org.apache.datasketches.InequalitySearch;
+import org.apache.datasketches.QuantileSearchCriteria;
/**
* The Sorted View provides a view of the data retained by the sketch that would be cumbersome to get any other way.
@@ -81,13 +86,14 @@ public class ReqSketchSortedView {
* @param inclusive determines the search criterion used.
* @return the quantile
*/
- public float getQuantile(final double normRank, final boolean inclusive) {
+ public float getQuantile(final double normRank, final QuantileSearchCriteria inclusive) {
final int len = cumWeights.length;
final long rank = (int)(normRank * N);
- final InequalitySearch crit = inclusive ? InequalitySearch.GE : InequalitySearch.GT;
+ final InequalitySearch crit = (inclusive == INCLUSIVE) ? InequalitySearch.GE : InequalitySearch.GT;
final int index = InequalitySearch.find(cumWeights, 0, len - 1, rank, crit);
if (index == -1) {
- return values[len - 1]; //GT: normRank >= 1.0; GE: normRank > 1.0
+ if (inclusive == NON_INCLUSIVE_STRICT) { return Float.NaN; } //GT: normRank == 1.0;
+ if (inclusive == NON_INCLUSIVE) { return values[len - 1]; }
}
return values[index];
}
@@ -98,9 +104,9 @@ public class ReqSketchSortedView {
* @param inclusive determines the search criterion used.
* @return the normalized rank
*/
- public double getRank(final float value, final boolean inclusive) {
+ public double getRank(final float value, final QuantileSearchCriteria inclusive) {
final int len = values.length;
- final InequalitySearch crit = inclusive ? InequalitySearch.LE : InequalitySearch.LT;
+ final InequalitySearch crit = (inclusive == INCLUSIVE) ? InequalitySearch.LE : InequalitySearch.LT;
final int index = InequalitySearch.find(values, 0, len - 1, value, crit);
if (index == -1) {
return 0; //LT: value <= minValue; LE: value < minValue
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketchSortedViewIterator.java b/src/main/java/org/apache/datasketches/req/ReqSketchSortedViewIterator.java
index 19437ae8..1bc81146 100644
--- a/src/main/java/org/apache/datasketches/req/ReqSketchSortedViewIterator.java
+++ b/src/main/java/org/apache/datasketches/req/ReqSketchSortedViewIterator.java
@@ -20,6 +20,8 @@
package org.apache.datasketches.req;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+import org.apache.datasketches.QuantileSearchCriteria;
/**
* Iterator over KllDoublesSketchSortedView.
*
@@ -66,9 +68,9 @@ public class ReqSketchSortedViewIterator {
* Otherwise, returns the cumulative weightof the previous value.
* @return cumulative weight for the current value.
*/
- public long getCumulativeWeight(final boolean inclusive) {
- return inclusive ? cumWeights[index]
- : (index == 0) ? 0 : cumWeights[index - 1];
+ public long getCumulativeWeight(final QuantileSearchCriteria inclusive) {
+ if (inclusive == INCLUSIVE) { return cumWeights[index]; }
+ return (index == 0) ? 0 : cumWeights[index - 1];
}
/**
@@ -80,7 +82,7 @@ public class ReqSketchSortedViewIterator {
* Otherwise, returns the normalized rank of the previous value.
* @return normalized rank for the current value or previous value.
*/
- public double getNormalizedRank(final boolean inclusive) {
+ public double getNormalizedRank(final QuantileSearchCriteria inclusive) {
return (double) getCumulativeWeight(inclusive) / totalN;
}
diff --git a/src/test/java/org/apache/datasketches/CrossCheckQuantilesTest.java b/src/test/java/org/apache/datasketches/CrossCheckQuantilesTest.java
index 945e9f98..545a40d6 100644
--- a/src/test/java/org/apache/datasketches/CrossCheckQuantilesTest.java
+++ b/src/test/java/org/apache/datasketches/CrossCheckQuantilesTest.java
@@ -26,6 +26,9 @@ import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.KLL;
import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.REQ;
import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.REQ_NO_DEDUP;
import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.REQ_SV;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE_STRICT;
import static org.testng.Assert.assertEquals;
import org.apache.datasketches.kll.KllFloatsSketch;
@@ -44,8 +47,6 @@ public class CrossCheckQuantilesTest {
final int k = 32; //all sketches are in exact mode
final boolean hra = false; //for the REQ sketch
- final boolean INCLUSIVE = true;
- final boolean NON_INCLUSIVE = false;
@Test
public void checkQuantileSketches() {
@@ -73,14 +74,14 @@ public class CrossCheckQuantilesTest {
double[] testQuantileDResults_NI = null;
double[] testQuantileDResults_I = null;
- private void checkQAndR(final SkType skType, final PrimType type, final boolean inclusive) {
+ private void checkQAndR(final SkType skType, final PrimType type, final QuantileSearchCriteria inclusive) {
String head = "CHECK " + skType.toString();
- if (inclusive) { println("\n---------- " + head + " INCLUSIVE ----------\n"); }
+ if (inclusive == INCLUSIVE) { println("\n---------- " + head + " INCLUSIVE ----------\n"); }
else { println("\n########## " + head + " NON-INCLUSIVE ##########\n"); }
//CREATE EMPTY SKETCHES
ReqSketchBuilder reqBldr = ReqSketch.builder();
- reqBldr.setK(k).setHighRankAccuracy(hra).setLessThanOrEqual(inclusive);
+ reqBldr.setK(k).setHighRankAccuracy(hra).setLessThanOrEqual(inclusive == INCLUSIVE ? true : false);
ReqSketch reqSk = reqBldr.build();
KllFloatsSketch kllSk = KllFloatsSketch.newHeapInstance(k);
@@ -88,14 +89,14 @@ public class CrossCheckQuantilesTest {
UpdateDoublesSketch udSk = DoublesSketch.builder().setK(k).build();
//SKETCH INPUT.
- float[] baseFVals = {10,20,30,40,50};
+ float[] baseFVals = {10,20,30,40,50};
double[] baseDVals = {10,20,30,40,50};
- int[] baseDups = { 1, 4, 6, 2, 1}; //number of duplicates per base value
+ int[] baseDups = { 1, 4, 6, 2, 1}; //number of duplicates per base value
//RAW TEST INPUT. This simulates what the Sorted View might see.
//This checks the search algos without the sketch and created by hand
float[] rawFVals = {10,20,20,30,30, 30, 40, 50}; //note grouping by twos
- long[] rawCumWts = { 1, 3, 5, 7, 9, 11, 13, 14};
+ long[] rawCumWts = { 1, 3, 5, 7, 9, 11, 13, 14};
//COMPUTE N
int N = 0;
@@ -169,7 +170,7 @@ public class CrossCheckQuantilesTest {
/**************************************/
- println(skType.toString() + " GetQuantile(NormalizedRank), INCLUSIVE = " + inclusive);
+ println(skType.toString() + " GetQuantile(NormalizedRank), INCLUSIVE = " + inclusive.toString());
println(" CumWeight is for illustration");
println(" Convert NormalizedRank to CumWeight (CW).");
println(" Search RSSV CumWeights[] array:");
@@ -186,11 +187,11 @@ public class CrossCheckQuantilesTest {
case REQ: { //this case creates the expected values for all the others
qF = reqSk.getQuantile(testRank, inclusive);
qD = qF;
- if (inclusive) {
+ if (inclusive == INCLUSIVE) {
testQuantileFResults_I[i] = qF;
testQuantileDResults_I[i] = qD;
}
- else {
+ else if (inclusive == NON_INCLUSIVE){
testQuantileFResults_NI[i] = qF;
testQuantileDResults_NI[i] = qD;
}
@@ -199,40 +200,40 @@ public class CrossCheckQuantilesTest {
case REQ_SV: {
qF = rssv.getQuantile(testRank, inclusive);
qD = 0;
- if (inclusive) { assertEquals(qF, testQuantileFResults_I[i]); }
+ if (inclusive == INCLUSIVE) { assertEquals(qF, testQuantileFResults_I[i]); }
else { assertEquals(qF, testQuantileFResults_NI[i]); };
break;
}
case REQ_NO_DEDUP: {
qF = this.getQuantile(rawCumWts, rawFVals, testRank, inclusive);
qD = 0;
- if (inclusive) { assertEquals(qF, testQuantileFResults_I[i]); }
+ if (inclusive == INCLUSIVE) { assertEquals(qF, testQuantileFResults_I[i]); }
else { assertEquals(qF, testQuantileFResults_NI[i]); };
break;
}
- case KLL: {
- qF = kllSk.getQuantile(testRank, inclusive);
- qD = 0;
- if (inclusive) { assertEquals(qF, testQuantileFResults_I[i]); }
- else { assertEquals(qF, testQuantileFResults_NI[i]); };
- break;
- }
- case CLASSIC: {
- qF = 0;
- qD = kllSk.getQuantile(testRank, inclusive);
- if (inclusive) { assertEquals(qD, testQuantileDResults_I[i]); }
- else { assertEquals(qD, testQuantileDResults_NI[i]); };
- break;
- }
+// case KLL: {
+// qF = kllSk.getQuantile(testRank, inclusive);
+// qD = 0;
+// if (inclusive) { assertEquals(qF, testQuantileFResults_I[i]); }
+// else { assertEquals(qF, testQuantileFResults_NI[i]); };
+// break;
+// }
+// case CLASSIC: {
+// qF = 0;
+// qD = kllSk.getQuantile(testRank, inclusive);
+// if (inclusive) { assertEquals(qD, testQuantileDResults_I[i]); }
+// else { assertEquals(qD, testQuantileDResults_NI[i]); };
+// break;
+// }
default: qD = qF = 0; break;
}
- if (inclusive) {
+ if (inclusive == INCLUSIVE) {
if (type == PrimType.DOUBLE) {
printf("%16.3f%16.3f%16.1f%16.1f\n", testRank, testRank * N, qD, testQuantileDResults_I[i]);
} else { //float
printf("%16.3f%16.3f%16.1f%16.1f\n", testRank, testRank * N, qF, testQuantileFResults_I[i]);
}
- } else { //else NI
+ } else if (inclusive == NON_INCLUSIVE){
if (type == PrimType.DOUBLE) {
printf("%16.3f%16.3f%16.1f%16.1f\n", testRank, testRank * N, qD, testQuantileDResults_NI[i]);
} else { //float
@@ -257,39 +258,39 @@ public class CrossCheckQuantilesTest {
switch (skType) {
case REQ: {
r = reqSk.getRank(testValue, inclusive);
- if (inclusive) { testRankResults_I[i] = r; }
- else { testRankResults_NI[i] = r; }
+ if (inclusive == INCLUSIVE) { testRankResults_I[i] = r; }
+ else if (inclusive == NON_INCLUSIVE) { testRankResults_NI[i] = r; }
break;
}
case REQ_SV: {
r = rssv.getRank(testValue, inclusive);
- if (inclusive) { assertEquals(r, testRankResults_I[i]); }
- else { assertEquals(r, testRankResults_NI[i]); };
+ if (inclusive == INCLUSIVE) { assertEquals(r, testRankResults_I[i]); }
+ else if (inclusive == NON_INCLUSIVE) { assertEquals(r, testRankResults_NI[i]); };
break;
}
case REQ_NO_DEDUP: {
r = getRank(rawCumWts, rawFVals, testValue, inclusive);
- if (inclusive) { assertEquals(r, testRankResults_I[i]); }
- else { assertEquals(r, testRankResults_NI[i]); };
- break;
- }
- case KLL: {
- r = kllSk.getRank(testValue, inclusive);
- if (inclusive) { assertEquals(r, testRankResults_I[i]); }
- else { assertEquals(r, testRankResults_NI[i]); };
- break;
- }
- case CLASSIC: {
- r = udSk.getRank(testValue, inclusive);
- if (inclusive) { assertEquals(r, testRankResults_I[i]); }
- else { assertEquals(r, testRankResults_NI[i]); };
+ if (inclusive == INCLUSIVE) { assertEquals(r, testRankResults_I[i]); }
+ else if (inclusive == NON_INCLUSIVE) { assertEquals(r, testRankResults_NI[i]); };
break;
}
+// case KLL: {
+// r = kllSk.getRank(testValue, inclusive);
+// if (inclusive == INCLUSIVE) { assertEquals(r, testRankResults_I[i]); }
+// else if (inclusive == NON_INCLUSIVE) { assertEquals(r, testRankResults_NI[i]); };
+// break;
+// }
+// case CLASSIC: {
+// r = udSk.getRank(testValue, inclusive);
+// if (inclusive == INCLUSIVE) { assertEquals(r, testRankResults_I[i]); }
+// else if (inclusive == NON_INCLUSIVE) { assertEquals(r, testRankResults_NI[i]); };
+// break;
+// }
default: r = 0; break;
}
- if (inclusive) {
+ if (inclusive == INCLUSIVE) {
printf("%16.1f%16.3f%16.3f\n", testValue, r, testRankResults_I[i]);
- } else {
+ } else if (inclusive == NON_INCLUSIVE) {
printf("%16.1f%16.3f%16.3f\n", testValue, r, testRankResults_NI[i]);
}
}
@@ -305,14 +306,15 @@ public class CrossCheckQuantilesTest {
* @return the quantile
*/
public float getQuantile(final long[] cumWeights, final float[] values, final double normRank,
- final boolean inclusive) {
+ final QuantileSearchCriteria inclusive) {
final int len = cumWeights.length;
final long N = cumWeights[len -1];
- final long rank = (int)(normRank * N);
- final InequalitySearch crit = inclusive ? InequalitySearch.GE : InequalitySearch.GT;
+ final long rank = (int)(normRank * N); //denormalize
+ final InequalitySearch crit = inclusive == INCLUSIVE ? InequalitySearch.GE : InequalitySearch.GT;
final int index = InequalitySearch.find(cumWeights, 0, len - 1, rank, crit);
if (index == -1) {
- return values[len - 1]; //GT: normRank >= 1.0; GE: normRank > 1.0
+ if (inclusive == NON_INCLUSIVE_STRICT) { return Float.NaN; } //GT: normRank == 1.0;
+ if (inclusive == NON_INCLUSIVE) { return values[len - 1]; }
}
return values[index];
}
@@ -322,18 +324,19 @@ public class CrossCheckQuantilesTest {
* @param cumWeights the given cumulative weights
* @param values the given values
* @param value the given value
- * @param ltEq determines the search criterion used.
+ * @param inclusive determines the search criterion used.
* @return the normalized rank
*/
- public double getRank(final long[] cumWeights, final float[] values, final float value, final boolean ltEq) {
+ public double getRank(final long[] cumWeights, final float[] values, final float value,
+ final QuantileSearchCriteria inclusive) {
final int len = values.length;
final long N = cumWeights[len -1];
- final InequalitySearch crit = ltEq ? InequalitySearch.LE : InequalitySearch.LT;
+ final InequalitySearch crit = inclusive == INCLUSIVE ? InequalitySearch.LE : InequalitySearch.LT;
final int index = InequalitySearch.find(values, 0, len - 1, value, crit);
if (index == -1) {
return 0; //LT: value <= minValue; LE: value < minValue
}
- return (double)cumWeights[index] / N;
+ return (double)cumWeights[index] / N; //normalize
}
private final static boolean enablePrinting = false;
diff --git a/src/test/java/org/apache/datasketches/req/FloatBufferTest.java b/src/test/java/org/apache/datasketches/req/ReqFloatBufferTest.java
similarity index 93%
rename from src/test/java/org/apache/datasketches/req/FloatBufferTest.java
rename to src/test/java/org/apache/datasketches/req/ReqFloatBufferTest.java
index 54c27a61..7594f90f 100644
--- a/src/test/java/org/apache/datasketches/req/FloatBufferTest.java
+++ b/src/test/java/org/apache/datasketches/req/ReqFloatBufferTest.java
@@ -19,6 +19,8 @@
package org.apache.datasketches.req;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertTrue;
import static org.testng.Assert.fail;
@@ -30,7 +32,7 @@ import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-public class FloatBufferTest {
+public class ReqFloatBufferTest {
@Test
public void checkTrimCount() {
@@ -125,9 +127,9 @@ public class FloatBufferTest {
final FloatBuffer buf = FloatBuffer.wrap(sortedArr, true, spaceAtBottom);
final FloatBuffer buf2 = new FloatBuffer(7,0, spaceAtBottom);
buf2.mergeSortIn(buf);
- assertEquals(buf2.getCountWithCriterion(4, false), 3);
+ assertEquals(buf2.getCountWithCriterion(4, NON_INCLUSIVE), 3);
buf2.mergeSortIn(buf);
- assertEquals(buf2.getCountWithCriterion(4, false), 6);
+ assertEquals(buf2.getCountWithCriterion(4, NON_INCLUSIVE), 6);
assertEquals(buf2.getCount(), 14);
buf2.trimCount(12);
assertEquals(buf2.getCount(), 12);
@@ -153,17 +155,17 @@ public class FloatBufferTest {
//@Test
public void checkCount() {
final FloatBuffer buf = createSortedFloatBuffer(120, 0, true, 100);
- println("LT: " + buf.getCountWithCriterion(100, false));
- println("LE: " + buf.getCountWithCriterion(100, true));
+ println("LT: " + buf.getCountWithCriterion(100, NON_INCLUSIVE));
+ println("LE: " + buf.getCountWithCriterion(100, INCLUSIVE));
}
private static void checkCountWithCriteria(final FloatBuffer buf, final float v) {
int count;
final int len = buf.getCount();
final int iv = (int) v;
- count = buf.getCountWithCriterion(v, false);
+ count = buf.getCountWithCriterion(v, NON_INCLUSIVE);
assertEquals(count, v > len ? len : v <= 1 ? 0 : iv == v? iv - 1 : iv);
- count = buf.getCountWithCriterion(v, true);
+ count = buf.getCountWithCriterion(v, INCLUSIVE);
assertEquals(count, v >= len ? len : v < 1 ? 0 : iv);
}
@@ -230,7 +232,7 @@ public class FloatBufferTest {
buf.append(3); buf.append(2); buf.append(1);
buf.trimCount(4);
assertEquals(buf.getCount(), 3);
- final int cnt = buf.getCountWithCriterion(3.0f, true);
+ final int cnt = buf.getCountWithCriterion(3.0f, INCLUSIVE);
assertEquals(cnt, 3);
assertEquals(buf.getItemFromIndex(2), 3.0f);
try { buf.getEvensOrOdds(0, 3, false); fail(); } catch (final SketchesArgumentException e) {}
diff --git a/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java b/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
index 82811264..69a02f5c 100644
--- a/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
+++ b/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
@@ -19,6 +19,9 @@
package org.apache.datasketches.req;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE;
+
import org.testng.annotations.Test;
/**
@@ -79,10 +82,10 @@ public class ReqSketchSortedViewTest {
while (itr.next()) {
float v = itr.getValue();
long wt = itr.getWeight();
- long cumWtNotInc = itr.getCumulativeWeight(false);
- double nRankNotInc = itr.getNormalizedRank(false);
- long cumWtInc = itr.getCumulativeWeight(true);
- double nRankInc = itr.getNormalizedRank(true);
+ long cumWtNotInc = itr.getCumulativeWeight(NON_INCLUSIVE);
+ double nRankNotInc = itr.getNormalizedRank(NON_INCLUSIVE);
+ long cumWtInc = itr.getCumulativeWeight(INCLUSIVE);
+ double nRankInc = itr.getNormalizedRank(INCLUSIVE);
printf(fmt, v, wt, cumWtNotInc, nRankNotInc, cumWtInc, nRankInc);
}
}
diff --git a/src/test/java/org/apache/datasketches/req/ReqSketchTest.java b/src/test/java/org/apache/datasketches/req/ReqSketchTest.java
index cdd3a8dd..3ba2700c 100644
--- a/src/test/java/org/apache/datasketches/req/ReqSketchTest.java
+++ b/src/test/java/org/apache/datasketches/req/ReqSketchTest.java
@@ -19,6 +19,11 @@
package org.apache.datasketches.req;
+import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE;
+import static org.apache.datasketches.QuantileSearchCriteria.NON_INCLUSIVE_STRICT;
+
+
import static org.apache.datasketches.Util.evenlySpacedFloats;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
@@ -29,6 +34,7 @@ import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.req.ReqSketchSortedView.Row;
import org.testng.annotations.Test;
+import org.apache.datasketches.QuantileSearchCriteria;
/**
* @author Lee Rhodes
@@ -340,8 +346,8 @@ public class ReqSketchTest {
assertEquals(sketch.getRetainedItems(), 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);
+ assertEquals(sketch.getRank(i, NON_INCLUSIVE), (i - 1) / 10.0);
+ assertEquals(sketch.getRank(i, INCLUSIVE), (i) / 10.0);
}
// inclusive = false (default)
assertEquals(sketch.getQuantile(0), 1); // always min value
@@ -356,17 +362,17 @@ public class ReqSketchTest {
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
+ assertEquals(sketch.getQuantile(0, INCLUSIVE), 1); // always min value
+ assertEquals(sketch.getQuantile(0.1, INCLUSIVE), 1);
+ assertEquals(sketch.getQuantile(0.2, INCLUSIVE), 2);
+ assertEquals(sketch.getQuantile(0.3, INCLUSIVE), 3);
+ assertEquals(sketch.getQuantile(0.4, INCLUSIVE), 4);
+ assertEquals(sketch.getQuantile(0.5, INCLUSIVE), 5);
+ assertEquals(sketch.getQuantile(0.6, INCLUSIVE), 6);
+ assertEquals(sketch.getQuantile(0.7, INCLUSIVE), 7);
+ assertEquals(sketch.getQuantile(0.8, INCLUSIVE), 8);
+ assertEquals(sketch.getQuantile(0.9, INCLUSIVE), 9);
+ assertEquals(sketch.getQuantile(1, INCLUSIVE), 10); // always max value
// getQuantile() and getQuantiles() equivalence
{
@@ -380,9 +386,9 @@ public class ReqSketchTest {
{
// 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);
+ sketch.getQuantiles(new double[] {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}, INCLUSIVE);
for (int i = 0; i <= 10; i++) {
- assertEquals(sketch.getQuantile(i / 10.0, true), quantiles[i]);
+ assertEquals(sketch.getQuantile(i / 10.0, INCLUSIVE), quantiles[i]);
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 06/08: Merge branch 'minor_changes_to_REQ' into Changes_to_kll
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 889c820b8845f5de95c121aac2f80c5cee054cbc
Merge: 1436f378 ad19fb65
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Jul 26 19:44:04 2022 -0700
Merge branch 'minor_changes_to_REQ' into Changes_to_kll
README.md | 6 ++++-
.../kll/KllDoublesSketchSortedView.java | 27 ++++++++++++++++++----
.../kll/KllFloatsSketchSortedView.java | 27 ++++++++++++++++++----
.../KllQuantilesHelper.java} | 11 +++++----
.../ClassicQuantilesHelper.java} | 10 +++++---
.../quantiles/DoublesSketchSortedView.java | 27 +++++++++++++++++-----
.../quantiles/ItemsSketchSortedView.java | 27 +++++++++++++++++-----
.../org/apache/datasketches/req/BaseReqSketch.java | 2 +-
.../datasketches/req/ReqSketchSortedView.java | 19 +++++++++++++--
.../req/ReqSketchSortedViewIterator.java | 5 ++--
.../datasketches/CrossCheckQuantilesTest.java | 2 +-
.../datasketches/kll/KllFloatsSketchTest.java | 2 +-
.../quantiles/HeapUpdateDoublesSketchTest.java | 4 ++--
.../org/apache/datasketches/req/ReqSketchTest.java | 3 ++-
14 files changed, 132 insertions(+), 40 deletions(-)
diff --cc src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
index f3359da5,9a2c0b24..2ea3d15a
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
@@@ -21,8 -21,6 +21,7 @@@ package org.apache.datasketches.kll
import java.util.Arrays;
- import org.apache.datasketches.QuantilesHelper;
+import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.SketchesStateException;
/**
diff --cc src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
index 073d562c,cb1951ff..a2d97dd9
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
@@@ -126,7 -125,7 +126,7 @@@ public class KllFloatsSketchTest
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
++ assertEquals(sketch.getQuantile(1, true), 10); // always max value TODO
// getQuantile() and getQuantiles() equivalence
{
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 04/08: incremental changes 1
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 1ba33414bc628338cadb7880b84ddee8c4739c4f
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Jul 25 14:38:00 2022 -0700
incremental changes 1
---
pom.xml | 1 +
.../apache/datasketches/kll/MiscFloatsTest.java | 42 +++++++++++++++++++---
2 files changed, 38 insertions(+), 5 deletions(-)
diff --git a/pom.xml b/pom.xml
index 51095f4b..c626f47c 100644
--- a/pom.xml
+++ b/pom.xml
@@ -682,6 +682,7 @@ under the License.
--add-exports java.base/jdk.internal.misc=ALL-UNNAMED
--add-exports java.base/jdk.internal.ref=ALL-UNNAMED
--add-opens java.base/java.nio=ALL-UNNAMED
+ --add-opens java.base/sun.nio.ch=ALL-UNNAMED
</argLine>
</configuration>
</plugin>
diff --git a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
index f0090486..3f827dfc 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
@@ -147,9 +147,29 @@ public class MiscFloatsTest {
show(sk, 108);
}
+ @Test
+ public void viewCompactionAndSortedView() {
+ KllFloatsSketch sk = KllFloatsSketch.newHeapInstance(20);
+ boolean cumulative = false;
+ boolean inclusive = false;
+ show(sk, 20);
+ KllFloatsSketchSortedView sv = sk.getSortedView(cumulative, inclusive);
+ KllFloatsSketchSortedViewIterator itr = sv.iterator();
+ if (cumulative) {
+ printf("%12s%12s\n", "Value", "CumWeight");
+ } else {
+ printf("%12s%12s\n", "Value", "Weight");
+ }
+ while (itr.next()) {
+ float v = itr.getValue();
+ long wt = itr.getWeight();
+ printf("%12.1f%12d\n", v, wt);
+ }
+ }
+
private static void show(final KllFloatsSketch sk, int limit) {
int i = (int) sk.getN();
- for ( ; i < limit; i++) { sk.update(i + 1); } //incremental update
+ for ( ; i < limit; i++) { sk.update(i + 1); }
println(sk.toString(true, true));
}
@@ -521,14 +541,26 @@ public class MiscFloatsTest {
@Test
public void printlnTest() {
- println("PRINTING: " + this.getClass().getName());
+ println("PRINTING: println in " + this.getClass().getName());
+ String s = "PRINTING: printf in " + this.getClass().getName();
+ printf("%s\n", s);
+ }
+
+ private final static boolean enablePrinting = true;
+
+ /**
+ * @param format the format
+ * @param args the args
+ */
+ private static final void printf(final String format, final Object ...args) {
+ if (enablePrinting) { System.out.printf(format, args); }
}
/**
- * @param o value to print
+ * @param o the Object to println
*/
- static void println(final Object o) {
- System.out.println(o.toString()); //disable here
+ private static final void println(final Object o) {
+ if (enablePrinting) { System.out.println(o.toString()); }
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 07/08: Interim 3
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 4a828111a9a508ab5404809b2373959351b5dfde
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Jul 27 10:06:38 2022 -0700
Interim 3
---
.../kll/KllDoublesSketchSortedView.java | 3 +-
.../apache/datasketches/kll/KllFloatsSketch.java | 90 +++++++++++-----------
.../kll/KllFloatsSketchSortedView.java | 44 +++++------
.../org/apache/datasketches/kll/KllHelper.java | 15 ++++
.../datasketches/kll/KllQuantilesHelper.java | 19 +----
.../datasketches/kll/KllFloatsSketchTest.java | 37 +--------
...blesTest.java => KllMiscDirectDoublesTest.java} | 2 +-
...loatsTest.java => KllMiscDirectFloatsTest.java} | 2 +-
...iscDoublesTest.java => KllMiscDoublesTest.java} | 2 +-
...{MiscFloatsTest.java => KllMiscFloatsTest.java} | 24 +++---
10 files changed, 102 insertions(+), 136 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
index 2fe496ac..cbf3f7fd 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
@@ -52,7 +52,6 @@ public final class KllDoublesSketchSortedView {
private int numLevels_;
// assumes that all levels are sorted including level 0
- @SuppressWarnings("deprecation")
KllDoublesSketchSortedView(final double[] items, final int[] levels, final int numLevels,
final long n, final boolean cumulative, final boolean inclusive) {
n_ = n;
@@ -63,7 +62,7 @@ public final class KllDoublesSketchSortedView {
populateFromSketch(items, levels, numLevels, numItems);
blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
if (cumulative) {
- KllQuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
+ KllHelper.convertToCumulative(weights_);
}
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
index 53538e2d..e420fcf6 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
@@ -34,6 +34,7 @@ import org.apache.datasketches.memory.MemoryRequestServer;
import org.apache.datasketches.memory.WritableMemory;
public abstract class KllFloatsSketch extends KllSketch {
+ KllFloatsSketchSortedView sortedView = null;
KllFloatsSketch(final WritableMemory wmem, final MemoryRequestServer memReqSvr) {
super(SketchType.FLOATS_SKETCH, wmem, memReqSvr);
@@ -156,6 +157,16 @@ public abstract class KllFloatsSketch extends KllSketch {
}
}
+ /**
+ * Same as {@link #getCDF(float[], boolean) getCDF(float[] splitPoints, false)}
+ * @param splitPoints splitPoints
+ * @return CDF
+ */
+ public double[] getCDF(final float[] splitPoints) {
+ //TDO add check for sorted view eventually
+ return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, true, false);
+ }
+
/**
* Returns an approximation to the Cumulative Distribution Function (CDF), which is the
* cumulative analog of the PMF, of the input stream given a set of splitPoint (values).
@@ -173,7 +184,7 @@ public abstract class KllFloatsSketch extends KllSketch {
* It is not necessary to include either the min or max values in these split points.
*
* @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
+ * Otherwise, the rank equals the sum of the weights of all values that are less than the given value
*
* @return an array of m+1 double values on the interval [0.0, 1.0),
* which are a consecutive approximation to the CDF of the input stream given the splitPoints.
@@ -181,18 +192,10 @@ public abstract class KllFloatsSketch extends KllSketch {
* in positions 0 through j of the returned PMF array.
*/
public double[] getCDF(final float[] splitPoints, final boolean inclusive) {
+ //TODO add check for sorted view eventually
return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, true, inclusive);
}
- /**
- * Same as {@link #getCDF(float[], boolean) getCDF(float[] splitPoints, false)}
- * @param splitPoints splitPoints
- * @return CDF
- */
- public double[] getCDF(final float[] splitPoints) {
- return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, true, false);
- }
-
/**
* Returns the max value of the stream.
* If the sketch is empty this returns NaN.
@@ -209,6 +212,15 @@ public abstract class KllFloatsSketch extends KllSketch {
*/
public float getMinValue() { return getMinFloatValue(); }
+ /**
+ * Same as {@link #getPMF(float[], boolean) getPMF(float[] splitPoints, false)}
+ * @param splitPoints splitPoints
+ * @return PMF
+ */
+ public double[] getPMF(final float[] splitPoints) {
+ return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, false, false);
+ }
+
/**
* Returns an approximation to the Probability Mass Function (PMF) of the input stream
* given a set of splitPoints (values).
@@ -235,16 +247,17 @@ public abstract class KllFloatsSketch extends KllSketch {
* splitPoint, with the exception that the last interval will include maximum value.
*/
public double[] getPMF(final float[] splitPoints, final boolean inclusive) {
+ //add check for sorted view eventually
return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, false, inclusive);
}
/**
- * Same as {@link #getPMF(float[], boolean) getPMF(float[] splitPoints, false)}
- * @param splitPoints splitPoints
- * @return PMF
+ * Same as {@link #getQuantile(double, boolean) getQuantile(double fraction, false)}
+ * @param rank the given normalized rank, a value in the interval [0.0,1.0].
+ * @return quantile
*/
- public double[] getPMF(final float[] splitPoints) {
- return KllFloatsSketchSortedView.getFloatsPmfOrCdf(this, splitPoints, false, false);
+ public float getQuantile(final double rank) {
+ return KllFloatsSketchSortedView.getFloatsQuantile(this, rank, false);
}
/**
@@ -258,36 +271,26 @@ public abstract class KllFloatsSketch extends KllSketch {
*
* <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 rank the given normalized rank, a value in the interval [0.0,1.0].
*
- * @param inclusive if true, the given fraction (rank) is considered inclusive
+ * @param inclusive if true, the given rank includes all values ≤ the value directly
+ * corresponding to the given rank.
* @return the approximation to the value at the given fraction
*/
- public float getQuantile(final double fraction, final boolean inclusive) {
- return KllFloatsSketchSortedView.getFloatsQuantile(this, fraction, inclusive);
- }
-
- /**
- * Same as {@link #getQuantile(double, boolean) getQuantile(double fraction, false)}
- * @param fraction fractional rank
- * @return quantile
- */
- public float getQuantile(final double fraction) {
- return KllFloatsSketchSortedView.getFloatsQuantile(this, fraction, false);
+ public float getQuantile(final double rank, final boolean inclusive) {
+ //TODO START HERE
+ return KllFloatsSketchSortedView.getFloatsQuantile(this, rank, inclusive);
}
/**
* Gets the lower bound of the value interval in which the true quantile of the given rank
* exists with a confidence of at least 99%.
- * @param fraction the given normalized rank as a fraction
+ * @param rank the given normalized rank, a value in the interval [0.0,1.0].
* @return the lower bound of the value interval in which the true quantile of the given rank
* exists with a confidence of at least 99%. Returns NaN if the sketch is empty.
*/
- public float getQuantileLowerBound(final double fraction) {
- return getQuantile(max(0, fraction - KllHelper.getNormalizedRankError(getMinK(), false)));
+ public float getQuantileLowerBound(final double rank) {
+ return getQuantile(max(0, rank - KllHelper.getNormalizedRankError(getMinK(), false)));
}
/**
@@ -301,11 +304,8 @@ public abstract class KllFloatsSketch extends KllSketch {
*
* <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
+ * @param fractions the given array of normalized ranks, each of which must be in the interval [0.0,1.0].
+ * @param inclusive if true, the given ranks include all values ≤ the value directly corresponding to each rank.
* @return array of approximations to the given fractions in the same order as given fractions
* array.
*/
@@ -315,11 +315,11 @@ public abstract class KllFloatsSketch extends KllSketch {
/**
* Same as {@link #getQuantiles(double[], boolean) getQuantiles(double[] fractions, false)}
- * @param fractions fractional ranks
+ * @param ranks fractional ranks
* @return quantiles
*/
- public float[] getQuantiles(final double[] fractions) {
- return KllFloatsSketchSortedView.getFloatsQuantiles(this, fractions, false);
+ public float[] getQuantiles(final double[] ranks) {
+ return KllFloatsSketchSortedView.getFloatsQuantiles(this, ranks, false);
}
/**
@@ -410,12 +410,10 @@ public abstract class KllFloatsSketch extends KllSketch {
/**
* Sorted view of the sketch.
* Complexity: linear, single-pass 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 KllFloatsSketchSortedView getSortedView(final boolean cumulative, final boolean inclusive) {
- return KllFloatsSketchSortedView.getFloatsSortedView(this, cumulative, inclusive);
+ public KllFloatsSketchSortedView getSortedView() {
+ return KllFloatsSketchSortedView.getFloatsSortedView(this);
}
@Override //Artifact of inheritance
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
index 2ea3d15a..b4f8191f 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
@@ -45,7 +45,6 @@ import org.apache.datasketches.SketchesStateException;
* @author Alexander Saydakov
*/
public final class KllFloatsSketchSortedView {
-
private final long n_;
private final float[] items_;
private final long[] weights_; //comes in as weights, converted to cumulative weights
@@ -53,19 +52,26 @@ public final class KllFloatsSketchSortedView {
private int numLevels_;
// assumes that all levels are sorted including level 0
- @SuppressWarnings("deprecation")
- KllFloatsSketchSortedView(final float[] items, final int[] levels, final int numLevels,
- final long n, final boolean cumulative, final boolean inclusive) {
+ KllFloatsSketchSortedView(final float[] items, final int[] levels, final int numLevels, final long n) {
n_ = n;
final int numItems = levels[numLevels] - levels[0];
items_ = new float[numItems];
- weights_ = new long[numItems + 1]; // one more is intentional
+ weights_ = new long[numItems];
levels_ = new int[numLevels + 1];
populateFromSketch(items, levels, numLevels, numItems);
blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
- if (cumulative) {
- KllQuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
+ KllHelper.convertToCumulative(weights_);
+ }
+
+ static KllFloatsSketchSortedView getFloatsSortedView(final KllSketch sketch) {
+ final float[] skFloatItemsArr = sketch.getFloatItemsArray();
+ final int[] skLevelsArr = sketch.getLevelsArray();
+
+ if (!sketch.isLevelZeroSorted()) {
+ Arrays.sort(skFloatItemsArr, skLevelsArr[0], skLevelsArr[1]);
+ if (!sketch.hasMemory()) { sketch.setLevelZeroSorted(true); }
}
+ return new KllFloatsSketchSortedView(skFloatItemsArr, skLevelsArr, sketch.getNumLevels(), sketch.getN());
}
private void populateFromSketch(final float[] srcItems, final int[] srcLevels,
@@ -91,18 +97,6 @@ public final class KllFloatsSketchSortedView {
numLevels_ = dstLevel;
}
- static KllFloatsSketchSortedView getFloatsSortedView(final KllSketch sketch,
- final boolean cumulative, final boolean inclusive) {
- final float[] skFloatItemsArr = sketch.getFloatItemsArray();
- final int[] skLevelsArr = sketch.getLevelsArray();
-
- if (!sketch.isLevelZeroSorted()) {
- Arrays.sort(skFloatItemsArr, skLevelsArr[0], skLevelsArr[1]);
- if (!sketch.hasMemory()) { sketch.setLevelZeroSorted(true); }
- }
- return new KllFloatsSketchSortedView(skFloatItemsArr, skLevelsArr, sketch.getNumLevels(), sketch.getN(),
- cumulative, inclusive);
- }
//For testing only. Allows testing of getQuantile without a sketch. NOT USED
KllFloatsSketchSortedView(final float[] items, final long[] weights, final long n) {
@@ -151,7 +145,7 @@ public final class KllFloatsSketchSortedView {
return (double) total / sketch.getN();
}
- //Called only from KllFloatsSketch
+ //Called only from KllFloatsSketch TODO rewrite using sorted view and new getRanks
static double[] getFloatsPmfOrCdf(final KllSketch sketch, final float[] splitPoints,
final boolean isCdf, final boolean inclusive) {
if (sketch.isEmpty()) { return null; }
@@ -242,13 +236,13 @@ public final class KllFloatsSketchSortedView {
}
//Called only from KllFloatsSketch
- static float getFloatsQuantile(final KllSketch sketch, final double fraction, final boolean inclusive) {
+ static float getFloatsQuantile(final KllSketch sketch, final double rank, final boolean inclusive) {
if (sketch.isEmpty()) { return Float.NaN; }
- if (fraction < 0.0 || fraction > 1.0) {
+ if (rank < 0.0 || rank > 1.0) {
throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
}
- final KllFloatsSketchSortedView kllFSV = KllFloatsSketchSortedView.getFloatsSortedView(sketch, true, inclusive);
- return kllFSV.getQuantile(fraction);
+ final KllFloatsSketchSortedView kllFSV = KllFloatsSketchSortedView.getFloatsSortedView(sketch);
+ return kllFSV.getQuantile(rank);
}
//Called only from KllFloatsSketch
@@ -262,7 +256,7 @@ public final class KllFloatsSketchSortedView {
throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
}
if (kllFSV == null) {
- kllFSV = KllFloatsSketchSortedView.getFloatsSortedView(sketch, true, inclusive);
+ kllFSV = getFloatsSortedView(sketch);
}
quantiles[i] = kllFSV.getQuantile(fraction);
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java
index 94512e08..8f5d4cc5 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java
@@ -260,6 +260,21 @@ final class KllHelper {
return (int) total;
}
+ /**
+ * Convert the individual weights into cumulative weights.
+ * An array of {1,1,1,1} becomes {1,2,3,4}
+ * @param array of actual weights from the sketch, where first element is not zero.
+ * @return total weight
+ */
+ public static long convertToCumulative(final long[] array) {
+ long subtotal = 0;
+ for (int i = 0; i < array.length; i++) {
+ final long newSubtotal = subtotal + array[i];
+ subtotal = array[i] = newSubtotal;
+ }
+ return subtotal;
+ }
+
static int currentLevelSize(final int level, final int numLevels, final int[] levels) {
if (level >= numLevels) { return 0; }
return levels[level + 1] - levels[level];
diff --git a/src/main/java/org/apache/datasketches/kll/KllQuantilesHelper.java b/src/main/java/org/apache/datasketches/kll/KllQuantilesHelper.java
index d07355b4..64667508 100644
--- a/src/main/java/org/apache/datasketches/kll/KllQuantilesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllQuantilesHelper.java
@@ -26,22 +26,6 @@ package org.apache.datasketches.kll;
*/
@Deprecated
public class KllQuantilesHelper {
- /**
- * Convert the weights into totals of the weights preceding each item.
- * An array of {1,1,1,0} becomes {0,1,2,3}
- * @param array of weights where first element is zero
- * @param inclusive for treating rank as including weight of an item
- * @return total weight
- */ //used by classic Quantiles and KLL
- public static long convertToPrecedingCumulative(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] = inclusive ? newSubtotal : subtotal;
- subtotal = newSubtotal;
- }
- return subtotal;
- }
/**
* Returns the linear zero-based index (position) of a value in the hypothetical sorted stream of
@@ -50,6 +34,7 @@ public class KllQuantilesHelper {
* @param n the size of the stream
* @return the index, a value between 0 and n-1.
*/ //used by classic Quantiles and KLL
+ @Deprecated
public static long posOfRank(final double rank, final long n) {
final long pos = (long) Math.floor(rank * n);
return pos == n ? n - 1 : pos; //avoids ArrayIndexOutOfBoundException
@@ -74,6 +59,7 @@ public class KllQuantilesHelper {
* @param pos the position
* @return the index of the chunk containing the position
*/ //also used by KLL
+ @Deprecated
public static int chunkContainingPos(final long[] wtArr, final long pos) {
final int nominalLength = wtArr.length - 1; /* remember, wtArr contains an "extra" position */
assert nominalLength > 0;
@@ -102,6 +88,7 @@ public class KllQuantilesHelper {
//
// A) and B) provide the invariants for our binary search.
// Observe that they are satisfied by the initial conditions: l = 0 and r = len.
+ @Deprecated
private static int searchForChunkContainingPos(final long[] arr, final long pos, final int l, final int r) {
// the following three asserts can probably go away eventually, since it is fairly clear
// that if these invariants hold at the beginning of the search, they will be maintained
diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
index a2d97dd9..fb600ce9 100644
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
@@ -28,7 +28,6 @@ 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;
@@ -547,40 +546,8 @@ public class KllFloatsSketchTest {
sk.update(3);
sk.update(1);
sk.update(2);
- { // non-cumulative (inclusive does not matter in this case)
- final KllFloatsSketchSortedView view = sk.getSortedView(false, false);
- final KllFloatsSketchSortedViewIterator 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
- final KllFloatsSketchSortedView view = sk.getSortedView(true, false);
- final KllFloatsSketchSortedViewIterator 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
- final KllFloatsSketchSortedView view = sk.getSortedView(true, true);
+ {
+ final KllFloatsSketchSortedView view = sk.getSortedView();
final KllFloatsSketchSortedViewIterator it = view.iterator();
assertEquals(it.next(), true);
assertEquals(it.getValue(), 1);
diff --git a/src/test/java/org/apache/datasketches/kll/MiscDirectDoublesTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscDirectDoublesTest.java
similarity index 99%
rename from src/test/java/org/apache/datasketches/kll/MiscDirectDoublesTest.java
rename to src/test/java/org/apache/datasketches/kll/KllMiscDirectDoublesTest.java
index 84f5f37b..127027be 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscDirectDoublesTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscDirectDoublesTest.java
@@ -29,7 +29,7 @@ import org.apache.datasketches.memory.DefaultMemoryRequestServer;
import org.apache.datasketches.memory.WritableMemory;
import org.testng.annotations.Test;
-public class MiscDirectDoublesTest {
+public class KllMiscDirectDoublesTest {
static final String LS = System.getProperty("line.separator");
private static final DefaultMemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
diff --git a/src/test/java/org/apache/datasketches/kll/MiscDirectFloatsTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscDirectFloatsTest.java
similarity index 99%
rename from src/test/java/org/apache/datasketches/kll/MiscDirectFloatsTest.java
rename to src/test/java/org/apache/datasketches/kll/KllMiscDirectFloatsTest.java
index 6810dc2d..dacf8497 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscDirectFloatsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscDirectFloatsTest.java
@@ -29,7 +29,7 @@ import org.apache.datasketches.memory.DefaultMemoryRequestServer;
import org.apache.datasketches.memory.WritableMemory;
import org.testng.annotations.Test;
-public class MiscDirectFloatsTest {
+public class KllMiscDirectFloatsTest {
static final String LS = System.getProperty("line.separator");
private static final DefaultMemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
diff --git a/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
similarity index 99%
rename from src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
rename to src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
index 656343cc..c2ddb6eb 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
@@ -35,7 +35,7 @@ import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-public class MiscDoublesTest {
+public class KllMiscDoublesTest {
static final String LS = System.getProperty("line.separator");
private final MemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
diff --git a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java
similarity index 98%
rename from src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
rename to src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java
index 3f827dfc..cbccca81 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java
@@ -35,10 +35,22 @@ import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-public class MiscFloatsTest {
+public class KllMiscFloatsTest {
static final String LS = System.getProperty("line.separator");
private final MemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
+ @Test
+ public void checkConvertToCumulative() {
+ long[] array = {1,2,3,2,1};
+ long out = KllHelper.convertToCumulative(array);
+ assertEquals(out, 9);
+ }
+
+ @Test
+ public void checkSortedViewConstruction() {
+
+ }
+
@Test
public void checkBounds() {
final KllFloatsSketch kll = KllFloatsSketch.newHeapInstance(); //default k = 200
@@ -150,16 +162,10 @@ public class MiscFloatsTest {
@Test
public void viewCompactionAndSortedView() {
KllFloatsSketch sk = KllFloatsSketch.newHeapInstance(20);
- boolean cumulative = false;
- boolean inclusive = false;
show(sk, 20);
- KllFloatsSketchSortedView sv = sk.getSortedView(cumulative, inclusive);
+ KllFloatsSketchSortedView sv = sk.getSortedView();
KllFloatsSketchSortedViewIterator itr = sv.iterator();
- if (cumulative) {
- printf("%12s%12s\n", "Value", "CumWeight");
- } else {
- printf("%12s%12s\n", "Value", "Weight");
- }
+ printf("%12s%12s\n", "Value", "CumWeight");
while (itr.next()) {
float v = itr.getValue();
long wt = itr.getWeight();
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 01/08: minor renaming of "mine" to "sketch".
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 5e36107ab48a5d31315a1f59acf3a5e84520a0c2
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Sat Jul 23 09:50:04 2022 -0700
minor renaming of "mine" to "sketch".
---
.../apache/datasketches/kll/KllFloatsHelper.java | 149 ++++++++++-----------
.../kll/KllFloatsSketchSortedView.java | 2 +-
2 files changed, 72 insertions(+), 79 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
index c0862f09..e11391a2 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
@@ -36,46 +36,46 @@ import org.apache.datasketches.SketchesArgumentException;
*/
final class KllFloatsHelper {
- static double getFloatRank(final KllSketch mine, final float value, final boolean inclusive) {
- if (mine.isEmpty()) { return Double.NaN; }
+ static double getFloatRank(final KllSketch sketch, final float value, final boolean inclusive) {
+ if (sketch.isEmpty()) { return Double.NaN; }
int level = 0;
int weight = 1;
long total = 0;
- final float[] myFloatItemsArr = mine.getFloatItemsArray();
- final int[] myLevelsArr = mine.getLevelsArray();
- while (level < mine.getNumLevels()) {
+ final float[] myFloatItemsArr = sketch.getFloatItemsArray();
+ final int[] myLevelsArr = sketch.getLevelsArray();
+ while (level < sketch.getNumLevels()) {
final int fromIndex = myLevelsArr[level];
final int toIndex = myLevelsArr[level + 1]; // exclusive
for (int i = fromIndex; i < toIndex; i++) {
if (inclusive ? myFloatItemsArr[i] <= value : myFloatItemsArr[i] < value) {
total += weight;
- } else if (level > 0 || mine.isLevelZeroSorted()) {
+ } else if (level > 0 || sketch.isLevelZeroSorted()) {
break; // levels above 0 are sorted, no point comparing further
}
}
level++;
weight *= 2;
}
- return (double) total / mine.getN();
+ return (double) total / sketch.getN();
}
- static double[] getFloatsPmfOrCdf(final KllSketch mine, final float[] splitPoints,
+ static double[] getFloatsPmfOrCdf(final KllSketch sketch, final float[] splitPoints,
final boolean isCdf, final boolean inclusive) {
- if (mine.isEmpty()) { return null; }
+ if (sketch.isEmpty()) { return null; }
validateFloatValues(splitPoints);
final double[] buckets = new double[splitPoints.length + 1];
- final int myNumLevels = mine.getNumLevels();
- final int[] myLevelsArr = mine.getLevelsArray();
+ final int myNumLevels = sketch.getNumLevels();
+ final int[] myLevelsArr = sketch.getLevelsArray();
int level = 0;
int weight = 1;
while (level < myNumLevels) {
final int fromIndex = myLevelsArr[level];
final int toIndex = myLevelsArr[level + 1]; // exclusive
- if (level == 0 && !mine.isLevelZeroSorted()) {
- KllFloatsHelper.incrementFloatBucketsUnsortedLevel(mine, fromIndex, toIndex, weight, splitPoints,
+ if (level == 0 && !sketch.isLevelZeroSorted()) {
+ KllFloatsHelper.incrementFloatBucketsUnsortedLevel(sketch, fromIndex, toIndex, weight, splitPoints,
buckets, inclusive);
} else {
- KllFloatsHelper.incrementFloatBucketsSortedLevel(mine, fromIndex, toIndex, weight, splitPoints,
+ KllFloatsHelper.incrementFloatBucketsSortedLevel(sketch, fromIndex, toIndex, weight, splitPoints,
buckets, inclusive);
}
level++;
@@ -86,81 +86,74 @@ final class KllFloatsHelper {
double subtotal = 0;
for (int i = 0; i < buckets.length; i++) {
subtotal += buckets[i];
- buckets[i] = subtotal / mine.getN();
+ buckets[i] = subtotal / sketch.getN();
}
} else {
for (int i = 0; i < buckets.length; i++) {
- buckets[i] /= mine.getN();
+ buckets[i] /= sketch.getN();
}
}
return buckets;
}
- static float getFloatsQuantile(final KllSketch mine, final double fraction, final boolean inclusive) {
- if (mine.isEmpty()) { return Float.NaN; }
+ static float getFloatsQuantile(final KllSketch sketch, final double fraction, final boolean inclusive) {
+ if (sketch.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");
}
- //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 KllFloatsSketchSortedView quant = KllFloatsHelper.getFloatsSortedView(mine, true, inclusive);
+ final KllFloatsSketchSortedView quant = KllFloatsHelper.getFloatsSortedView(sketch, true, inclusive);
return quant.getQuantile(fraction);
}
- static float[] getFloatsQuantiles(final KllSketch mine, final double[] fractions, final boolean inclusive) {
- if (mine.isEmpty()) { return null; }
- KllFloatsSketchSortedView quant = null;
+ static float[] getFloatsQuantiles(final KllSketch sketch, final double[] fractions, final boolean inclusive) {
+ if (sketch.isEmpty()) { return null; }
+ KllFloatsSketchSortedView kllFSV = null;
final float[] quantiles = new float[fractions.length];
- for (int i = 0; i < fractions.length; i++) {
+ for (int i = 0; i < fractions.length; i++) { //check if fraction are in [0, 1]
final double fraction = fractions[i];
if (fraction < 0.0 || fraction > 1.0) {
throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
}
- if (fraction == 0.0) { quantiles[i] = mine.getMinFloatValue(); }
- else if (fraction == 1.0) { quantiles[i] = mine.getMaxFloatValue(); }
- else {
- if (quant == null) {
- quant = KllFloatsHelper.getFloatsSortedView(mine, true, inclusive);
- }
- quantiles[i] = quant.getQuantile(fraction);
+ if (kllFSV == null) {
+ kllFSV = KllFloatsHelper.getFloatsSortedView(sketch, true, inclusive);
}
+ quantiles[i] = kllFSV.getQuantile(fraction);
}
return quantiles;
}
- static void mergeFloatImpl(final KllSketch mine, final KllSketch other) {
+ static void mergeFloatImpl(final KllSketch sketch, final KllSketch other) {
if (other.isEmpty()) { return; }
- final long finalN = mine.getN() + other.getN();
+ final long finalN = sketch.getN() + other.getN();
final int otherNumLevels = other.getNumLevels();
final int[] otherLevelsArr = other.getLevelsArray();
final float[] otherFloatItemsArr;
//capture my min & max, minK
- final float myMin = mine.getMinFloatValue();
- final float myMax = mine.getMaxFloatValue();
- final int myMinK = mine.getMinK();
+ final float myMin = sketch.getMinFloatValue();
+ final float myMax = sketch.getMaxFloatValue();
+ final int myMinK = sketch.getMinK();
//update this sketch with level0 items from the other sketch
if (other.isCompactSingleItem()) {
- updateFloat(mine, other.getFloatSingleItem());
+ updateFloat(sketch, other.getFloatSingleItem());
otherFloatItemsArr = new float[0];
} else {
otherFloatItemsArr = other.getFloatItemsArray();
for (int i = otherLevelsArr[0]; i < otherLevelsArr[1]; i++) {
- updateFloat(mine, otherFloatItemsArr[i]);
+ updateFloat(sketch, otherFloatItemsArr[i]);
}
}
// after the level 0 update, we capture the state of levels and items arrays
- final int myCurNumLevels = mine.getNumLevels();
- final int[] myCurLevelsArr = mine.getLevelsArray();
- final float[] myCurFloatItemsArr = mine.getFloatItemsArray();
+ final int myCurNumLevels = sketch.getNumLevels();
+ final int[] myCurLevelsArr = sketch.getLevelsArray();
+ final float[] myCurFloatItemsArr = sketch.getFloatItemsArray();
int myNewNumLevels = myCurNumLevels;
int[] myNewLevelsArr = myCurLevelsArr;
float[] myNewFloatItemsArr = myCurFloatItemsArr;
if (otherNumLevels > 1 && !other.isCompactSingleItem()) { //now merge higher levels if they exist
- final int tmpSpaceNeeded = mine.getNumRetained()
+ final int tmpSpaceNeeded = sketch.getNumRetained()
+ KllHelper.getNumRetainedAboveLevelZero(otherNumLevels, otherLevelsArr);
final float[] workbuf = new float[tmpSpaceNeeded];
final int ub = KllHelper.ubOnNumLevels(finalN);
@@ -174,8 +167,8 @@ final class KllFloatsHelper {
otherNumLevels, otherLevelsArr, otherFloatItemsArr);
// notice that workbuf is being used as both the input and output
- final int[] result = generalFloatsCompress(mine.getK(), mine.getM(), provisionalNumLevels,
- workbuf, worklevels, workbuf, outlevels, mine.isLevelZeroSorted(), KllSketch.random);
+ final int[] result = generalFloatsCompress(sketch.getK(), sketch.getM(), provisionalNumLevels,
+ workbuf, worklevels, workbuf, outlevels, sketch.isLevelZeroSorted(), KllSketch.random);
final int targetItemCount = result[1]; //was finalCapacity. Max size given k, m, numLevels
final int curItemCount = result[2]; //was finalPop
@@ -206,28 +199,28 @@ final class KllFloatsHelper {
}
//MEMORY SPACE MANAGEMENT
- if (mine.updatableMemFormat) {
- mine.wmem = KllHelper.memorySpaceMgmt(mine, myNewLevelsArr.length, myNewFloatItemsArr.length);
+ if (sketch.updatableMemFormat) {
+ sketch.wmem = KllHelper.memorySpaceMgmt(sketch, myNewLevelsArr.length, myNewFloatItemsArr.length);
}
}
//Update Preamble:
- mine.setN(finalN);
+ sketch.setN(finalN);
if (other.isEstimationMode()) { //otherwise the merge brings over exact items.
- mine.setMinK(min(myMinK, other.getMinK()));
+ sketch.setMinK(min(myMinK, other.getMinK()));
}
//Update numLevels, levelsArray, items
- mine.setNumLevels(myNewNumLevels);
- mine.setLevelsArray(myNewLevelsArr);
- mine.setFloatItemsArray(myNewFloatItemsArr);
+ sketch.setNumLevels(myNewNumLevels);
+ sketch.setLevelsArray(myNewLevelsArr);
+ sketch.setFloatItemsArray(myNewFloatItemsArr);
//Update min, max values
final float otherMin = other.getMinFloatValue();
final float otherMax = other.getMaxFloatValue();
- mine.setMinFloatValue(resolveFloatMinValue(myMin, otherMin));
- mine.setMaxFloatValue(resolveFloatMaxValue(myMax, otherMax));
- assert KllHelper.sumTheSampleWeights(mine.getNumLevels(), mine.getLevelsArray()) == mine.getN();
+ sketch.setMinFloatValue(resolveFloatMinValue(myMin, otherMin));
+ sketch.setMaxFloatValue(resolveFloatMaxValue(myMax, otherMax));
+ assert KllHelper.sumTheSampleWeights(sketch.getNumLevels(), sketch.getLevelsArray()) == sketch.getN();
}
static void mergeSortedFloatArrays(
@@ -299,20 +292,20 @@ final class KllFloatsHelper {
}
}
- static void updateFloat(final KllSketch mine, final float value) {
+ static void updateFloat(final KllSketch sketch, final float value) {
if (Float.isNaN(value)) { return; }
- final float prevMin = mine.getMinFloatValue();
- final float prevMax = mine.getMaxFloatValue();
- mine.setMinFloatValue(resolveFloatMinValue(prevMin, value));
- mine.setMaxFloatValue(resolveFloatMaxValue(prevMax, value));
- if (mine.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(mine); }
- final int myLevelsArrAtZero = mine.getLevelsArray()[0]; //LevelsArr could be expanded
- mine.incN();
- mine.setLevelZeroSorted(false);
+ final float prevMin = sketch.getMinFloatValue();
+ final float prevMax = sketch.getMaxFloatValue();
+ sketch.setMinFloatValue(resolveFloatMinValue(prevMin, value));
+ sketch.setMaxFloatValue(resolveFloatMaxValue(prevMax, value));
+ if (sketch.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(sketch); }
+ final int myLevelsArrAtZero = sketch.getLevelsArray()[0]; //LevelsArr could be expanded
+ sketch.incN();
+ sketch.setLevelZeroSorted(false);
final int nextPos = myLevelsArrAtZero - 1;
assert myLevelsArrAtZero >= 0;
- mine.setLevelsArrayAt(0, nextPos);
- mine.setFloatItemsArrayAt(nextPos, value);
+ sketch.setLevelsArrayAt(0, nextPos);
+ sketch.setFloatItemsArrayAt(nextPos, value);
}
/**
@@ -436,22 +429,22 @@ final class KllFloatsHelper {
return new int[] {numLevels, targetItemCount, currentItemCount};
}
- static KllFloatsSketchSortedView getFloatsSortedView(final KllSketch mine,
+ static KllFloatsSketchSortedView getFloatsSortedView(final KllSketch sketch,
final boolean cumulative, 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); }
+ final int[] skLevelsArr = sketch.getLevelsArray();
+ final float[] skFloatItemsArr = sketch.getFloatItemsArray();
+ if (!sketch.isLevelZeroSorted()) {
+ Arrays.sort(skFloatItemsArr, skLevelsArr[0], skLevelsArr[1]);
+ if (!sketch.hasMemory()) { sketch.setLevelZeroSorted(true); }
}
- return new KllFloatsSketchSortedView(myFloatItemsArr, myLevelsArr, mine.getNumLevels(), mine.getN(),
+ return new KllFloatsSketchSortedView(skFloatItemsArr, skLevelsArr, sketch.getNumLevels(), sketch.getN(),
cumulative, inclusive);
}
private static void incrementFloatBucketsSortedLevel(
- final KllSketch mine, final int fromIndex, final int toIndex, final int weight,
+ final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
final float[] splitPoints, final double[] buckets, final boolean inclusive) {
- final float[] myFloatItemsArr = mine.getFloatItemsArray();
+ final float[] myFloatItemsArr = sketch.getFloatItemsArray();
int i = fromIndex;
int j = 0;
while (i < toIndex && j < splitPoints.length) {
@@ -471,9 +464,9 @@ final class KllFloatsHelper {
}
private static void incrementFloatBucketsUnsortedLevel(
- final KllSketch mine, final int fromIndex, final int toIndex, final int weight,
+ final KllSketch sketch, final int fromIndex, final int toIndex, final int weight,
final float[] splitPoints, final double[] buckets, final boolean inclusive) {
- final float[] myFloatItemsArr = mine.getFloatItemsArray();
+ final float[] myFloatItemsArr = sketch.getFloatItemsArray();
for (int i = fromIndex; i < toIndex; i++) {
int j;
for (j = 0; j < splitPoints.length; j++) {
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
index 8627fcfc..e4824c8a 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
@@ -52,7 +52,7 @@ public final class KllFloatsSketchSortedView {
}
}
- //For testing only. Allows testing of getQuantile without a sketch.
+ //For testing only. Allows testing of getQuantile without a sketch. NOT USED
KllFloatsSketchSortedView(final float[] items, final long[] weights, final long n) {
n_ = n;
items_ = items;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-java] 03/08: Merge branch 'minor_changes_to_REQ' into Changes_to_kll
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch More_changes_to_REQ
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 6e30aba521a10b3842c5d4de450ead5b10a610f6
Merge: e2fb4365 5370ed4d
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Jul 25 14:31:09 2022 -0700
Merge branch 'minor_changes_to_REQ' into Changes_to_kll
README.md | 5 -----
pom.xml | 14 ++++++++------
2 files changed, 8 insertions(+), 11 deletions(-)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org