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 2023/12/17 19:26:52 UTC
(datasketches-java) branch remove_duplicate_code created (now 677e1da8)
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a change to branch remove_duplicate_code
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
at 677e1da8 By adding 3 small package-private methods I was able to eliminate a whole bunch of duplicate code in KLL.
This branch includes the following new commits:
new 677e1da8 By adding 3 small package-private methods I was able to eliminate a whole bunch of duplicate code in KLL.
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
(datasketches-java) 01/01: By adding 3 small package-private methods I was able to eliminate a whole bunch of duplicate code in KLL.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch remove_duplicate_code
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 677e1da812901664dad2823790c401d4203e0474
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Sun Dec 17 11:26:35 2023 -0800
By adding 3 small package-private methods I was able to eliminate a
whole bunch of duplicate code in KLL.
Plus some other code cleanup and javadoc cleanup.
Changes to some test code to help with diagnostic understanding of the
operation of the sketch.
---
.../kll/KllDirectCompactItemsSketch.java | 20 ++
.../datasketches/kll/KllDirectDoublesSketch.java | 20 +-
.../datasketches/kll/KllDirectFloatsSketch.java | 18 ++
.../apache/datasketches/kll/KllDoublesHelper.java | 8 +-
.../apache/datasketches/kll/KllFloatsHelper.java | 8 +-
.../datasketches/kll/KllHeapDoublesSketch.java | 20 ++
.../datasketches/kll/KllHeapFloatsSketch.java | 20 ++
.../datasketches/kll/KllHeapItemsSketch.java | 20 ++
.../org/apache/datasketches/kll/KllHelper.java | 225 ++++++---------------
.../apache/datasketches/kll/KllItemsHelper.java | 8 +-
.../org/apache/datasketches/kll/KllSketch.java | 27 ++-
.../quantilescommon/QuantilesDoublesAPI.java | 8 +-
.../datasketches/kll/KllMiscDoublesTest.java | 65 +++++-
13 files changed, 274 insertions(+), 193 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java b/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java
index b8d91fef..443ff4ae 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java
@@ -65,6 +65,14 @@ final class KllDirectCompactItemsSketch<T> extends KllItemsSketch<T> {
levelsArr = memVal.levelsArr; //always converted to writable form.
}
+ //End of constructors
+
+ @Override
+ String getItemAsString(final int index) {
+ if (isEmpty()) { return "Null"; }
+ return serDe.toString(getTotalItemsArray()[index]);
+ }
+
@Override
public int getK() {
return getMemoryK(mem);
@@ -83,6 +91,12 @@ final class KllDirectCompactItemsSketch<T> extends KllItemsSketch<T> {
return serDe.deserializeFromMemory(mem, offset, 2)[1];
}
+ @Override
+ String getMaxItemAsString() {
+ if (isEmpty()) { return "Null"; }
+ return serDe.toString(getMaxItem());
+ }
+
@Override
public T getMinItem() {
if (sketchStructure == COMPACT_EMPTY || isEmpty()) {
@@ -96,6 +110,12 @@ final class KllDirectCompactItemsSketch<T> extends KllItemsSketch<T> {
return serDe.deserializeFromMemory(mem, offset, 1)[0];
}
+ @Override
+ String getMinItemAsString() {
+ if (isEmpty()) { return "Null"; }
+ return serDe.toString(getMinItem());
+ }
+
@Override
public long getN() {
if (sketchStructure == COMPACT_EMPTY) { return 0; }
diff --git a/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java
index 64e340d9..21a46069 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java
@@ -116,7 +116,13 @@ class KllDirectDoublesSketch extends KllDoublesSketch {
return new KllDirectDoublesSketch(UPDATABLE, wMem, memReqSvr, memVal);
}
- //END of Constructors
+ //End of constructors
+
+ @Override
+ String getItemAsString(final int index) {
+ if (isEmpty()) { return "NaN"; }
+ return Double.toString(getDoubleItemsArray()[index]);
+ }
@Override
public int getK() {
@@ -137,6 +143,12 @@ class KllDirectDoublesSketch extends KllDoublesSketch {
return wmem.getDouble(offset);
}
+ @Override
+ String getMaxItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Double.toString(getMaxItem());
+ }
+
@Override
public double getMinItem() {
int levelsArrBytes = 0;
@@ -151,6 +163,12 @@ class KllDirectDoublesSketch extends KllDoublesSketch {
return wmem.getDouble(offset);
}
+ @Override
+ String getMinItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Double.toString(getMinItem());
+ }
+
@Override
public long getN() {
if (sketchStructure == COMPACT_EMPTY) { return 0; }
diff --git a/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java
index c8665147..542eda59 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java
@@ -118,6 +118,12 @@ class KllDirectFloatsSketch extends KllFloatsSketch {
//END of Constructors
+ @Override
+ String getItemAsString(final int index) {
+ if (isEmpty()) { return "NaN"; }
+ return Float.toString(getFloatItemsArray()[index]);
+ }
+
@Override
public int getK() {
return getMemoryK(wmem);
@@ -137,6 +143,12 @@ class KllDirectFloatsSketch extends KllFloatsSketch {
return wmem.getFloat(offset);
}
+ @Override
+ String getMaxItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Float.toString(getMaxItem());
+ }
+
@Override
public float getMinItem() {
int levelsArrBytes = 0;
@@ -151,6 +163,12 @@ class KllDirectFloatsSketch extends KllFloatsSketch {
return wmem.getFloat(offset);
}
+ @Override
+ String getMinItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Float.toString(getMinItem());
+ }
+
@Override
public long getN() {
if (sketchStructure == COMPACT_EMPTY) { return 0; }
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
index 49bfe220..9f5c3732 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java
@@ -309,12 +309,12 @@ final class KllDoublesHelper {
dblSk.setMinItem(min(dblSk.getMinItem(), item));
dblSk.setMaxItem(max(dblSk.getMaxItem(), item));
}
- if (dblSk.levelsArr[0] == 0) { compressWhileUpdatingSketch(dblSk); }
- final int myLevelsArrAtZero = dblSk.levelsArr[0]; //LevelsArr could be expanded
+ final int level0space = dblSk.levelsArr[0];
+ assert level0space >= 0;
+ if (level0space == 0) { compressWhileUpdatingSketch(dblSk); }
dblSk.incN();
dblSk.setLevelZeroSorted(false);
- final int nextPos = myLevelsArrAtZero - 1;
- assert myLevelsArrAtZero >= 0;
+ final int nextPos = level0space - 1;
dblSk.setLevelsArrayAt(0, nextPos);
dblSk.setDoubleItemsArrayAt(nextPos, item);
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
index 9f732e94..cc4e9aca 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java
@@ -309,12 +309,12 @@ final class KllFloatsHelper {
fltSk.setMinItem(min(fltSk.getMinItem(), item));
fltSk.setMaxItem(max(fltSk.getMaxItem(), item));
}
- if (fltSk.levelsArr[0] == 0) { compressWhileUpdatingSketch(fltSk); }
- final int myLevelsArrAtZero = fltSk.levelsArr[0]; //LevelsArr could be expanded
+ final int level0space = fltSk.levelsArr[0];
+ assert level0space >= 0;
+ if (level0space == 0) { compressWhileUpdatingSketch(fltSk); }
fltSk.incN();
fltSk.setLevelZeroSorted(false);
- final int nextPos = myLevelsArrAtZero - 1;
- assert myLevelsArrAtZero >= 0;
+ final int nextPos = level0space - 1;
fltSk.setLevelsArrayAt(0, nextPos);
fltSk.setFloatItemsArrayAt(nextPos, item);
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java
index 61d8243d..df81a34c 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java
@@ -141,6 +141,14 @@ final class KllHeapDoublesSketch extends KllDoublesSketch {
return new KllHeapDoublesSketch(srcMem, memVal);
}
+ //End of constructors
+
+ @Override
+ String getItemAsString(final int index) {
+ if (isEmpty()) { return "NaN"; }
+ return Double.toString(doubleItems[index]);
+ }
+
@Override
public int getK() { return k; }
@@ -150,12 +158,24 @@ final class KllHeapDoublesSketch extends KllDoublesSketch {
return maxDoubleItem;
}
+ @Override
+ String getMaxItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Double.toString(maxDoubleItem);
+ }
+
@Override
public double getMinItem() {
if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
return minDoubleItem;
}
+ @Override
+ String getMinItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Double.toString(minDoubleItem);
+ }
+
@Override
public long getN() { return n; }
diff --git a/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java
index 0af73128..47287185 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java
@@ -141,6 +141,14 @@ final class KllHeapFloatsSketch extends KllFloatsSketch {
return new KllHeapFloatsSketch(srcMem, memVal);
}
+ //End of constructors
+
+ @Override
+ String getItemAsString(final int index) {
+ if (isEmpty()) { return "NaN"; }
+ return Double.toString(floatItems[index]);
+ }
+
@Override
public int getK() { return k; }
@@ -150,12 +158,24 @@ final class KllHeapFloatsSketch extends KllFloatsSketch {
return maxFloatItem;
}
+ @Override
+ String getMaxItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Float.toString(maxFloatItem);
+ }
+
@Override
public float getMinItem() {
if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
return minFloatItem;
}
+ @Override
+ String getMinItemAsString() {
+ if (isEmpty()) { return "NaN"; }
+ return Float.toString(minFloatItem);
+ }
+
@Override
public long getN() { return n; }
diff --git a/src/main/java/org/apache/datasketches/kll/KllHeapItemsSketch.java b/src/main/java/org/apache/datasketches/kll/KllHeapItemsSketch.java
index 4b3c6c7c..3ed776f2 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHeapItemsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHeapItemsSketch.java
@@ -117,6 +117,14 @@ final class KllHeapItemsSketch<T> extends KllItemsSketch<T> {
}
}
+ //End of constructors
+
+ @Override
+ String getItemAsString(final int index) {
+ if (isEmpty()) { return "Null"; }
+ return serDe.toString((T)(itemsArr[index]));
+ }
+
@Override
public int getK() {
return k;
@@ -128,12 +136,24 @@ final class KllHeapItemsSketch<T> extends KllItemsSketch<T> {
return maxItem;
}
+ @Override
+ String getMaxItemAsString() {
+ if (isEmpty()) { return "Null"; }
+ return serDe.toString(maxItem);
+ }
+
@Override
public T getMinItem() {
if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
return minItem;
}
+ @Override
+ String getMinItemAsString() {
+ if (isEmpty()) { return "Null"; }
+ return serDe.toString(minItem);
+ }
+
@Override
public long getN() {
return n;
diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java
index 4127c9f1..a73c5caf 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java
@@ -47,7 +47,6 @@ import java.util.Arrays;
import org.apache.datasketches.common.ArrayOfItemsSerDe;
import org.apache.datasketches.common.SketchesArgumentException;
-import org.apache.datasketches.common.Util;
import org.apache.datasketches.kll.KllSketch.SketchStructure;
import org.apache.datasketches.kll.KllSketch.SketchType;
import org.apache.datasketches.memory.WritableBuffer;
@@ -58,8 +57,14 @@ import org.apache.datasketches.memory.WritableMemory;
*
* @author Lee Rhodes
*/
-@SuppressWarnings("unchecked")
final class KllHelper {
+ public static final String LS = System.getProperty("line.separator");
+ static final double EPS_DELTA_THRESHOLD = 1E-6;
+ static final double MIN_EPS = 4.7634E-5;
+ static final double PMF_COEF = 2.446;
+ static final double PMF_EXP = 0.9433;
+ static final double CDF_COEF = 2.296;
+ static final double CDF_EXP = 0.9723;
static class GrowthStats {
SketchType sketchType;
@@ -85,13 +90,6 @@ final class KllHelper {
}
}
- static final double EPS_DELTA_THRESHOLD = 1E-6;
- static final double MIN_EPS = 4.7634E-5;
- static final double PMF_COEF = 2.446;
- static final double PMF_EXP = 0.9433;
- static final double CDF_COEF = 2.296;
- static final double CDF_EXP = 0.9723;
-
/**
* This is the exact powers of 3 from 3^0 to 3^30 where the exponent is the index
*/
@@ -313,7 +311,7 @@ final class KllHelper {
assert (k <= (1 << 29));
assert (numLevels >= 1) && (numLevels <= 61);
assert (level >= 0) && (level < numLevels);
- final int depth = numLevels - level - 1;
+ final int depth = numLevels - level - 1; //depth is # levels from the top level (= 0)
return (int) Math.max(m, intCapAux(k, depth));
}
@@ -359,108 +357,44 @@ final class KllHelper {
return newWmem;
}
- private static <T> String outputItemsData(final int numLevels, final int[] levelsArr, final Object[] itemsArr,
- final ArrayOfItemsSerDe<T> serDe) {
- final StringBuilder sb = new StringBuilder();
- sb.append("### KLL items data {index, item}:").append(Util.LS);
- if (levelsArr[0] > 0) {
- sb.append(" Empty/Garbage:" + Util.LS);
- for (int i = 0; i < levelsArr[0]; i++) {
- sb.append(" ").append(i + ", ").append(serDe.toString((T)itemsArr[i])).append(Util.LS);
- }
- }
- int level = 0;
- while (level < numLevels) {
- final int fromIndex = levelsArr[level];
- final int toIndex = levelsArr[level + 1]; // exclusive
- if (fromIndex < toIndex) {
- sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level));
- sb.append(Util.LS);
- }
-
- for (int i = fromIndex; i < toIndex; i++) {
- sb.append(" ").append(i + ", ").append(serDe.toString((T)itemsArr[i])).append(Util.LS);
- }
- level++;
- }
- sb.append(" level[" + level + "]: offset: " + levelsArr[level] + " (Exclusive)");
- sb.append(Util.LS);
- sb.append("### End items data").append(Util.LS);
- return sb.toString();
-
- }
-
- private static String outputDoublesData(final int numLevels, final int[] levelsArr, final double[] doubleItemsArr) {
- final StringBuilder sb = new StringBuilder();
- sb.append("### KLL items data {index, item}:").append(Util.LS);
- if (levelsArr[0] > 0) {
- sb.append(" Empty/Garbage:" + Util.LS);
- for (int i = 0; i < levelsArr[0]; i++) {
- sb.append(" ").append(i + ", ").append(doubleItemsArr[i]).append(Util.LS);
- }
- }
- int level = 0;
- while (level < numLevels) {
- final int fromIndex = levelsArr[level];
- final int toIndex = levelsArr[level + 1]; // exclusive
- if (fromIndex < toIndex) {
- sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level));
- sb.append(Util.LS);
- }
-
- for (int i = fromIndex; i < toIndex; i++) {
- sb.append(" ").append(i + ", ").append(doubleItemsArr[i]).append(Util.LS);
- }
- level++;
- }
- sb.append(" level[" + level + "]: offset: " + levelsArr[level] + " (Exclusive)");
- sb.append(Util.LS);
- sb.append("### End items data").append(Util.LS);
- return sb.toString();
- }
-
- private static String outputFloatsData(final int numLevels, final int[] levelsArr, final float[] floatsItemsArr) {
+ private static String outputData(final KllSketch sketch) {
+ final int[] levelsArr = sketch.getLevelsArray(sketch.sketchStructure);
+ final int numLevels = sketch.getNumLevels();
+ final int k = sketch.getK();
+ final int m = sketch.getM();
final StringBuilder sb = new StringBuilder();
- sb.append("### KLL items data {index, item}:").append(Util.LS);
+ sb.append("### KllSketch itemsArray & levelsArray data:").append(LS);
+ sb.append("Index, Value").append(LS);
if (levelsArr[0] > 0) {
- sb.append(" Empty/Garbage:" + Util.LS);
+ final String gbg = " Empty or Garbage, size = " + levelsArr[0];
for (int i = 0; i < levelsArr[0]; i++) {
- sb.append(" ").append(i + ", ").append(floatsItemsArr[i]).append(Util.LS);
+ sb.append(" ").append(i + ", ").append(sketch.getItemAsString(i));
+ if (i == 0) { sb.append(gbg); }
+ sb.append(LS);
}
}
int level = 0;
while (level < numLevels) {
final int fromIndex = levelsArr[level];
final int toIndex = levelsArr[level + 1]; // exclusive
+ String lvlData = "";
if (fromIndex < toIndex) {
- sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level));
- sb.append(Util.LS);
+ lvlData = " level[" + level + "]=" + levelsArr[level]
+ + ", cap=" + KllHelper.levelCapacity(k, numLevels, level, m)
+ + ", size=" + KllHelper.currentLevelSizeItems(level, numLevels, levelsArr)
+ + ", wt=" + (1 << level) + LS;
}
for (int i = fromIndex; i < toIndex; i++) {
- sb.append(" ").append(i + ", ").append(floatsItemsArr[i]).append(Util.LS);
+ sb.append(" ").append(i + ", ").append(sketch.getItemAsString(i));
+ if (i == fromIndex) { sb.append(lvlData); } else { sb.append(LS); }
}
level++;
}
- sb.append(" level[" + level + "]: offset: " + levelsArr[level] + " (Exclusive)");
- sb.append(Util.LS);
- sb.append("### End items data").append(Util.LS);
- return sb.toString();
- }
+ sb.append(" ----------level[" + level + "]=" + levelsArr[level] + ": itemsArray[].length");
+ sb.append(LS);
+ sb.append("### End data").append(LS);
- static String outputLevels(final int k, final int m, final int numLevels, final int[] levelsArr) {
- final StringBuilder sb = new StringBuilder();
- sb.append("### KLL levels array:").append(Util.LS)
- .append(" level, offset: nominal capacity, actual size").append(Util.LS);
- int level = 0;
- for ( ; level < numLevels; level++) {
- sb.append(" ").append(level).append(", ").append(levelsArr[level]).append(": ")
- .append(KllHelper.levelCapacity(k, numLevels, level, m))
- .append(", ").append(KllHelper.currentLevelSizeItems(level, numLevels, levelsArr)).append(Util.LS);
- }
- sb.append(" ").append(level).append(", ").append(levelsArr[level]).append(": (Exclusive)")
- .append(Util.LS);
- sb.append("### End levels array").append(Util.LS);
return sb.toString();
}
@@ -541,7 +475,7 @@ final class KllHelper {
return bytesOut;
}
- static <T> String toStringImpl(final KllSketch sketch, final boolean withLevels, final boolean withData,
+ static <T> String toStringImpl(final KllSketch sketch, final boolean withSummary, final boolean withData,
final ArrayOfItemsSerDe<T> serDe) {
final SketchType sketchType = sketch.sketchType;
final boolean hasMemory = sketch.hasMemory();
@@ -562,70 +496,36 @@ final class KllHelper {
final String skTypeStr = sketchType.getName();
final String className = "Kll" + directStr + compactStr + skTypeStr;
- sb.append(Util.LS).append("### ").append(className).append(" Summary:").append(Util.LS);
- sb.append(" K : ").append(k).append(Util.LS);
- sb.append(" Dynamic min K : ").append(sketch.getMinK()).append(Util.LS);
- sb.append(" M : ").append(m).append(Util.LS);
- sb.append(" N : ").append(n).append(Util.LS);
- sb.append(" Epsilon : ").append(epsPct).append(Util.LS);
- sb.append(" Epsilon PMF : ").append(epsPMFPct).append(Util.LS);
- sb.append(" Empty : ").append(sketch.isEmpty()).append(Util.LS);
- sb.append(" Estimation Mode : ").append(sketch.isEstimationMode()).append(Util.LS);
- sb.append(" Levels : ").append(numLevels).append(Util.LS);
- sb.append(" Level 0 Sorted : ").append(sketch.isLevelZeroSorted()).append(Util.LS);
- sb.append(" Capacity Items : ").append(fullLevelsArr[numLevels]).append(Util.LS);
- sb.append(" Retained Items : ").append(sketch.getNumRetained()).append(Util.LS);
- sb.append(" Empty/Garbage Items : ").append(sketch.levelsArr[0]).append(Util.LS);
- sb.append(" ReadOnly : ").append(readOnlyStr).append(Util.LS);
+ sb.append(LS).append("### ").append(className).append(" Summary:").append(LS);
+ sb.append(" K : ").append(k).append(LS);
+ sb.append(" Dynamic min K : ").append(sketch.getMinK()).append(LS);
+ sb.append(" M : ").append(m).append(LS);
+ sb.append(" N : ").append(n).append(LS);
+ sb.append(" Epsilon : ").append(epsPct).append(LS);
+ sb.append(" Epsilon PMF : ").append(epsPMFPct).append(LS);
+ sb.append(" Empty : ").append(sketch.isEmpty()).append(LS);
+ sb.append(" Estimation Mode : ").append(sketch.isEstimationMode()).append(LS);
+ sb.append(" Levels : ").append(numLevels).append(LS);
+ sb.append(" Level 0 Sorted : ").append(sketch.isLevelZeroSorted()).append(LS);
+ sb.append(" Capacity Items : ").append(fullLevelsArr[numLevels]).append(LS);
+ sb.append(" Retained Items : ").append(sketch.getNumRetained()).append(LS);
+ sb.append(" Empty/Garbage Items : ").append(sketch.levelsArr[0]).append(LS);
+ sb.append(" ReadOnly : ").append(readOnlyStr).append(LS);
if (sketchType != ITEMS_SKETCH) {
- sb.append(" Updatable Storage Bytes: ").append(sketch.currentSerializedSizeBytes(true))
- .append(Util.LS);
+ sb.append(" Updatable Storage Bytes: ").append(sketch.currentSerializedSizeBytes(true)).append(LS);
}
- sb.append(" Compact Storage Bytes : ").append(sketch.currentSerializedSizeBytes(false))
- .append(Util.LS);
+ sb.append(" Compact Storage Bytes : ").append(sketch.currentSerializedSizeBytes(false)).append(LS);
- if (sketchType == DOUBLES_SKETCH) {
- final KllDoublesSketch dblSk = (KllDoublesSketch) sketch;
- sb.append(" Min Item : ").append(dblSk.isEmpty() ? Double.NaN : dblSk.getMinItem())
- .append(Util.LS);
- sb.append(" Max Item : ").append(dblSk.isEmpty() ? Double.NaN : dblSk.getMaxItem())
- .append(Util.LS);
- }
- else if (sketchType == FLOATS_SKETCH) {
- final KllFloatsSketch fltSk = (KllFloatsSketch) sketch;
- sb.append(" Min Item : ").append(fltSk.isEmpty() ? Float.NaN : fltSk.getMinItem())
- .append(Util.LS);
- sb.append(" Max Item : ").append(fltSk.isEmpty() ? Float.NaN : fltSk.getMaxItem())
- .append(Util.LS);
- }
- else { //sketchType == ITEMS_SKETCH
- final KllItemsSketch<T> itmSk = (KllItemsSketch<T>) sketch;
- sb.append(" Min Item : ").append(itmSk.isEmpty() ? "null" : serDe.toString(itmSk.getMinItem()))
- .append(Util.LS);
- sb.append(" Max Item : ").append(itmSk.isEmpty() ? "null" : serDe.toString(itmSk.getMaxItem()))
- .append(Util.LS);
- }
- sb.append("### End sketch summary").append(Util.LS);
+ final String emptyStr = (sketchType == ITEMS_SKETCH) ? "Null" : "NaN";
- if (withLevels) {
- sb.append(outputLevels(k, m, numLevels, fullLevelsArr));
- }
- if (withData) {
- if (sketchType == DOUBLES_SKETCH) {
- final KllDoublesSketch dblSk = (KllDoublesSketch) sketch;
- final double[] myDoubleItemsArr = dblSk.getDoubleItemsArray();
- sb.append(outputDoublesData(numLevels, fullLevelsArr, myDoubleItemsArr));
- } else if (sketchType == FLOATS_SKETCH) {
- final KllFloatsSketch fltSk = (KllFloatsSketch) sketch;
- final float[] myFloatItemsArr = fltSk.getFloatItemsArray();
- sb.append(outputFloatsData(numLevels, fullLevelsArr, myFloatItemsArr));
- }
- else { //sketchType == KllItemsSketch
- final KllItemsSketch<T> itmSk = (KllItemsSketch<T>) sketch;
- final T[] myItemsArr = itmSk.getTotalItemsArray();
- sb.append(outputItemsData(numLevels, fullLevelsArr, myItemsArr, serDe));
- }
- }
+ sb.append(" Min Item : ").append(sketch.isEmpty() ? emptyStr : sketch.getMinItemAsString())
+ .append(LS);
+ sb.append(" Max Item : ").append(sketch.isEmpty() ? emptyStr : sketch.getMaxItemAsString())
+ .append(LS);
+ sb.append("### End sketch summary").append(LS);
+
+ if (! withSummary) { sb.setLength(0); }
+ if (withData) { sb.append(outputData(sketch)); }
return sb.toString();
}
@@ -789,8 +689,9 @@ final class KllHelper {
/**
* Computes the actual item capacity of a given level given its depth index.
* If the depth of levels exceeds 30, this uses a folding technique to accurately compute the
- * actual level capacity up to a depth of 60. Without folding, the internal calculations would
- * exceed the capacity of a long.
+ * actual level capacity up to a depth of 60 (or 61 levels).
+ * Without folding, the internal calculations would exceed the capacity of a long.
+ * This method just decides whether folding is required or not.
* @param k the configured k of the sketch
* @param depth the zero-based index of the level being computed.
* @return the actual capacity of a given level given its depth index.
@@ -806,13 +707,13 @@ final class KllHelper {
/**
* Performs the integer based calculation of an individual level (or folded level).
* @param k the configured k of the sketch
- * @param depth depth the zero-based index of the level being computed.
+ * @param depth the zero-based index of the level being computed. The max depth is 30!
* @return the actual capacity of a given level given its depth index.
*/
private static long intCapAuxAux(final long k, final int depth) {
- final long twok = k << 1; // for rounding pre-multiply by 2
- final long tmp = ((twok << depth) / powersOfThree[depth]);
- final long result = ((tmp + 1L) >>> 1); // add 1 and divide by 2
+ final long twok = k << 1; // for rounding at the end, pre-multiply by 2 here, divide by 2 during rounding.
+ final long tmp = ((twok << depth) / powersOfThree[depth]); //2k* (2/3)^depth. 2k also keeps the fraction larger.
+ final long result = ((tmp + 1L) >>> 1); // (tmp + 1)/2. If odd, round up. This guarantees an integer.
assert (result <= k);
return result;
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java b/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java
index 03bc931a..a1596032 100644
--- a/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java
@@ -305,12 +305,12 @@ final class KllItemsHelper<T> {
itmSk.setMinItem(Util.minT(itmSk.getMinItem(), item, comp));
itmSk.setMaxItem(Util.maxT(itmSk.getMaxItem(), item, comp));
}
- if (itmSk.levelsArr[0] == 0) { compressWhileUpdatingSketch(itmSk); }
- final int myLevelsArrAtZero = itmSk.levelsArr[0]; //LevelsArr could be expanded
+ final int level0space = itmSk.levelsArr[0];
+ assert level0space >= 0;
+ if (level0space == 0) { compressWhileUpdatingSketch(itmSk); }
itmSk.incN();
itmSk.setLevelZeroSorted(false);
- final int nextPos = myLevelsArrAtZero - 1;
- assert myLevelsArrAtZero >= 0;
+ final int nextPos = level0space - 1;
itmSk.setLevelsArrayAt(0, nextPos);
itmSk.setItemsArrayAt(nextPos, item);
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllSketch.java b/src/main/java/org/apache/datasketches/kll/KllSketch.java
index 874d64fa..67f6bb98 100644
--- a/src/main/java/org/apache/datasketches/kll/KllSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllSketch.java
@@ -130,6 +130,13 @@ public abstract class KllSketch implements QuantilesAPI {
this.sketchStructure = sketchStructure;
}
+ /**
+ * Gets the string value of the item at the given index.
+ * @param index the index of the value
+ * @return the string value of the item at the given index.
+ */
+ abstract String getItemAsString(int index);
+
/**
* Gets the approximate <em>k</em> to use given epsilon, the normalized rank error.
* @param epsilon the normalized rank error between zero and one.
@@ -159,6 +166,18 @@ public abstract class KllSketch implements QuantilesAPI {
return updatableMemFormat ? gStats.updatableBytes : gStats.compactBytes;
}
+ /**
+ * Gets the string value of the max item
+ * @return the string value of the max item
+ */
+ abstract String getMaxItemAsString();
+
+ /**
+ * Gets the string value of the min item
+ * @return the string value of the min item
+ */
+ abstract String getMinItemAsString();
+
/**
* Gets the normalized rank error given k and pmf.
* Static method version of the <i>getNormalizedRankError(boolean)</i>.
@@ -262,17 +281,17 @@ public abstract class KllSketch implements QuantilesAPI {
@Override
public final String toString() {
- return toString(false, false);
+ return toString(true, false);
}
/**
* Returns a summary of the sketch as a string.
- * @param withLevels if true include information about levels
+ * @param withSummary if true includes sketch summary information
* @param withData if true include sketch data
* @return string representation of sketch summary
*/
- public String toString(final boolean withLevels, final boolean withData) {
- return KllHelper.toStringImpl(this, withLevels, withData, getSerDe());
+ public String toString(final boolean withSummary, final boolean withData) {
+ return KllHelper.toStringImpl(this, withSummary, withData, getSerDe());
}
//restricted
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/QuantilesDoublesAPI.java b/src/main/java/org/apache/datasketches/quantilescommon/QuantilesDoublesAPI.java
index 31a5bedf..02aab3c6 100644
--- a/src/main/java/org/apache/datasketches/quantilescommon/QuantilesDoublesAPI.java
+++ b/src/main/java/org/apache/datasketches/quantilescommon/QuantilesDoublesAPI.java
@@ -75,8 +75,8 @@ public interface QuantilesDoublesAPI extends QuantilesAPI {
double[] getCDF(double[] splitPoints, QuantileSearchCriteria searchCrit);
/**
- * Returns the maximum item of the stream. This is provided for convenience, but may be different from the largest
- * item retained by the sketch algorithm.
+ * Returns the maximum item of the stream. This is provided for convenience and may be different from the
+ * item returned by <i>getQuantile(1.0)</i>.
*
* @return the maximum item of the stream
* @throws IllegalArgumentException if sketch is empty.
@@ -84,8 +84,8 @@ public interface QuantilesDoublesAPI extends QuantilesAPI {
double getMaxItem();
/**
- * Returns the minimum item of the stream. This is provided for convenience, but is distinct from the smallest
- * item retained by the sketch algorithm.
+ * Returns the minimum item of the stream. This is provided for convenience and may be different from the
+ * item returned by <i>getQuantile(0.0)</i>.
*
* @return the minimum item of the stream
* @throws IllegalArgumentException if sketch is empty.
diff --git a/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
index b6b9801c..aeeb31fd 100644
--- a/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
@@ -40,6 +40,7 @@ import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
+@SuppressWarnings("unused")
public class KllMiscDoublesTest {
static final String LS = System.getProperty("line.separator");
private final MemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
@@ -166,30 +167,74 @@ public class KllMiscDoublesTest {
assertEquals(sk2.getNumRetained(), 56);
}
- @Test //set static enablePrinting = true for visual checking //HERE
+ @Test //set static enablePrinting = true for visual checking
public void viewHeapCompactions() {
int k = 20;
- int n = 21;
+ int n = 108;
+ boolean withSummary = false;
+ boolean withData = true;
int compaction = 0;
KllDoublesSketch sk = KllDoublesSketch.newHeapInstance(k);
for (int i = 1; i <= n; i++) {
- sk.update(1);//i
+ sk.update(i);
if (sk.levelsArr[0] == 0) {
println(LS + "#<<< BEFORE COMPACTION # " + (++compaction) + " >>>");
- println(sk.toString(true, true));
- if (i == n) { break; }
- sk.update(1); ++i; //++i
+ println(sk.toString(withSummary, withData));
+ sk.update(++i);
println(LS + "#<<< AFTER COMPACTION # " + (compaction) + " >>>");
- println(sk.toString(true, true));
- //assertEquals(sk.getDoubleItemsArray()[sk.levelsArr[0]], i);
+ println(sk.toString(withSummary, withData));
+ assertEquals(sk.getDoubleItemsArray()[sk.levelsArr[0]], i);
}
}
println(LS + "#<<< END STATE # >>>");
- println(sk.toString(true, true));
+ println(sk.toString(withSummary, withData));
println("");
- getGrowthSchemeForGivenN(k,8,n,SketchType.DOUBLES_SKETCH, true);
+ //getGrowthSchemeForGivenN(k,8,n,SketchType.DOUBLES_SKETCH, true);
}
+ //@Test //set static enablePrinting = true for visual checking
+ // // must also make KllHelper.intCapAux(...) visible
+ // public void checkIntCapAux() {
+ // String[] hdr = {"level", "depth", "wt", "cap", "(end)", "MaxN"};
+ // String hdrFmt = "%6s %6s %28s %10s %10s %34s\n";
+ // String dataFmt = "%6d %6d %,28d %,10d %,10d %,34.0f\n";
+ // int k = 1000;
+ // int m = 8;
+ // int numLevels = 20;
+ // println("k=" + k + ", m=" + m + ", numLevels=" + numLevels);
+ // printf(hdrFmt, (Object[]) hdr);
+ // double maxN = 0;
+ // for (int i = 0; i < numLevels; i++) {
+ // int depth = numLevels - i - 1;
+ // long cap = KllHelper.intCapAux(k, depth);
+ // long end = Math.max(m, cap);
+ // long wt = 1L << i;
+ // maxN += (double)wt * (double)end;
+ // printf(dataFmt, i, depth, wt, cap, end, maxN);
+ // }
+ // }
+
+ //@Test //set static enablePrinting = true for visual checking
+ // // must also make KllHelper.powersOfThree visible
+ // public void checkIntCapAuxAux() {
+ // String[] hdr = {"d","twoK","2k*2^d","3^d","tmp=2k*2^d/3^d","(tmp + 1)/2", "(end)"};
+ // String hdrFmt = "%6s %10s %20s %20s %15s %12s %10s\n";
+ // String dataFmt = "%6d %10d %,20d %,20d %15d %12d %10d\n";
+ // long k = (1L << 16) - 1L;
+ // long m = 8;
+ // println("k = " + k + ", m = " + m);
+ // printf(hdrFmt, (Object[]) hdr);
+ // for (int i = 0; i < 31; i++) {
+ // long twoK = k << 1;
+ // long twoKxtwoD = twoK << i;
+ // long threeToD = KllHelper.powersOfThree[i];
+ // long tmp = twoKxtwoD / threeToD;
+ // long result = (tmp + 1L) >>> 1;
+ // long end = Math.max(m, result); //performed later
+ // printf(dataFmt, i, twoK, twoKxtwoD, threeToD, tmp, result, end);
+ // }
+ // }
+
@Test //set static enablePrinting = true for visual checking
public void viewDirectCompactions() {
int k = 20;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org