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:03 UTC
[datasketches-java] 01/12: Interim 1
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 45b36816ea3fa779e3c67ba53c698b1c98c50ec4
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Feb 28 17:00:41 2022 -0800
Interim 1
---
.../org/apache/datasketches/kll/BaseKllSketch.java | 94 +----
.../apache/datasketches/kll/KllDoublesHelper.java | 1 +
.../apache/datasketches/kll/KllDoublesSketch.java | 138 ++++---
.../apache/datasketches/kll/KllFloatsHelper.java | 1 +
.../apache/datasketches/kll/KllFloatsSketch.java | 132 ++++---
.../org/apache/datasketches/kll/KllHelper.java | 94 ++++-
.../org/apache/datasketches/kll/PreambleUtil.java | 409 +++++++++++++++++++++
.../datasketches/quantiles/PreambleUtil.java | 18 +-
.../datasketches/kll/KllDoublesSketchTest.java | 42 ++-
.../datasketches/kll/KllFloatsSketchTest.java | 31 +-
.../apache/datasketches/kll/MiscDoublesTest.java | 32 +-
.../apache/datasketches/kll/MiscFloatsTest.java | 38 +-
12 files changed, 783 insertions(+), 247 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java b/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
index be2335f..4a019b5 100644
--- a/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
@@ -27,6 +27,8 @@ 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;
@@ -34,89 +36,12 @@ import org.apache.datasketches.SketchesArgumentException;
abstract class BaseKllSketch {
- /* Serialized float sketch layout, more than one item:
- * Adr:
- * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
- * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
- * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
- * 1 ||---------------------------------N_LONG---------------------------------------|
- * || 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
- * 2 ||<--------------data----------------| unused |numLevels|-------min K-----------|
- *
- *
- *
- * Serialized float sketch layout, Empty and Single Item:
- * Adr:
- * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
- * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
- * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
- * 1 || |-------------------data-------------------|
- */
-
- /* Serialized double sketch layout, more than one item:
- * Adr:
- * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
- * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
- * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
- * 1 ||---------------------------------N_LONG---------------------------------------|
- * || 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
- * 2 ||<-------------unused------------------------|numLevels|-------min K-----------|
- * || | 24 |
- * 3 ||<---------------------------------data----------------------------------------|
- *
- * Serialized double sketch layout, Empty and Single Item:
- * Adr:
- * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
- * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
- * || | 8 |
- * 1 ||----------------------------------data----------------------------------------|
- */
-
- /**
- * The default value of K.
- */
- public static final int DEFAULT_K = 200;
- static final int DEFAULT_M = 8;
- static final int MIN_K = DEFAULT_M;
- static final int MAX_K = (1 << 16) - 1; // serialized as an unsigned short
-
- // Preamble byte addresses
- static final int PREAMBLE_INTS_BYTE = 0;
- static final int SER_VER_BYTE = 1;
- static final int FAMILY_BYTE = 2;
- static final int FLAGS_BYTE = 3;
- static final int K_SHORT = 4; // to 5
- static final int M_BYTE = 6;
- // 7 is reserved for future use
- // SINGLE ITEM ONLY
- static final int DATA_START_SINGLE_ITEM = 8;
-
- // MULTI-ITEM
- static final int N_LONG = 8; // to 15
- static final int MIN_K_SHORT = 16; // to 17
- static final int NUM_LEVELS_BYTE = 18;
-
- // FLOAT SKETCH 19 is reserved for future use in float sketch
- static final int DATA_START_FLOAT = 20; // float sketch, not single item
-
- // DOUBLE SKETCH 19 to 23 is reserved for future use in double sketch
- static final int DATA_START_DOUBLE = 24; // double sketch, not single item
-
- // Other static values
- static final byte SERIAL_VERSION = 1;
- static final byte SERIAL_VERSION_SINGLE = 2; // only used to specify the single-item format
- static final int PREAMBLE_INTS_EMPTY_SINGLE = 2; // for empty and single item
- static final int PREAMBLE_INTS_FLOAT = 5; // not empty or single item
- static final int PREAMBLE_INTS_DOUBLE = 6; // not empty or single item
-
- enum Flags { IS_EMPTY, IS_LEVEL_ZERO_SORTED, IS_SINGLE_ITEM }
-
/*
* Data is stored in items_.
* The data for level i lies in positions levels_[i] through levels_[i + 1] - 1 inclusive.
- * Hence levels_ must contain (numLevels_ + 1) indices.
- * The valid portion of items_ is completely packed, except for level 0.
- * Level 0 is filled from the top down.
+ * Hence, levels_ must contain (numLevels_ + 1) indices.
+ * The valid portion of items_ is completely packed, except for level 0,
+ * which is filled from the top down.
*
* Invariants:
* 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
@@ -124,8 +49,8 @@ abstract class BaseKllSketch {
* so there is room for least 1 more item in level zero.
* 3) There are no gaps except at the bottom, so if levels_[0] = 0,
* the sketch is exactly filled to capacity and must be compacted.
- * 4) Sum of weights of retained items == N.
- * 5) curTotalCap == items_.length == levels_[numLevels_].
+ * 4) Sum of weights of all retained items == N.
+ * 5) curTotalCap = items_.length = levels_[numLevels_].
*/
final int k_; // configured value of K
@@ -137,13 +62,14 @@ abstract class BaseKllSketch {
int[] levels_; // array of index offsets into the items[]. Size = numLevels + 1.
boolean isLevelZeroSorted_;
- final boolean compatible; //compatible with quantiles sketch
+ final boolean compatible; //compatible with quantiles sketch treatment of rank 0.0 and 1.0.
static final Random random = new Random();
/**
* Heap constructor.
* @param k configured size of sketch. Range [m, 2^16]
* @param m minimum level size. Default is 8.
+ * @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);
@@ -278,7 +204,7 @@ abstract class BaseKllSketch {
* Checks the validity of the given value k
* @param k must be greater than 7 and less than 65536.
*/
- private static void checkK(final int k) {
+ 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);
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index 9b73855..125419e 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -112,6 +112,7 @@ class KllDoublesHelper {
* @param outBuf the same array as inBuf
* @param outLevels the same size as inLevels
* @param isLevelZeroSorted true if this.level 0 is sorted
+ * @param random instance of java.util.Random
* @return int array of: {numLevels, targetItemCount, currentItemCount)
*/
static int[] generalDoublesCompress(
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index 1503ddb..a0d4a6c 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -22,12 +22,34 @@ package org.apache.datasketches.kll;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static org.apache.datasketches.Util.isOdd;
+import static org.apache.datasketches.kll.KllHelper.getAllLevelStatsGivenN;
+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.EMPTY_BIT_MASK;
+import static org.apache.datasketches.kll.PreambleUtil.FAMILY_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.FLAGS_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.K_SHORT_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.LEVEL_ZERO_SORTED_BIT_MASK;
+import static org.apache.datasketches.kll.PreambleUtil.MIN_K_SHORT_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.M_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.NUM_LEVELS_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.N_LONG_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.PREAMBLE_INTS_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.PREAMBLE_INTS_DOUBLE;
+import static org.apache.datasketches.kll.PreambleUtil.PREAMBLE_INTS_EMPTY_SINGLE;
+import static org.apache.datasketches.kll.PreambleUtil.SERIAL_VERSION_EMPTY_FULL;
+import static org.apache.datasketches.kll.PreambleUtil.SERIAL_VERSION_SINGLE;
+import static org.apache.datasketches.kll.PreambleUtil.SER_VER_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.SINGLE_ITEM_BIT_MASK;
import java.util.Arrays;
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.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
@@ -62,7 +84,7 @@ public class KllDoublesSketch extends BaseKllSketch {
/**
* Used for testing only.
* @param k configured size of sketch. Range [m, 2^16]
- * @param compatible if true, compatible with quantiles sketch.
+ * @param compatible if true, compatible with quantiles sketch treatment of rank 0.0 and 1.0.
*/
KllDoublesSketch(final int k, final boolean compatible) {
this(k, DEFAULT_M, compatible);
@@ -72,6 +94,7 @@ public class KllDoublesSketch extends BaseKllSketch {
* Heap constructor.
* @param k configured size of sketch. Range [m, 2^16]
* @param m minimum level size. Default is 8.
+ * @param compatible if true, compatible with quantiles sketch treatment of rank 0.0 and 1.0.
*/
private KllDoublesSketch(final int k, final int m, final boolean compatible) {
super(k, m, compatible);
@@ -85,10 +108,10 @@ public class KllDoublesSketch extends BaseKllSketch {
* @param mem Memory object that contains data serialized by this sketch.
*/
private KllDoublesSketch(final Memory mem) {
- super(mem.getShort(K_SHORT) & 0xffff, DEFAULT_M, true);
- final int flags = mem.getByte(FLAGS_BYTE) & 0xff;
- final boolean empty = (flags & 1 << Flags.IS_EMPTY.ordinal()) > 0;
- final boolean singleItem = (flags & 1 << Flags.IS_SINGLE_ITEM.ordinal()) > 0;
+ 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) {
numLevels_ = 1;
levels_ = new int[] {k_, k_};
@@ -103,12 +126,12 @@ public class KllDoublesSketch extends BaseKllSketch {
minK_ = k_;
numLevels_ = 1;
} else {
- n_ = mem.getLong(N_LONG);
- minK_ = mem.getShort(MIN_K_SHORT) & 0xffff;
- numLevels_ = mem.getByte(NUM_LEVELS_BYTE) & 0xff;
+ 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_SINGLE_ITEM : DATA_START_DOUBLE;
+ int offset = singleItem ? DATA_START_ADR_SINGLE_ITEM : DATA_START_ADR_DOUBLE;
final int itemCapacity = KllHelper.computeTotalItemCapacity(k_, m_, numLevels_);
if (singleItem) {
levels_[0] = itemCapacity - 1;
@@ -130,7 +153,7 @@ public class KllDoublesSketch extends BaseKllSketch {
minValue_ = items_[levels_[0]];
maxValue_ = items_[levels_[0]];
}
- isLevelZeroSorted_ = (flags & 1 << Flags.IS_LEVEL_ZERO_SORTED.ordinal()) > 0;
+ isLevelZeroSorted_ = (flags & LEVEL_ZERO_SORTED_BIT_MASK) > 0;
}
}
@@ -144,17 +167,17 @@ public class KllDoublesSketch extends BaseKllSketch {
//To simplify the code, this method does all the validity checking
// then passes the verified Memory to the actual heapify constructor
public static KllDoublesSketch heapify(final Memory mem) {
- final int preambleInts = mem.getByte(PREAMBLE_INTS_BYTE) & 0xff;
- final int serialVersion = mem.getByte(SER_VER_BYTE) & 0xff;
- final int family = mem.getByte(FAMILY_BYTE) & 0xff;
- final int flags = mem.getByte(FLAGS_BYTE) & 0xff;
- final int m = mem.getByte(M_BYTE) & 0xff;
+ 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 & 1 << Flags.IS_EMPTY.ordinal()) > 0;
- final boolean singleItem = (flags & 1 << Flags.IS_SINGLE_ITEM.ordinal()) > 0;
+ 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 "
@@ -166,9 +189,9 @@ public class KllDoublesSketch extends BaseKllSketch {
+ PREAMBLE_INTS_DOUBLE + " for a sketch with more than one item: " + preambleInts);
}
}
- if (serialVersion != SERIAL_VERSION && serialVersion != SERIAL_VERSION_SINGLE) {
+ if (serialVersion != SERIAL_VERSION_EMPTY_FULL && serialVersion != SERIAL_VERSION_SINGLE) {
throw new SketchesArgumentException(
- "Possible corruption: serial version mismatch: expected " + SERIAL_VERSION + " or "
+ "Possible corruption: serial version mismatch: expected " + SERIAL_VERSION_EMPTY_FULL + " or "
+ SERIAL_VERSION_SINGLE + ", got " + serialVersion);
}
if (family != Family.KLL.getID()) {
@@ -227,17 +250,23 @@ public class KllDoublesSketch extends BaseKllSketch {
/**
* Returns upper bound on the serialized size of a sketch given a parameter <em>k</em> and stream
- * length. The resulting size is an overestimate to make sure actual sketches don't exceed it.
- * This method can be used if allocation of storage is necessary beforehand, but it is not
- * optimal.
+ * 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
*/
public static int getMaxSerializedSizeBytes(final int k, final long n) {
- final int numLevels = KllHelper.ubOnNumLevels(n);
- final int maxNumItems = KllHelper.computeTotalItemCapacity(k, DEFAULT_M, numLevels);
- return getSerializedSizeBytes(numLevels, maxNumItems);
+ final LevelStats lvlStats = getAllLevelStatsGivenN(k, DEFAULT_M, n, false, false, true);
+ return lvlStats.getBytes();
+ }
+
+ /**
+ * Returns the current number of bytes this sketch would require to store in compact form.
+ * @return the current number of bytes this sketch would require to store in compact form.
+ */
+ public int getCurrentCompactSerializedSizeBytes() {
+ if (isEmpty()) { return N_LONG_ADR; }
+ return KllHelper.getCompactSerializedSizeBytes(numLevels_, getNumRetained(), true);
}
/**
@@ -285,13 +314,13 @@ public class KllDoublesSketch extends BaseKllSketch {
*/
public double getQuantile(final double fraction) {
if (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");
+ }
if (compatible) {
if (fraction == 0.0) { return minValue_; }
if (fraction == 1.0) { return maxValue_; }
}
- if (fraction < 0.0 || fraction > 1.0) {
- throw new SketchesArgumentException("Fraction cannot be less than zero or greater than 1.0");
- }
final KllDoublesQuantileCalculator quant = getQuantileCalculator();
return quant.getQuantile(fraction);
}
@@ -343,7 +372,7 @@ public class KllDoublesSketch extends BaseKllSketch {
for (int i = 0; i < fractions.length; i++) {
final double fraction = fractions[i];
if (fraction < 0.0 || fraction > 1.0) {
- throw new SketchesArgumentException("Fraction cannot be less than zero or greater than 1.0");
+ throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
}
if (fraction == 0.0 && compatible) { quantiles[i] = minValue_; }
else if (fraction == 1.0 && compatible) { quantiles[i] = maxValue_; }
@@ -412,10 +441,11 @@ public class KllDoublesSketch extends BaseKllSketch {
/**
* Returns the number of bytes this sketch would require to store.
* @return the number of bytes this sketch would require to store.
+ * @deprecated use {@link #getCurrentCompactSerializedSizeBytes() }
*/
+ @Deprecated
public int getSerializedSizeBytes() {
- if (isEmpty()) { return N_LONG; }
- return getSerializedSizeBytes(numLevels_, getNumRetained());
+ return getCurrentCompactSerializedSizeBytes();
}
/**
@@ -455,29 +485,30 @@ public class KllDoublesSketch extends BaseKllSketch {
@Override
public byte[] toByteArray() {
- final byte[] bytes = new byte[getSerializedSizeBytes()];
+ final byte[] bytes = new byte[getCurrentCompactSerializedSizeBytes()];
final WritableMemory wmem = WritableMemory.writableWrap(bytes);
final boolean singleItem = n_ == 1;
final boolean empty = isEmpty();
//load the preamble
- wmem.putByte(PREAMBLE_INTS_BYTE, (byte) (empty || singleItem ? PREAMBLE_INTS_EMPTY_SINGLE : PREAMBLE_INTS_DOUBLE));
- wmem.putByte(SER_VER_BYTE, singleItem ? SERIAL_VERSION_SINGLE : SERIAL_VERSION);
- wmem.putByte(FAMILY_BYTE, (byte) Family.KLL.getID());
+ wmem.putByte(PREAMBLE_INTS_BYTE_ADR, (byte)
+ (empty || singleItem ? PREAMBLE_INTS_EMPTY_SINGLE : PREAMBLE_INTS_DOUBLE));
+ wmem.putByte(SER_VER_BYTE_ADR, singleItem ? SERIAL_VERSION_SINGLE : SERIAL_VERSION_EMPTY_FULL);
+ wmem.putByte(FAMILY_BYTE_ADR, (byte) Family.KLL.getID());
final byte flags = (byte) (
- (empty ? 1 << Flags.IS_EMPTY.ordinal() : 0)
- | (isLevelZeroSorted_ ? 1 << Flags.IS_LEVEL_ZERO_SORTED.ordinal() : 0)
- | (singleItem ? 1 << Flags.IS_SINGLE_ITEM.ordinal() : 0));
- wmem.putByte(FLAGS_BYTE, flags);
- wmem.putShort(K_SHORT, (short) k_);
- wmem.putByte(M_BYTE, (byte) m_);
+ (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_);
if (empty) { return bytes; }
//load data
- int offset = DATA_START_SINGLE_ITEM;
+ int offset = DATA_START_ADR_SINGLE_ITEM;
if (!singleItem) {
- wmem.putLong(N_LONG, n_);
- wmem.putShort(MIN_K_SHORT, (short) minK_);
- wmem.putByte(NUM_LEVELS_BYTE, (byte) numLevels_);
- offset = DATA_START_DOUBLE;
+ wmem.putLong(N_LONG_ADR, n_);
+ wmem.putShort(MIN_K_SHORT_ADR, (short) minK_);
+ wmem.putByte(NUM_LEVELS_BYTE_ADR, (byte) numLevels_);
+ offset = DATA_START_ADR_DOUBLE;
// the last integer in levels_ is not serialized because it can be derived
final int len = levels_.length - 1;
wmem.putIntArray(offset, levels_, 0, len);
@@ -509,7 +540,7 @@ public class KllDoublesSketch extends BaseKllSketch {
sb.append(" Level 0 Sorted : ").append(isLevelZeroSorted_).append(Util.LS);
sb.append(" Capacity Items : ").append(items_.length).append(Util.LS);
sb.append(" Retained Items : ").append(getNumRetained()).append(Util.LS);
- sb.append(" Storage Bytes : ").append(getSerializedSizeBytes()).append(Util.LS);
+ sb.append(" Storage Bytes : ").append(getCurrentCompactSerializedSizeBytes()).append(Util.LS);
sb.append(" Min Value : ").append(minValue_).append(Util.LS);
sb.append(" Max Value : ").append(maxValue_).append(Util.LS);
sb.append("### End sketch summary").append(Util.LS);
@@ -766,7 +797,7 @@ public class KllDoublesSketch extends BaseKllSketch {
final int finalCapacity = result[1];
final int finalPop = result[2];
- assert finalNumLevels <= ub; // can sometimes be much bigger
+ assert finalNumLevels <= ub; // ub may be much bigger
// now we need to transfer the results back into the "self" sketch
final double[] newbuf = finalCapacity == items_.length ? items_ : new double[finalCapacity];
@@ -811,16 +842,7 @@ public class KllDoublesSketch extends BaseKllSketch {
}
}
- private static int getSerializedSizeBytes(final int numLevels, final int numRetained) {
- if (numLevels == 1 && numRetained == 1) {
- return DATA_START_SINGLE_ITEM + Double.BYTES;
- }
- // the last integer in levels_ is not serialized because it can be derived
- // + 2 for min and max
- return DATA_START_DOUBLE + numLevels * Integer.BYTES + (numRetained + 2) * Double.BYTES;
- }
-
- // for testing
+ // only for testing
double[] getItems() {
return items_;
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
index 065e38e..79e730e 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
@@ -112,6 +112,7 @@ class KllFloatsHelper {
* @param outBuf the same array as inBuf
* @param outLevels the same size as inLevels
* @param isLevelZeroSorted true if this.level 0 is sorted
+ * @param random instance of java.util.Random
* @return int array of: {numLevels, targetItemCount, currentItemCount)
*/
static int[] generalFloatsCompress(
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
index 7d2639f..c8e928a 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
@@ -22,12 +22,34 @@ package org.apache.datasketches.kll;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static org.apache.datasketches.Util.isOdd;
+import static org.apache.datasketches.kll.KllHelper.getAllLevelStatsGivenN;
+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.DEFAULT_K;
+import static org.apache.datasketches.kll.PreambleUtil.DEFAULT_M;
+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;
+import static org.apache.datasketches.kll.PreambleUtil.K_SHORT_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.LEVEL_ZERO_SORTED_BIT_MASK;
+import static org.apache.datasketches.kll.PreambleUtil.MIN_K_SHORT_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.M_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.NUM_LEVELS_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.N_LONG_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.PREAMBLE_INTS_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.PREAMBLE_INTS_EMPTY_SINGLE;
+import static org.apache.datasketches.kll.PreambleUtil.PREAMBLE_INTS_FLOAT;
+import static org.apache.datasketches.kll.PreambleUtil.SERIAL_VERSION_EMPTY_FULL;
+import static org.apache.datasketches.kll.PreambleUtil.SERIAL_VERSION_SINGLE;
+import static org.apache.datasketches.kll.PreambleUtil.SER_VER_BYTE_ADR;
+import static org.apache.datasketches.kll.PreambleUtil.SINGLE_ITEM_BIT_MASK;
import java.util.Arrays;
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.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
@@ -62,7 +84,7 @@ public class KllFloatsSketch extends BaseKllSketch {
/**
* Used for testing only.
* @param k configured size of sketch. Range [m, 2^16]
- * @param compatible if true, compatible with quantiles sketch.
+ * @param compatible if true, compatible with quantiles sketch treatment of rank 0.0 and 1.0.
*/
KllFloatsSketch(final int k, final boolean compatible) {
this(k, DEFAULT_M, compatible);
@@ -72,6 +94,7 @@ public class KllFloatsSketch extends BaseKllSketch {
* Heap constructor.
* @param k configured size of sketch. Range [m, 2^16]
* @param m minimum level size. Default is 8.
+ * @param compatible if true, compatible with quantiles sketch treatment of rank 0.0 and 1.0.
*/
private KllFloatsSketch(final int k, final int m, final boolean compatible) {
super(k, m, compatible);
@@ -85,10 +108,10 @@ public class KllFloatsSketch extends BaseKllSketch {
* @param mem Memory object that contains data serialized by this sketch.
*/
private KllFloatsSketch(final Memory mem) {
- super(mem.getShort(K_SHORT) & 0xffff, DEFAULT_M, true);
- final int flags = mem.getByte(FLAGS_BYTE) & 0xff;
- final boolean empty = (flags & 1 << Flags.IS_EMPTY.ordinal()) > 0;
- final boolean singleItem = (flags & 1 << Flags.IS_SINGLE_ITEM.ordinal()) > 0;
+ 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) {
numLevels_ = 1;
levels_ = new int[] {k_, k_};
@@ -103,12 +126,12 @@ public class KllFloatsSketch extends BaseKllSketch {
minK_ = k_;
numLevels_ = 1;
} else {
- n_ = mem.getLong(N_LONG);
- minK_ = mem.getShort(MIN_K_SHORT) & 0xffff;
- numLevels_ = mem.getByte(NUM_LEVELS_BYTE) & 0xff;
+ 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_SINGLE_ITEM : DATA_START_FLOAT;
+ int offset = singleItem ? DATA_START_ADR_SINGLE_ITEM : DATA_START_ADR_FLOAT;
final int itemCapacity = KllHelper.computeTotalItemCapacity(k_, m_, numLevels_);
if (singleItem) {
levels_[0] = itemCapacity - 1;
@@ -130,7 +153,7 @@ public class KllFloatsSketch extends BaseKllSketch {
minValue_ = items_[levels_[0]];
maxValue_ = items_[levels_[0]];
}
- isLevelZeroSorted_ = (flags & 1 << Flags.IS_LEVEL_ZERO_SORTED.ordinal()) > 0;
+ isLevelZeroSorted_ = (flags & LEVEL_ZERO_SORTED_BIT_MASK) > 0;
}
}
@@ -144,17 +167,17 @@ public class KllFloatsSketch extends BaseKllSketch {
//To simplify the code, this method does all the validity checking
// then passes the verified Memory to the actual heapify constructor
public static KllFloatsSketch heapify(final Memory mem) {
- final int preambleInts = mem.getByte(PREAMBLE_INTS_BYTE) & 0xff;
- final int serialVersion = mem.getByte(SER_VER_BYTE) & 0xff;
- final int family = mem.getByte(FAMILY_BYTE) & 0xff;
- final int flags = mem.getByte(FLAGS_BYTE) & 0xff;
- final int m = mem.getByte(M_BYTE) & 0xff;
+ 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 & 1 << Flags.IS_EMPTY.ordinal()) > 0;
- final boolean singleItem = (flags & 1 << Flags.IS_SINGLE_ITEM.ordinal()) > 0;
+ 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 "
@@ -166,9 +189,9 @@ public class KllFloatsSketch extends BaseKllSketch {
+ PREAMBLE_INTS_FLOAT + " for a sketch with more than one item: " + preambleInts);
}
}
- if (serialVersion != SERIAL_VERSION && serialVersion != SERIAL_VERSION_SINGLE) {
+ if (serialVersion != SERIAL_VERSION_EMPTY_FULL && serialVersion != SERIAL_VERSION_SINGLE) {
throw new SketchesArgumentException(
- "Possible corruption: serial version mismatch: expected " + SERIAL_VERSION + " or "
+ "Possible corruption: serial version mismatch: expected " + SERIAL_VERSION_EMPTY_FULL + " or "
+ SERIAL_VERSION_SINGLE + ", got " + serialVersion);
}
if (family != Family.KLL.getID()) {
@@ -227,17 +250,23 @@ public class KllFloatsSketch extends BaseKllSketch {
/**
* Returns upper bound on the serialized size of a sketch given a parameter <em>k</em> and stream
- * length. The resulting size is an overestimate to make sure actual sketches don't exceed it.
- * This method can be used if allocation of storage is necessary beforehand, but it is not
- * optimal.
+ * 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
*/
public static int getMaxSerializedSizeBytes(final int k, final long n) {
- final int numLevels = KllHelper.ubOnNumLevels(n);
- final int maxNumItems = KllHelper.computeTotalItemCapacity(k, DEFAULT_M, numLevels);
- return getSerializedSizeBytes(numLevels, maxNumItems);
+ final LevelStats lvlStats = getAllLevelStatsGivenN(k, DEFAULT_M, n, false, false, false);
+ return lvlStats.getBytes();
+ }
+
+ /**
+ * Returns the current number of bytes this sketch would require to store in compact form.
+ * @return the current number of bytes this sketch would require to store in compact form.
+ */
+ public int getCurrentCompactSerializedSizeBytes() {
+ if (isEmpty()) { return N_LONG_ADR; }
+ return KllHelper.getCompactSerializedSizeBytes(numLevels_, getNumRetained(), false);
}
/**
@@ -285,13 +314,13 @@ public class KllFloatsSketch extends BaseKllSketch {
*/
public float getQuantile(final double fraction) {
if (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");
+ }
if (compatible) {
if (fraction == 0.0) { return minValue_; }
if (fraction == 1.0) { return maxValue_; }
}
- if (fraction < 0.0 || fraction > 1.0) {
- throw new SketchesArgumentException("Fraction cannot be less than zero or greater than 1.0");
- }
final KllFloatsQuantileCalculator quant = getQuantileCalculator();
return quant.getQuantile(fraction);
}
@@ -343,7 +372,7 @@ public class KllFloatsSketch extends BaseKllSketch {
for (int i = 0; i < fractions.length; i++) {
final double fraction = fractions[i];
if (fraction < 0.0 || fraction > 1.0) {
- throw new SketchesArgumentException("Fraction cannot be less than zero or greater than 1.0");
+ throw new SketchesArgumentException("Fraction cannot be less than zero nor greater than 1.0");
}
if (fraction == 0.0 && compatible) { quantiles[i] = minValue_; }
else if (fraction == 1.0 && compatible) { quantiles[i] = maxValue_; }
@@ -412,10 +441,11 @@ public class KllFloatsSketch extends BaseKllSketch {
/**
* Returns the number of bytes this sketch would require to store.
* @return the number of bytes this sketch would require to store.
+ * @deprecated use {@link #getCurrentCompactSerializedSizeBytes() }
*/
+ @Deprecated
public int getSerializedSizeBytes() {
- if (isEmpty()) { return N_LONG; }
- return getSerializedSizeBytes(numLevels_, getNumRetained());
+ return getCurrentCompactSerializedSizeBytes();
}
/**
@@ -460,24 +490,25 @@ public class KllFloatsSketch extends BaseKllSketch {
final boolean singleItem = n_ == 1;
final boolean empty = isEmpty();
//load the preamble
- wmem.putByte(PREAMBLE_INTS_BYTE, (byte) (empty || singleItem ? PREAMBLE_INTS_EMPTY_SINGLE : PREAMBLE_INTS_FLOAT));
- wmem.putByte(SER_VER_BYTE, singleItem ? SERIAL_VERSION_SINGLE : SERIAL_VERSION);
- wmem.putByte(FAMILY_BYTE, (byte) Family.KLL.getID());
+ wmem.putByte(PREAMBLE_INTS_BYTE_ADR, (byte)
+ (empty || singleItem ? PREAMBLE_INTS_EMPTY_SINGLE : PREAMBLE_INTS_FLOAT));
+ wmem.putByte(SER_VER_BYTE_ADR, singleItem ? SERIAL_VERSION_SINGLE : SERIAL_VERSION_EMPTY_FULL);
+ wmem.putByte(FAMILY_BYTE_ADR, (byte) Family.KLL.getID());
final byte flags = (byte) (
- (empty ? 1 << Flags.IS_EMPTY.ordinal() : 0)
- | (isLevelZeroSorted_ ? 1 << Flags.IS_LEVEL_ZERO_SORTED.ordinal() : 0)
- | (singleItem ? 1 << Flags.IS_SINGLE_ITEM.ordinal() : 0));
- wmem.putByte(FLAGS_BYTE, flags);
- wmem.putShort(K_SHORT, (short) k_);
- wmem.putByte(M_BYTE, (byte) m_);
+ (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_);
if (empty) { return bytes; }
//load data
- int offset = DATA_START_SINGLE_ITEM;
+ int offset = DATA_START_ADR_SINGLE_ITEM;
if (!singleItem) {
- wmem.putLong(N_LONG, n_);
- wmem.putShort(MIN_K_SHORT, (short) minK_);
- wmem.putByte(NUM_LEVELS_BYTE, (byte) numLevels_);
- offset = DATA_START_FLOAT;
+ wmem.putLong(N_LONG_ADR, n_);
+ wmem.putShort(MIN_K_SHORT_ADR, (short) minK_);
+ wmem.putByte(NUM_LEVELS_BYTE_ADR, (byte) numLevels_);
+ offset = DATA_START_ADR_FLOAT;
// the last integer in levels_ is not serialized because it can be derived
final int len = levels_.length - 1;
wmem.putIntArray(offset, levels_, 0, len);
@@ -766,7 +797,7 @@ public class KllFloatsSketch extends BaseKllSketch {
final int finalCapacity = result[1];
final int finalPop = result[2];
- assert finalNumLevels <= ub; // ub can sometimes be much bigger
+ assert finalNumLevels <= ub; // ub may be much bigger
// now we need to transfer the results back into the "self" sketch
final float[] newbuf = finalCapacity == items_.length ? items_ : new float[finalCapacity];
@@ -811,15 +842,6 @@ public class KllFloatsSketch extends BaseKllSketch {
}
}
- private static int getSerializedSizeBytes(final int numLevels, final int numRetained) {
- if (numLevels == 1 && numRetained == 1) {
- return DATA_START_SINGLE_ITEM + Float.BYTES;
- }
- // the last integer in levels_ is not serialized because it can be derived
- // + 2 for min and max
- return DATA_START_FLOAT + numLevels * Integer.BYTES + (numRetained + 2) * Float.BYTES;
- }
-
// for testing
float[] getItems() {
diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java
index d59dfc6..9cb1123 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java
@@ -20,8 +20,12 @@
package org.apache.datasketches.kll;
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;
class KllHelper {
+ static final String LS = System.getProperty("line.separator");
/**
* Copy the old array into a new larger array.
@@ -39,7 +43,7 @@ class KllHelper {
}
/**
- * Returns the upper bound of the number of levels based on <i>n</i>.
+ * Returns very conservative upper bound of the number of levels based on <i>n</i>.
* @param n the length of the stream
* @return floor( log_2(n) )
*/
@@ -47,6 +51,94 @@ class KllHelper {
return 1 + Long.numberOfTrailingZeros(floorPowerOf2(n));
}
+ public 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;
+ LevelStats lvlStats;
+ do {
+ numLevels++;
+ lvlStats = getLevelStats(k, m, numLevels, printDetail, printSummaries, isDouble);
+ cumN = lvlStats.getMaxN();
+ } while (cumN < n);
+ return lvlStats;
+ }
+
+ static LevelStats getLevelStats(final int k, final int m, final int numLevels,
+ final boolean printDetail, final boolean printSummary, final boolean isDouble) {
+ int cumN = 0;
+ int cumCap = 0;
+ if (printDetail) {
+ System.out.println("Total Levels: " + numLevels);
+ System.out.printf("%6s%12s%8s%16s\n", "Level","Wt","Cap","N");
+ }
+ for (int level = 0; level < numLevels; level++) {
+ final long levelCap = levelCapacity(k, numLevels, level, m);
+ final long maxNAtLevel = levelCap << level;
+ cumN += maxNAtLevel;
+ cumCap += (int)levelCap;
+ if (printDetail) {
+ System.out.printf("%6d%,12d%8d%,16d\n", level, 1 << level, levelCap, maxNAtLevel);
+ }
+ }
+ final int bytes = getCompactSerializedSizeBytes(numLevels, cumCap, isDouble);
+ if (printDetail) {
+ System.out.printf(" TOTALS%10s %8d%,16d\n", "", cumCap, cumN);
+ System.out.println(" TOTAL BYTES: " + bytes);
+ System.out.println("");
+ }
+ final LevelStats lvlStats = new LevelStats(cumN, bytes, numLevels, cumCap);
+ if (printSummary) { System.out.println(lvlStats.toString()); }
+ return lvlStats;
+ }
+
+ public static class LevelStats {
+ private long maxN;
+ private int bytes;
+ private int numLevels;
+ private int maxCap;
+
+ LevelStats(final long maxN, final int bytes, final int numLevels, final int maxCap) {
+ this.maxN = maxN;
+ this.bytes = bytes;
+ this.numLevels = numLevels;
+ this.maxCap = maxCap;
+ }
+
+ @Override
+ public String toString() {
+ 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);
+ return sb.toString();
+ }
+
+ public long getMaxN() { return maxN; }
+
+ public int getBytes() { return bytes; }
+
+ public int getNumLevels() { return numLevels; }
+
+ public int getMaxCap() { return maxCap; }
+ }
+
+ 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);
+ }
+ // The last integer in levels_ is not serialized because it can be derived.
+ // The + 2 is for min and max
+ if (isDouble) {
+ return DATA_START_ADR_DOUBLE + numLevels * Integer.BYTES + (numRetained + 2) * Double.BYTES;
+ } else {
+ return DATA_START_ADR_FLOAT + numLevels * Integer.BYTES + (numRetained + 2) * Float.BYTES;
+ }
+ }
+
/**
* Returns the maximum number of items that this sketch can handle
* @param k The sizing / accuracy parameter of the sketch in items.
diff --git a/src/main/java/org/apache/datasketches/kll/PreambleUtil.java b/src/main/java/org/apache/datasketches/kll/PreambleUtil.java
new file mode 100644
index 0000000..c2211db
--- /dev/null
+++ b/src/main/java/org/apache/datasketches/kll/PreambleUtil.java
@@ -0,0 +1,409 @@
+/*
+ * 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.Family.idToFamily;
+
+import org.apache.datasketches.Family;
+import org.apache.datasketches.SketchesArgumentException;
+import org.apache.datasketches.memory.Memory;
+import org.apache.datasketches.memory.WritableMemory;
+
+//@formatter:off
+
+/**
+ * This class defines the serialized data structure and provides access methods for the key fields.
+ *
+ * <p>The intent of the design of this class was to isolate the detailed knowledge of the bit and
+ * byte layout of the serialized form of the sketches derived from the base sketch classes into one place.
+ * This allows the possibility of the introduction of different serialization
+ * schemes with minimal impact on the rest of the library.</p>
+ *
+ * <p>
+ * LAYOUT: The low significance bytes of this <i>long</i> based data structure are on the right.
+ * The multi-byte primitives are stored in native byte order.
+ * The single byte fields are treated as unsigned.</p>
+ *
+ * <p>An empty sketch requires only 8 bytes, which is only preamble.
+ * A serialized, non-empty KllDoublesSketch requires at least 16 bytes of preamble.
+ * A serialized, non-empty KllFloatsSketch requires at least 12 bytes of preamble.</p>
+ *
+ * <pre>{@code
+ * Serialized float sketch layout, more than one item:
+ * Adr:
+ * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+ * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
+ * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
+ * 1 ||---------------------------------N_LONG---------------------------------------|
+ * || 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
+ * 2 ||<--------------data----------------| unused |numLevels|-------min K-----------|
+ *
+ * Serialized float sketch layout, Empty (8 bytes) and Single Item (12 bytes):
+ * Adr:
+ * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+ * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
+ * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
+ * 1 || |-------------------data-------------------|
+ *
+ *
+ *
+ * Serialized double sketch layout, more than one item:
+ * Adr:
+ * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+ * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
+ * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
+ * 1 ||---------------------------------N_LONG---------------------------------------|
+ * || 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
+ * 2 ||--------------unused------------------------|numLevels|-------min K-----------|
+ * || | 24 |
+ * 3 ||<---------------------------------data----------------------------------------|
+ *
+ * Serialized double sketch layout, Empty (8 bytes) and Single Item (16 bytes):
+ * Adr:
+ * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+ * 0 || unused | M |--------K--------| Flags | FamID | SerVer | PreambleInts |
+ * || | 8 |
+ * 1 ||----------------------------------data----------------------------------------|
+ * }</pre>
+ *
+ * @author Lee Rhodes
+ */
+final class PreambleUtil {
+
+ private PreambleUtil() {}
+
+ static final String LS = System.getProperty("line.separator");
+
+ /**
+ * The default value of K
+ */
+ public static final int DEFAULT_K = 200;
+ static final int DEFAULT_M = 8;
+ static final int MIN_K = DEFAULT_M;
+ static final int MAX_K = (1 << 16) - 1; // serialized as an unsigned short
+
+ // Preamble byte addresses
+ static final int PREAMBLE_INTS_BYTE_ADR = 0;
+ static final int SER_VER_BYTE_ADR = 1;
+ static final int FAMILY_BYTE_ADR = 2;
+ static final int FLAGS_BYTE_ADR = 3;
+ static final int K_SHORT_ADR = 4; // to 5
+ static final int M_BYTE_ADR = 6;
+ // 7 is reserved for future use
+ // SINGLE ITEM ONLY
+ static final int DATA_START_ADR_SINGLE_ITEM = 8;
+
+ // MULTI-ITEM
+ static final int N_LONG_ADR = 8; // to 15
+ static final int MIN_K_SHORT_ADR = 16; // to 17
+ static final int NUM_LEVELS_BYTE_ADR = 18;
+
+ // FLOAT SKETCH 19 is reserved for future use in float sketch
+ static final int DATA_START_ADR_FLOAT = 20; // float sketch, not single item
+
+ // DOUBLE SKETCH 19 to 23 is reserved for future use in double sketch
+ static final int DATA_START_ADR_DOUBLE = 24; // double sketch, not single item
+
+ // Other static values
+ static final byte SERIAL_VERSION_EMPTY_FULL = 1; // Empty or full preamble, NOT single item format
+ static final byte SERIAL_VERSION_SINGLE = 2; // only single-item format
+ static final int PREAMBLE_INTS_EMPTY_SINGLE = 2; // for empty or single item
+ static final int PREAMBLE_INTS_FLOAT = 5; // not empty nor single item, full preamble float
+ static final int PREAMBLE_INTS_DOUBLE = 6; // not empty nor single item, full preamble double
+
+ // Flag bit masks
+ static final int EMPTY_BIT_MASK = 1;
+ 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;
+
+ enum Layout {
+ FLOAT_FULL_COMPACT, FLOAT_EMPTY_COMPACT, FLOAT_SINGLE_COMPACT,
+ DOUBLE_FULL_COMPACT, DOUBLE_EMPTY_COMPACT, DOUBLE_SINGLE_COMPACT,
+ 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.
+ *
+ * @param byteArr the given byte array.
+ * @return the summary string.
+ */
+ static String toString(final byte[] byteArr) {
+ final Memory mem = Memory.wrap(byteArr);
+ return toString(mem);
+ }
+
+ /**
+ * Returns a human readable string summary of the internal state of the given Memory.
+ * Used primarily in testing.
+ *
+ * @param mem the given Memory
+ * @return the summary string.
+ */
+ static String toString(final Memory mem) {
+ return null; //memoryToString(mem);
+ }
+
+
+ @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;
+ 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;
+ }
+ 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;
+ }
+ 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;
+ }
+ 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;
+ 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;
+ }
+ break;
+ }
+ }
+
+ BaseKllSketch.checkK(k);
+
+ if (m != 8) {
+ System.err.println("WARNING: Minimum Level width set to non-default value: " + m);
+ }
+
+
+ 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;
+ }
+
+ static int extractSerVer(final Memory mem) {
+ return mem.getByte(SER_VER_BYTE_ADR) & 0XFF;
+ }
+
+ static int extractFamilyID(final Memory mem) {
+ return mem.getByte(FAMILY_BYTE_ADR) & 0XFF;
+ }
+
+ static int extractFlags(final Memory mem) {
+ return mem.getByte(FLAGS_BYTE_ADR) & 0XFF;
+ }
+
+ static boolean extractEmptyFlag(final Memory mem) {
+ return (extractFlags(mem) & EMPTY_BIT_MASK) != 0;
+ }
+
+ static boolean extractLevelZeroSortedFlag(final Memory mem) {
+ return (extractFlags(mem) & LEVEL_ZERO_SORTED_BIT_MASK) != 0;
+ }
+
+ static boolean extractSingleItemFlag(final Memory mem) {
+ return (extractFlags(mem) & SINGLE_ITEM_BIT_MASK) != 0;
+ }
+
+ static int extractK(final Memory mem) {
+ return mem.getShort(K_SHORT_ADR) & 0XFFFF;
+ }
+
+ static int extractM(final Memory mem) {
+ return mem.getByte(M_BYTE_ADR) & 0XFF;
+ }
+
+ static long extractN(final Memory mem) {
+ return mem.getLong(N_LONG_ADR);
+ }
+
+ static int extractMinK(final Memory mem) {
+ return mem.getShort(MIN_K_SHORT_ADR) & 0XFFFF;
+ }
+
+ static int extractNumLevels(final Memory mem) {
+ return mem.getByte(NUM_LEVELS_BYTE_ADR) & 0XFF;
+ }
+
+ static void insertPreInts(final WritableMemory wmem, final int value) {
+ wmem.putByte(PREAMBLE_INTS_BYTE_ADR, (byte) value);
+ }
+
+ static void insertSerVer(final WritableMemory wmem, final int value) {
+ wmem.putByte(SER_VER_BYTE_ADR, (byte) value);
+ }
+
+ static void insertFamilyID(final WritableMemory wmem, final int value) {
+ wmem.putByte(FAMILY_BYTE_ADR, (byte) value);
+ }
+
+ static void insertFlags(final WritableMemory wmem, final int value) {
+ wmem.putByte(FLAGS_BYTE_ADR, (byte) value);
+ }
+
+ static void insertEmptyFlag(final WritableMemory wmem, final boolean empty) {
+ final int flags = extractFlags(wmem);
+ insertFlags(wmem, empty ? flags | EMPTY_BIT_MASK : flags & ~EMPTY_BIT_MASK);
+ }
+
+ static void insertLevelZeroSortedFlag(final WritableMemory wmem, final boolean levelZeroSorted) {
+ final int flags = extractFlags(wmem);
+ insertFlags(wmem, levelZeroSorted ? flags | LEVEL_ZERO_SORTED_BIT_MASK : flags & ~LEVEL_ZERO_SORTED_BIT_MASK);
+ }
+
+ static void insertSingleItemFlag(final WritableMemory wmem, final boolean singleItem) {
+ final int flags = extractFlags(wmem);
+ insertFlags(wmem, singleItem ? flags | SINGLE_ITEM_BIT_MASK : flags & ~SINGLE_ITEM_BIT_MASK);
+ }
+
+ static void insertK(final WritableMemory wmem, final int value) {
+ wmem.putShort(K_SHORT_ADR, (short) value);
+ }
+
+ static void insertM(final WritableMemory wmem, final int value) {
+ wmem.putByte(M_BYTE_ADR, (byte) value);
+ }
+
+ static void insertN(final WritableMemory wmem, final long value) {
+ wmem.putLong(N_LONG_ADR, value);
+ }
+
+ static void insertMinK(final WritableMemory wmem, final int value) {
+ wmem.putShort(MIN_K_SHORT_ADR, (short) value);
+ }
+
+ static void insertNumLevels(final WritableMemory wmem, final int value) {
+ wmem.putByte(NUM_LEVELS_BYTE_ADR, (byte) value);
+ }
+
+}
+
diff --git a/src/main/java/org/apache/datasketches/quantiles/PreambleUtil.java b/src/main/java/org/apache/datasketches/quantiles/PreambleUtil.java
index 45990bc..2b3f539 100644
--- a/src/main/java/org/apache/datasketches/quantiles/PreambleUtil.java
+++ b/src/main/java/org/apache/datasketches/quantiles/PreambleUtil.java
@@ -31,23 +31,23 @@ import org.apache.datasketches.memory.WritableMemory;
//@formatter:off
/**
- * This class defines the preamble data structure and provides basic utilities for some of the key
- * fields.
+ * This class defines the serialized data structure and provides access methods for the key fields.
+ *
* <p>The intent of the design of this class was to isolate the detailed knowledge of the bit and
- * byte layout of the serialized form of the sketches derived from the Sketch class into one place.
+ * byte layout of the serialized form of the sketches derived from the base sketch classes into one place.
* This allows the possibility of the introduction of different serialization
* schemes with minimal impact on the rest of the library.</p>
*
* <p>
- * MAP: Low significance bytes of this <i>long</i> data structure are on the right. However, the
- * multi-byte integers (<i>int</i> and <i>long</i>) are stored in native byte order. The
- * <i>byte</i> values are treated as unsigned.</p>
+ * LAYOUT: The low significance bytes of this <i>long</i> based data structure are on the right.
+ * The multi-byte primitives are stored in native byte order.
+ * The single byte fields are treated as unsigned.</p>
*
* <p>An empty ItemsSketch, on-heap DoublesSketch or compact off-heap DoublesSketch only require 8
- * bytes. An off-heap UpdateDoublesSketch and all non-empty skethces require at least 16 bytes of
+ * bytes. An off-heap UpdateDoublesSketch and all non-empty sketches require at least 16 bytes of
* preamble.</p>
*
- * <pre>
+ * <pre>{@code
* Long || Start Byte Adr: Common for both DoublesSketch and ItemsSketch
* Adr:
* || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
@@ -66,7 +66,7 @@ import org.apache.datasketches.memory.WritableMemory;
*
* || 39 | 38 | 37 | 36 | 35 | 34 | 33 | 32 |
* 4 ||---------------------------START OF COMBINED BUfFER----------------------------|
- * </pre>
+ * }</pre>
*
* @author Lee Rhodes
*/
diff --git a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
index 7eeea73..860e175 100644
--- a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java
@@ -19,6 +19,10 @@
package org.apache.datasketches.kll;
+//import static org.apache.datasketches.Util.getResourceBytes;
+import static org.apache.datasketches.kll.PreambleUtil.DEFAULT_K;
+import static org.apache.datasketches.kll.PreambleUtil.MAX_K;
+import static org.apache.datasketches.kll.PreambleUtil.MIN_K;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertNotNull;
@@ -276,32 +280,32 @@ public class KllDoublesSketchTest {
@SuppressWarnings("unused")
@Test(expectedExceptions = SketchesArgumentException.class)
public void kTooSmall() {
- new KllDoublesSketch(BaseKllSketch.MIN_K - 1);
+ new KllDoublesSketch(MIN_K - 1);
}
@SuppressWarnings("unused")
@Test(expectedExceptions = SketchesArgumentException.class)
public void kTooLarge() {
- new KllDoublesSketch(BaseKllSketch.MAX_K + 1);
+ new KllDoublesSketch(MAX_K + 1);
}
@Test
public void minK() {
- final KllDoublesSketch sketch = new KllDoublesSketch(BaseKllSketch.MIN_K);
+ final KllDoublesSketch sketch = new KllDoublesSketch(MIN_K);
for (int i = 0; i < 1000; i++) {
sketch.update(i);
}
- assertEquals(sketch.getK(), BaseKllSketch.MIN_K);
+ assertEquals(sketch.getK(), MIN_K);
assertEquals(sketch.getQuantile(0.5), 500, 500 * PMF_EPS_FOR_K_8);
}
@Test
public void maxK() {
- final KllDoublesSketch sketch = new KllDoublesSketch(BaseKllSketch.MAX_K);
+ final KllDoublesSketch sketch = new KllDoublesSketch(MAX_K);
for (int i = 0; i < 1000; i++) {
sketch.update(i);
}
- assertEquals(sketch.getK(), BaseKllSketch.MAX_K);
+ assertEquals(sketch.getK(), MAX_K);
assertEquals(sketch.getQuantile(0.5), 500, 500 * PMF_EPS_FOR_K_256);
}
@@ -310,14 +314,14 @@ public class KllDoublesSketchTest {
final KllDoublesSketch sketch1 = new KllDoublesSketch();
final byte[] bytes = sketch1.toByteArray();
final KllDoublesSketch sketch2 = KllDoublesSketch.heapify(Memory.wrap(bytes));
- assertEquals(bytes.length, sketch1.getSerializedSizeBytes());
+ assertEquals(bytes.length, sketch1.getCurrentCompactSerializedSizeBytes());
assertTrue(sketch2.isEmpty());
assertEquals(sketch2.getNumRetained(), sketch1.getNumRetained());
assertEquals(sketch2.getN(), sketch1.getN());
assertEquals(sketch2.getNormalizedRankError(false), sketch1.getNormalizedRankError(false));
assertTrue(Double.isNaN(sketch2.getMinValue()));
assertTrue(Double.isNaN(sketch2.getMaxValue()));
- assertEquals(sketch2.getSerializedSizeBytes(), sketch1.getSerializedSizeBytes());
+ assertEquals(sketch2.getCurrentCompactSerializedSizeBytes(), sketch1.getCurrentCompactSerializedSizeBytes());
}
@Test
@@ -326,16 +330,26 @@ public class KllDoublesSketchTest {
sketch1.update(1);
final byte[] bytes = sketch1.toByteArray();
final KllDoublesSketch sketch2 = KllDoublesSketch.heapify(Memory.wrap(bytes));
- assertEquals(bytes.length, sketch1.getSerializedSizeBytes());
+ assertEquals(bytes.length, sketch1.getCurrentCompactSerializedSizeBytes());
assertFalse(sketch2.isEmpty());
assertEquals(sketch2.getNumRetained(), 1);
assertEquals(sketch2.getN(), 1);
assertEquals(sketch2.getNormalizedRankError(false), sketch1.getNormalizedRankError(false));
assertFalse(Double.isNaN(sketch2.getMinValue()));
assertFalse(Double.isNaN(sketch2.getMaxValue()));
- assertEquals(sketch2.getSerializedSizeBytes(), 8 + Double.BYTES);
+ assertEquals(sketch2.getCurrentCompactSerializedSizeBytes(), 8 + Double.BYTES);
}
+// @Test //not implemented from C++ yet
+// public void deserializeOneItemV1() throws Exception {
+// final byte[] bytes = getResourceBytes("kll_sketch_float_one_item_v1.sk");
+// final KllFloatsSketch sketch = KllFloatsSketch.heapify(Memory.wrap(bytes));
+// assertFalse(sketch.isEmpty());
+// assertFalse(sketch.isEstimationMode());
+// assertEquals(sketch.getN(), 1);
+// assertEquals(sketch.getNumRetained(), 1);
+// }
+
@Test
public void serializeDeserialize() {
final KllDoublesSketch sketch1 = new KllDoublesSketch();
@@ -345,14 +359,14 @@ public class KllDoublesSketchTest {
}
final byte[] bytes = sketch1.toByteArray();
final KllDoublesSketch sketch2 = KllDoublesSketch.heapify(Memory.wrap(bytes));
- assertEquals(bytes.length, sketch1.getSerializedSizeBytes());
+ assertEquals(bytes.length, sketch1.getCurrentCompactSerializedSizeBytes());
assertFalse(sketch2.isEmpty());
assertEquals(sketch2.getNumRetained(), sketch1.getNumRetained());
assertEquals(sketch2.getN(), sketch1.getN());
assertEquals(sketch2.getNormalizedRankError(false), sketch1.getNormalizedRankError(false));
assertEquals(sketch2.getMinValue(), sketch1.getMinValue());
assertEquals(sketch2.getMaxValue(), sketch1.getMaxValue());
- assertEquals(sketch2.getSerializedSizeBytes(), sketch1.getSerializedSizeBytes());
+ assertEquals(sketch2.getCurrentCompactSerializedSizeBytes(), sketch1.getCurrentCompactSerializedSizeBytes());
}
@Test(expectedExceptions = SketchesArgumentException.class)
@@ -372,8 +386,8 @@ public class KllDoublesSketchTest {
@Test
public void getMaxSerializedSizeBytes() {
final int sizeBytes =
- KllDoublesSketch.getMaxSerializedSizeBytes(BaseKllSketch.DEFAULT_K, 1_000_000_000);
- assertEquals(sizeBytes, 6184);
+ KllDoublesSketch.getMaxSerializedSizeBytes(DEFAULT_K, 1L << 30);
+ assertEquals(sizeBytes, 5708);
}
@Test
diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
index fd2313b..fa1fd7b 100644
--- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java
@@ -19,6 +19,9 @@
package org.apache.datasketches.kll;
+import static org.apache.datasketches.kll.PreambleUtil.DEFAULT_K;
+import static org.apache.datasketches.kll.PreambleUtil.MAX_K;
+import static org.apache.datasketches.kll.PreambleUtil.MIN_K;
import static org.apache.datasketches.Util.getResourceBytes;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
@@ -277,32 +280,32 @@ public class KllFloatsSketchTest {
@SuppressWarnings("unused")
@Test(expectedExceptions = SketchesArgumentException.class)
public void kTooSmall() {
- new KllFloatsSketch(BaseKllSketch.MIN_K - 1);
+ new KllFloatsSketch(MIN_K - 1);
}
@SuppressWarnings("unused")
@Test(expectedExceptions = SketchesArgumentException.class)
public void kTooLarge() {
- new KllFloatsSketch(BaseKllSketch.MAX_K + 1);
+ new KllFloatsSketch(MAX_K + 1);
}
@Test
public void minK() {
- final KllFloatsSketch sketch = new KllFloatsSketch(BaseKllSketch.MIN_K);
+ final KllFloatsSketch sketch = new KllFloatsSketch(MIN_K);
for (int i = 0; i < 1000; i++) {
sketch.update(i);
}
- assertEquals(sketch.getK(), BaseKllSketch.MIN_K);
+ assertEquals(sketch.getK(), MIN_K);
assertEquals(sketch.getQuantile(0.5), 500, 500 * PMF_EPS_FOR_K_8);
}
@Test
public void maxK() {
- final KllFloatsSketch sketch = new KllFloatsSketch(BaseKllSketch.MAX_K);
+ final KllFloatsSketch sketch = new KllFloatsSketch(MAX_K);
for (int i = 0; i < 1000; i++) {
sketch.update(i);
}
- assertEquals(sketch.getK(), BaseKllSketch.MAX_K);
+ assertEquals(sketch.getK(), MAX_K);
assertEquals(sketch.getQuantile(0.5), 500, 500 * PMF_EPS_FOR_K_256);
}
@@ -311,14 +314,14 @@ public class KllFloatsSketchTest {
final KllFloatsSketch sketch1 = new KllFloatsSketch();
final byte[] bytes = sketch1.toByteArray();
final KllFloatsSketch sketch2 = KllFloatsSketch.heapify(Memory.wrap(bytes));
- assertEquals(bytes.length, sketch1.getSerializedSizeBytes());
+ assertEquals(bytes.length, sketch1.getCurrentCompactSerializedSizeBytes());
assertTrue(sketch2.isEmpty());
assertEquals(sketch2.getNumRetained(), sketch1.getNumRetained());
assertEquals(sketch2.getN(), sketch1.getN());
assertEquals(sketch2.getNormalizedRankError(false), sketch1.getNormalizedRankError(false));
assertTrue(Float.isNaN(sketch2.getMinValue()));
assertTrue(Float.isNaN(sketch2.getMaxValue()));
- assertEquals(sketch2.getSerializedSizeBytes(), sketch1.getSerializedSizeBytes());
+ assertEquals(sketch2.getCurrentCompactSerializedSizeBytes(), sketch1.getCurrentCompactSerializedSizeBytes());
}
@Test
@@ -327,14 +330,14 @@ public class KllFloatsSketchTest {
sketch1.update(1);
final byte[] bytes = sketch1.toByteArray();
final KllFloatsSketch sketch2 = KllFloatsSketch.heapify(Memory.wrap(bytes));
- assertEquals(bytes.length, sketch1.getSerializedSizeBytes());
+ assertEquals(bytes.length, sketch1.getCurrentCompactSerializedSizeBytes());
assertFalse(sketch2.isEmpty());
assertEquals(sketch2.getNumRetained(), 1);
assertEquals(sketch2.getN(), 1);
assertEquals(sketch2.getNormalizedRankError(false), sketch1.getNormalizedRankError(false));
assertFalse(Float.isNaN(sketch2.getMinValue()));
assertFalse(Float.isNaN(sketch2.getMaxValue()));
- assertEquals(sketch2.getSerializedSizeBytes(), 8 + Float.BYTES);
+ assertEquals(sketch2.getCurrentCompactSerializedSizeBytes(), 8 + Float.BYTES);
}
@Test
@@ -356,14 +359,14 @@ public class KllFloatsSketchTest {
}
final byte[] bytes = sketch1.toByteArray();
final KllFloatsSketch sketch2 = KllFloatsSketch.heapify(Memory.wrap(bytes));
- assertEquals(bytes.length, sketch1.getSerializedSizeBytes());
+ assertEquals(bytes.length, sketch1.getCurrentCompactSerializedSizeBytes());
assertFalse(sketch2.isEmpty());
assertEquals(sketch2.getNumRetained(), sketch1.getNumRetained());
assertEquals(sketch2.getN(), sketch1.getN());
assertEquals(sketch2.getNormalizedRankError(false), sketch1.getNormalizedRankError(false));
assertEquals(sketch2.getMinValue(), sketch1.getMinValue());
assertEquals(sketch2.getMaxValue(), sketch1.getMaxValue());
- assertEquals(sketch2.getSerializedSizeBytes(), sketch1.getSerializedSizeBytes());
+ assertEquals(sketch2.getCurrentCompactSerializedSizeBytes(), sketch1.getCurrentCompactSerializedSizeBytes());
}
@Test(expectedExceptions = SketchesArgumentException.class)
@@ -383,8 +386,8 @@ public class KllFloatsSketchTest {
@Test
public void getMaxSerializedSizeBytes() {
final int sizeBytes =
- KllFloatsSketch.getMaxSerializedSizeBytes(BaseKllSketch.DEFAULT_K, 1_000_000_000);
- assertEquals(sizeBytes, 3160);
+ KllFloatsSketch.getMaxSerializedSizeBytes(DEFAULT_K, 1L << 30);
+ assertEquals(sizeBytes, 2908);
}
@Test
diff --git a/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java b/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
index 791684e..a02d728 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
+++ b/src/test/java/org/apache/datasketches/kll/MiscDoublesTest.java
@@ -19,12 +19,16 @@
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;
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;
@@ -33,10 +37,11 @@ import org.testng.annotations.Test;
*/
@SuppressWarnings("javadoc")
public class MiscDoublesTest {
+ static final String LS = System.getProperty("line.separator");
@Test
public void checkGetKFromEps() {
- final int k = BaseKllSketch.DEFAULT_K;
+ final int k = DEFAULT_K;
final double eps = BaseKllSketch.getNormalizedRankError(k, false);
final double epsPmf = BaseKllSketch.getNormalizedRankError(k, true);
final int kEps = BaseKllSketch.getKFromEpsilon(eps, false);
@@ -119,8 +124,8 @@ public class MiscDoublesTest {
assertEquals(sk.getNumLevels(), 2);
}
- //@Test //requires visual check
- public void visualCheck() {
+ @Test //enable static println(..) for visual checking
+ public void visualCheckToString() {
final KllDoublesSketch sketch = new KllDoublesSketch(20);
for (int i = 0; i < 10; i++) { sketch.update(i + 1); }
println(sketch.toString(true, true));
@@ -130,7 +135,26 @@ public class MiscDoublesTest {
println("\n" + sketch2.toString(true, true));
sketch2.merge(sketch);
- println("\n" + sketch2.toString(true, true));
+ final String s2 = sketch2.toString(true, true);
+ 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
diff --git a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
index f7a0aee..92b54a3 100644
--- a/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/MiscFloatsTest.java
@@ -19,14 +19,17 @@
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;
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;
/**
@@ -34,10 +37,11 @@ import org.testng.annotations.Test;
*/
@SuppressWarnings("javadoc")
public class MiscFloatsTest {
+ static final String LS = System.getProperty("line.separator");
@Test
public void checkGetKFromEps() {
- final int k = BaseKllSketch.DEFAULT_K;
+ final int k = DEFAULT_K;
final double eps = BaseKllSketch.getNormalizedRankError(k, false);
final double epsPmf = BaseKllSketch.getNormalizedRankError(k, true);
final int kEps = BaseKllSketch.getKFromEpsilon(eps, false);
@@ -120,19 +124,37 @@ public class MiscFloatsTest {
assertEquals(sk.getNumLevels(), 2);
}
- //@Test //requires visual check
- public void checkNumRetainedAboveLevelZero() {
+ @Test //enable static println(..) for visual checking
+ public void visualCheckToString() {
final KllFloatsSketch sketch = new KllFloatsSketch(20);
for (int i = 0; i < 10; i++) { sketch.update(i + 1); }
final String s1 = sketch.toString(true, true);
println(s1);
+
final KllFloatsSketch sketch2 = new KllFloatsSketch(20);
- for (int i = 0; i < 400; i++) {
- sketch2.update(i + 1);
- }
+ for (int i = 0; i < 400; i++) { sketch2.update(i + 1); }
+
sketch2.merge(sketch);
final String s2 = sketch2.toString(true, true);
- println(s2);
+ 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
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org