You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by GitBox <gi...@apache.org> on 2022/02/19 00:13:45 UTC
[GitHub] [datasketches-java] leerho opened a new pull request #389: Refactor kll
leerho opened a new pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389
Refactor KllDoublesSketch and KllFloatsSketch to extend a BaseKllSketch.
The base class contains all the common methods that don't depend on
float or double type. This reduced a lot of duplicate code.
No substantive code changes, no changes to API. Just moved stuff around.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r811434583
##########
File path: src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
##########
@@ -0,0 +1,324 @@
+/*
+ * 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 java.lang.Math.abs;
+import static java.lang.Math.ceil;
+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 java.util.Random;
+
+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.
+ *
+ * Invariants:
+ * 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
+ * 2) After a compaction, (sum of capacities) - (sum of items) >= 1,
+ * 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.
+ */
Review comment:
- An item is an abstraction of the comparable "object" that the sketch is designed to be updated with and compute the quantiles and ranks of after being updated with many such items. For this base class a unit could be either a float or a double.
- To help the user perform _a priori_ space planning (i.e., how big will the sketch be?) , the user must start with an estimate of N, the largest anticipated number of items that the sketch will see, and the value of K to be used, which determines the error distribution of the sketch. The user then calls the method _getMaxSerializedSizeBytes(k, N)_, which returns the maximum serialized size of the sketch.
- Internally, in order to compute this size, the sketch first compute the upper bound on the maximum number of levels required, which is _floor(log2(N))_. The sketch takes this information and then computes the total number of items that can be retained in a sketch given K, M, numLevels. Where M is the internal _fixed_ value of the size of the smallest level.
- To compute this, the sketch then iterates over all levels computing the maximum capacity of each level given K, M, numLevels. This is a tricky computation that involves numerical folding so that the sketch could handle as many as 60 levels, which would be _extremely_ unlikely.
- The "Total Capacity" then, is the upper bound on the number of items that can be retained in the sketch given K, M, and the maximum number of levels, which, in turn, is determined from the anticipated N.
- In the description, the "sum of capacities" is the "Total Capacity" given K, M, and numLevels (or N).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] davecromberge commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
davecromberge commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r812636067
##########
File path: src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
##########
@@ -0,0 +1,324 @@
+/*
+ * 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 java.lang.Math.abs;
+import static java.lang.Math.ceil;
+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 java.util.Random;
+
+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.
+ *
+ * Invariants:
+ * 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
+ * 2) After a compaction, (sum of capacities) - (sum of items) >= 1,
+ * 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.
+ */
Review comment:
Thanks @leerho - the extra detail that you provided is helpful and answers my question.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] davecromberge commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
davecromberge commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r811212962
##########
File path: src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
##########
@@ -762,65 +447,51 @@ public void merge(final KllDoublesSketch other) {
if (Double.isNaN(maxValue_) || other.maxValue_ > maxValue_) { maxValue_ = other.maxValue_; }
n_ = finalN;
- assertCorrectTotalWeight();
+ assert KllHelper.sumTheSampleWeights(numLevels_, levels_) == n_;
Review comment:
I tried to find this as an invariant that was documented in the base class, but it does not appear to be listed:
```
Invariants:
1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
2) After a compaction, (sum of capacities) - (sum of items) >= 1, 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.
```
##########
File path: src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
##########
@@ -0,0 +1,324 @@
+/*
+ * 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 java.lang.Math.abs;
+import static java.lang.Math.ceil;
+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 java.util.Random;
+
+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.
+ *
+ * Invariants:
+ * 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
+ * 2) After a compaction, (sum of capacities) - (sum of items) >= 1,
+ * 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.
+ */
+
+ final int k_; // configured value of K
+ final int m_; // configured minimum buffer "width", Must always be DEFAULT_M for now.
+
+ int minK_; // for error estimation after merging with different k
+ long n_; // number of items input into this sketch
+ int numLevels_; // one-based number of current levels,
+ int[] levels_; // array of index offsets into the items[]. Size = numLevels + 1.
+ boolean isLevelZeroSorted_;
+
+ final boolean compatible; //compatible with quantiles sketch
+ 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.
+ */
+ BaseKllSketch(final int k, final int m, final boolean compatible) {
+ checkK(k);
+ k_ = k;
+ minK_ = k;
+ m_ = m;
+ numLevels_ = 1;
+ levels_ = new int[] {k, k};
+ isLevelZeroSorted_ = false;
+ this.compatible = compatible;
+ }
+
+ // public functions
+
+ /**
+ * Returns the parameter k
+ * @return parameter k
+ */
+ public int getK() {
+ return k_;
+ }
+
+ /**
+ * Gets the approximate value of <em>k</em> to use given epsilon, the normalized rank error.
+ * @param epsilon the normalized rank error between zero and one.
+ * @param pmf if true, this function returns the value of <em>k</em> assuming the input epsilon
+ * is the desired "double-sided" epsilon for the getPMF() function. Otherwise, this function
+ * returns the value of <em>k</em> assuming the input epsilon is the desired "single-sided"
+ * epsilon for all the other queries.
+ * @return the value of <i>k</i> given a value of epsilon.
+ * @see KllDoublesSketch
+ */
+ // constants were derived as the best fit to 99 percentile empirically measured max error in
+ // thousands of trials
+ public static int getKFromEpsilon(final double epsilon, final boolean pmf) {
+ //Ensure that eps is >= than the lowest possible eps given MAX_K and pmf=false.
+ final double eps = max(epsilon, 4.7634E-5);
+ final double kdbl = pmf
+ ? exp(log(2.446 / eps) / 0.9433)
+ : exp(log(2.296 / eps) / 0.9723);
+ final double krnd = round(kdbl);
+ final double del = abs(krnd - kdbl);
+ final int k = (int) (del < 1E-6 ? krnd : ceil(kdbl));
+ return max(MIN_K, min(MAX_K, k));
+ }
+
+ /**
+ * Returns the length of the input stream.
+ * @return stream length
+ */
+ public long getN() {
+ return n_;
+ }
+
+ /**
+ * Gets the approximate rank error of this sketch normalized as a fraction between zero and one.
+ * @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, returns the normalized rank error for the getPMF() function.
+ * Otherwise, it is the "single-sided" normalized rank error for all the other queries.
+ * @see KllDoublesSketch
+ */
+ public double getNormalizedRankError(final boolean pmf) {
+ return getNormalizedRankError(minK_, pmf);
+ }
+
+ /**
+ * 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
+ public static double getNormalizedRankError(final int k, final boolean pmf) {
+ return pmf
+ ? 2.446 / pow(k, 0.9433)
+ : 2.296 / pow(k, 0.9723);
+ }
+
+ /**
+ * Returns the number of retained items (samples) in the sketch.
+ * @return the number of retained items (samples) in the sketch
+ */
+ public int getNumRetained() {
+ return levels_[numLevels_] - levels_[0];
+ }
+
+ /**
+ * Returns true if this sketch is empty.
+ * @return empty flag
+ */
+ public boolean isEmpty() {
+ return n_ == 0;
+ }
+
+ /**
+ * Returns true if this sketch is in estimation mode.
+ * @return estimation mode flag
+ */
+ public boolean isEstimationMode() {
+ return numLevels_ > 1;
+ }
+
+ /**
+ * Returns serialized sketch in a compact byte array form.
+ * @return serialized sketch in a compact byte array form.
+ */
+ public abstract byte[] toByteArray();
+
+
+ @Override
+ public String toString() {
+ return toString(false, false);
+ }
+
+ /**
+ * Returns a summary of the sketch as a string.
+ * @param withLevels if true include information about levels
+ * @param withData if true include sketch data
+ * @return string representation of sketch summary
+ */
+ 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.
+ */
+ private 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++;
+ }
+ }
Review comment:
Does the compaction always work top down ie start at level 0?
##########
File path: src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
##########
@@ -287,32 +74,22 @@ public KllDoublesSketch(final int k) {
* @param m minimum level size. Default is 8.
*/
private KllDoublesSketch(final int k, final int m, final boolean compatible) {
- checkK(k);
- k_ = k;
- minK_ = k;
- m_ = m;
- numLevels_ = 1;
- levels_ = new int[] {k, k};
+ super(k, m, compatible);
items_ = new double[k];
minValue_ = Double.NaN;
maxValue_ = Double.NaN;
- isLevelZeroSorted_ = false;
- this.compatible = compatible;
-
}
/**
- * Off-heap constructor.
+ * Private heapify constructor.
* @param mem Memory object that contains data serialized by this sketch.
*/
private KllDoublesSketch(final Memory mem) {
- m_ = DEFAULT_M;
- k_ = mem.getShort(K_SHORT) & 0xffff;
+ super(mem.getShort(K_SHORT) & 0xffff, DEFAULT_M, true);
Review comment:
I don't understand where the preamble is handled here, is it handled in the public heapify method first?
##########
File path: src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
##########
@@ -0,0 +1,324 @@
+/*
+ * 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 java.lang.Math.abs;
+import static java.lang.Math.ceil;
+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 java.util.Random;
+
+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.
+ *
+ * Invariants:
+ * 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
+ * 2) After a compaction, (sum of capacities) - (sum of items) >= 1,
+ * 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.
+ */
+
+ final int k_; // configured value of K
+ final int m_; // configured minimum buffer "width", Must always be DEFAULT_M for now.
+
+ int minK_; // for error estimation after merging with different k
+ long n_; // number of items input into this sketch
+ int numLevels_; // one-based number of current levels,
+ int[] levels_; // array of index offsets into the items[]. Size = numLevels + 1.
+ boolean isLevelZeroSorted_;
+
+ final boolean compatible; //compatible with quantiles sketch
+ 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.
+ */
+ BaseKllSketch(final int k, final int m, final boolean compatible) {
+ checkK(k);
+ k_ = k;
+ minK_ = k;
+ m_ = m;
+ numLevels_ = 1;
+ levels_ = new int[] {k, k};
+ isLevelZeroSorted_ = false;
+ this.compatible = compatible;
+ }
Review comment:
Why does checkK not use m as parameter to verify lower bound - as per the comment on k being in the range [m, 2^16]?
##########
File path: src/main/java/org/apache/datasketches/kll/KllHelper.java
##########
@@ -65,24 +65,24 @@ static int computeTotalCapacity(final int k, final int m, final int numLevels) {
}
/**
- * Returns the capacity of a specific level.
+ * Returns the item capacity of a specific level.
* @param k the accuracy parameter of the sketch. Maximum is 2^29.
* @param numLevels the number of current levels in the sketch. Maximum is 61.
* @param height the zero-based index of a level with respect to the smallest level.
* This varies from 0 to 60.
- * @param minWidth the minimum level width. Default is 8.
+ * @param m the minimum level width. Default is 8.
* @return the capacity of a specific level
*/
- static int levelCapacity(final int k, final int numLevels, final int height, final int minWidth) {
+ static int levelCapacity(final int k, final int numLevels, final int height, final int m) {
assert (k <= (1 << 29));
assert (numLevels >= 1) && (numLevels <= 61);
assert (height >= 0) && (height < numLevels);
final int depth = numLevels - height - 1;
- return (int) Math.max(minWidth, intCapAux(k, depth));
+ return (int) Math.max(m, intCapAux(k, depth));
Review comment:
Is there a reason that you renamed `minWidth` to m, which conveys less information than the former version?
##########
File path: src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
##########
@@ -0,0 +1,324 @@
+/*
+ * 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 java.lang.Math.abs;
+import static java.lang.Math.ceil;
+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 java.util.Random;
+
+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.
+ *
+ * Invariants:
+ * 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
+ * 2) After a compaction, (sum of capacities) - (sum of items) >= 1,
+ * 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.
+ */
Review comment:
Concerning point 2, does the `sum of capacities` refer to the size capacity available? Similarly, would summing the items refer to the size of the items or the actual float or double values?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r811445563
##########
File path: src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
##########
@@ -762,65 +447,51 @@ public void merge(final KllDoublesSketch other) {
if (Double.isNaN(maxValue_) || other.maxValue_ > maxValue_) { maxValue_ = other.maxValue_; }
n_ = finalN;
- assertCorrectTotalWeight();
+ assert KllHelper.sumTheSampleWeights(numLevels_, levels_) == n_;
Review comment:
It is an invariant as well as another invariant that I added to that text in the BaseKllSketch class.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho merged pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho merged pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#issuecomment-1049438084
The Java Valhalla project hopes to eliminate a number of these restrictions.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r811445629
##########
File path: src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
##########
@@ -0,0 +1,324 @@
+/*
+ * 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 java.lang.Math.abs;
+import static java.lang.Math.ceil;
+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 java.util.Random;
+
+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.
+ *
+ * Invariants:
+ * 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
+ * 2) After a compaction, (sum of capacities) - (sum of items) >= 1,
+ * 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.
+ */
+
+ final int k_; // configured value of K
+ final int m_; // configured minimum buffer "width", Must always be DEFAULT_M for now.
+
+ int minK_; // for error estimation after merging with different k
+ long n_; // number of items input into this sketch
+ int numLevels_; // one-based number of current levels,
+ int[] levels_; // array of index offsets into the items[]. Size = numLevels + 1.
+ boolean isLevelZeroSorted_;
+
+ final boolean compatible; //compatible with quantiles sketch
+ 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.
+ */
+ BaseKllSketch(final int k, final int m, final boolean compatible) {
+ checkK(k);
+ k_ = k;
+ minK_ = k;
+ m_ = m;
+ numLevels_ = 1;
+ levels_ = new int[] {k, k};
+ isLevelZeroSorted_ = false;
+ this.compatible = compatible;
+ }
+
+ // public functions
+
+ /**
+ * Returns the parameter k
+ * @return parameter k
+ */
+ public int getK() {
+ return k_;
+ }
+
+ /**
+ * Gets the approximate value of <em>k</em> to use given epsilon, the normalized rank error.
+ * @param epsilon the normalized rank error between zero and one.
+ * @param pmf if true, this function returns the value of <em>k</em> assuming the input epsilon
+ * is the desired "double-sided" epsilon for the getPMF() function. Otherwise, this function
+ * returns the value of <em>k</em> assuming the input epsilon is the desired "single-sided"
+ * epsilon for all the other queries.
+ * @return the value of <i>k</i> given a value of epsilon.
+ * @see KllDoublesSketch
+ */
+ // constants were derived as the best fit to 99 percentile empirically measured max error in
+ // thousands of trials
+ public static int getKFromEpsilon(final double epsilon, final boolean pmf) {
+ //Ensure that eps is >= than the lowest possible eps given MAX_K and pmf=false.
+ final double eps = max(epsilon, 4.7634E-5);
+ final double kdbl = pmf
+ ? exp(log(2.446 / eps) / 0.9433)
+ : exp(log(2.296 / eps) / 0.9723);
+ final double krnd = round(kdbl);
+ final double del = abs(krnd - kdbl);
+ final int k = (int) (del < 1E-6 ? krnd : ceil(kdbl));
+ return max(MIN_K, min(MAX_K, k));
+ }
+
+ /**
+ * Returns the length of the input stream.
+ * @return stream length
+ */
+ public long getN() {
+ return n_;
+ }
+
+ /**
+ * Gets the approximate rank error of this sketch normalized as a fraction between zero and one.
+ * @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, returns the normalized rank error for the getPMF() function.
+ * Otherwise, it is the "single-sided" normalized rank error for all the other queries.
+ * @see KllDoublesSketch
+ */
+ public double getNormalizedRankError(final boolean pmf) {
+ return getNormalizedRankError(minK_, pmf);
+ }
+
+ /**
+ * 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
+ public static double getNormalizedRankError(final int k, final boolean pmf) {
+ return pmf
+ ? 2.446 / pow(k, 0.9433)
+ : 2.296 / pow(k, 0.9723);
+ }
+
+ /**
+ * Returns the number of retained items (samples) in the sketch.
+ * @return the number of retained items (samples) in the sketch
+ */
+ public int getNumRetained() {
+ return levels_[numLevels_] - levels_[0];
+ }
+
+ /**
+ * Returns true if this sketch is empty.
+ * @return empty flag
+ */
+ public boolean isEmpty() {
+ return n_ == 0;
+ }
+
+ /**
+ * Returns true if this sketch is in estimation mode.
+ * @return estimation mode flag
+ */
+ public boolean isEstimationMode() {
+ return numLevels_ > 1;
+ }
+
+ /**
+ * Returns serialized sketch in a compact byte array form.
+ * @return serialized sketch in a compact byte array form.
+ */
+ public abstract byte[] toByteArray();
+
+
+ @Override
+ public String toString() {
+ return toString(false, false);
+ }
+
+ /**
+ * Returns a summary of the sketch as a string.
+ * @param withLevels if true include information about levels
+ * @param withData if true include sketch data
+ * @return string representation of sketch summary
+ */
+ 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.
+ */
+ private 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++;
+ }
+ }
Review comment:
Yes. If you study the compaction algorithm (designed by Kevin Lang), it is quite clever. You can use the test called _visualCheck()_ in the MiscDoublesTest class, and/or _toString(true,true)_ to help you understand how it works.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r811438650
##########
File path: src/main/java/org/apache/datasketches/kll/BaseKllSketch.java
##########
@@ -0,0 +1,324 @@
+/*
+ * 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 java.lang.Math.abs;
+import static java.lang.Math.ceil;
+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 java.util.Random;
+
+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.
+ *
+ * Invariants:
+ * 1) After a compaction, or an update, or a merge, all levels are sorted except for level zero.
+ * 2) After a compaction, (sum of capacities) - (sum of items) >= 1,
+ * 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.
+ */
+
+ final int k_; // configured value of K
+ final int m_; // configured minimum buffer "width", Must always be DEFAULT_M for now.
+
+ int minK_; // for error estimation after merging with different k
+ long n_; // number of items input into this sketch
+ int numLevels_; // one-based number of current levels,
+ int[] levels_; // array of index offsets into the items[]. Size = numLevels + 1.
+ boolean isLevelZeroSorted_;
+
+ final boolean compatible; //compatible with quantiles sketch
+ 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.
+ */
+ BaseKllSketch(final int k, final int m, final boolean compatible) {
+ checkK(k);
+ k_ = k;
+ minK_ = k;
+ m_ = m;
+ numLevels_ = 1;
+ levels_ = new int[] {k, k};
+ isLevelZeroSorted_ = false;
+ this.compatible = compatible;
+ }
Review comment:
MIN_K = DEFAULT_M = 8. This is an artifact of the design. In theory, this allows the possibility that in the future we might choose MIN_K > DEFAULT_M. And the possibility that in the future, we could change the value of DEFAULT_M. In fact, we could probably substitute DEFAULT_M for _m_ everywhere in the code because we are not allowing it to be anything else.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r811451517
##########
File path: src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
##########
@@ -287,32 +74,22 @@ public KllDoublesSketch(final int k) {
* @param m minimum level size. Default is 8.
*/
private KllDoublesSketch(final int k, final int m, final boolean compatible) {
- checkK(k);
- k_ = k;
- minK_ = k;
- m_ = m;
- numLevels_ = 1;
- levels_ = new int[] {k, k};
+ super(k, m, compatible);
items_ = new double[k];
minValue_ = Double.NaN;
maxValue_ = Double.NaN;
- isLevelZeroSorted_ = false;
- this.compatible = compatible;
-
}
/**
- * Off-heap constructor.
+ * Private heapify constructor.
* @param mem Memory object that contains data serialized by this sketch.
*/
private KllDoublesSketch(final Memory mem) {
- m_ = DEFAULT_M;
- k_ = mem.getShort(K_SHORT) & 0xffff;
+ super(mem.getShort(K_SHORT) & 0xffff, DEFAULT_M, true);
Review comment:
The public static heapify does all the checking of the PreambleInts, SerVer, FamID and Flags. Once these are determined to be correct, the private constructor, KllDoublesSketch(mem) does the work of populating the sketch on the heap. The sketch in memory (heap) doesn't care about the PreambleInts, SerVer, FamID fields as those are only used to validate the serialized image, which can be stored anywhere (disk, off-heap, etc.).
The key non-static variables of the sketch are initialized by the BaseKllSketch constructor, and then changed as necessary by the remainder of the private KllDoublesSketch(mem) construtor.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#issuecomment-1047262155
These comments were very helpful. I made a few minor code comment changes to improve the documentation. No code changes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#issuecomment-1049437598
> Does the library always use concrete primitives instead of generics because of the performance overhead for using generics? Would this also be the case with C++?
Current versions of Java Generics require generic variables to be Objects. Boxing of primitives is space and time inefficient. Serializing Generic objects is also inefficient. This is why we try not to use them. Nonetheless, we do have a few sketches that have also been implemented as Generic classes for those cases where the standard primitives are too limiting. But these sketches cannot operate off heap.
C++ does not have any of these limitations.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
leerho commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r811452534
##########
File path: src/main/java/org/apache/datasketches/kll/KllHelper.java
##########
@@ -65,24 +65,24 @@ static int computeTotalCapacity(final int k, final int m, final int numLevels) {
}
/**
- * Returns the capacity of a specific level.
+ * Returns the item capacity of a specific level.
* @param k the accuracy parameter of the sketch. Maximum is 2^29.
* @param numLevels the number of current levels in the sketch. Maximum is 61.
* @param height the zero-based index of a level with respect to the smallest level.
* This varies from 0 to 60.
- * @param minWidth the minimum level width. Default is 8.
+ * @param m the minimum level width. Default is 8.
* @return the capacity of a specific level
*/
- static int levelCapacity(final int k, final int numLevels, final int height, final int minWidth) {
+ static int levelCapacity(final int k, final int numLevels, final int height, final int m) {
assert (k <= (1 << 29));
assert (numLevels >= 1) && (numLevels <= 61);
assert (height >= 0) && (height < numLevels);
final int depth = numLevels - height - 1;
- return (int) Math.max(minWidth, intCapAux(k, depth));
+ return (int) Math.max(m, intCapAux(k, depth));
Review comment:
The variable "m" is used everywhere else in the sketch and is defined multiples places as well. I see no need to have another variable name that means the same thing, which adds confusion. (How is minWidth different from m?) The answer is that it is not!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] davecromberge commented on a change in pull request #389: Refactor kll
Posted by GitBox <gi...@apache.org>.
davecromberge commented on a change in pull request #389:
URL: https://github.com/apache/datasketches-java/pull/389#discussion_r812639196
##########
File path: src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
##########
@@ -287,32 +74,22 @@ public KllDoublesSketch(final int k) {
* @param m minimum level size. Default is 8.
*/
private KllDoublesSketch(final int k, final int m, final boolean compatible) {
- checkK(k);
- k_ = k;
- minK_ = k;
- m_ = m;
- numLevels_ = 1;
- levels_ = new int[] {k, k};
+ super(k, m, compatible);
items_ = new double[k];
minValue_ = Double.NaN;
maxValue_ = Double.NaN;
- isLevelZeroSorted_ = false;
- this.compatible = compatible;
-
}
/**
- * Off-heap constructor.
+ * Private heapify constructor.
* @param mem Memory object that contains data serialized by this sketch.
*/
private KllDoublesSketch(final Memory mem) {
- m_ = DEFAULT_M;
- k_ = mem.getShort(K_SHORT) & 0xffff;
+ super(mem.getShort(K_SHORT) & 0xffff, DEFAULT_M, true);
Review comment:
This design makes a lot of sense.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org