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/03/26 02:26:04 UTC
[datasketches-java] 02/12: Interim 2
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch DirectKllDouble
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit f8cf41dcb11f577df4f68ec039c4bd73ecde5d9f
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Mar 3 11:26:38 2022 -0800
Interim 2
---
.../org/apache/datasketches/kll/BaseKllSketch.java | 67 +----
.../apache/datasketches/kll/KllDoublesSketch.java | 136 ++++------
.../apache/datasketches/kll/KllFloatsSketch.java | 130 ++++------
.../org/apache/datasketches/kll/KllHelper.java | 114 +++++++--
.../org/apache/datasketches/kll/PreambleUtil.java | 276 +++++++++++----------
.../datasketches/kll/KllDoublesSketchTest.java | 6 +-
.../datasketches/kll/KllDoublesValidationTest.java | 4 +-
.../datasketches/kll/KllFloatsSketchTest.java | 8 +-
.../datasketches/kll/KllFloatsValidationTest.java | 4 +-
.../org/apache/datasketches/kll/KllHelperTest.java | 48 ++++
.../apache/datasketches/kll/MiscDoublesTest.java | 33 +--
.../apache/datasketches/kll/MiscFloatsTest.java | 33 +--
12 files changed, 429 insertions(+), 430 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java b/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
index 4a019b5..6dab928 100644
--- a/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
@@ -25,15 +25,12 @@ import static java.lang.Math.exp;
import static java.lang.Math.log;
import static java.lang.Math.max;
import static java.lang.Math.min;
-import static java.lang.Math.pow;
import static java.lang.Math.round;
import static org.apache.datasketches.kll.PreambleUtil.MAX_K;
import static org.apache.datasketches.kll.PreambleUtil.MIN_K;
import java.util.Random;
-import org.apache.datasketches.SketchesArgumentException;
-
abstract class BaseKllSketch {
/*
@@ -72,7 +69,7 @@ abstract class BaseKllSketch {
* @param compatible if true, compatible with quantiles sketch treatment of rank 0.0 and 1.0.
*/
BaseKllSketch(final int k, final int m, final boolean compatible) {
- checkK(k);
+ KllHelper.checkK(k);
k_ = k;
minK_ = k;
m_ = m;
@@ -133,7 +130,7 @@ abstract class BaseKllSketch {
* @see KllDoublesSketch
*/
public double getNormalizedRankError(final boolean pmf) {
- return getNormalizedRankError(minK_, pmf);
+ return KllHelper.getNormalizedRankError(minK_, pmf);
}
/**
@@ -144,14 +141,9 @@ abstract class BaseKllSketch {
* Otherwise, it is the "single-sided" normalized rank error for all the other queries.
* @return if pmf is true, the normalized rank error for the getPMF() function.
* Otherwise, it is the "single-sided" normalized rank error for all the other queries.
- * @see KllDoublesSketch
*/
- // constants were derived as the best fit to 99 percentile empirically measured max error in
- // thousands of trials
public static double getNormalizedRankError(final int k, final boolean pmf) {
- return pmf
- ? 2.446 / pow(k, 0.9433)
- : 2.296 / pow(k, 0.9723);
+ return KllHelper.getNormalizedRankError(k, pmf);
}
/**
@@ -159,7 +151,7 @@ abstract class BaseKllSketch {
* @return the number of retained items (samples) in the sketch
*/
public int getNumRetained() {
- return levels_[numLevels_] - levels_[0];
+ return KllHelper.getNumRetained(numLevels_, levels_);
}
/**
@@ -198,55 +190,4 @@ abstract class BaseKllSketch {
*/
public abstract String toString(final boolean withLevels, final boolean withData);
- // Restricted Methods
-
- /**
- * Checks the validity of the given value k
- * @param k must be greater than 7 and less than 65536.
- */
- static void checkK(final int k) {
- if (k < MIN_K || k > MAX_K) {
- throw new SketchesArgumentException(
- "K must be >= " + MIN_K + " and <= " + MAX_K + ": " + k);
- }
- }
-
- /**
- * Finds the first level starting with level 0 that exceeds its nominal capacity
- * @return level to compact
- */
- int findLevelToCompact() { //
- int level = 0;
- while (true) {
- assert level < numLevels_;
- final int pop = levels_[level + 1] - levels_[level];
- final int cap = KllHelper.levelCapacity(k_, numLevels_, level, m_);
- if (pop >= cap) {
- return level;
- }
- level++;
- }
- }
-
- int currentLevelSize(final int level) {
- if (level >= numLevels_) { return 0; }
- return levels_[level + 1] - levels_[level];
- }
-
- int getNumRetainedAboveLevelZero() {
- if (numLevels_ == 1) { return 0; }
- return levels_[numLevels_] - levels_[1];
- }
-
- // for testing
-
- int[] getLevels() {
- return levels_;
- }
-
- int getNumLevels() {
- return numLevels_;
- }
-
}
-
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index a0d4a6c..ec1e0a2 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -27,6 +27,7 @@ import static org.apache.datasketches.kll.PreambleUtil.DATA_START_ADR_DOUBLE;
import static org.apache.datasketches.kll.PreambleUtil.DATA_START_ADR_SINGLE_ITEM;
import static org.apache.datasketches.kll.PreambleUtil.DEFAULT_K;
import static org.apache.datasketches.kll.PreambleUtil.DEFAULT_M;
+import static org.apache.datasketches.kll.PreambleUtil.DOUBLES_SKETCH_BIT_MASK;
import static org.apache.datasketches.kll.PreambleUtil.EMPTY_BIT_MASK;
import static org.apache.datasketches.kll.PreambleUtil.FAMILY_BYTE_ADR;
import static org.apache.datasketches.kll.PreambleUtil.FLAGS_BYTE_ADR;
@@ -50,6 +51,7 @@ import org.apache.datasketches.Family;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.Util;
import org.apache.datasketches.kll.KllHelper.LevelStats;
+import org.apache.datasketches.kll.PreambleUtil.MemoryCheck;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
@@ -106,13 +108,12 @@ public class KllDoublesSketch extends BaseKllSketch {
/**
* Private heapify constructor.
* @param mem Memory object that contains data serialized by this sketch.
+ * @param memChk the MemoryCheck object
*/
- private KllDoublesSketch(final Memory mem) {
- super(mem.getShort(K_SHORT_ADR) & 0xffff, DEFAULT_M, true);
- final int flags = mem.getByte(FLAGS_BYTE_ADR) & 0xff;
- final boolean empty = (flags & EMPTY_BIT_MASK) > 0;
- final boolean singleItem = (flags & SINGLE_ITEM_BIT_MASK) > 0;
- if (empty) {
+ private KllDoublesSketch(final Memory mem, final MemoryCheck memChk) {
+ super(memChk.k, memChk.m, true);
+ isLevelZeroSorted_ = memChk.level0Sorted;
+ if (memChk.empty) {
numLevels_ = 1;
levels_ = new int[] {k_, k_};
isLevelZeroSorted_ = false;
@@ -120,40 +121,36 @@ public class KllDoublesSketch extends BaseKllSketch {
items_ = new double[k_];
minValue_ = Double.NaN;
maxValue_ = Double.NaN;
+ } else if (memChk.singleItem) {
+ n_ = 1;
+ minK_ = k_;
+ numLevels_ = 1;
+ levels_ = new int[numLevels_ + 1]; //ALL
+ final int offset = DATA_START_ADR_SINGLE_ITEM;
+ final int itemCapacity = KllHelper.computeTotalItemCapacity(k_, m_, numLevels_);
+ levels_[0] = itemCapacity - 1;
+ levels_[numLevels_] = itemCapacity; //load the last integer in levels_
+ items_ = new double[itemCapacity];
+ mem.getDoubleArray(offset, items_, levels_[0], getNumRetained());
+ minValue_ = items_[levels_[0]];
+ maxValue_ = items_[levels_[0]];
} else {
- if (singleItem) {
- n_ = 1;
- minK_ = k_;
- numLevels_ = 1;
- } else {
- n_ = mem.getLong(N_LONG_ADR);
- minK_ = mem.getShort(MIN_K_SHORT_ADR) & 0xffff;
- numLevels_ = mem.getByte(NUM_LEVELS_BYTE_ADR) & 0xff;
- }
- levels_ = new int[numLevels_ + 1];
- int offset = singleItem ? DATA_START_ADR_SINGLE_ITEM : DATA_START_ADR_DOUBLE;
+ n_ = memChk.n;
+ minK_ = memChk.minK;
+ numLevels_ = memChk.numLevels;
+ levels_ = new int[numLevels_ + 1]; //ALL
+ int offset = DATA_START_ADR_DOUBLE;
final int itemCapacity = KllHelper.computeTotalItemCapacity(k_, m_, numLevels_);
- if (singleItem) {
- levels_[0] = itemCapacity - 1;
- } else {
- // the last integer in levels_ is not serialized because it can be derived
- mem.getIntArray(offset, levels_, 0, numLevels_);
- offset += numLevels_ * Integer.BYTES;
- }
- levels_[numLevels_] = itemCapacity;
- if (!singleItem) {
- minValue_ = mem.getDouble(offset);
- offset += Double.BYTES;
- maxValue_ = mem.getDouble(offset);
- offset += Double.BYTES;
- }
+ // the last integer in levels_ is not serialized because it can be derived
+ mem.getIntArray(offset, levels_, 0, numLevels_); //load levels_
+ offset += numLevels_ * Integer.BYTES;
+ levels_[numLevels_] = itemCapacity; //load the last integer in levels_
+ minValue_ = mem.getDouble(offset);
+ offset += Double.BYTES;
+ maxValue_ = mem.getDouble(offset);
+ offset += Double.BYTES;
items_ = new double[itemCapacity];
mem.getDoubleArray(offset, items_, levels_[0], getNumRetained());
- if (singleItem) {
- minValue_ = items_[levels_[0]];
- maxValue_ = items_[levels_[0]];
- }
- isLevelZeroSorted_ = (flags & LEVEL_ZERO_SORTED_BIT_MASK) > 0;
}
}
@@ -164,41 +161,14 @@ public class KllDoublesSketch extends BaseKllSketch {
* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
* @return a heap-based sketch based on the given Memory.
*/
- //To simplify the code, this method does all the validity checking
- // then passes the verified Memory to the actual heapify constructor
+ //To simplify the code, the PreambleUtil.MemoryCheck does nearly all the validity checking.
+ //The verified Memory is then passed to the actual private heapify constructor.
public static KllDoublesSketch heapify(final Memory mem) {
- final int preambleInts = mem.getByte(PREAMBLE_INTS_BYTE_ADR) & 0xff;
- final int serialVersion = mem.getByte(SER_VER_BYTE_ADR) & 0xff;
- final int family = mem.getByte(FAMILY_BYTE_ADR) & 0xff;
- final int flags = mem.getByte(FLAGS_BYTE_ADR) & 0xff;
- final int m = mem.getByte(M_BYTE_ADR) & 0xff;
- if (m != DEFAULT_M) {
- throw new SketchesArgumentException(
- "Possible corruption: M must be " + DEFAULT_M + ": " + m);
- }
- final boolean empty = (flags & EMPTY_BIT_MASK) > 0;
- final boolean singleItem = (flags & SINGLE_ITEM_BIT_MASK) > 0;
- if (empty || singleItem) {
- if (preambleInts != PREAMBLE_INTS_EMPTY_SINGLE) {
- throw new SketchesArgumentException("Possible corruption: preambleInts must be "
- + PREAMBLE_INTS_EMPTY_SINGLE + " for an empty or single item sketch: " + preambleInts);
- }
- } else {
- if (preambleInts != PREAMBLE_INTS_DOUBLE) {
- throw new SketchesArgumentException("Possible corruption: preambleInts must be "
- + PREAMBLE_INTS_DOUBLE + " for a sketch with more than one item: " + preambleInts);
- }
- }
- if (serialVersion != SERIAL_VERSION_EMPTY_FULL && serialVersion != SERIAL_VERSION_SINGLE) {
- throw new SketchesArgumentException(
- "Possible corruption: serial version mismatch: expected " + SERIAL_VERSION_EMPTY_FULL + " or "
- + SERIAL_VERSION_SINGLE + ", got " + serialVersion);
- }
- if (family != Family.KLL.getID()) {
- throw new SketchesArgumentException(
- "Possible corruption: family mismatch: expected " + Family.KLL.getID() + ", got " + family);
+ final MemoryCheck memChk = new MemoryCheck(mem);
+ if (!memChk.doublesSketch) {
+ throw new SketchesArgumentException("Memory object is not a KllDoublesSketch.");
}
- return new KllDoublesSketch(mem);
+ return new KllDoublesSketch(mem, memChk);
}
// public functions
@@ -249,15 +219,15 @@ public class KllDoublesSketch extends BaseKllSketch {
}
/**
- * Returns upper bound on the serialized size of a sketch given a parameter <em>k</em> and stream
+ * Returns upper bound on the compact serialized size of a sketch given a parameter <em>k</em> and stream
* length. This method can be used if allocation of storage is necessary beforehand.
* @param k parameter that controls size of the sketch and accuracy of estimates
* @param n stream length
- * @return upper bound on the serialized size
+ * @return upper bound on the compact serialized size
*/
public static int getMaxSerializedSizeBytes(final int k, final long n) {
final LevelStats lvlStats = getAllLevelStatsGivenN(k, DEFAULT_M, n, false, false, true);
- return lvlStats.getBytes();
+ return lvlStats.getCompactBytes();
}
/**
@@ -333,7 +303,7 @@ public class KllDoublesSketch extends BaseKllSketch {
* exists with a confidence of at least 99%. Returns NaN if the sketch is empty.
*/
public double getQuantileUpperBound(final double fraction) {
- return getQuantile(min(1.0, fraction + getNormalizedRankError(minK_, false)));
+ return getQuantile(min(1.0, fraction + KllHelper.getNormalizedRankError(minK_, false)));
}
/**
@@ -344,7 +314,7 @@ public class KllDoublesSketch extends BaseKllSketch {
* exists with a confidence of at least 99%. Returns NaN if the sketch is empty.
*/
public double getQuantileLowerBound(final double fraction) {
- return getQuantile(max(0, fraction - getNormalizedRankError(minK_, false)));
+ return getQuantile(max(0, fraction - KllHelper.getNormalizedRankError(minK_, false)));
}
/**
@@ -497,7 +467,8 @@ public class KllDoublesSketch extends BaseKllSketch {
final byte flags = (byte) (
(empty ? EMPTY_BIT_MASK : 0)
| (isLevelZeroSorted_ ? LEVEL_ZERO_SORTED_BIT_MASK : 0)
- | (singleItem ? SINGLE_ITEM_BIT_MASK : 0));
+ | (singleItem ? SINGLE_ITEM_BIT_MASK : 0)
+ | DOUBLES_SKETCH_BIT_MASK);
wmem.putByte(FLAGS_BYTE_ADR, flags);
wmem.putShort(K_SHORT_ADR, (short) k_);
wmem.putByte(M_BYTE_ADR, (byte) m_);
@@ -527,7 +498,7 @@ public class KllDoublesSketch extends BaseKllSketch {
final String epsPct = String.format("%.3f%%", getNormalizedRankError(false) * 100);
final String epsPMFPct = String.format("%.3f%%", getNormalizedRankError(true) * 100);
final StringBuilder sb = new StringBuilder();
- sb.append(Util.LS).append("### KLL sketch summary:").append(Util.LS);
+ sb.append(Util.LS).append("### KLL Doubles Sketch summary:").append(Util.LS);
sb.append(" K : ").append(k_).append(Util.LS);
sb.append(" min K : ").append(minK_).append(Util.LS);
sb.append(" M : ").append(m_).append(Util.LS);
@@ -551,7 +522,7 @@ public class KllDoublesSketch extends BaseKllSketch {
for (int i = 0; i < numLevels_; i++) {
sb.append(" ").append(i).append(", ").append(levels_[i]).append(": ")
.append(KllHelper.levelCapacity(k_, numLevels_, i, m_))
- .append(", ").append(currentLevelSize(i)).append(Util.LS);
+ .append(", ").append(KllHelper.currentLevelSize(i, numLevels_, levels_)).append(Util.LS);
}
sb.append("### End sketch levels").append(Util.LS);
}
@@ -686,7 +657,7 @@ public class KllDoublesSketch extends BaseKllSketch {
// 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.
private void compressWhileUpdating() {
- final int level = findLevelToCompact();
+ final int level = KllHelper.findLevelToCompact(k_, m_, numLevels_, levels_);
// It is important to do add the new top level right here. Be aware that this operation
// grows the buffer and shifts the data and also the boundaries of the data and grows the
@@ -780,7 +751,8 @@ public class KllDoublesSketch extends BaseKllSketch {
}
private void mergeHigherLevels(final KllDoublesSketch other, final long finalN) {
- final int tmpSpaceNeeded = getNumRetained() + other.getNumRetainedAboveLevelZero();
+ final int tmpSpaceNeeded = getNumRetained()
+ + KllHelper.getNumRetainedAboveLevelZero(other.numLevels_, other.levels_);
final double[] workbuf = new double[tmpSpaceNeeded];
final int ub = KllHelper.ubOnNumLevels(finalN);
final int[] worklevels = new int[ub + 2]; // ub+1 does not work
@@ -822,13 +794,13 @@ public class KllDoublesSketch extends BaseKllSketch {
worklevels[0] = 0;
// Note: the level zero data from "other" was already inserted into "self"
- final int selfPopZero = currentLevelSize(0);
+ final int selfPopZero = KllHelper.currentLevelSize(0, numLevels_, levels_);
System.arraycopy(items_, levels_[0], workbuf, worklevels[0], selfPopZero);
worklevels[1] = worklevels[0] + selfPopZero;
for (int lvl = 1; lvl < provisionalNumLevels; lvl++) {
- final int selfPop = currentLevelSize(lvl);
- final int otherPop = other.currentLevelSize(lvl);
+ final int selfPop = KllHelper.currentLevelSize(lvl, numLevels_, levels_);
+ final int otherPop = KllHelper.currentLevelSize(lvl, other.numLevels_, other.levels_);
worklevels[lvl + 1] = worklevels[lvl] + selfPop + otherPop;
if (selfPop > 0 && otherPop == 0) {
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
index c8e928a..f0aa48e 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
@@ -50,9 +50,11 @@ import org.apache.datasketches.Family;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.Util;
import org.apache.datasketches.kll.KllHelper.LevelStats;
+import org.apache.datasketches.kll.PreambleUtil.MemoryCheck;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
+
/**
* Please refer to the documentation in the package-info:<br>
* {@link org.apache.datasketches.kll}
@@ -106,13 +108,12 @@ public class KllFloatsSketch extends BaseKllSketch {
/**
* Private heapify constructor.
* @param mem Memory object that contains data serialized by this sketch.
+ * @param memChk the MemoryCheck object
*/
- private KllFloatsSketch(final Memory mem) {
- super(mem.getShort(K_SHORT_ADR) & 0xffff, DEFAULT_M, true);
- final int flags = mem.getByte(FLAGS_BYTE_ADR) & 0xff;
- final boolean empty = (flags & EMPTY_BIT_MASK) > 0;
- final boolean singleItem = (flags & SINGLE_ITEM_BIT_MASK) > 0;
- if (empty) {
+ private KllFloatsSketch(final Memory mem, final MemoryCheck memChk) {
+ super(memChk.k, memChk.m, true);
+ isLevelZeroSorted_ = memChk.level0Sorted;
+ if (memChk.empty) {
numLevels_ = 1;
levels_ = new int[] {k_, k_};
isLevelZeroSorted_ = false;
@@ -120,40 +121,36 @@ public class KllFloatsSketch extends BaseKllSketch {
items_ = new float[k_];
minValue_ = Float.NaN;
maxValue_ = Float.NaN;
+ } else if (memChk.singleItem) {
+ n_ = 1;
+ minK_ = k_;
+ numLevels_ = 1;
+ levels_ = new int[numLevels_ + 1]; //ALL
+ final int offset = DATA_START_ADR_SINGLE_ITEM;
+ final int itemCapacity = KllHelper.computeTotalItemCapacity(k_, m_, numLevels_);
+ levels_[0] = itemCapacity - 1;
+ levels_[numLevels_] = itemCapacity; //load the last integer in levels_
+ items_ = new float[itemCapacity];
+ mem.getFloatArray(offset, items_, levels_[0], getNumRetained());
+ minValue_ = items_[levels_[0]];
+ maxValue_ = items_[levels_[0]];
} else {
- if (singleItem) {
- n_ = 1;
- minK_ = k_;
- numLevels_ = 1;
- } else {
- n_ = mem.getLong(N_LONG_ADR);
- minK_ = mem.getShort(MIN_K_SHORT_ADR) & 0xffff;
- numLevels_ = mem.getByte(NUM_LEVELS_BYTE_ADR) & 0xff;
- }
- levels_ = new int[numLevels_ + 1];
- int offset = singleItem ? DATA_START_ADR_SINGLE_ITEM : DATA_START_ADR_FLOAT;
+ n_ = memChk.n;
+ minK_ = memChk.minK;
+ numLevels_ = memChk.numLevels;
+ levels_ = new int[numLevels_ + 1]; //ALL
+ int offset = DATA_START_ADR_FLOAT;
final int itemCapacity = KllHelper.computeTotalItemCapacity(k_, m_, numLevels_);
- if (singleItem) {
- levels_[0] = itemCapacity - 1;
- } else {
- // the last integer in levels_ is not serialized because it can be derived
- mem.getIntArray(offset, levels_, 0, numLevels_);
- offset += numLevels_ * Integer.BYTES;
- }
- levels_[numLevels_] = itemCapacity;
- if (!singleItem) {
- minValue_ = mem.getFloat(offset);
- offset += Float.BYTES;
- maxValue_ = mem.getFloat(offset);
- offset += Float.BYTES;
- }
+ // the last integer in levels_ is not serialized because it can be derived
+ mem.getIntArray(offset, levels_, 0, numLevels_); //load levels_
+ offset += numLevels_ * Integer.BYTES;
+ levels_[numLevels_] = itemCapacity; //load the last integer in levels_
+ minValue_ = mem.getFloat(offset);
+ offset += Float.BYTES;
+ maxValue_ = mem.getFloat(offset);
+ offset += Float.BYTES;
items_ = new float[itemCapacity];
mem.getFloatArray(offset, items_, levels_[0], getNumRetained());
- if (singleItem) {
- minValue_ = items_[levels_[0]];
- maxValue_ = items_[levels_[0]];
- }
- isLevelZeroSorted_ = (flags & LEVEL_ZERO_SORTED_BIT_MASK) > 0;
}
}
@@ -164,41 +161,14 @@ public class KllFloatsSketch extends BaseKllSketch {
* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
* @return a heap-based sketch based on the given Memory.
*/
- //To simplify the code, this method does all the validity checking
- // then passes the verified Memory to the actual heapify constructor
+ //To simplify the code, the PreambleUtil.MemoryCheck does nearly all the validity checking.
+ //The verified Memory is then passed to the actual private heapify constructor.
public static KllFloatsSketch heapify(final Memory mem) {
- final int preambleInts = mem.getByte(PREAMBLE_INTS_BYTE_ADR) & 0xff;
- final int serialVersion = mem.getByte(SER_VER_BYTE_ADR) & 0xff;
- final int family = mem.getByte(FAMILY_BYTE_ADR) & 0xff;
- final int flags = mem.getByte(FLAGS_BYTE_ADR) & 0xff;
- final int m = mem.getByte(M_BYTE_ADR) & 0xff;
- if (m != DEFAULT_M) {
- throw new SketchesArgumentException(
- "Possible corruption: M must be " + DEFAULT_M + ": " + m);
+ final MemoryCheck memChk = new MemoryCheck(mem);
+ if (memChk.doublesSketch) {
+ throw new SketchesArgumentException("Memory object is not a KllFloatsSketch.");
}
- final boolean empty = (flags & EMPTY_BIT_MASK) > 0;
- final boolean singleItem = (flags & SINGLE_ITEM_BIT_MASK) > 0;
- if (empty || singleItem) {
- if (preambleInts != PREAMBLE_INTS_EMPTY_SINGLE) {
- throw new SketchesArgumentException("Possible corruption: preambleInts must be "
- + PREAMBLE_INTS_EMPTY_SINGLE + " for an empty or single item sketch: " + preambleInts);
- }
- } else {
- if (preambleInts != PREAMBLE_INTS_FLOAT) {
- throw new SketchesArgumentException("Possible corruption: preambleInts must be "
- + PREAMBLE_INTS_FLOAT + " for a sketch with more than one item: " + preambleInts);
- }
- }
- if (serialVersion != SERIAL_VERSION_EMPTY_FULL && serialVersion != SERIAL_VERSION_SINGLE) {
- throw new SketchesArgumentException(
- "Possible corruption: serial version mismatch: expected " + SERIAL_VERSION_EMPTY_FULL + " or "
- + SERIAL_VERSION_SINGLE + ", got " + serialVersion);
- }
- if (family != Family.KLL.getID()) {
- throw new SketchesArgumentException(
- "Possible corruption: family mismatch: expected " + Family.KLL.getID() + ", got " + family);
- }
- return new KllFloatsSketch(mem);
+ return new KllFloatsSketch(mem, memChk);
}
// public functions
@@ -257,7 +227,7 @@ public class KllFloatsSketch extends BaseKllSketch {
*/
public static int getMaxSerializedSizeBytes(final int k, final long n) {
final LevelStats lvlStats = getAllLevelStatsGivenN(k, DEFAULT_M, n, false, false, false);
- return lvlStats.getBytes();
+ return lvlStats.getCompactBytes();
}
/**
@@ -333,7 +303,7 @@ public class KllFloatsSketch extends BaseKllSketch {
* exists with a confidence of at least 99%. Returns NaN if the sketch is empty.
*/
public float getQuantileUpperBound(final double fraction) {
- return getQuantile(min(1.0, fraction + getNormalizedRankError(minK_, false)));
+ return getQuantile(min(1.0, fraction + KllHelper.getNormalizedRankError(minK_, false)));
}
/**
@@ -344,7 +314,7 @@ public class KllFloatsSketch extends BaseKllSketch {
* 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 - getNormalizedRankError(minK_, false)));
+ return getQuantile(max(0, fraction - KllHelper.getNormalizedRankError(minK_, false)));
}
/**
@@ -498,6 +468,7 @@ public class KllFloatsSketch extends BaseKllSketch {
(empty ? EMPTY_BIT_MASK : 0)
| (isLevelZeroSorted_ ? LEVEL_ZERO_SORTED_BIT_MASK : 0)
| (singleItem ? SINGLE_ITEM_BIT_MASK : 0));
+
wmem.putByte(FLAGS_BYTE_ADR, flags);
wmem.putShort(K_SHORT_ADR, (short) k_);
wmem.putByte(M_BYTE_ADR, (byte) m_);
@@ -527,7 +498,7 @@ public class KllFloatsSketch extends BaseKllSketch {
final String epsPct = String.format("%.3f%%", getNormalizedRankError(false) * 100);
final String epsPMFPct = String.format("%.3f%%", getNormalizedRankError(true) * 100);
final StringBuilder sb = new StringBuilder();
- sb.append(Util.LS).append("### KLL sketch summary:").append(Util.LS);
+ sb.append(Util.LS).append("### KLL Floats Sketch summary:").append(Util.LS);
sb.append(" K : ").append(k_).append(Util.LS);
sb.append(" min K : ").append(minK_).append(Util.LS);
sb.append(" M : ").append(m_).append(Util.LS);
@@ -551,7 +522,7 @@ public class KllFloatsSketch extends BaseKllSketch {
for (int i = 0; i < numLevels_; i++) {
sb.append(" ").append(i).append(", ").append(levels_[i]).append(": ")
.append(KllHelper.levelCapacity(k_, numLevels_, i, m_))
- .append(", ").append(currentLevelSize(i)).append(Util.LS);
+ .append(", ").append(KllHelper.currentLevelSize(i, numLevels_, levels_)).append(Util.LS);
}
sb.append("### End sketch levels").append(Util.LS);
}
@@ -686,7 +657,7 @@ public class KllFloatsSketch extends BaseKllSketch {
// 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.
private void compressWhileUpdating() {
- final int level = findLevelToCompact();
+ final int level = KllHelper.findLevelToCompact(k_, m_, numLevels_, levels_);
// It is important to do add the new top level right here. Be aware that this operation
// grows the buffer and shifts the data and also the boundaries of the data and grows the
@@ -780,7 +751,8 @@ public class KllFloatsSketch extends BaseKllSketch {
}
private void mergeHigherLevels(final KllFloatsSketch other, final long finalN) {
- final int tmpSpaceNeeded = getNumRetained() + other.getNumRetainedAboveLevelZero();
+ final int tmpSpaceNeeded = getNumRetained()
+ + KllHelper.getNumRetainedAboveLevelZero(other.numLevels_, other.levels_);
final float[] workbuf = new float[tmpSpaceNeeded];
final int ub = KllHelper.ubOnNumLevels(finalN);
final int[] worklevels = new int[ub + 2]; // ub+1 does not work
@@ -822,13 +794,13 @@ public class KllFloatsSketch extends BaseKllSketch {
worklevels[0] = 0;
// Note: the level zero data from "other" was already inserted into "self"
- final int selfPopZero = currentLevelSize(0);
+ final int selfPopZero = KllHelper.currentLevelSize(0, numLevels_, levels_);
System.arraycopy(items_, levels_[0], workbuf, worklevels[0], selfPopZero);
worklevels[1] = worklevels[0] + selfPopZero;
for (int lvl = 1; lvl < provisionalNumLevels; lvl++) {
- final int selfPop = currentLevelSize(lvl);
- final int otherPop = other.currentLevelSize(lvl);
+ final int selfPop = KllHelper.currentLevelSize(lvl, numLevels_, levels_);
+ final int otherPop = KllHelper.currentLevelSize(lvl, other.numLevels_, other.levels_);
worklevels[lvl + 1] = worklevels[lvl] + selfPop + otherPop;
if (selfPop > 0 && otherPop == 0) {
diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java
index 9cb1123..891ed3c 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java
@@ -19,10 +19,15 @@
package org.apache.datasketches.kll;
+import static java.lang.Math.pow;
import static org.apache.datasketches.Util.floorPowerOf2;
import static org.apache.datasketches.kll.PreambleUtil.DATA_START_ADR_DOUBLE;
import static org.apache.datasketches.kll.PreambleUtil.DATA_START_ADR_FLOAT;
import static org.apache.datasketches.kll.PreambleUtil.DATA_START_ADR_SINGLE_ITEM;
+import static org.apache.datasketches.kll.PreambleUtil.MAX_K;
+import static org.apache.datasketches.kll.PreambleUtil.MIN_K;
+
+import org.apache.datasketches.SketchesArgumentException;
class KllHelper {
static final String LS = System.getProperty("line.separator");
@@ -51,7 +56,7 @@ class KllHelper {
return 1 + Long.numberOfTrailingZeros(floorPowerOf2(n));
}
- public static LevelStats getAllLevelStatsGivenN(final int k, final int m, final long n,
+ static LevelStats getAllLevelStatsGivenN(final int k, final int m, final long n,
final boolean printDetail, final boolean printSummaries, final boolean isDouble) {
long cumN;
int numLevels = 0;
@@ -81,52 +86,56 @@ class KllHelper {
System.out.printf("%6d%,12d%8d%,16d\n", level, 1 << level, levelCap, maxNAtLevel);
}
}
- final int bytes = getCompactSerializedSizeBytes(numLevels, cumCap, isDouble);
+ final int compactBytes = getCompactSerializedSizeBytes(numLevels, cumCap, isDouble);
+ final int updatableBytes = getUpdatableSerializedSizeBytes(k, m, numLevels, isDouble);
if (printDetail) {
System.out.printf(" TOTALS%10s %8d%,16d\n", "", cumCap, cumN);
- System.out.println(" TOTAL BYTES: " + bytes);
+ System.out.println(" COMPACT BYTES: " + compactBytes);
+ System.out.println(" UPDATABLE BYTES: " + updatableBytes);
System.out.println("");
}
- final LevelStats lvlStats = new LevelStats(cumN, bytes, numLevels, cumCap);
+ final LevelStats lvlStats = new LevelStats(cumN, numLevels, cumCap, compactBytes, updatableBytes);
if (printSummary) { System.out.println(lvlStats.toString()); }
return lvlStats;
}
- public static class LevelStats {
+ static class LevelStats {
private long maxN;
- private int bytes;
+ private int compactBytes;
+ private int updatableBytes;
private int numLevels;
private int maxCap;
- LevelStats(final long maxN, final int bytes, final int numLevels, final int maxCap) {
+ LevelStats(final long maxN, final int numLevels, final int maxCap, final int compactBytes,
+ final int updatableBytes) {
this.maxN = maxN;
- this.bytes = bytes;
this.numLevels = numLevels;
this.maxCap = maxCap;
+ this.compactBytes = compactBytes;
+ this.updatableBytes = updatableBytes;
+
}
@Override
public String toString() {
+ final String[] hdr = {"NumLevels", "MaxCap", "MaxN", "TotCompactBytes", "TotUpdatableBytes"};
final StringBuilder sb = new StringBuilder();
sb.append("Level Stats Summary:" + LS);
- sb.append(" NumLevels: " + numLevels + LS);
- sb.append(" MaxCap : " + maxCap + LS);
- sb.append(" MaxN : " + maxN + LS);
- sb.append(" TotBytes : " + bytes + LS + LS);
+ sb.append(String.format("%10s %10s %14s %17s %17s" + LS, (Object[]) hdr));
+ sb.append(String.format("%10d %10d %14d %17d %17d" + LS, numLevels, maxCap, maxN, compactBytes, updatableBytes));
return sb.toString();
}
public long getMaxN() { return maxN; }
- public int getBytes() { return bytes; }
+ public int getCompactBytes() { return compactBytes; }
public int getNumLevels() { return numLevels; }
public int getMaxCap() { return maxCap; }
}
- static int getCompactSerializedSizeBytes(final int numLevels, final int numRetained,
- final boolean isDouble) {
+ static int getCompactSerializedSizeBytes(final int numLevels, final int numRetained, final boolean isDouble) {
if (numLevels == 1 && numRetained == 1) {
return DATA_START_ADR_SINGLE_ITEM + (isDouble ? Double.BYTES : Float.BYTES);
}
@@ -139,6 +148,18 @@ class KllHelper {
}
}
+ static int getUpdatableSerializedSizeBytes(final int k, final int m, final int numLevels, final boolean isDouble) {
+ //There are no special accommodations for empty or single item.
+ //The last integer in levels IS serialized.
+ // The + 2 is for min and max
+ final int totCap = computeTotalItemCapacity(k, m, numLevels) + 2;
+ if (isDouble) {
+ return DATA_START_ADR_DOUBLE + (numLevels + 1) * Integer.BYTES + totCap * Double.BYTES;
+ } else {
+ return DATA_START_ADR_FLOAT + (numLevels + 1) * Integer.BYTES + totCap * Float.BYTES;
+ }
+ }
+
/**
* Returns the maximum number of items that this sketch can handle
* @param k The sizing / accuracy parameter of the sketch in items.
@@ -225,5 +246,68 @@ class KllHelper {
return total;
}
+ /**
+ * Gets the normalized rank error given k and pmf.
+ * Static method version of the <i>getNormalizedRankError(boolean)</i>.
+ * @param k the configuration parameter
+ * @param pmf if true, returns the "double-sided" normalized rank error for the getPMF() function.
+ * Otherwise, it is the "single-sided" normalized rank error for all the other queries.
+ * @return if pmf is true, the normalized rank error for the getPMF() function.
+ * Otherwise, it is the "single-sided" normalized rank error for all the other queries.
+ * @see KllDoublesSketch
+ */
+ // constants were derived as the best fit to 99 percentile empirically measured max error in
+ // thousands of trials
+ static double getNormalizedRankError(final int k, final boolean pmf) {
+ return pmf
+ ? 2.446 / pow(k, 0.9433)
+ : 2.296 / pow(k, 0.9723);
+ }
+
+ /**
+ * Checks the validity of the given value k
+ * @param k must be greater than 7 and less than 65536.
+ */
+ static void checkK(final int k) {
+ if (k < MIN_K || k > MAX_K) {
+ throw new SketchesArgumentException(
+ "K must be >= " + MIN_K + " and <= " + MAX_K + ": " + k);
+ }
+ }
+
+ /**
+ * Finds the first level starting with level 0 that exceeds its nominal capacity
+ * @param k configured size of sketch. Range [m, 2^16]
+ * @param m minimum level size. Default is 8.
+ * @param numLevels one-based number of current levels
+ * @return level to compact
+ */
+ static int findLevelToCompact(final int k, final int m, final int numLevels, final int[] levels) {
+ int level = 0;
+ while (true) {
+ assert level < numLevels;
+ final int pop = levels[level + 1] - levels[level];
+ final int cap = KllHelper.levelCapacity(k, numLevels, level, m);
+ if (pop >= cap) {
+ return level;
+ }
+ level++;
+ }
+ }
+
+ static int currentLevelSize(final int level, final int numLevels, final int[] levels) {
+ if (level >= numLevels) { return 0; }
+ return levels[level + 1] - levels[level];
+ }
+
+ static int getNumRetained(final int numLevels, final int[] levels) {
+ return levels[numLevels] - levels[0];
+ }
+
+ static int getNumRetainedAboveLevelZero(final int numLevels, final int[] levels) {
+ return levels[numLevels] - levels[1];
+ }
+
+
}
diff --git a/src/main/java/org/apache/datasketches/kll/PreambleUtil.java b/src/main/java/org/apache/datasketches/kll/PreambleUtil.java
index c2211db..3d9314b 100644
--- a/src/main/java/org/apache/datasketches/kll/PreambleUtil.java
+++ b/src/main/java/org/apache/datasketches/kll/PreambleUtil.java
@@ -133,7 +133,7 @@ final class PreambleUtil {
static final int LEVEL_ZERO_SORTED_BIT_MASK = 2;
static final int SINGLE_ITEM_BIT_MASK = 4;
static final int DOUBLES_SKETCH_BIT_MASK = 8;
- static final int NOT_COMPACT_BIT_MASK = 16;
+ static final int UPDATABLE_BIT_MASK = 16;
enum Layout {
FLOAT_FULL_COMPACT, FLOAT_EMPTY_COMPACT, FLOAT_SINGLE_COMPACT,
@@ -141,8 +141,6 @@ final class PreambleUtil {
FLOAT_FULL_NOT_COMPACT, FLOAT_EMPTY_NOT_COMPACT, FLOAT_SINGLE_NOT_COMPACT,
DOUBLE_FULL_NOT_COMPACT, DOUBLE_EMPTY_NOT_COMPACT, DOUBLE_SINGLE_NOT_COMPACT }
- static Layout layout;
-
/**
* Returns a human readable string summary of the internal state of the given byte array.
* Used primarily in testing.
@@ -167,144 +165,170 @@ final class PreambleUtil {
}
- @SuppressWarnings("unused")
- private static String memoryToString(final Memory srcMem) {
- final int preInts = extractPreInts(srcMem);
- final int serVer = extractSerVer(srcMem);
- final int familyID = extractFamilyID(srcMem);
- final String famName = idToFamily(familyID).toString();
- final int flags = extractFlags(srcMem);
- final boolean empty = (flags & EMPTY_BIT_MASK) > 0;
- final boolean level0Sorted = (flags & LEVEL_ZERO_SORTED_BIT_MASK) > 0;
- final boolean singleItem = (flags & SINGLE_ITEM_BIT_MASK) > 0;
- final boolean doublesSketch = (flags & DOUBLES_SKETCH_BIT_MASK) > 0;
- final boolean notCompact = (flags & NOT_COMPACT_BIT_MASK) > 0;
- final int k = extractK(srcMem);
- final int m = extractM(srcMem);
- long n = 0;
- final int minK;
- final int numLevels;
-
- //preamble checks
- if (familyID != Family.KLL.getID()) { throwCustom(0, familyID); }
- final int checkFlags = (empty ? 1 : 0) | (singleItem ? 4 : 0) | (doublesSketch ? 8 : 0);
- if ((checkFlags & 5) == 5) { throwCustom(20, flags); }
- switch (checkFlags) {
- case 0: { //not empty, not single item, float full
- if (preInts != PREAMBLE_INTS_FLOAT) { throwCustom(6, preInts); }
- if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
- layout = notCompact ? Layout.FLOAT_FULL_NOT_COMPACT : Layout.FLOAT_FULL_COMPACT;
- n = extractN(srcMem);
- minK = extractMinK(srcMem);
- numLevels = extractNumLevels(srcMem);
- break;
- }
- case 1: { //empty, not single item, float empty
- if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
- if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
- if (notCompact) {
- layout = Layout.FLOAT_EMPTY_NOT_COMPACT;
+
+
+
+
+ static class MemoryCheck {
+ final int preInts; // = extractPreInts(srcMem);
+ final int serVer;
+ final int familyID;
+ final String famName;
+ final int flags;
+ final boolean empty;
+ final boolean level0Sorted;
+ final boolean singleItem;
+ final boolean doublesSketch;
+ final boolean updatable;
+ final int k;
+ final int m;
+ long n;
+ int minK;
+ int dataStart;
+ int numLevels;
+ int[] levels;
+ Layout layout;
+
+ MemoryCheck(final Memory srcMem) {
+ preInts = extractPreInts(srcMem);
+ serVer = extractSerVer(srcMem);
+ familyID = extractFamilyID(srcMem);
+ flags = extractFlags(srcMem);
+ empty = (flags & EMPTY_BIT_MASK) > 0;
+ level0Sorted = (flags & LEVEL_ZERO_SORTED_BIT_MASK) > 0;
+ singleItem = (flags & SINGLE_ITEM_BIT_MASK) > 0;
+ doublesSketch = (flags & DOUBLES_SKETCH_BIT_MASK) > 0;
+ updatable = (flags & UPDATABLE_BIT_MASK) > 0;
+ k = extractK(srcMem);
+ m = extractM(srcMem);
+
+ KllHelper.checkK(k);
+ if (m != 8) { System.err.println("WARNING: Minimum Level width set to non-default value: " + m); }
+ if (familyID != Family.KLL.getID()) { throwCustom(0, familyID); }
+ famName = idToFamily(familyID).toString();
+ if (famName != "KLL") { throwCustom(23, 0); }
+
+ final int checkFlags = (empty ? 1 : 0) | (singleItem ? 4 : 0) | (doublesSketch ? 8 : 0);
+ if ((checkFlags & 5) == 5) { throwCustom(20, flags); }
+
+ switch (checkFlags) {
+ case 0: { //not empty, not single item, float full
+ if (preInts != PREAMBLE_INTS_FLOAT) { throwCustom(6, preInts); }
+ if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
+ layout = updatable ? Layout.FLOAT_FULL_NOT_COMPACT : Layout.FLOAT_FULL_COMPACT;
n = extractN(srcMem);
- if (n != 0) { throwCustom(21, (int) n); }
minK = extractMinK(srcMem);
numLevels = extractNumLevels(srcMem);
- } else {
- layout = Layout.FLOAT_EMPTY_COMPACT;
- n = 0;
- minK = k;
- numLevels = 1;
+ dataStart = DATA_START_ADR_FLOAT;
+ break;
}
- break;
- }
- case 4: { //not empty, single item, float single item
- if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
- if (serVer != SERIAL_VERSION_SINGLE) { throwCustom(4, serVer); }
- if (notCompact) {
- layout = Layout.FLOAT_SINGLE_NOT_COMPACT;
- n = extractN(srcMem);
- if (n != 1) { throwCustom(22, (int)n); }
- minK = extractMinK(srcMem);
- numLevels = extractNumLevels(srcMem);
- } else {
- layout = Layout.FLOAT_SINGLE_COMPACT;
- n = 1;
- minK = k;
- numLevels = 1;
+ case 1: { //empty, not single item, float empty
+ if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
+ if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
+ if (updatable) {
+ layout = Layout.FLOAT_EMPTY_NOT_COMPACT;
+ n = extractN(srcMem);
+ if (n != 0) { throwCustom(21, (int) n); }
+ minK = extractMinK(srcMem);
+ numLevels = extractNumLevels(srcMem);
+ dataStart = DATA_START_ADR_FLOAT;
+ } else {
+ layout = Layout.FLOAT_EMPTY_COMPACT;
+ n = 0;
+ minK = k;
+ numLevels = 1;
+ dataStart = DATA_START_ADR_SINGLE_ITEM; //ignore if empty
+ }
+ break;
}
- break;
- }
- case 8: { //not empty, not single item, double full
- if (preInts != PREAMBLE_INTS_DOUBLE) { throwCustom(5, preInts); }
- if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
- layout = notCompact ? Layout.DOUBLE_FULL_NOT_COMPACT : Layout.DOUBLE_FULL_COMPACT;
- n = extractN(srcMem);
- minK = extractMinK(srcMem);
- numLevels = extractNumLevels(srcMem);
- break;
- }
- case 9: { //empty, not single item, double empty
- if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
- if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
- if (notCompact) {
- layout = Layout.DOUBLE_EMPTY_NOT_COMPACT;
- n = extractN(srcMem);
- if (n != 0) { throwCustom(21, (int) n); }
- minK = extractMinK(srcMem);
- numLevels = extractNumLevels(srcMem);
- } else {
- layout = Layout.DOUBLE_EMPTY_COMPACT;
- n = 0;
- minK = k;
- numLevels = 1;
+ case 4: { //not empty, single item, float single item
+ if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
+ if (serVer != SERIAL_VERSION_SINGLE) { throwCustom(4, serVer); }
+ if (updatable) {
+ layout = Layout.FLOAT_SINGLE_NOT_COMPACT;
+ n = extractN(srcMem);
+ if (n != 1) { throwCustom(22, (int)n); }
+ minK = extractMinK(srcMem);
+ numLevels = extractNumLevels(srcMem);
+ dataStart = DATA_START_ADR_FLOAT;
+ } else {
+ layout = Layout.FLOAT_SINGLE_COMPACT;
+ n = 1;
+ minK = k;
+ numLevels = 1;
+ dataStart = DATA_START_ADR_SINGLE_ITEM;
+ }
+ break;
}
- break;
- }
- case 12: { //not empty, single item, double single item
- if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
- if (serVer != SERIAL_VERSION_SINGLE) { throwCustom(4, serVer); }
- if (notCompact) {
- layout = Layout.DOUBLE_SINGLE_NOT_COMPACT;
+ case 8: { //not empty, not single item, double full
+ if (preInts != PREAMBLE_INTS_DOUBLE) { throwCustom(5, preInts); }
+ if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
+ layout = updatable ? Layout.DOUBLE_FULL_NOT_COMPACT : Layout.DOUBLE_FULL_COMPACT;
n = extractN(srcMem);
- if (n != 1) { throwCustom(22, (int)n); }
minK = extractMinK(srcMem);
numLevels = extractNumLevels(srcMem);
- } else {
- layout = Layout.DOUBLE_SINGLE_COMPACT;
- n = 1;
- minK = k;
- numLevels = 1;
+ dataStart = DATA_START_ADR_DOUBLE;
+ break;
+ }
+ case 9: { //empty, not single item, double empty
+ if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
+ if (serVer != SERIAL_VERSION_EMPTY_FULL) { throwCustom(2, serVer); }
+ if (updatable) {
+ layout = Layout.DOUBLE_EMPTY_NOT_COMPACT;
+ n = extractN(srcMem);
+ if (n != 0) { throwCustom(21, (int) n); }
+ minK = extractMinK(srcMem);
+ numLevels = extractNumLevels(srcMem);
+ dataStart = DATA_START_ADR_DOUBLE;
+ } else {
+ layout = Layout.DOUBLE_EMPTY_COMPACT;
+ n = 0;
+ minK = k;
+ numLevels = 1;
+ dataStart = DATA_START_ADR_SINGLE_ITEM; //ignore if empty
+ }
+ break;
+ }
+ case 12: { //not empty, single item, double single item
+ if (preInts != PREAMBLE_INTS_EMPTY_SINGLE) { throwCustom(1, preInts); }
+ if (serVer != SERIAL_VERSION_SINGLE) { throwCustom(4, serVer); }
+ if (updatable) {
+ layout = Layout.DOUBLE_SINGLE_NOT_COMPACT;
+ n = extractN(srcMem);
+ if (n != 1) { throwCustom(22, (int)n); }
+ minK = extractMinK(srcMem);
+ numLevels = extractNumLevels(srcMem);
+ dataStart = DATA_START_ADR_DOUBLE;
+ } else {
+ layout = Layout.DOUBLE_SINGLE_COMPACT;
+ n = 1;
+ minK = k;
+ numLevels = 1;
+ dataStart = DATA_START_ADR_SINGLE_ITEM;
+ }
+ break;
}
- break;
}
}
- BaseKllSketch.checkK(k);
-
- if (m != 8) {
- System.err.println("WARNING: Minimum Level width set to non-default value: " + m);
+ private static void throwCustom(final int errNo, final int value) {
+ String msg = "";
+ switch (errNo) {
+ case 0: msg = "FamilyID Field must be: " + Family.KLL.getID() + ", NOT: " + value; break;
+ case 1: msg = "Empty Bit: 1 -> PreInts: " + PREAMBLE_INTS_EMPTY_SINGLE + ", NOT: " + value; break;
+ case 2: msg = "Empty Bit: 1 -> SerVer: " + SERIAL_VERSION_EMPTY_FULL + ", NOT: " + value; break;
+ case 3: msg = "Single Item Bit: 1 -> PreInts: " + PREAMBLE_INTS_EMPTY_SINGLE + ", NOT: " + value; break;
+ case 4: msg = "Single Item Bit: 1 -> SerVer: " + SERIAL_VERSION_SINGLE + ", NOT: " + value; break;
+ case 5: msg = "Double Sketch Bit: 1 -> PreInts: " + PREAMBLE_INTS_DOUBLE + ", NOT: " + value; break;
+ case 6: msg = "Double Sketch Bit: 0 -> PreInts: " + PREAMBLE_INTS_FLOAT + ", NOT: " + value; break;
+ case 20: msg = "Empty flag bit and SingleItem flag bit cannot both be set. Flags: " + value; break;
+ case 21: msg = "N != 0 and empty bit is set. N: " + value; break;
+ case 22: msg = "N != 1 and single item bit is set. N: " + value; break;
+ case 23: msg = "Family name is not KLL"; break;
+ }
+ throw new SketchesArgumentException(msg);
}
-
-
- return null;
- }
-
-private static void throwCustom(final int errNo, final int value) {
- String msg = "";
- switch (errNo) {
- case 0: msg = "FamilyID Field must be: " + Family.KLL.getID() + ", NOT: " + value; break;
- case 1: msg = "Empty Bit: 1 -> PreInts: " + PREAMBLE_INTS_EMPTY_SINGLE + ", NOT: " + value; break;
- case 2: msg = "Empty Bit: 1 -> SerVer: " + SERIAL_VERSION_EMPTY_FULL + ", NOT: " + value; break;
- case 3: msg = "Single Item Bit: 1 -> PreInts: " + PREAMBLE_INTS_EMPTY_SINGLE + ", NOT: " + value; break;
- case 4: msg = "Single Item Bit: 1 -> SerVer: " + SERIAL_VERSION_SINGLE + ", NOT: " + value; break;
- case 5: msg = "Double Sketch Bit: 1 -> PreInts: " + PREAMBLE_INTS_DOUBLE + ", NOT: " + value; break;
- case 6: msg = "Double Sketch Bit: 0 -> PreInts: " + PREAMBLE_INTS_FLOAT + ", NOT: " + value; break;
- case 20: msg = "Empty flag bit and SingleItem flag bit cannot both be set. Flags: " + value; break;
- case 21: msg = "N != 0 and empty bit is set. N: " + value; break;
- case 22: msg = "N != 1 and single item bit is set. N: " + value; break;
-
}
- throw new SketchesArgumentException(msg);
-}
static int extractPreInts(final Memory mem) {
return mem.getByte(PREAMBLE_INTS_BYTE_ADR) & 0XFF;
diff --git a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
index 860e175..f210242 100644
--- a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
@@ -268,13 +268,13 @@ public class KllDoublesSketchTest {
@Test
public void mergeMinAndMaxFromOther() {
final KllDoublesSketch sketch1 = new KllDoublesSketch();
- for (int i = 0; i < 1000000; i++) {
+ for (int i = 1; i <= 1_000_000; i++) {
sketch1.update(i);
}
final KllDoublesSketch sketch2 = new KllDoublesSketch();
sketch2.merge(sketch1);
- assertEquals(sketch2.getMinValue(), 0F);
- assertEquals(sketch2.getMaxValue(), 999999F);
+ assertEquals(sketch2.getMinValue(), 1F);
+ assertEquals(sketch2.getMaxValue(), 1_000_000F);
}
@SuppressWarnings("unused")
diff --git a/src/test/java/org/apache/datasketches/kll/KllDoublesValidationTest.java b/src/test/java/org/apache/datasketches/kll/KllDoublesValidationTest.java
index ec1087d..32c5ebb 100644
--- a/src/test/java/org/apache/datasketches/kll/KllDoublesValidationTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllDoublesValidationTest.java
@@ -215,9 +215,9 @@ public class KllDoublesValidationTest {
for (int i = 0; i < n; i++) {
sketch.update(inputArray[i]);
}
- int numLevels = sketch.getNumLevels();
+ int numLevels = sketch.numLevels_;
int numSamples = sketch.getNumRetained();
- int[] levels = sketch.getLevels();
+ int[] levels = sketch.levels_;
long hashedSamples = simpleHashOfSubArray(sketch.getItems(), levels[0], numSamples);
System.out.print(testI);
assert correctResultsWithReset[(7 * testI) + 4] == numLevels;
diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
index fa1fd7b..6c9b485 100644
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
@@ -268,13 +268,13 @@ public class KllFloatsSketchTest {
@Test
public void mergeMinAndMaxFromOther() {
final KllFloatsSketch sketch1 = new KllFloatsSketch();
- for (int i = 0; i < 1000000; i++) {
+ for (int i = 1; i <= 1_000_000; i++) {
sketch1.update(i);
}
- final KllFloatsSketch sketch2 = new KllFloatsSketch();
+ final KllFloatsSketch sketch2 = new KllFloatsSketch(10);
sketch2.merge(sketch1);
- assertEquals(sketch2.getMinValue(), 0F);
- assertEquals(sketch2.getMaxValue(), 999999F);
+ assertEquals(sketch2.getMinValue(), 1F);
+ assertEquals(sketch2.getMaxValue(), 1_000_000F);
}
@SuppressWarnings("unused")
diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsValidationTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsValidationTest.java
index 71de641..2b57766 100644
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsValidationTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsValidationTest.java
@@ -216,9 +216,9 @@ public class KllFloatsValidationTest {
for (int i = 0; i < n; i++) {
sketch.update(inputArray[i]);
}
- int numLevels = sketch.getNumLevels();
+ int numLevels = sketch.numLevels_;
int numSamples = sketch.getNumRetained();
- int[] levels = sketch.getLevels();
+ int[] levels = sketch.levels_;
long hashedSamples = simpleHashOfSubArray(sketch.getItems(), levels[0], numSamples);
System.out.print(testI);
assert correctResultsWithReset[(7 * testI) + 4] == numLevels;
diff --git a/src/test/java/org/apache/datasketches/kll/KllHelperTest.java b/src/test/java/org/apache/datasketches/kll/KllHelperTest.java
new file mode 100644
index 0000000..4e56f86
--- /dev/null
+++ b/src/test/java/org/apache/datasketches/kll/KllHelperTest.java
@@ -0,0 +1,48 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.datasketches.kll;
+
+import static org.apache.datasketches.kll.KllHelper.getAllLevelStatsGivenN;
+import static org.apache.datasketches.kll.KllHelper.getLevelStats;
+import static org.testng.Assert.assertEquals;
+
+import org.apache.datasketches.kll.KllHelper.LevelStats;
+import org.testng.annotations.Test;
+
+public class KllHelperTest {
+
+ @Test //convert two false below to true for visual checking
+ public void testGetAllLevelStats() {
+ long n = 1L << 30;
+ int k = 200;
+ int m = 8;
+ LevelStats lvlStats = getAllLevelStatsGivenN(k, m, n, false, false, true);
+ assertEquals(lvlStats.getCompactBytes(), 5708);
+ }
+
+ @Test //convert two false below to true for visual checking
+ public void getStatsAtNumLevels() {
+ int k = 200;
+ int m = 8;
+ int numLevels = 23;
+ LevelStats lvlStats = getLevelStats(k, m, numLevels, false, false, true);
+ assertEquals(lvlStats.getCompactBytes(), 5708);
+ }
+}
diff --git a/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java b/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
index a02d728..17e4e3d 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
+++ b/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
@@ -19,8 +19,6 @@
package org.apache.datasketches.kll;
-import static org.apache.datasketches.kll.KllHelper.getAllLevelStatsGivenN;
-import static org.apache.datasketches.kll.KllHelper.getLevelStats;
import static org.apache.datasketches.kll.PreambleUtil.DEFAULT_K;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertTrue;
@@ -28,7 +26,6 @@ import static org.testng.Assert.assertTrue;
import java.util.Objects;
import org.apache.datasketches.SketchesArgumentException;
-import org.apache.datasketches.kll.KllHelper.LevelStats;
import org.apache.datasketches.memory.WritableMemory;
import org.testng.annotations.Test;
@@ -42,8 +39,8 @@ public class MiscDoublesTest {
@Test
public void checkGetKFromEps() {
final int k = DEFAULT_K;
- final double eps = BaseKllSketch.getNormalizedRankError(k, false);
- final double epsPmf = BaseKllSketch.getNormalizedRankError(k, true);
+ final double eps = KllHelper.getNormalizedRankError(k, false);
+ final double epsPmf = KllHelper.getNormalizedRankError(k, true);
final int kEps = BaseKllSketch.getKFromEpsilon(eps, false);
final int kEpsPmf = BaseKllSketch.getKFromEpsilon(epsPmf, true);
assertEquals(kEps, k);
@@ -67,11 +64,11 @@ public class MiscDoublesTest {
println("LB : " + lb);
}
- @Test(expectedExceptions = SketchesArgumentException.class)
+ @Test
public void checkHeapifyExceptions1() {
KllDoublesSketch sk = new KllDoublesSketch();
WritableMemory wmem = WritableMemory.writableWrap(sk.toByteArray());
- wmem.putByte(6, (byte)4); //corrupt M
+ wmem.putByte(6, (byte)4); //use different M: produces a warning
KllDoublesSketch.heapify(wmem);
}
@@ -119,9 +116,9 @@ public class MiscDoublesTest {
sk.toByteArray();
final double[] items = sk.getItems();
assertEquals(items.length, 16);
- final int[] levels = sk.getLevels();
+ final int[] levels = sk.levels_;
assertEquals(levels.length, 3);
- assertEquals(sk.getNumLevels(), 2);
+ assertEquals(sk.numLevels_, 2);
}
@Test //enable static println(..) for visual checking
@@ -139,24 +136,6 @@ public class MiscDoublesTest {
println(LS + s2);
}
- @Test //convert false to true below for visual checking
- public void testGetAllLevelStats() {
- long n = 1L << 30;
- int k = 200;
- int m = 8;
- LevelStats lvlStats = getAllLevelStatsGivenN(k, m, n, false, false, true);
- assertEquals(lvlStats.getBytes(), 5708);
- }
-
- @Test //convert false to true below for visual checking
- public void getStatsAtNumLevels() {
- int k = 200;
- int m = 8;
- int numLevels = 23;
- LevelStats lvlStats = getLevelStats(k, m, numLevels, false, false, true);
- assertEquals(lvlStats.getBytes(), 5708);
- }
-
@Test
public void printlnTest() {
println("PRINTING: " + this.getClass().getName());
diff --git a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
index 92b54a3..77d5a5a 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
@@ -19,8 +19,6 @@
package org.apache.datasketches.kll;
-import static org.apache.datasketches.kll.KllHelper.getLevelStats;
-import static org.apache.datasketches.kll.KllHelper.getAllLevelStatsGivenN;
import static org.apache.datasketches.kll.PreambleUtil.DEFAULT_K;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertTrue;
@@ -28,7 +26,6 @@ import static org.testng.Assert.assertTrue;
import java.util.Objects;
import org.apache.datasketches.SketchesArgumentException;
-import org.apache.datasketches.kll.KllHelper.LevelStats;
import org.apache.datasketches.memory.WritableMemory;
import org.testng.annotations.Test;
@@ -42,8 +39,8 @@ public class MiscFloatsTest {
@Test
public void checkGetKFromEps() {
final int k = DEFAULT_K;
- final double eps = BaseKllSketch.getNormalizedRankError(k, false);
- final double epsPmf = BaseKllSketch.getNormalizedRankError(k, true);
+ final double eps = KllHelper.getNormalizedRankError(k, false);
+ final double epsPmf = KllHelper.getNormalizedRankError(k, true);
final int kEps = BaseKllSketch.getKFromEpsilon(eps, false);
final int kEpsPmf = BaseKllSketch.getKFromEpsilon(epsPmf, true);
assertEquals(kEps, k);
@@ -67,11 +64,11 @@ public class MiscFloatsTest {
println("LB : " + lb);
}
- @Test(expectedExceptions = SketchesArgumentException.class)
+ @Test
public void checkHeapifyExceptions1() {
KllFloatsSketch sk = new KllFloatsSketch();
WritableMemory wmem = WritableMemory.writableWrap(sk.toByteArray());
- wmem.putByte(6, (byte)4); //corrupt M
+ wmem.putByte(6, (byte)4); //use different M: produces a warning
KllFloatsSketch.heapify(wmem);
}
@@ -119,9 +116,9 @@ public class MiscFloatsTest {
sk.toByteArray();
final float[] items = sk.getItems();
assertEquals(items.length, 16);
- final int[] levels = sk.getLevels();
+ final int[] levels = sk.levels_;
assertEquals(levels.length, 3);
- assertEquals(sk.getNumLevels(), 2);
+ assertEquals(sk.numLevels_, 2);
}
@Test //enable static println(..) for visual checking
@@ -139,24 +136,6 @@ public class MiscFloatsTest {
println(LS + s2);
}
- @Test //convert false to true below for visual checking
- public void testGetAllLevelStats() {
- long n = 1L << 30;
- int k = 200;
- int m = 8;
- LevelStats lvlStats = getAllLevelStatsGivenN(k, m, n, false, false, false);
- assertEquals(lvlStats.getBytes(), 2908);
- }
-
- @Test //convert false to true below for visual checking
- public void getStatsAtNumLevels() {
- int k = 200;
- int m = 8;
- int numLevels = 23;
- LevelStats lvlStats = getLevelStats(k, m, numLevels, false, false, false);
- assertEquals(lvlStats.getBytes(), 2908);
- }
-
@Test
public void printlnTest() {
println("PRINTING: " + this.getClass().getName());
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org