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 2019/12/17 18:05:45 UTC
[incubator-datasketches-java] branch NewHllIterator updated
(38afc41 -> 53e1d9f)
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a change to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git.
from 38afc41 Make Hll iterators an abstract hierarchy instead of interface.
new 7f417d2 Speedup changes
new 791717d Remove empty boolean, not needed
new 7423b13 Improvements to Hll6Array
add 670ea2f Update checkstyle config
add 71133e1 Mostly code cleanup
add c0819b9 Adding finals to many test files.
add 3de5e4b Update Checkstyle config.
add 8826665 Update memory dependency to 1.2.0-incubating
add 7e80e4c performance tweak.
add edd552f Add comment
new 4195e45 Merge branch 'Cleanup' into NewHllIterator
add 79934fa Merge pull request #285 from apache/Cleanup
new d4a3c5e Merge branch 'master' into NewHllIterator
add acd3df5 update checkstyle
new f33c080 Merge branch 'master' into NewHllIterator
new baa9da4 Updating UnionLogic
new 965b0af Add dedicated rebuild of KxQ registers.
new a2589aa Update UnionImpl
new 53e1d9f Interim update
The 10 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.
Summary of changes:
.gitignore | 2 -
pom.xml | 2 +-
.../org/apache/datasketches/cpc/BitMatrix.java | 10 +-
.../cpc/CompressionCharacterization.java | 95 ++--
.../org/apache/datasketches/cpc/CpcSketch.java | 4 +-
.../apache/datasketches/cpc/MergingValidation.java | 57 +--
.../datasketches/cpc/QuickMergingValidation.java | 69 +--
.../datasketches/cpc/StreamingValidation.java | 41 +-
.../java/org/apache/datasketches/cpc/TestUtil.java | 18 +-
.../apache/datasketches/hll/AbstractCoupons.java | 8 +
.../apache/datasketches/hll/AbstractHllArray.java | 54 ++-
.../org/apache/datasketches/hll/Conversions.java | 14 +-
.../org/apache/datasketches/hll/CouponList.java | 20 +-
.../org/apache/datasketches/hll/CouponMapping.java | 4 +-
.../apache/datasketches/hll/DirectCouponList.java | 35 +-
.../apache/datasketches/hll/DirectHll4Array.java | 32 +-
.../apache/datasketches/hll/DirectHll6Array.java | 20 +-
.../apache/datasketches/hll/DirectHll8Array.java | 18 +-
.../apache/datasketches/hll/DirectHllArray.java | 7 +
.../org/apache/datasketches/hll/Hll4Array.java | 29 +-
.../org/apache/datasketches/hll/Hll6Array.java | 37 +-
.../org/apache/datasketches/hll/Hll8Array.java | 57 ++-
.../java/org/apache/datasketches/hll/HllArray.java | 34 +-
.../org/apache/datasketches/hll/HllEstimators.java | 24 +-
.../org/apache/datasketches/hll/HllSketch.java | 20 +-
.../org/apache/datasketches/hll/HllSketchImpl.java | 26 +-
.../apache/datasketches/hll/ToByteArrayImpl.java | 2 +-
.../java/org/apache/datasketches/hll/Union.java | 333 +++++++-------
.../apache/datasketches/hllmap/package-info.java | 2 +-
.../java/org/apache/datasketches/package-info.java | 2 +-
.../apache/datasketches/BinomialBoundsNTest.java | 78 ++--
.../BoundsOnBinomialProportionsTest.java | 100 ++---
.../BoundsOnRatiosInThetaSketchedSetsTest.java | 53 ++-
.../org/apache/datasketches/ByteArrayUtilTest.java | 80 ++--
.../java/org/apache/datasketches/FamilyTest.java | 26 +-
.../apache/datasketches/HashOperationsTest.java | 53 ++-
.../org/apache/datasketches/QuickSelectTest.java | 258 +++++------
.../apache/datasketches/SketchesExceptionTest.java | 4 +-
.../java/org/apache/datasketches/UtilTest.java | 72 +--
.../datasketches/cpc/CompressedStateTest.java | 25 +-
.../apache/datasketches/cpc/CpcCBinariesTest.java | 166 +++----
.../datasketches/cpc/CpcCompressionTest.java | 44 +-
.../org/apache/datasketches/cpc/CpcSketchTest.java | 51 ++-
.../{LzTzSpeedTesting.java => LzTzSpeedTest.java} | 5 +-
.../org/apache/datasketches/cpc/TestAllTest.java | 20 +-
...ressTestHashMap.java => HashMapStressTest.java} | 24 +-
.../datasketches/hll/DirectUnionCaseTest.java | 458 -------------------
.../MiscTests.java} | 58 ++-
.../org/apache/datasketches/hll/UnionCaseTest.java | 487 +++++++++------------
.../datasketches/theta/BackwardConversions.java | 36 +-
.../org/apache/datasketches/tuple/TestUtil.java | 14 +-
.../tuple/aninteger/EngagementTest.java | 2 +-
tools/SketchesCheckstyle.xml | 40 +-
53 files changed, 1530 insertions(+), 1700 deletions(-)
rename src/{test => main}/java/org/apache/datasketches/cpc/BitMatrix.java (93%)
rename src/{test => main}/java/org/apache/datasketches/cpc/CompressionCharacterization.java (76%)
rename src/{test => main}/java/org/apache/datasketches/cpc/MergingValidation.java (75%)
rename src/{test => main}/java/org/apache/datasketches/cpc/QuickMergingValidation.java (66%)
rename src/{test => main}/java/org/apache/datasketches/cpc/StreamingValidation.java (76%)
rename src/{test => main}/java/org/apache/datasketches/cpc/TestUtil.java (90%)
rename src/test/java/org/apache/datasketches/cpc/{LzTzSpeedTesting.java => LzTzSpeedTest.java} (97%)
rename src/test/java/org/apache/datasketches/frequencies/{StressTestHashMap.java => HashMapStressTest.java} (79%)
delete mode 100644 src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java
copy src/test/java/org/apache/datasketches/{quantiles/DoublesSketchBuilderTest.java => hll/MiscTests.java} (57%)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 05/10: Merge branch 'master' into
NewHllIterator
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit d4a3c5e7b5e7e297229f63e6bf55bd599d14a448
Merge: 4195e45 79934fa
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Dec 3 16:56:35 2019 -0800
Merge branch 'master' into NewHllIterator
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 06/10: Merge branch 'master' into
NewHllIterator
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit f33c080a06b0f1b56fe2c8ad3d6ce58e287245b7
Merge: d4a3c5e acd3df5
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Wed Dec 4 14:04:10 2019 -0800
Merge branch 'master' into NewHllIterator
tools/SketchesCheckstyle.xml | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 03/10: Improvements to Hll6Array
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 7423b1314c7ede804f333e03e8f282df564df646
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Nov 25 11:30:16 2019 -0800
Improvements to Hll6Array
---
src/main/java/org/apache/datasketches/hll/Hll6Array.java | 12 ++++++------
1 file changed, 6 insertions(+), 6 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/hll/Hll6Array.java b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
index 271100c..495b54a 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
@@ -67,17 +67,17 @@ class Hll6Array extends HllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
- final int configKmask = (1 << getLgConfigK()) - 1;
- final int slotNo = HllUtil.getLow26(coupon) & configKmask;
- final int newVal = HllUtil.getValue(coupon);
+ final int configKmask = (1 << lgConfigK) - 1;
+ final int slotNo = coupon & configKmask;
+ final int newVal = coupon >>> KEY_BITS_26;
assert newVal > 0;
- final int curVal = getSlot(slotNo);
+ final int curVal = get6Bit(mem, 0, slotNo);
if (newVal > curVal) {
- putSlot(slotNo, newVal);
+ put6Bit(mem, 0, slotNo, newVal);
hipAndKxQIncrementalUpdate(this, curVal, newVal);
if (curVal == 0) {
- decNumAtCurMin(); //interpret numAtCurMin as num Zeros
+ numAtCurMin--; //interpret numAtCurMin as num Zeros
assert getNumAtCurMin() >= 0;
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 09/10: Update UnionImpl
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit a2589aa7d9a4fc3580149400c5f4282513258830
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Dec 9 14:27:24 2019 -0800
Update UnionImpl
---
.../apache/datasketches/hll/AbstractHllArray.java | 9 +-
.../org/apache/datasketches/hll/Hll8Array.java | 17 +-
.../java/org/apache/datasketches/hll/Union.java | 257 +++++++++++----------
3 files changed, 152 insertions(+), 131 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
index f1541f0..aa20026 100644
--- a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
@@ -94,8 +94,9 @@ abstract class AbstractHllArray extends HllSketchImpl {
/**
* For each actual update of the sketch, where the state of the sketch is changed, this register
* tracks the Historical Inverse Probability or HIP. Before the update is recorded this register
- * is incremented by adding 1/Q (defined below). Since KxQ is scaled by K, the actual increment
- * is K/KxQ as can be seen in the hipAndKxQIncrementalUpdate(...) routine below.
+ * is incremented by adding the inverse probability 1/Q (defined below). Since KxQ is scaled by K,
+ * the actual increment is K/KxQ as can be seen in the hipAndKxQIncrementalUpdate(...) method
+ * below.
* @return the HIP Accumulator
*/
abstract double getHipAccum();
@@ -109,9 +110,9 @@ abstract class AbstractHllArray extends HllSketchImpl {
*
* <p>The KxQ registers serve dual purposes: They are used in the HIP estimator and in
* the "raw" HLL estimator defined in the Flajolet, et al, 2007 HLL paper. In order to do this,
- * the way the KxQ registers are computed here differ from how they are defined in the paper.
+ * the way the KxQ registers are computed here differ from how they are defined in the paper.</p>
*
- * <p>The paper Fig 2 defines
+ * <p>The paper Fig 2 defines</p>
* <pre>Z := ( sum[j=1,m](2^(-M[j])) )^(-1).</pre>
* But the HIP estimator requires a computation of the probability defined above.
* We accomplish both by redefing Z as
diff --git a/src/main/java/org/apache/datasketches/hll/Hll8Array.java b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
index 535df45..ec87630 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
@@ -94,14 +94,15 @@ class Hll8Array extends HllArray {
@Override
void mergeTo(final HllSketchImpl that) {
final int thisK = 1 << lgConfigK;
- if ((thisK == that.getLgConfigK()) && (that instanceof Hll8Array)) {
- final byte[] thisArr = hllByteArr;
- final byte[] thatArr = ((Hll8Array) that).hllByteArr;
- for (int i = 0; i < thisK; i++) {
- thatArr[i] = (thisArr[i] > thatArr[i]) ? thisArr[i] : thatArr[i];
- }
- return;
- }
+ // if ((thisK == that.getLgConfigK()) && (that instanceof Hll8Array)) {
+ // //does not update KxQ
+ // final byte[] thisArr = hllByteArr;
+ // final byte[] thatArr = ((Hll8Array) that).hllByteArr;
+ // for (int i = 0; i < thisK; i++) {
+ // thatArr[i] = (thisArr[i] > thatArr[i]) ? thisArr[i] : thatArr[i];
+ // }
+ // return;
+ // }
for (int i = 0; i < thisK; i++ ) {
final int value = hllByteArr[i] & VAL_MASK_6;
if (value == 0) { continue; }
diff --git a/src/main/java/org/apache/datasketches/hll/Union.java b/src/main/java/org/apache/datasketches/hll/Union.java
index 3611c23..d9fdd30 100644
--- a/src/main/java/org/apache/datasketches/hll/Union.java
+++ b/src/main/java/org/apache/datasketches/hll/Union.java
@@ -19,7 +19,6 @@
package org.apache.datasketches.hll;
-import static org.apache.datasketches.hll.CurMode.HLL;
import static org.apache.datasketches.hll.HllUtil.EMPTY;
import static org.apache.datasketches.hll.TgtHllType.HLL_8;
@@ -235,7 +234,7 @@ public class Union extends BaseHllSketch {
}
@Override
- boolean isOutOfOrderFlag() {
+ public boolean isOutOfOrderFlag() { //TODO return to pkg private
return gadget.isOutOfOrderFlag();
}
@@ -324,134 +323,161 @@ public class Union extends BaseHllSketch {
if ((incoming == null) || incoming.isEmpty()) { return gadget.hllSketchImpl; }
final HllSketchImpl srcImpl = incoming.hllSketchImpl;
HllSketchImpl gdtImpl = gadget.hllSketchImpl;
- final int inLgK = incoming.getLgConfigK();
+ if (srcImpl.getCurMode() == CurMode.LIST ) {
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
+ return gdtImpl;
+ }
+ if (srcImpl.getCurMode() == CurMode.SET ) {
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(true);
+ return gdtImpl;
+ }
+ //Hereafter, the srcImpl is in HLL mode.
+ final int srcLgK = incoming.getLgConfigK();
final int gadgetLgK = gadget.getLgConfigK();
-
- final int hi2bits = (gadget.isEmpty()) ? 3 : gadget.getCurMode().ordinal();
- final int lo2bits = incoming.getCurMode().ordinal();
- final int sw = (hi2bits << 2) | lo2bits;
+ final int bit0 = gadget.isMemory() ? 1 : 0;
+ final int bits1_2 = (gadget.isEmpty() ? 3 : gadget.getCurMode().ordinal()) << 1;
+ final int bit3 = (srcLgK < gadgetLgK) ? 8 : 0;
+ final int bit4 = (srcLgK > lgMaxK) ? 16 : 0;
+ final int sw = bit4 | bit3 | bits1_2 | bit0;
switch (sw) {
- case 0: { //src: LIST, gadget: LIST
- srcImpl.mergeTo(gdtImpl);
- //whichever is True wins:
+ case 0: //src <= max, src >= gdt, gdtLIST, gdtHeap, swap, no downsample, ooof=OR
+ case 8: //src <= max, src < gdt, gdtLIST, gdtHeap, swap, no downsample, ooof=OR
+ { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ gdtImpl = srcHll8Heap; //replace gdt
+ gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
+ break;
+ }
+ case 1: //src <= max, src >= gdt, gdtLIST, gdtDirect, swap, no downsample, ooof=OR
+ case 9: //src <= max, src < gdt, gdtLIST, gdtDirect, swap, no downsample, ooof=OR
+ { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
break;
}
- case 1: { //src: SET, gadget: LIST
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ case 2: //src <= max, src >= gdt, gdtSET, gdtHeap, swap, no downsample, ooof=True
+ case 10: //src <= max, src < gdt, gdtSET, gdtHeap, swap, no downsample, ooof=True
+ { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ gdtImpl = srcHll8Heap; //replace gdt
+ gdtImpl.putOutOfOrderFlag(true);
break;
}
- case 2: { //src: HLL, gadget: LIST; Swap, Downsample if srcLgK > maxLgK
- final HllSketchImpl srcHll8HeapCopy = srcImpl.copyAs(HLL_8); //to heap HLL8
- final boolean gdtIsMem = gdtImpl.isMemory();
- gdtImpl.mergeTo(srcHll8HeapCopy); //reverse merge
- //srcHll8HeapCopy now has the right merged data.
-
- HllSketchImpl gdtImplTmp = gdtImpl;
-
- if (inLgK > lgMaxK) { //downsample
- gdtImplTmp = copyOrDownsampleHll(gdtImplTmp, lgMaxK);
- }
- if (gdtIsMem) {
- final byte[] byteArr = gdtImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the original wmem
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
- }
- gdtImpl = gdtImplTmp;
- //whichever is True wins:
- gdtImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag() | gdtImpl.isOutOfOrderFlag());
+ case 3: //src <= max, src >= gdt, gdtSET, gdtDirect, swap, no downsample, ooof=True
+ case 11: //src <= max, src < gdt, gdtSET, gdtDirect, swap, no downsample, ooof=True
+ { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ gdtImpl.putOutOfOrderFlag(true);
break;
}
- case 4: { //src: LIST, gadget: SET
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ case 4: //src <= max, src >= gdt, gdtHLL, gdtHeap, no swap, no downsample, ooof=True
+ case 5: //src <= max, src >= gdt, gdtHLL, gdtDirect, no swap, no downsample, ooof=True
+ case 20: //src > max, src >= gdt, gdtHLL, gdtHeap, no swap, no downsample, ooof=True
+ case 21: //src > max, src >= gdt, gdtHLL, gdtDirect, no swap, no downsample, ooof=True
+ { //Possible Optimization if srcLgK = gdtLgK && src is HLL_8
+ srcImpl.mergeTo(gdtImpl); //merge src -> gdt
+ gdtImpl.putOutOfOrderFlag(true);
break;
}
- case 5: { //src: SET, gadget: SET
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ case 6: //src <= max, src >= gdt, gdtEmpty, gdtHeap, no swap, no downsample, ooof=Src
+ case 14: //src <= max, src < gdt, gdtEmpty, gdtHeap, no swap, no downsample, ooof=Src
+ { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
+ gdtImpl = srcHll8Heap;
+ //ooof is already what source is.
break;
}
- case 6: { //src: HLL, gadget: SET
- final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
- final boolean memory = gdtImpl.isMemory();
- gdtImpl.mergeTo(heapSrcHll8); //reverse merge
- HllSketchImpl dstImplTmp = gdtImpl;
-
- if (inLgK > lgMaxK) { //downsample
- dstImplTmp = copyOrDownsampleHll(gdtImpl, lgMaxK);
- }
- if (memory) {
- final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the original wmem
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
- }
- gdtImpl = dstImplTmp;
- gdtImpl.putOutOfOrderFlag(true); //merging SET into non-empty HLL -> true
+ case 7: //src <= max, src >= gdt, gdtEmpty, gdtDirect, no swap, no downsample, ooof=Src
+ case 15: //src <= max, src < gdt, gdtEmpty, gdtDirect, no swap, no downsample, ooof=Src
+ { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ //ooof is already what source is.
break;
}
- case 8: { //src: LIST, gadget: HLL
- srcImpl.mergeTo(gdtImpl);
- //whichever is True wins:
+ case 12: //src <= max, src < gdt, gdtHLL, gdtHeap, no swap, downsample Gdt, ooof=True
+ {
+ final HllSketchImpl gdtHll8Heap = downsample(gdtImpl, srcLgK); //downsample gdt to srcLgK
+ srcImpl.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
+ gdtImpl = gdtHll8Heap; //replace gdt
+ gdtImpl.putOutOfOrderFlag(true);
+ break;
+ }
+ case 13: //src <= max, src < gdt, gdtHLL, gdtDirect, no swap, downsample Gdt, ooof=True
+ {
+ final HllSketchImpl gdtHll8Heap = downsample(gdtImpl, srcLgK); //downsample gdt to srcLgK
+ srcImpl.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = gdtHll8Heap.toUpdatableByteArray(); //serialize gdtCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ gdtImpl.putOutOfOrderFlag(true);
+ break;
+ }
+ case 16: //src > max, src >= gdt, gdtList, gdtHeap, swap, downsample Src, ooof=OR
+ {
+ final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ gdtImpl = srcHll8Heap; //replace gdt
gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
break;
}
- case 9: { //src: SET, gadget: HLL
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(true); //merging SET into existing HLL -> true
+ case 17: //src > max, src >= gdt, gdtList, gdtDirect, swap, downsample Src, ooof=OR
+ {
+ final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
break;
}
- case 10: { //src: HLL, gadget: HLL
- if (inLgK >= gadgetLgK) {
- srcImpl.mergeTo(gdtImpl); //normal merge direction
- gdtImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
- break; //done
- }
- final boolean memory = gdtImpl.isMemory();
- //inLgK < gadgetLgK, must reverse merge to src copy, then downsample gadget to inLgK
- final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
- gdtImpl.mergeTo(heapSrcHll8); //swap merge direction
- HllSketchImpl dstImplTmp = copyOrDownsampleHll(heapSrcHll8, inLgK); //heap, HLL8, inLgK
-
- if (memory) {
- final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //need to use the original wmem
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
- }
- gdtImpl = dstImplTmp;
- gdtImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
+ case 18: //src > max, src >= gdt, gdtSet, gdtHeap, swap, downsample Src, ooof=True
+ {
+ final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ gdtImpl = srcHll8Heap; //replace gdt
+ gdtImpl.putOutOfOrderFlag(true);
break;
}
- case 12: { //src: LIST, gadget: empty
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is
+ case 19: //src > max, src >= gdt, gdtSet, gdtDirect, swap, downsample Src, ooof=True
+ {
+ final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
+ gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ gdtImpl.putOutOfOrderFlag(true);
break;
}
- case 13: { //src: SET, gadget: empty
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ case 22: //src > max, src >= gdt, gdtEmpty, gdtHeap, no swap, downsample Src, ooof=Src
+ {
+ final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
+ gdtImpl = srcHll8Heap; //replace gdt
+ //ooof is already what source is.
break;
}
- case 14: { //src: HLL, gadget: empty; Downsample if srcLgK > maxLgK
- final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
- final boolean memory = gdtImpl.isMemory();
- HllSketchImpl dstImplTmp = heapSrcHll8; //no merge
-
- if (inLgK > lgMaxK) { //downsample
- dstImplTmp = copyOrDownsampleHll(dstImplTmp, lgMaxK);
- }
- if (memory) {
- final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the original wmem
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
- }
- gdtImpl = dstImplTmp;
- gdtImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is.
+ case 23: //src > max, src >= gdt, gdtEmpty, gdtDirect, no swap, downsample Src, ooof=Src
+ {
+ final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ //ooof is already what source is.
break;
}
}
@@ -463,28 +489,21 @@ public class Union extends BaseHllSketch {
/**
* Copies or downsamples the given HLLmode sketch to tgtLgK, HLL_8, on the heap.
*
- * @param srcImpl the HllSketchImpl to possibly downsample
+ * @param candidate the HllSketchImpl to downsample
* @param tgtLgK the LgK to downsample to.
* @return the downsampled HllSketchImpl.
*/
- private static final HllSketchImpl copyOrDownsampleHll(
- final HllSketchImpl srcImpl, final int tgtLgK) {
- assert (srcImpl.getCurMode() == HLL) && (!srcImpl.isEmpty());
- final AbstractHllArray src = (AbstractHllArray) srcImpl;
- final int srcLgK = src.getLgConfigK();
- if ((srcLgK <= tgtLgK) && (src.getTgtHllType() == TgtHllType.HLL_8)) {
- return src.copy(); //on heap
- }
- final int minLgK = Math.min(srcLgK, tgtLgK);
- final HllArray tgtHllArr = HllArray.newHeapHll(minLgK, TgtHllType.HLL_8);
- final PairIterator srcItr = src.iterator();
+ private static final HllSketchImpl downsample(final HllSketchImpl candidate, final int tgtLgK) {
+ final AbstractHllArray candArr = (AbstractHllArray) candidate;
+ final HllArray tgtHllArr = HllArray.newHeapHll(tgtLgK, TgtHllType.HLL_8);
+ final PairIterator srcItr = candArr.iterator();
while (srcItr.nextValid()) {
tgtHllArr.couponUpdate(srcItr.getPair());
}
//both of these are required for isomorphism
- tgtHllArr.putHipAccum(src.getHipAccum());
- tgtHllArr.putOutOfOrderFlag(src.isOutOfOrderFlag());
- return tgtHllArr; //on heap
+ tgtHllArr.putHipAccum(candArr.getHipAccum());
+ tgtHllArr.putOutOfOrderFlag(candArr.isOutOfOrderFlag());
+ return tgtHllArr;
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 01/10: Speedup changes
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 7f417d254ebf4c23d3d4815ec3076a53ab87fd4a
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Nov 21 10:19:01 2019 -0800
Speedup changes
---
.gitignore | 2 -
.../cpc/IconPolynomialCoefficients.java | 4 +-
.../apache/datasketches/hll/AbstractCoupons.java | 3 +
.../apache/datasketches/hll/AbstractHllArray.java | 6 +-
.../hll/CompositeInterpolationXTable.java | 4 +-
.../org/apache/datasketches/hll/Conversions.java | 4 +-
.../org/apache/datasketches/hll/CouponList.java | 22 ++-
.../org/apache/datasketches/hll/CouponMapping.java | 4 +-
.../apache/datasketches/hll/DirectCouponList.java | 37 ++--
.../apache/datasketches/hll/DirectHll4Array.java | 34 +++-
.../apache/datasketches/hll/DirectHll6Array.java | 23 ++-
.../apache/datasketches/hll/DirectHll8Array.java | 20 +-
.../apache/datasketches/hll/DirectHllArray.java | 7 +
.../org/apache/datasketches/hll/Hll4Array.java | 32 +++-
.../org/apache/datasketches/hll/Hll6Array.java | 40 +++-
.../org/apache/datasketches/hll/Hll8Array.java | 51 +++++-
.../java/org/apache/datasketches/hll/HllArray.java | 37 ++--
.../org/apache/datasketches/hll/HllSketchImpl.java | 26 ++-
.../java/org/apache/datasketches/hll/Union.java | 203 ++++++++++++---------
.../apache/datasketches/hllmap/package-info.java | 2 +-
.../java/org/apache/datasketches/package-info.java | 2 +-
.../datasketches/hll/DirectUnionCaseTest.java | 6 +-
.../org/apache/datasketches/hll/MiscTests.java | 72 ++++++++
.../org/apache/datasketches/hll/UnionCaseTest.java | 8 +-
.../tuple/aninteger/EngagementTest.java | 2 +-
tools/SketchesCheckstyle.xml | 47 +++--
26 files changed, 506 insertions(+), 192 deletions(-)
diff --git a/.gitignore b/.gitignore
index a28a3b9..7ac1ad8 100644
--- a/.gitignore
+++ b/.gitignore
@@ -60,8 +60,6 @@ build.xml
*.tag
# Jekyll
-Gemfile
-Gemfile.lock
_site/
_*
_*/
diff --git a/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java b/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java
index 6c08528..27cad7a 100644
--- a/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java
+++ b/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java
@@ -31,7 +31,7 @@ final class IconPolynomialCoefficients {
static final int iconPolynomialNumCoefficients = 1 + iconPolynomialDegree;
static final int iconTableSize = iconPolynomialNumCoefficients * ((1 + maxLgK) - minLgK);
- //CHECKSTYLE.OFF: LineLength
+ // CHECKSTYLE:OFF LineLength
static final double[] iconPolynomialCoefficents = new double[] {
// log K = 4
0.9895027971889700513, 0.3319496644645180128, 0.1242818722715769986, -0.03324149686026930256, -0.2985637298081619817,
@@ -171,5 +171,5 @@ final class IconPolynomialCoefficients {
-18.29035093605569884, 15.28892246224570073, -9.724916375991760731, 4.6978877652334603, -1.707974125916829955,
0.4588937864564729963, -0.08824617586088029375, 0.01147732114826570046, -0.00090384524860747295, 3.253252703695579795e-05,
};
- //CHECKSTYLE.ON: LineLength
+ // CHECKSTYLE:ON LineLength
}
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java b/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java
index 1c8cc42..a713d28 100644
--- a/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java
+++ b/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java
@@ -100,6 +100,9 @@ abstract class AbstractCoupons extends HllSketchImpl {
}
@Override
+ void putEmptyFlag(final boolean empty) {} //no-op for coupons
+
+ @Override
byte[] toCompactByteArray() {
return toCouponByteArray(this, true);
}
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
index c6a8bf9..fef06b3 100644
--- a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
@@ -95,9 +95,6 @@ abstract class AbstractHllArray extends HllSketchImpl {
abstract int getHllByteArrBytes();
- @Override
- abstract PairIterator iterator();
-
abstract double getKxQ0();
abstract double getKxQ1();
@@ -135,6 +132,9 @@ abstract class AbstractHllArray extends HllSketchImpl {
return HllEstimators.hllUpperBound(this, numStdDev);
}
+ @Override
+ abstract PairIterator iterator();
+
abstract void putAuxHashMap(AuxHashMap auxHashMap, boolean compact);
abstract void putCurMin(int curMin);
diff --git a/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java b/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java
index 119f1c7..47726ab 100644
--- a/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java
+++ b/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java
@@ -25,7 +25,7 @@ package org.apache.datasketches.hll;
*/
final class CompositeInterpolationXTable {
- //CHECKSTYLE.OFF: LineLength
+ // CHECKSTYLE:OFF LineLength
/**
* 18 Values, index 0 is LgK = 4, index 17 is LgK = 21.
*/
@@ -779,5 +779,5 @@ final class CompositeInterpolationXTable {
20970344.006053
}
};
- //CHECKSTYLE.ON: LineLength
+ // CHECKSTYLE:ON LineLength
}
diff --git a/src/main/java/org/apache/datasketches/hll/Conversions.java b/src/main/java/org/apache/datasketches/hll/Conversions.java
index e5e7239..b1d1706 100644
--- a/src/main/java/org/apache/datasketches/hll/Conversions.java
+++ b/src/main/java/org/apache/datasketches/hll/Conversions.java
@@ -24,7 +24,9 @@ import static org.apache.datasketches.hll.HllUtil.EMPTY;
import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;
/**
- * Converters for one TgtHllType to another.
+ * Converters for one TgtHllType to another. The source can be heap or direct, but the output is
+ * always on heap.
+ *
* @author Lee Rhodes
*/
class Conversions {
diff --git a/src/main/java/org/apache/datasketches/hll/CouponList.java b/src/main/java/org/apache/datasketches/hll/CouponList.java
index 59e8aed..6c67b73 100644
--- a/src/main/java/org/apache/datasketches/hll/CouponList.java
+++ b/src/main/java/org/apache/datasketches/hll/CouponList.java
@@ -151,11 +151,6 @@ class CouponList extends AbstractCoupons {
}
@Override
- PairIterator iterator() {
- return new IntArrayPairIterator(couponIntArr, lgConfigK);
- }
-
- @Override
int getLgCouponArrInts() {
return lgCouponArrInts;
}
@@ -206,6 +201,23 @@ class CouponList extends AbstractCoupons {
}
@Override
+ PairIterator iterator() {
+ return new IntArrayPairIterator(couponIntArr, lgConfigK);
+ }
+
+ @Override
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int arrLen = couponIntArr.length;
+ for (int i = 0; i < arrLen; i++) {
+ final int pair = couponIntArr[i];
+ if (pair == 0) { continue; }
+ out = out.couponUpdate(pair);
+ }
+ return out;
+ }
+
+ @Override
void putOutOfOrderFlag(final boolean oooFlag) {
this.oooFlag = oooFlag;
}
diff --git a/src/main/java/org/apache/datasketches/hll/CouponMapping.java b/src/main/java/org/apache/datasketches/hll/CouponMapping.java
index 418449e..25d9276 100644
--- a/src/main/java/org/apache/datasketches/hll/CouponMapping.java
+++ b/src/main/java/org/apache/datasketches/hll/CouponMapping.java
@@ -40,7 +40,7 @@ final class CouponMapping {
9300000.0, 9600000.0, 9900000.0, 10200000.0
};
- //CHECKSTYLE.OFF: LineLength
+ // CHECKSTYLE:OFF LineLength
//Computed for Coupon lgK = 26 ONLY. Designed for the cubic interpolator function.
static final double[] yArr = new double[] {
0.0000000000000000, 1.0000000000000000, 20.0000009437402611, 400.0003963713384110,
@@ -54,5 +54,5 @@ final class CouponMapping {
8266778.9590033423155546, 8579518.2264420464634895, 8892738.0987390466034412, 9206439.8362383283674717,
9520624.7036988288164139, 9835293.9703129194676876, 10150448.9097250290215015, 10466090.8000503256917000
};
- //CHECKSTYLE.ON: LineLength
+ // CHECKSTYLE:ON LineLength
}
diff --git a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
index 14b8b62..9d26d4d 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
@@ -125,13 +125,13 @@ class DirectCouponList extends AbstractCoupons {
HllSketchImpl couponUpdate(final int coupon) {
if (wmem == null) { noWriteAccess(); }
final int len = 1 << getLgCouponArrInts();
- for (int i = 0; i < len; i++) { //search for empty slot
+ for (int i = 0; i < len; i++) { //search for empty slot and duplicates
final int couponAtIdx = extractInt(mem, LIST_INT_ARR_START + (i << 2));
if (couponAtIdx == EMPTY) {
insertInt(wmem, LIST_INT_ARR_START + (i << 2), coupon);
int couponCount = extractListCount(mem);
insertListCount(wmem, ++couponCount);
- insertEmptyFlag(wmem, false);
+ insertEmptyFlag(wmem, false); //TODO only first time
if (couponCount >= len) { //array full
if (lgConfigK < 8) {
return promoteListOrSetToHll(this);//oooFlag = false
@@ -141,7 +141,7 @@ class DirectCouponList extends AbstractCoupons {
return this;
}
//cell not empty
- if (couponAtIdx == coupon) { return this; } //duplicate
+ if (couponAtIdx == coupon) { return this; } //return if duplicate
//cell not empty & not a duplicate, continue
} //end for
throw new SketchesStateException("Invalid State: no empties & no duplicates");
@@ -163,13 +163,6 @@ class DirectCouponList extends AbstractCoupons {
}
@Override
- PairIterator iterator() {
- final long dataStart = getMemDataStart();
- final int lenInts = (compact) ? getCouponCount() : 1 << getLgCouponArrInts();
- return new IntMemoryPairIterator(mem, dataStart, lenInts, lgConfigK);
- }
-
- @Override
int getLgCouponArrInts() {
final int lgArr = extractLgArr(mem);
if (lgArr >= LG_INIT_LIST_SIZE) { return lgArr; }
@@ -223,6 +216,26 @@ class DirectCouponList extends AbstractCoupons {
return this.mem.isSameResource(mem);
}
+ @Override
+ PairIterator iterator() {
+ final long dataStart = getMemDataStart();
+ final int lenInts = (compact) ? getCouponCount() : 1 << getLgCouponArrInts();
+ return new IntMemoryPairIterator(mem, dataStart, lenInts, lgConfigK);
+ }
+
+ @Override
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int lenInts = (compact) ? getCouponCount() : 1 << getLgCouponArrInts();
+ final int dataStart = getMemDataStart();
+ for (int i = 0; i < lenInts; i++) {
+ final int pair = mem.getInt(dataStart + (i << 2));
+ if (pair == 0) { continue; }
+ out = out.couponUpdate(pair);
+ }
+ return out;
+ }
+
@Override //not used on the direct side
void putOutOfOrderFlag(final boolean oooFlag) {
assert wmem != null;
@@ -234,8 +247,10 @@ class DirectCouponList extends AbstractCoupons {
if (wmem == null) {
throw new SketchesArgumentException("Cannot reset a read-only sketch");
}
+ insertEmptyFlag(wmem, true);
final int bytes = HllSketch.getMaxUpdatableSerializationBytes(lgConfigK, tgtHllType);
wmem.clear(0, bytes);
+
return DirectCouponList.newInstance(lgConfigK, tgtHllType, wmem);
}
@@ -259,7 +274,7 @@ class DirectCouponList extends AbstractCoupons {
insertFlags(wmem, (byte) OUT_OF_ORDER_FLAG_MASK); //set oooFlag
insertCurMin(wmem, 0); //was list count
insertCurMode(wmem, CurMode.SET);
- //tgtHllType should already be set
+ //tgtHllType should already be ok
final int maxBytes = HllSketch.getMaxUpdatableSerializationBytes(lgConfigK, tgtHllType);
wmem.clear(LIST_INT_ARR_START, maxBytes - LIST_INT_ARR_START); //clear all past first 8
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
index 1cae169..e016b58 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
@@ -20,6 +20,8 @@
package org.apache.datasketches.hll;
import static org.apache.datasketches.hll.HllUtil.AUX_TOKEN;
+import static org.apache.datasketches.hll.HllUtil.KEY_BITS_26;
+import static org.apache.datasketches.hll.HllUtil.KEY_MASK_26;
import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;
import static org.apache.datasketches.hll.HllUtil.hiNibbleMask;
import static org.apache.datasketches.hll.HllUtil.loNibbleMask;
@@ -29,6 +31,7 @@ import static org.apache.datasketches.hll.PreambleUtil.extractAuxCount;
import static org.apache.datasketches.hll.PreambleUtil.extractCompactFlag;
import static org.apache.datasketches.hll.PreambleUtil.insertAuxCount;
import static org.apache.datasketches.hll.PreambleUtil.insertCompactFlag;
+import static org.apache.datasketches.hll.PreambleUtil.insertEmptyFlag;
import static org.apache.datasketches.hll.PreambleUtil.insertInt;
import static org.apache.datasketches.hll.PreambleUtil.insertLgArr;
@@ -72,6 +75,7 @@ class DirectHll4Array extends DirectHllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
if (wmem == null) { noWriteAccess(); }
+ insertEmptyFlag(wmem, false);
final int newValue = HllUtil.getValue(coupon);
if (newValue <= getCurMin()) {
return this; // super quick rejection; only works for large N, HLL4
@@ -88,11 +92,6 @@ class DirectHll4Array extends DirectHllArray {
}
@Override
- PairIterator iterator() {
- return new DirectHll4Iterator(1 << lgConfigK);
- }
-
- @Override
final int getSlot(final int slotNo) {
final long offset = HLL_BYTE_ARR_START + (slotNo >>> 1);
int theByte = mem.getByte(offset);
@@ -115,6 +114,30 @@ class DirectHll4Array extends DirectHllArray {
}
@Override
+ PairIterator iterator() {
+ return new DirectHll4Iterator(1 << lgConfigK);
+ }
+
+ @Override
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int slots = 1 << lgConfigK;
+ for (int slotNo = 0; slotNo < slots; slotNo++) {
+ int value = mem.getByte(HLL_BYTE_ARR_START + (slotNo >>> 1)) & 0xFF;
+ final int nib = ((slotNo & 1) > 0) ? value >>> 4 : value & loNibbleMask;
+ if (nib == AUX_TOKEN) {
+ final AuxHashMap auxHashMap = getAuxHashMap();
+ value = auxHashMap.mustFindValueFor(slotNo); //auxHashMap cannot be null here
+ } else {
+ value = nib;
+ }
+ if (value == 0) { continue; }
+ out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
+ }
+ return out;
+ }
+
+ @Override
final void putSlot(final int slotNo, final int newValue) {
final long offset = HLL_BYTE_ARR_START + (slotNo >>> 1);
final int oldValue = mem.getByte(offset);
@@ -124,7 +147,6 @@ class DirectHll4Array extends DirectHllArray {
wmem.putByte(offset, value);
}
-
@Override
byte[] toCompactByteArray() {
final boolean srcMemIsCompact = extractCompactFlag(mem);
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
index 8278550..d69d2ed 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
@@ -19,9 +19,12 @@
package org.apache.datasketches.hll;
+import static org.apache.datasketches.hll.HllUtil.KEY_BITS_26;
+import static org.apache.datasketches.hll.HllUtil.KEY_MASK_26;
import static org.apache.datasketches.hll.HllUtil.VAL_MASK_6;
import static org.apache.datasketches.hll.HllUtil.noWriteAccess;
import static org.apache.datasketches.hll.PreambleUtil.HLL_BYTE_ARR_START;
+import static org.apache.datasketches.hll.PreambleUtil.insertEmptyFlag;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
@@ -49,6 +52,7 @@ class DirectHll6Array extends DirectHllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
if (wmem == null) { noWriteAccess(); }
+ insertEmptyFlag(wmem, false);
final int configKmask = (1 << getLgConfigK()) - 1;
final int slotNo = HllUtil.getLow26(coupon) & configKmask;
final int newVal = HllUtil.getValue(coupon);
@@ -72,13 +76,28 @@ class DirectHll6Array extends DirectHllArray {
}
@Override
+ final int getSlot(final int slotNo) {
+ return Hll6Array.get6Bit(mem, HLL_BYTE_ARR_START, slotNo);
+ }
+
+ @Override
PairIterator iterator() {
return new DirectHll6Iterator(1 << lgConfigK);
}
@Override
- final int getSlot(final int slotNo) {
- return Hll6Array.get6Bit(mem, HLL_BYTE_ARR_START, slotNo);
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int slots = 1 << lgConfigK;
+ for (int slotNo = 0, bitOffset = 0; slotNo < slots; slotNo++, bitOffset += 6) {
+ final int tmp = mem.getShort(HLL_BYTE_ARR_START + (bitOffset / 8));
+ final int shift = (bitOffset % 8) & 0X7;
+ final int value = (tmp >>> shift) & VAL_MASK_6;
+ if (value == 0) { continue; }
+ out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
+ System.out.println(out.curMode.toString()); //TODO
+ }
+ return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
index 8b046f6..938ad8c 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
@@ -19,9 +19,12 @@
package org.apache.datasketches.hll;
+import static org.apache.datasketches.hll.HllUtil.KEY_BITS_26;
+import static org.apache.datasketches.hll.HllUtil.KEY_MASK_26;
import static org.apache.datasketches.hll.HllUtil.VAL_MASK_6;
import static org.apache.datasketches.hll.HllUtil.noWriteAccess;
import static org.apache.datasketches.hll.PreambleUtil.HLL_BYTE_ARR_START;
+import static org.apache.datasketches.hll.PreambleUtil.insertEmptyFlag;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
@@ -51,6 +54,7 @@ class DirectHll8Array extends DirectHllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
if (wmem == null) { noWriteAccess(); }
+ insertEmptyFlag(wmem, false);
final int configKmask = (1 << getLgConfigK()) - 1;
final int slotNo = HllUtil.getLow26(coupon) & configKmask;
final int newVal = HllUtil.getValue(coupon);
@@ -74,13 +78,25 @@ class DirectHll8Array extends DirectHllArray {
}
@Override
+ final int getSlot(final int slotNo) {
+ return mem.getByte(HLL_BYTE_ARR_START + slotNo) & VAL_MASK_6;
+ }
+
+ @Override
PairIterator iterator() {
return new DirectHll8Iterator(1 << lgConfigK);
}
@Override
- final int getSlot(final int slotNo) {
- return mem.getByte(HLL_BYTE_ARR_START + slotNo) & VAL_MASK_6;
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int slots = 1 << lgConfigK;
+ for (int i = 0; i < slots; i++ ) {
+ final int value = mem.getByte(HLL_BYTE_ARR_START + i) & VAL_MASK_6;
+ if (value == 0) { continue; }
+ out = out.couponUpdate((value << KEY_BITS_26) | (i & KEY_MASK_26));
+ }
+ return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHllArray.java b/src/main/java/org/apache/datasketches/hll/DirectHllArray.java
index 8e5aa6d..48f798f 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHllArray.java
@@ -35,6 +35,7 @@ import static org.apache.datasketches.hll.PreambleUtil.extractTgtHllType;
import static org.apache.datasketches.hll.PreambleUtil.insertAuxCount;
import static org.apache.datasketches.hll.PreambleUtil.insertCompactFlag;
import static org.apache.datasketches.hll.PreambleUtil.insertCurMin;
+import static org.apache.datasketches.hll.PreambleUtil.insertEmptyFlag;
import static org.apache.datasketches.hll.PreambleUtil.insertHipAccum;
import static org.apache.datasketches.hll.PreambleUtil.insertKxQ0;
import static org.apache.datasketches.hll.PreambleUtil.insertKxQ1;
@@ -201,6 +202,11 @@ abstract class DirectHllArray extends AbstractHllArray {
}
@Override
+ void putEmptyFlag(final boolean empty) {
+ insertEmptyFlag(wmem, empty);
+ }
+
+ @Override
void putHipAccum(final double hipAccum) {
insertHipAccum(wmem, hipAccum);
}
@@ -245,6 +251,7 @@ abstract class DirectHllArray extends AbstractHllArray {
if (wmem == null) {
throw new SketchesArgumentException("Cannot reset a read-only sketch");
}
+ insertEmptyFlag(wmem, true);
final int bytes = HllSketch.getMaxUpdatableSerializationBytes(lgConfigK, tgtHllType);
wmem.clear(0, bytes);
return DirectCouponList.newInstance(lgConfigK, tgtHllType, wmem);
diff --git a/src/main/java/org/apache/datasketches/hll/Hll4Array.java b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
index 05515a5..d9fcea4 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll4Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
@@ -20,6 +20,8 @@
package org.apache.datasketches.hll;
import static org.apache.datasketches.hll.HllUtil.AUX_TOKEN;
+import static org.apache.datasketches.hll.HllUtil.KEY_BITS_26;
+import static org.apache.datasketches.hll.HllUtil.KEY_MASK_26;
import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;
import static org.apache.datasketches.hll.HllUtil.hiNibbleMask;
import static org.apache.datasketches.hll.HllUtil.loNibbleMask;
@@ -77,6 +79,7 @@ class Hll4Array extends HllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
+ empty = false;
final int newValue = HllUtil.getValue(coupon);
if (newValue <= getCurMin()) {
return this; // super quick rejection; only works for large N
@@ -88,11 +91,6 @@ class Hll4Array extends HllArray {
}
@Override
- PairIterator iterator() {
- return new HeapHll4Iterator(1 << lgConfigK);
- }
-
- @Override
int getSlot(final int slotNo) {
int theByte = hllByteArr[slotNo >>> 1];
if ((slotNo & 1) > 0) { //odd?
@@ -114,6 +112,30 @@ class Hll4Array extends HllArray {
}
@Override
+ PairIterator iterator() {
+ return new HeapHll4Iterator(1 << lgConfigK);
+ }
+
+ @Override
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int slots = 1 << lgConfigK;
+ for (int slotNo = 0; slotNo < slots; slotNo++) {
+ int value = hllByteArr[slotNo >>> 1] & 0xFF;
+ final int nib = ((slotNo & 1) > 0) ? value >>> 4 : value & loNibbleMask;
+ if (nib == AUX_TOKEN) {
+ final AuxHashMap auxHashMap = getAuxHashMap();
+ value = auxHashMap.mustFindValueFor(slotNo); //auxHashMap cannot be null here
+ } else {
+ value = nib;
+ }
+ if (value == 0) { continue; }
+ out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
+ }
+ return out;
+ }
+
+ @Override
void putSlot(final int slotNo, final int newValue) {
final int byteno = slotNo >>> 1;
final int oldValue = hllByteArr[byteno];
diff --git a/src/main/java/org/apache/datasketches/hll/Hll6Array.java b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
index a3418a4..0d6df0e 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
@@ -19,6 +19,8 @@
package org.apache.datasketches.hll;
+import static org.apache.datasketches.hll.HllUtil.KEY_BITS_26;
+import static org.apache.datasketches.hll.HllUtil.KEY_MASK_26;
import static org.apache.datasketches.hll.HllUtil.VAL_MASK_6;
import static org.apache.datasketches.hll.PreambleUtil.extractLgK;
@@ -64,8 +66,23 @@ class Hll6Array extends HllArray {
}
@Override
- PairIterator iterator() {
- return new HeapHll6Iterator(1 << lgConfigK);
+ HllSketchImpl couponUpdate(final int coupon) {
+ empty = false;
+ final int configKmask = (1 << getLgConfigK()) - 1;
+ final int slotNo = HllUtil.getLow26(coupon) & configKmask;
+ final int newVal = HllUtil.getValue(coupon);
+ assert newVal > 0;
+
+ final int curVal = getSlot(slotNo);
+ if (newVal > curVal) {
+ putSlot(slotNo, newVal);
+ hipAndKxQIncrementalUpdate(this, curVal, newVal);
+ if (curVal == 0) {
+ decNumAtCurMin(); //interpret numAtCurMin as num Zeros
+ assert getNumAtCurMin() >= 0;
+ }
+ }
+ return this;
}
@Override
@@ -74,6 +91,25 @@ class Hll6Array extends HllArray {
}
@Override
+ PairIterator iterator() {
+ return new HeapHll6Iterator(1 << lgConfigK);
+ }
+
+ @Override
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int slots = 1 << lgConfigK;
+ for (int slotNo = 0, bitOffset = 0; slotNo < slots; slotNo++, bitOffset += 6) {
+ final int tmp = mem.getShort(bitOffset / 8);
+ final int shift = (bitOffset % 8) & 0X7;
+ final int value = (tmp >>> shift) & VAL_MASK_6;
+ if (value == 0) { continue; }
+ out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
+ }
+ return out;
+ }
+
+ @Override
final void putSlot(final int slotNo, final int value) {
Hll6Array.put6Bit(mem, 0, slotNo, value);
}
diff --git a/src/main/java/org/apache/datasketches/hll/Hll8Array.java b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
index 5ae5c78..944435b 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
@@ -19,6 +19,9 @@
package org.apache.datasketches.hll;
+import static org.apache.datasketches.hll.HllUtil.EMPTY;
+import static org.apache.datasketches.hll.HllUtil.KEY_BITS_26;
+import static org.apache.datasketches.hll.HllUtil.KEY_MASK_26;
import static org.apache.datasketches.hll.HllUtil.VAL_MASK_6;
import static org.apache.datasketches.hll.PreambleUtil.extractLgK;
@@ -60,8 +63,23 @@ class Hll8Array extends HllArray {
}
@Override
- PairIterator iterator() {
- return new HeapHll8Iterator(1 << lgConfigK);
+ HllSketchImpl couponUpdate(final int coupon) {
+ empty = false;
+ final int configKmask = (1 << lgConfigK) - 1;
+ final int slotNo = coupon & configKmask;
+ final int newVal = coupon >>> KEY_BITS_26;
+ assert newVal > 0;
+
+ final int curVal = hllByteArr[slotNo] & VAL_MASK_6;
+ if (newVal > curVal) {
+ hllByteArr[slotNo] = (byte) newVal;
+ hipAndKxQIncrementalUpdate(this, curVal, newVal);
+ if (curVal == 0) {
+ numAtCurMin--; //interpret numAtCurMin as num Zeros
+ assert getNumAtCurMin() >= 0;
+ }
+ }
+ return this;
}
@Override
@@ -70,6 +88,23 @@ class Hll8Array extends HllArray {
}
@Override
+ PairIterator iterator() {
+ return new HeapHll8Iterator(1 << lgConfigK);
+ }
+
+ @Override
+ HllSketchImpl mergeTo(final HllSketchImpl impl) {
+ HllSketchImpl out = impl;
+ final int slots = 1 << lgConfigK;
+ for (int i = 0; i < slots; i++ ) {
+ final int value = hllByteArr[i] & VAL_MASK_6;
+ if (value == 0) { continue; }
+ out = out.couponUpdate((value << KEY_BITS_26) | (i & KEY_MASK_26));
+ }
+ return out;
+ }
+
+ @Override
final void putSlot(final int slotNo, final int value) {
hllByteArr[slotNo] = (byte) (value & VAL_MASK_6);
}
@@ -86,6 +121,18 @@ class Hll8Array extends HllArray {
int value() {
return hllByteArr[index] & VAL_MASK_6;
}
+
+ @Override
+ public boolean nextValid() {
+ while (++index < lengthPairs) {
+ value = hllByteArr[index] & VAL_MASK_6;
+ if (value != EMPTY) {
+ return true;
+ }
+ }
+ return false;
+ }
+
}
}
diff --git a/src/main/java/org/apache/datasketches/hll/HllArray.java b/src/main/java/org/apache/datasketches/hll/HllArray.java
index 6b95a5b..35b985f 100644
--- a/src/main/java/org/apache/datasketches/hll/HllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/HllArray.java
@@ -22,6 +22,7 @@ package org.apache.datasketches.hll;
import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;
import static org.apache.datasketches.hll.PreambleUtil.HLL_BYTE_ARR_START;
import static org.apache.datasketches.hll.PreambleUtil.extractCurMin;
+import static org.apache.datasketches.hll.PreambleUtil.extractEmptyFlag;
import static org.apache.datasketches.hll.PreambleUtil.extractHipAccum;
import static org.apache.datasketches.hll.PreambleUtil.extractKxQ0;
import static org.apache.datasketches.hll.PreambleUtil.extractKxQ1;
@@ -39,12 +40,14 @@ import org.apache.datasketches.memory.WritableMemory;
*/
abstract class HllArray extends AbstractHllArray {
boolean oooFlag = false; //Out-Of-Order Flag
+ boolean empty = true;
int curMin; //always zero for Hll6 and Hll8, only used / tracked by Hll4Array
int numAtCurMin; //interpreted as num zeros when curMin == 0
double hipAccum;
double kxq0;
double kxq1;
byte[] hllByteArr = null; //init by sub-classes
+ final int configKmask;
/**
* Standard constructor for new instance
@@ -58,6 +61,7 @@ abstract class HllArray extends AbstractHllArray {
hipAccum = 0;
kxq0 = 1 << lgConfigK;
kxq1 = 0;
+ configKmask = (1 << lgConfigK) - 1;
}
/**
@@ -67,6 +71,7 @@ abstract class HllArray extends AbstractHllArray {
HllArray(final HllArray that) {
super(that.getLgConfigK(), that.getTgtHllType(), CurMode.HLL);
oooFlag = that.isOutOfOrderFlag();
+ empty = that.isEmpty();
curMin = that.getCurMin();
numAtCurMin = that.getNumAtCurMin();
hipAccum = that.getHipAccum();
@@ -79,6 +84,7 @@ abstract class HllArray extends AbstractHllArray {
} else {
putAuxHashMap(null, false);
}
+ configKmask = (1 << lgConfigK) - 1;
}
static final HllArray newHeapHll(final int lgConfigK, final TgtHllType tgtHllType) {
@@ -92,25 +98,6 @@ abstract class HllArray extends AbstractHllArray {
hipAccum += delta;
}
- @Override //used by HLL6 and HLL8, overridden by HLL4
- HllSketchImpl couponUpdate(final int coupon) {
- final int configKmask = (1 << getLgConfigK()) - 1;
- final int slotNo = HllUtil.getLow26(coupon) & configKmask;
- final int newVal = HllUtil.getValue(coupon);
- assert newVal > 0;
-
- final int curVal = getSlot(slotNo);
- if (newVal > curVal) {
- putSlot(slotNo, newVal);
- hipAndKxQIncrementalUpdate(this, curVal, newVal);
- if (curVal == 0) {
- decNumAtCurMin(); //interpret numAtCurMin as num Zeros
- assert getNumAtCurMin() >= 0;
- }
- }
- return this;
- }
-
@Override
void decNumAtCurMin() {
numAtCurMin--;
@@ -173,8 +160,9 @@ abstract class HllArray extends AbstractHllArray {
@Override
boolean isEmpty() {
- final int configK = 1 << getLgConfigK();
- return (getCurMin() == 0) && (getNumAtCurMin() == configK);
+ return empty;
+ //final int configK = 1 << getLgConfigK();
+ //return (getCurMin() == 0) && (getNumAtCurMin() == configK);
}
@Override
@@ -208,6 +196,11 @@ abstract class HllArray extends AbstractHllArray {
}
@Override
+ void putEmptyFlag(final boolean empty) {
+ this.empty = empty;
+ }
+
+ @Override
void putHipAccum(final double value) {
hipAccum = value;
}
@@ -234,6 +227,7 @@ abstract class HllArray extends AbstractHllArray {
@Override
HllSketchImpl reset() {
+ empty = true;
return new CouponList(lgConfigK, tgtHllType, CurMode.LIST);
}
@@ -251,6 +245,7 @@ abstract class HllArray extends AbstractHllArray {
//used by heapify by all Heap HLL
static final void extractCommonHll(final Memory srcMem, final HllArray hllArray) {
hllArray.putOutOfOrderFlag(extractOooFlag(srcMem));
+ hllArray.putEmptyFlag(extractEmptyFlag(srcMem));
hllArray.putCurMin(extractCurMin(srcMem));
hllArray.putHipAccum(extractHipAccum(srcMem));
hllArray.putKxQ0(extractKxQ0(srcMem));
diff --git a/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java b/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
index c1e7624..15497c5 100644
--- a/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
+++ b/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
@@ -38,23 +38,31 @@ abstract class HllSketchImpl {
this.curMode = curMode;
}
+ /**
+ * Returns a copy of this sketch on the Heap.
+ * The LgConfigK, TgtHllType and CurMode are not changed.
+ * @return Returns a copy of this sketch on the Heap.
+ */
abstract HllSketchImpl copy();
+ /**
+ * Returns a copy of this sketch on the Heap with the given TgtHllType.
+ * The LgConfigK and CurMode are not changed.
+ * @return Returns a copy of this sketch on the Heap with the given TgtHllType.
+ */
abstract HllSketchImpl copyAs(TgtHllType tgtHllType);
abstract HllSketchImpl couponUpdate(int coupon);
- CurMode getCurMode() {
- return curMode;
- }
-
abstract int getCompactSerializationBytes();
abstract double getCompositeEstimate();
- abstract double getEstimate();
+ CurMode getCurMode() {
+ return curMode;
+ }
- abstract PairIterator iterator();
+ abstract double getEstimate();
int getLgConfigK() {
return lgConfigK;
@@ -88,6 +96,12 @@ abstract class HllSketchImpl {
abstract boolean isSameResource(Memory mem);
+ abstract PairIterator iterator();
+
+ abstract HllSketchImpl mergeTo(HllSketchImpl impl);
+
+ abstract void putEmptyFlag(boolean empty);
+
abstract void putOutOfOrderFlag(boolean oooFlag);
abstract HllSketchImpl reset();
diff --git a/src/main/java/org/apache/datasketches/hll/Union.java b/src/main/java/org/apache/datasketches/hll/Union.java
index bc3988a..9497364 100644
--- a/src/main/java/org/apache/datasketches/hll/Union.java
+++ b/src/main/java/org/apache/datasketches/hll/Union.java
@@ -19,7 +19,6 @@
package org.apache.datasketches.hll;
-import static java.lang.Math.min;
import static org.apache.datasketches.hll.CurMode.HLL;
import static org.apache.datasketches.hll.HllUtil.EMPTY;
import static org.apache.datasketches.hll.TgtHllType.HLL_8;
@@ -60,14 +59,14 @@ public class Union extends BaseHllSketch {
* Construct this Union operator with the default maximum log-base-2 of <i>K</i>.
*/
public Union() {
- this.lgMaxK = HllSketch.DEFAULT_LG_K;
+ lgMaxK = HllSketch.DEFAULT_LG_K;
gadget = new HllSketch(lgMaxK, HLL_8);
}
/**
* Construct this Union operator with a given maximum log-base-2 of <i>K</i>.
* @param lgMaxK the desired maximum log-base-2 of <i>K</i>. This value must be
- * between 7 and 21 inclusively.
+ * between 4 and 21 inclusively.
*/
public Union(final int lgMaxK) {
this.lgMaxK = HllUtil.checkLgK(lgMaxK);
@@ -83,7 +82,7 @@ public class Union extends BaseHllSketch {
* <p>The given <i>dstMem</i> is checked for the required capacity as determined by
* {@link HllSketch#getMaxUpdatableSerializationBytes(int, TgtHllType)}.
* @param lgMaxK the desired maximum log-base-2 of <i>K</i>. This value must be
- * between 7 and 21 inclusively.
+ * between 4 and 21 inclusively.
* @param dstMem the destination memory for the sketch.
*/
public Union(final int lgMaxK, final WritableMemory dstMem) {
@@ -282,7 +281,7 @@ public class Union extends BaseHllSketch {
* @param sketch the given sketch.
*/
public void update(final HllSketch sketch) {
- gadget.hllSketchImpl = unionImpl(sketch.hllSketchImpl, gadget.hllSketchImpl, lgMaxK);
+ gadget.hllSketchImpl = unionImpl(sketch, gadget, lgMaxK);
}
@Override
@@ -299,156 +298,180 @@ public class Union extends BaseHllSketch {
* perform the union. This may involve swapping, down-sampling, transforming, and / or
* copying one of the arguments and may completely replace the internals of the union.
*
- * @param incomingImpl the given incoming sketch, which may not be modified.
- * @param gadgetImpl the given gadget sketch, which must have a target of HLL_8 and may be
+ * <p>Copies or downsamples the given HLLmode sketch to tgtLgK, HLL_8.</p>
+ *
+ * <p>A swap in update direction is required:</p>
+ * <ul><li>If Gadget is in LIST, SET or EMPTY mode, AND </li>
+ * <li>(The incoming source sketch is in HLL mode and not empty,</li>
+ * <li>OR, if both source and Gadget are in HLL mode and src LgK < Gadget LgK.)</li>
+ * </ul>
+ *
+ * <p>A downsample or copy is required:</p>
+ * <ul><li>If swap is required, AND</li>
+ * <li>(If source lgK > destination LgK OR if source sketch is not type HLL_8),</li>
+ * <li>OR, if source lgK > maxLgK.</li>
+ * </ul>
+ *
+ * @param incoming the given incoming sketch, which may not be modified.
+ * @param gadget the given gadget sketch, which must have a target of HLL_8 and may be
* modified.
* @param lgMaxK the maximum value of log2 K for this union.
* @return the union of the two sketches in the form of the internal HllSketchImpl, which for
* the union is always in HLL_8 form.
*/
- private static final HllSketchImpl unionImpl(final HllSketchImpl incomingImpl,
- final HllSketchImpl gadgetImpl, final int lgMaxK) {
- assert gadgetImpl.getTgtHllType() == HLL_8;
- HllSketchImpl srcImpl = incomingImpl; //default
- HllSketchImpl dstImpl = gadgetImpl; //default
- if ((incomingImpl == null) || incomingImpl.isEmpty()) { return gadgetImpl; }
-
- final int hi2bits = (gadgetImpl.isEmpty()) ? 3 : gadgetImpl.getCurMode().ordinal();
- final int lo2bits = incomingImpl.getCurMode().ordinal();
-
+ private static final HllSketchImpl unionImpl(final HllSketch incoming,
+ final HllSketch gadget, final int lgMaxK) {
+ assert gadget.getTgtHllType() == HLL_8;
+ if ((incoming == null) || incoming.isEmpty()) { return gadget.hllSketchImpl; }
+ final HllSketchImpl srcImpl = incoming.hllSketchImpl;
+ HllSketchImpl dstImpl = gadget.hllSketchImpl;
+ final int inLgK = incoming.getLgConfigK();
+ final int gadgetLgK = gadget.getLgConfigK();
+
+ final int hi2bits = (gadget.isEmpty()) ? 3 : gadget.getCurMode().ordinal();
+ final int lo2bits = incoming.getCurMode().ordinal();
final int sw = (hi2bits << 2) | lo2bits;
-
switch (sw) {
case 0: { //src: LIST, gadget: LIST
- final PairIterator srcItr = srcImpl.iterator(); //LIST
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ dstImpl = srcImpl.mergeTo(dstImpl);
//whichever is True wins:
dstImpl.putOutOfOrderFlag(dstImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
break;
}
case 1: { //src: SET, gadget: LIST
- //consider a swap here
- final PairIterator srcItr = srcImpl.iterator(); //SET
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ dstImpl = srcImpl.mergeTo(dstImpl);
dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
- case 2: { //src: HLL, gadget: LIST
- //swap so that src is gadget-LIST, tgt is HLL
- //use lgMaxK because LIST has effective K of 2^26
- srcImpl = gadgetImpl;
- dstImpl = copyOrDownsampleHll(incomingImpl, lgMaxK);
- final PairIterator srcItr = srcImpl.iterator();
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
+ case 2: { //src: HLL, gadget: LIST; Swap, Downsample if srcLgK > maxLgK
+ final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
+ HllSketchImpl dstImplTmp = dstImpl.mergeTo(heapSrcHll8); //reverse merge
+
+ if (inLgK > lgMaxK) { //downsample
+ dstImplTmp = copyOrDownsampleHll(dstImplTmp, lgMaxK);
+ }
+ if (dstImpl.isMemory()) {
+ final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
+ final WritableMemory wmem = dstImpl.getWritableMemory(); //use the original wmem
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
}
+ dstImpl = dstImplTmp;
//whichever is True wins:
dstImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag() | dstImpl.isOutOfOrderFlag());
break;
}
case 4: { //src: LIST, gadget: SET
- final PairIterator srcItr = srcImpl.iterator(); //LIST
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ dstImpl = srcImpl.mergeTo(dstImpl);
dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
case 5: { //src: SET, gadget: SET
- final PairIterator srcItr = srcImpl.iterator(); //SET
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ dstImpl = srcImpl.mergeTo(dstImpl);
dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
case 6: { //src: HLL, gadget: SET
- //swap so that src is gadget-SET, tgt is HLL
- //use lgMaxK because LIST has effective K of 2^26
- srcImpl = gadgetImpl;
- dstImpl = copyOrDownsampleHll(incomingImpl, lgMaxK);
- final PairIterator srcItr = srcImpl.iterator(); //LIST
- assert dstImpl.getCurMode() == HLL;
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
+ final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
+ HllSketchImpl dstImplTmp = dstImpl.mergeTo(heapSrcHll8); //reverse merge
+
+ if (inLgK > lgMaxK) { //downsample
+ dstImplTmp = copyOrDownsampleHll(dstImplTmp, lgMaxK);
}
+ if (dstImpl.isMemory()) {
+ final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
+ final WritableMemory wmem = dstImpl.getWritableMemory(); //use the original wmem
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
+ }
+ dstImpl = dstImplTmp;
dstImpl.putOutOfOrderFlag(true); //merging SET into non-empty HLL -> true
break;
}
case 8: { //src: LIST, gadget: HLL
- assert dstImpl.getCurMode() == HLL;
- final PairIterator srcItr = srcImpl.iterator(); //LIST
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ //if (inLgK < gadgetLgK) { dstImpl = downsample(dstImpl, inLgK); }
+ dstImpl = srcImpl.mergeTo(dstImpl);
//whichever is True wins:
dstImpl.putOutOfOrderFlag(dstImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
break;
}
case 9: { //src: SET, gadget: HLL
- assert dstImpl.getCurMode() == HLL;
- final PairIterator srcItr = srcImpl.iterator(); //SET
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ dstImpl = srcImpl.mergeTo(dstImpl);
dstImpl.putOutOfOrderFlag(true); //merging SET into existing HLL -> true
break;
}
case 10: { //src: HLL, gadget: HLL
- final int srcLgK = srcImpl.getLgConfigK();
- final int dstLgK = dstImpl.getLgConfigK();
- if ((srcLgK < dstLgK) || (dstImpl.getTgtHllType() != HLL_8)) {
- dstImpl = copyOrDownsampleHll(dstImpl, min(dstLgK, srcLgK)); //TODO Fix for off-heap
+ if (inLgK >= gadgetLgK) {
+ dstImpl = srcImpl.mergeTo(dstImpl); //normal merge direction
+ dstImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
+ break; //done
}
- final PairIterator srcItr = srcImpl.iterator(); //HLL
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
+ //inLgK < gadgetLgK, must reverse merge to src copy, then downsample gadget to inLgK
+ final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
+ HllSketchImpl dstImplTmp = dstImpl.mergeTo(heapSrcHll8); //swap merge direction
+ dstImplTmp = copyOrDownsampleHll(dstImplTmp, inLgK); //heap, HLL8, inLgK
+
+ if (dstImpl.isMemory()) {
+ final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
+ final WritableMemory wmem = dstImpl.getWritableMemory(); //need to use the original wmem
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
}
+ dstImpl = dstImplTmp;
dstImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
break;
}
case 12: { //src: LIST, gadget: empty
- final PairIterator srcItr = srcImpl.iterator(); //LIST
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ dstImpl = srcImpl.mergeTo(dstImpl);
dstImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is
break;
}
case 13: { //src: SET, gadget: empty
- final PairIterator srcItr = srcImpl.iterator(); //SET
- while (srcItr.nextValid()) {
- dstImpl = dstImpl.couponUpdate(srcItr.getPair()); //assignment required
- }
+ dstImpl = srcImpl.mergeTo(dstImpl);
dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
- case 14: { //src: HLL, gadget: empty
- dstImpl = copyOrDownsampleHll(srcImpl, lgMaxK);
+ case 14: { //src: HLL, gadget: empty; Downsample if srcLgK > maxLgK
+ final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
+ HllSketchImpl dstImplTmp = heapSrcHll8; //no merge
+
+ if (inLgK > lgMaxK) { //downsample
+ dstImplTmp = copyOrDownsampleHll(dstImplTmp, lgMaxK);
+ }
+ if (dstImpl.isMemory()) {
+ final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
+ final WritableMemory wmem = dstImpl.getWritableMemory(); //use the original wmem
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
+ }
+ dstImpl = dstImplTmp;
dstImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is.
break;
}
}
- if (gadgetImpl.isMemory() && !dstImpl.isMemory()) {
- //dstImpl is on heap, gadget is Memory; we have to put dstImpl back into the gadget
- final WritableMemory gadgetWmem = gadgetImpl.getWritableMemory();
- assert gadgetWmem != null;
- final int bytes =
- HllSketch.getMaxUpdatableSerializationBytes(dstImpl.getLgConfigK(), HLL_8);
- gadgetWmem.clear(0, bytes);
- final byte[] dstByteArr = dstImpl.toUpdatableByteArray();
- gadgetWmem.putByteArray(0, dstByteArr, 0, dstByteArr.length);
- dstImpl = HllSketch.writableWrap(gadgetWmem).hllSketchImpl;
- }
return dstImpl;
}
//Used by union operator. Always copies or downsamples to Heap HLL_8.
- //Caller must ultimately manage oooFlag, as caller has more info
+ //Caller must ultimately manage oooFlag, as caller has more context.
+ /**
+ * Copies or downsamples the given HLLmode sketch to tgtLgK, HLL_8.
+ *
+ * <p>A swap in update direction is required:</p>
+ * <ul><li>If Gadget is in LIST, SET or EMPTY mode, AND </li>
+ * <li>The incoming source sketch is in HLL mode and not empty.</li>
+ * <li>Or, if both source and Gadget are in HLL mode and src LgK < Gadget LgK.</li>
+ * </ul>
+ *
+ * <p>A downsample is required:</p>
+ * <ul><li>If swap is required, AND</li>
+ * <li>If source lgK > Gadget LgK OR if source sketch is not type HLL_8.</li>
+ * </ul>
+ *
+ * @param srcImpl the HllSketchImpl to possibly downsample
+ * @param tgtLgK the LgK to downsample to.
+ * @return the downsampled HllSketchImpl.
+ */
private static final HllSketchImpl copyOrDownsampleHll(
final HllSketchImpl srcImpl, final int tgtLgK) {
assert srcImpl.getCurMode() == HLL;
diff --git a/src/main/java/org/apache/datasketches/hllmap/package-info.java b/src/main/java/org/apache/datasketches/hllmap/package-info.java
index 0ba1bb8..373a9f2 100644
--- a/src/main/java/org/apache/datasketches/hllmap/package-info.java
+++ b/src/main/java/org/apache/datasketches/hllmap/package-info.java
@@ -18,7 +18,7 @@
*/
/**
- * <p>The hllmap package contains a space efficient HLL mapping sketch of keys to approximate unique
+ * The hllmap package contains a space efficient HLL mapping sketch of keys to approximate unique
* count of identifiers. For example, counting the number of unique users (identifiers) per IP
* address.
*
diff --git a/src/main/java/org/apache/datasketches/package-info.java b/src/main/java/org/apache/datasketches/package-info.java
index ffe2f13..b5ed8c8 100644
--- a/src/main/java/org/apache/datasketches/package-info.java
+++ b/src/main/java/org/apache/datasketches/package-info.java
@@ -18,7 +18,7 @@
*/
/**
- * <p>This package is the parent package for all sketch algorithms.
+ * This package is the parent package for all sketch algorithms.
* Classes at this level are used by more than one sub-package.
*
* @author Lee Rhodes
diff --git a/src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java b/src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java
index be543f3..e00cc09 100644
--- a/src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java
+++ b/src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java
@@ -29,9 +29,8 @@ import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
-import org.testng.annotations.Test;
-
import org.apache.datasketches.memory.WritableMemory;
+import org.testng.annotations.Test;
/**
* @author Lee Rhodes
@@ -47,6 +46,7 @@ public class DirectUnionCaseTest {
int n3 = 2;
int sum = n1 + n2 + n3;
Union u = buildUnion(12, n1);
+ println(u.toString());
HllSketch h2 = build(11, HLL_6, n2);
HllSketch h3 = build(10, HLL_8, n3);
u.update(h2);
@@ -269,7 +269,7 @@ public class DirectUnionCaseTest {
int sum = n1 + n2 + n3;
Union u = buildUnion(12, n1); //LIST
HllSketch h2 = build(11, HLL_6, n2); //HLL
- HllSketch h3 = build(10, HLL_8, n3);
+ HllSketch h3 = build(10, HLL_8, n3); //HLL
u.update(h2);
println(u.toString());
assertEquals(u.getCurMode(), HLL);
diff --git a/src/test/java/org/apache/datasketches/hll/MiscTests.java b/src/test/java/org/apache/datasketches/hll/MiscTests.java
new file mode 100644
index 0000000..0ded712
--- /dev/null
+++ b/src/test/java/org/apache/datasketches/hll/MiscTests.java
@@ -0,0 +1,72 @@
+/*
+ * 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.hll;
+
+import org.testng.annotations.Test;
+
+/**
+ * @author Lee Rhodes
+ */
+@SuppressWarnings("javadoc")
+public class MiscTests {
+ long v = 0;
+
+ //@Test
+ public void checkSrcGTTgt() {
+ int unionLgK = 5;
+ int delLgK = 1;
+ int srcLgK = unionLgK + delLgK;
+ TgtHllType srcType = TgtHllType.HLL_8;
+
+ Union union = buildUnion(unionLgK, 1 << unionLgK);
+ HllSketch sk = build(srcLgK, srcType, 1 << srcLgK);
+ union.update(sk);
+
+ }
+
+
+
+
+ private Union buildUnion(int lgMaxK, int n) {
+ Union u = new Union(lgMaxK);
+ for (int i = 0; i < n; i++) { u.update(i + v); }
+ v += n;
+ return u;
+ }
+
+ private HllSketch build(int lgK, TgtHllType tgtHllType, int n) {
+ HllSketch sk = new HllSketch(lgK, tgtHllType);
+ for (int i = 0; i < n; i++) { sk.update(i + v); }
+ v += n;
+ return sk;
+ }
+
+ @Test
+ public void printlnTest() {
+ println("PRINTING: "+this.getClass().getName());
+ }
+
+ /**
+ * @param s value to print
+ */
+ static void println(String s) {
+ //System.out.println(s); //disable here
+ }
+}
diff --git a/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java b/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
index f4e4590..c5daf8d 100644
--- a/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
+++ b/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
@@ -243,10 +243,10 @@ public class UnionCaseTest {
int n2 = 193;
int n3 = 16;
int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL
- HllSketch h3 = build(10, HLL_8, n3);
- u.update(h2);
+ Union u = buildUnion(12, n1); //LIST 6
+ HllSketch h2 = build(11, HLL_6, n2); //HLL 193
+ HllSketch h3 = build(10, HLL_8, n3); //16
+ u.update(h2); //6 + 193 = 199 HLL
println(u.toString());
assertEquals(u.getCurMode(), HLL);
u.update(h3);
diff --git a/src/test/java/org/apache/datasketches/tuple/aninteger/EngagementTest.java b/src/test/java/org/apache/datasketches/tuple/aninteger/EngagementTest.java
index 7413181..631e688 100644
--- a/src/test/java/org/apache/datasketches/tuple/aninteger/EngagementTest.java
+++ b/src/test/java/org/apache/datasketches/tuple/aninteger/EngagementTest.java
@@ -139,6 +139,6 @@ public class EngagementTest {
* @param args arguments
*/
private static void printf(String fmt, Object ... args) {
- System.out.printf(fmt, args); //Enable/Disable printing here
+ //System.out.printf(fmt, args); //Enable/Disable printing here
}
}
diff --git a/tools/SketchesCheckstyle.xml b/tools/SketchesCheckstyle.xml
index 7299741..9e245c3 100644
--- a/tools/SketchesCheckstyle.xml
+++ b/tools/SketchesCheckstyle.xml
@@ -48,6 +48,25 @@ under the License.
<property name="lineSeparator" value="lf"/>
</module>
+ <!-- Size Violations -->
+ <module name="LineLength">
+ <property name="fileExtensions" value="java"/>
+ <property name="severity" value="warning"/>
+ <property name="max" value="110"/>
+ <property name="ignorePattern" value="^package.*|^import.*|a href|href|http://|https://|ftp://"/>
+ <metadata name="net.sf.eclipsecs.core.lastEnabledSeverity" value="inherit"/>
+ </module>
+
+ <!-- Filters -->
+ <!-- Enable suppression using comments: // CHECKSTYLE:OFF "RULE" and // CHECKSTYLE:ON "RULE"
+ You must specify the specific rule, as in: // CHECKSTYLE.OFF: LineLength -->
+ <module name="SuppressWithPlainTextCommentFilter">
+ <property name="offCommentFormat" value="// *CHECKSTYLE:OFF ([\w\|]+)"/>
+ <property name="onCommentFormat" value="// *CHECKSTYLE:ON ([\w\|]+)"/>
+ <property name="checkFormat" value="$1"/>
+ </module>
+
+
<module name="TreeWalker">
<!-- Annotations -->
@@ -149,6 +168,16 @@ under the License.
<module name="FinalClass"/>
+ <!-- Filters -->
+ <!-- Enable suppression using comments: //CHECKSTYLE.OFF: "RULE" and //CHECKSTYLE.ON: "RULE"
+ You must specify the specific rule, as in: //CHECKSTYLE.OFF: LineLength -->
+ <module name="SuppressionCommentFilter">
+ <property name="offCommentFormat" value="// *CHECKSTYLE:OFF ([\w\|]+)"/>
+ <property name="onCommentFormat" value="// *CHECKSTYLE:ON ([\w\|]+)"/>
+ <property name="checkFormat" value="$1"/>
+ </module>
+
+
<!-- Imports -->
<module name="AvoidStarImport"/>
@@ -164,15 +193,6 @@ under the License.
<module name="UnusedImports"/>
- <!-- Filters -->
- <!-- Enable suppression using comments: //CHECKSTYLE.OFF: "RULE" and //CHECKSTYLE.ON: "RULE"
- You must specify the specific rule, as in: //CHECKSTYLE.OFF: LineLength -->
- <module name="SuppressionCommentFilter">
- <property name="offCommentFormat" value="CHECKSTYLE.OFF\: ([\w\|]+)"/>
- <property name="onCommentFormat" value="CHECKSTYLE.ON\: ([\w\|]+)"/>
- <property name="checkFormat" value="$1"/>
- </module>
-
<!-- Javadoc Comments -->
<!-- JavadocPackage under Checker -->
<module name="AtclauseOrder">
@@ -185,7 +205,6 @@ under the License.
<property name="allowMissingParamTags" value="false"/>
<property name="allowMissingThrowsTags" value="true"/>
<property name="allowMissingReturnTag" value="false"/>
- <property name="minLineCount" value="2"/>
<property name="allowedAnnotations" value="Override, Test"/>
<property name="allowThrowsTagsForSubclasses" value="true"/>
</module>
@@ -333,14 +352,6 @@ under the License.
<property name="ignoreComments" value="true"/>
</module>
- <!-- Size Violations -->
- <module name="LineLength">
- <property name="severity" value="warning"/>
- <property name="max" value="110"/>
- <property name="ignorePattern" value="^package.*|^import.*|a href|href|http://|https://|ftp://"/>
- <!-- <metadata name="net.sf.eclipsecs.core.lastEnabledSeverity" value="inherit"/> -->
- </module>
-
<!-- Whitespace -->
<module name="EmptyLineSeparator">
<property name="allowNoEmptyLineBetweenFields" value="true"/>
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 02/10: Remove empty boolean,
not needed
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 791717d1961006fe3aea701b9d43bbf06235c54d
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Fri Nov 22 16:02:59 2019 -0800
Remove empty boolean, not needed
---
.../org/apache/datasketches/hll/AbstractHllArray.java | 5 +++++
src/main/java/org/apache/datasketches/hll/Hll4Array.java | 1 -
src/main/java/org/apache/datasketches/hll/Hll6Array.java | 1 -
src/main/java/org/apache/datasketches/hll/Hll8Array.java | 1 -
src/main/java/org/apache/datasketches/hll/HllArray.java | 15 ++++-----------
src/main/java/org/apache/datasketches/hll/HllSketch.java | 3 ++-
.../java/org/apache/datasketches/hll/ToByteArrayImpl.java | 2 +-
src/main/java/org/apache/datasketches/hll/Union.java | 1 -
8 files changed, 12 insertions(+), 17 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
index fef06b3..690d3ac 100644
--- a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
@@ -112,6 +112,11 @@ abstract class AbstractHllArray extends HllSketchImpl {
abstract AuxHashMap getNewAuxHashMap();
+ /**
+ * Returns the number of slots that have the value CurMin.
+ * If CurMin is 0, then it returns the number of zeros in the array.
+ * @return the number of slots that have the value CurMin.
+ */
abstract int getNumAtCurMin();
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/Hll4Array.java b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
index d9fcea4..5c4af9d 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll4Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
@@ -79,7 +79,6 @@ class Hll4Array extends HllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
- empty = false;
final int newValue = HllUtil.getValue(coupon);
if (newValue <= getCurMin()) {
return this; // super quick rejection; only works for large N
diff --git a/src/main/java/org/apache/datasketches/hll/Hll6Array.java b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
index 0d6df0e..271100c 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
@@ -67,7 +67,6 @@ class Hll6Array extends HllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
- empty = false;
final int configKmask = (1 << getLgConfigK()) - 1;
final int slotNo = HllUtil.getLow26(coupon) & configKmask;
final int newVal = HllUtil.getValue(coupon);
diff --git a/src/main/java/org/apache/datasketches/hll/Hll8Array.java b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
index 944435b..f810f1c 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
@@ -64,7 +64,6 @@ class Hll8Array extends HllArray {
@Override
HllSketchImpl couponUpdate(final int coupon) {
- empty = false;
final int configKmask = (1 << lgConfigK) - 1;
final int slotNo = coupon & configKmask;
final int newVal = coupon >>> KEY_BITS_26;
diff --git a/src/main/java/org/apache/datasketches/hll/HllArray.java b/src/main/java/org/apache/datasketches/hll/HllArray.java
index 35b985f..7772070 100644
--- a/src/main/java/org/apache/datasketches/hll/HllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/HllArray.java
@@ -40,9 +40,8 @@ import org.apache.datasketches.memory.WritableMemory;
*/
abstract class HllArray extends AbstractHllArray {
boolean oooFlag = false; //Out-Of-Order Flag
- boolean empty = true;
- int curMin; //always zero for Hll6 and Hll8, only used / tracked by Hll4Array
- int numAtCurMin; //interpreted as num zeros when curMin == 0
+ int curMin; //always zero for Hll6 and Hll8, only used by Hll4Array
+ int numAtCurMin; //# of values at curMin. If curMin = 0, it is # of zeros
double hipAccum;
double kxq0;
double kxq1;
@@ -71,7 +70,6 @@ abstract class HllArray extends AbstractHllArray {
HllArray(final HllArray that) {
super(that.getLgConfigK(), that.getTgtHllType(), CurMode.HLL);
oooFlag = that.isOutOfOrderFlag();
- empty = that.isEmpty();
curMin = that.getCurMin();
numAtCurMin = that.getNumAtCurMin();
hipAccum = that.getHipAccum();
@@ -160,9 +158,7 @@ abstract class HllArray extends AbstractHllArray {
@Override
boolean isEmpty() {
- return empty;
- //final int configK = 1 << getLgConfigK();
- //return (getCurMin() == 0) && (getNumAtCurMin() == configK);
+ return false; //because there should be no normal way to create an HllArray that is empty
}
@Override
@@ -196,9 +192,7 @@ abstract class HllArray extends AbstractHllArray {
}
@Override
- void putEmptyFlag(final boolean empty) {
- this.empty = empty;
- }
+ void putEmptyFlag(final boolean empty) { }
@Override
void putHipAccum(final double value) {
@@ -227,7 +221,6 @@ abstract class HllArray extends AbstractHllArray {
@Override
HllSketchImpl reset() {
- empty = true;
return new CouponList(lgConfigK, tgtHllType, CurMode.LIST);
}
diff --git a/src/main/java/org/apache/datasketches/hll/HllSketch.java b/src/main/java/org/apache/datasketches/hll/HllSketch.java
index 917a646..16c02b9 100644
--- a/src/main/java/org/apache/datasketches/hll/HllSketch.java
+++ b/src/main/java/org/apache/datasketches/hll/HllSketch.java
@@ -20,6 +20,7 @@
package org.apache.datasketches.hll;
import static org.apache.datasketches.hll.HllUtil.EMPTY;
+import static org.apache.datasketches.hll.HllUtil.KEY_BITS_26;
import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;
import static org.apache.datasketches.hll.HllUtil.checkPreamble;
import static org.apache.datasketches.hll.PreambleUtil.HLL_BYTE_ARR_START;
@@ -474,7 +475,7 @@ public class HllSketch extends BaseHllSketch {
@Override
void couponUpdate(final int coupon) {
- if (coupon == EMPTY) { return; }
+ if ((coupon >>> KEY_BITS_26 ) == EMPTY) { return; }
hllSketchImpl = hllSketchImpl.couponUpdate(coupon);
}
diff --git a/src/main/java/org/apache/datasketches/hll/ToByteArrayImpl.java b/src/main/java/org/apache/datasketches/hll/ToByteArrayImpl.java
index 7b97e8f..2705fe7 100644
--- a/src/main/java/org/apache/datasketches/hll/ToByteArrayImpl.java
+++ b/src/main/java/org/apache/datasketches/hll/ToByteArrayImpl.java
@@ -52,7 +52,7 @@ import org.apache.datasketches.memory.WritableMemory;
*/
class ToByteArrayImpl {
- // To byte array used by the heap HLL types.
+ // To byte array used by the heap HLL modes.
static final byte[] toHllByteArray(final AbstractHllArray impl, final boolean compact) {
int auxBytes = 0;
if (impl.tgtHllType == TgtHllType.HLL_4) {
diff --git a/src/main/java/org/apache/datasketches/hll/Union.java b/src/main/java/org/apache/datasketches/hll/Union.java
index 9497364..1a58984 100644
--- a/src/main/java/org/apache/datasketches/hll/Union.java
+++ b/src/main/java/org/apache/datasketches/hll/Union.java
@@ -389,7 +389,6 @@ public class Union extends BaseHllSketch {
break;
}
case 8: { //src: LIST, gadget: HLL
- //if (inLgK < gadgetLgK) { dstImpl = downsample(dstImpl, inLgK); }
dstImpl = srcImpl.mergeTo(dstImpl);
//whichever is True wins:
dstImpl.putOutOfOrderFlag(dstImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 04/10: Merge branch 'Cleanup' into
NewHllIterator
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 4195e45ac3c5bf60edf29dd5a72945338322ed62
Merge: 7423b13 edd552f
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Dec 3 16:45:04 2019 -0800
Merge branch 'Cleanup' into NewHllIterator
pom.xml | 2 +-
.../org/apache/datasketches/cpc/BitMatrix.java | 10 +-
.../cpc/CompressionCharacterization.java | 95 ++++----
.../org/apache/datasketches/cpc/CpcSketch.java | 4 +-
.../apache/datasketches/cpc/MergingValidation.java | 57 ++---
.../datasketches/cpc/QuickMergingValidation.java | 69 +++---
.../datasketches/cpc/StreamingValidation.java | 41 ++--
.../java/org/apache/datasketches/cpc/TestUtil.java | 18 +-
.../org/apache/datasketches/hll/HllEstimators.java | 1 +
.../apache/datasketches/BinomialBoundsNTest.java | 78 +++----
.../BoundsOnBinomialProportionsTest.java | 100 ++++----
.../BoundsOnRatiosInThetaSketchedSetsTest.java | 53 +++--
.../org/apache/datasketches/ByteArrayUtilTest.java | 80 +++----
.../java/org/apache/datasketches/FamilyTest.java | 26 +--
.../apache/datasketches/HashOperationsTest.java | 53 +++--
.../org/apache/datasketches/QuickSelectTest.java | 258 ++++++++++-----------
.../apache/datasketches/SketchesExceptionTest.java | 4 +-
.../java/org/apache/datasketches/UtilTest.java | 72 +++---
.../datasketches/cpc/CompressedStateTest.java | 25 +-
.../apache/datasketches/cpc/CpcCBinariesTest.java | 166 ++++++-------
.../datasketches/cpc/CpcCompressionTest.java | 44 ++--
.../org/apache/datasketches/cpc/CpcSketchTest.java | 51 ++--
.../{LzTzSpeedTesting.java => LzTzSpeedTest.java} | 5 +-
.../org/apache/datasketches/cpc/TestAllTest.java | 20 +-
...ressTestHashMap.java => HashMapStressTest.java} | 24 +-
.../datasketches/theta/BackwardConversions.java | 36 +--
.../org/apache/datasketches/tuple/TestUtil.java | 14 +-
tools/SketchesCheckstyle.xml | 41 ++--
28 files changed, 739 insertions(+), 708 deletions(-)
diff --cc tools/SketchesCheckstyle.xml
index 9e245c3,90597a9..b0832cb
--- a/tools/SketchesCheckstyle.xml
+++ b/tools/SketchesCheckstyle.xml
@@@ -193,6 -184,15 +184,16 @@@ under the License
<module name="UnusedImports"/>
++
+ <!-- Filters -->
+ <!-- Enable suppression using comments: //CHECKSTYLE.OFF: "RULE" and //CHECKSTYLE.ON: "RULE"
+ You must specify the specific rule, as in: //CHECKSTYLE.OFF: LineLength -->
+ <module name="SuppressionCommentFilter">
+ <property name="offCommentFormat" value="//CHECKSTYLE.OFF\: ([\w\|]+)"/>
+ <property name="onCommentFormat" value="//CHECKSTYLE.ON\: ([\w\|]+)"/>
+ <property name="checkFormat" value="$1"/>
+ </module>
+
<!-- Javadoc Comments -->
<!-- JavadocPackage under Checker -->
<module name="AtclauseOrder">
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 08/10: Add dedicated rebuild of KxQ
registers.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 965b0af3f33a069d4532137ba4dd7e3752f1b050
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Sun Dec 8 11:38:32 2019 -0800
Add dedicated rebuild of KxQ registers.
---
.../apache/datasketches/hll/AbstractHllArray.java | 37 ++++++++++++++++++++--
.../org/apache/datasketches/hll/Conversions.java | 10 +++---
.../org/apache/datasketches/hll/HllEstimators.java | 24 ++++++++++++--
3 files changed, 60 insertions(+), 11 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
index 690d3ac..f1541f0 100644
--- a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
@@ -78,7 +78,7 @@ abstract class AbstractHllArray extends HllSketchImpl {
//In C: again-two-registers.c hhb_get_composite_estimate L1489
@Override
double getCompositeEstimate() {
- return HllEstimators.hllCompositeEstimate(this);
+ return HllEstimators.hllCompositeEstimate(this, false);
}
abstract int getCurMin();
@@ -91,12 +91,43 @@ abstract class AbstractHllArray extends HllSketchImpl {
return getHipAccum();
}
+ /**
+ * For each actual update of the sketch, where the state of the sketch is changed, this register
+ * tracks the Historical Inverse Probability or HIP. Before the update is recorded this register
+ * is incremented by adding 1/Q (defined below). Since KxQ is scaled by K, the actual increment
+ * is K/KxQ as can be seen in the hipAndKxQIncrementalUpdate(...) routine below.
+ * @return the HIP Accumulator
+ */
abstract double getHipAccum();
abstract int getHllByteArrBytes();
+ /**
+ * Q = KxQ/K is the probability that an incoming event can modify the state of the sketch.
+ * KxQ is literally K times Q. The HIP estimator is based on tracking this probability as the
+ * sketch gets populated. It is tracked in the hipAccum register.
+ *
+ * <p>The KxQ registers serve dual purposes: They are used in the HIP estimator and in
+ * the "raw" HLL estimator defined in the Flajolet, et al, 2007 HLL paper. In order to do this,
+ * the way the KxQ registers are computed here differ from how they are defined in the paper.
+ *
+ * <p>The paper Fig 2 defines
+ * <pre>Z := ( sum[j=1,m](2^(-M[j])) )^(-1).</pre>
+ * But the HIP estimator requires a computation of the probability defined above.
+ * We accomplish both by redefing Z as
+ * <pre>Z := ( m + sum[j=1,m](2^(-M[j] - 1)) )^(-1).</pre>
+ * They are mathematically equivalent since:
+ * <pre>m + sum[j=1,m](2^(-M[j] - 1)) == m + sum[j=1,m](2^(-M[j])) - m == sum[j=1,m](2^(-M[j])).</pre>
+ *
+ * @return KxQ0
+ */
abstract double getKxQ0();
+ /**
+ * This second KxQ register is shifted by 32 bits to give us more than 90 bits of mantissa
+ * precision, which produces more accurate results for very large counts.
+ * @return KxQ1
+ */
abstract double getKxQ1();
@Override
@@ -177,8 +208,8 @@ abstract class AbstractHllArray extends HllSketchImpl {
*/
//In C: again-two-registers.c Lines 851 to 871
//Called here and by Heap and Direct 6 and 8 bit implementations
- static final void hipAndKxQIncrementalUpdate(final AbstractHllArray host, final int oldValue,
- final int newValue) {
+ static final void hipAndKxQIncrementalUpdate(final AbstractHllArray host,
+ final int oldValue, final int newValue) {
assert newValue > oldValue;
final int configK = 1 << host.getLgConfigK();
//update hipAccum BEFORE updating kxq0 and kxq1
diff --git a/src/main/java/org/apache/datasketches/hll/Conversions.java b/src/main/java/org/apache/datasketches/hll/Conversions.java
index b1d1706..9983e6a 100644
--- a/src/main/java/org/apache/datasketches/hll/Conversions.java
+++ b/src/main/java/org/apache/datasketches/hll/Conversions.java
@@ -47,7 +47,7 @@ class Conversions {
while (itr.nextValid()) {
final int slotNo = itr.getIndex();
final int actualValue = itr.getValue();
- AbstractHllArray.hipAndKxQIncrementalUpdate(hll4Array, 0, actualValue); //was srcHllArr
+ AbstractHllArray.hipAndKxQIncrementalUpdate(hll4Array, 0, actualValue);
if (actualValue >= (curMin + 15)) {
hll4Array.putSlot(slotNo, AUX_TOKEN);
if (auxHashMap == null) {
@@ -62,7 +62,7 @@ class Conversions {
hll4Array.putCurMin(curMin);
hll4Array.putNumAtCurMin(numAtCurMin);
- hll4Array.putHipAccum(srcHllArr.getHipAccum());
+ hll4Array.putHipAccum(srcHllArr.getHipAccum()); //intentional overwrite
return hll4Array;
}
@@ -95,7 +95,7 @@ class Conversions {
}
}
hll6Array.putNumAtCurMin(numZeros);
- hll6Array.putHipAccum(srcHllArr.getHipAccum());
+ hll6Array.putHipAccum(srcHllArr.getHipAccum()); //intentional overwrite
return hll6Array;
}
@@ -108,11 +108,11 @@ class Conversions {
while (itr.nextAll()) {
if (itr.getValue() != EMPTY) {
numZeros--;
- hll8Array.couponUpdate(itr.getPair());
+ hll8Array.couponUpdate(itr.getPair()); //creates KxQ registers
}
}
hll8Array.putNumAtCurMin(numZeros);
- hll8Array.putHipAccum(srcHllArr.getHipAccum());
+ hll8Array.putHipAccum(srcHllArr.getHipAccum()); //intentional overwrite
return hll8Array;
}
diff --git a/src/main/java/org/apache/datasketches/hll/HllEstimators.java b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
index 4aed96d..5dda41c 100644
--- a/src/main/java/org/apache/datasketches/hll/HllEstimators.java
+++ b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
@@ -19,6 +19,7 @@
package org.apache.datasketches.hll;
+import static org.apache.datasketches.Util.invPow2;
import static org.apache.datasketches.hll.HllUtil.HLL_HIP_RSE_FACTOR;
import static org.apache.datasketches.hll.HllUtil.HLL_NON_HIP_RSE_FACTOR;
import static org.apache.datasketches.hll.HllUtil.MIN_LOG_K;
@@ -95,10 +96,14 @@ class HllEstimators {
* @return the composite estimate
*/
//In C: again-two-registers.c hhb_get_composite_estimate L1489
- static final double hllCompositeEstimate(final AbstractHllArray absHllArr) {
+ static final double hllCompositeEstimate(final AbstractHllArray absHllArr,
+ final boolean rebuildKxQ) {
final int lgConfigK = absHllArr.getLgConfigK();
- //TODO Rebuild KxQ registers.
- final double rawEst = getHllRawEstimate(lgConfigK, absHllArr.getKxQ0() + absHllArr.getKxQ1());
+ final double kxqSum;
+ if (rebuildKxQ) { kxqSum = computeKxQSum(absHllArr); }
+ else { kxqSum = absHllArr.getKxQ0() + absHllArr.getKxQ1(); }
+
+ final double rawEst = getHllRawEstimate(lgConfigK, kxqSum);
final double[] xArr = CompositeInterpolationXTable.xArrs[lgConfigK - MIN_LOG_K];
final double yStride = CompositeInterpolationXTable.yStrides[lgConfigK - MIN_LOG_K];
@@ -179,4 +184,17 @@ class HllEstimators {
return hyperEst;
}
+ static final double computeKxQSum(final AbstractHllArray host) {
+ final int configK = 1 << host.getLgConfigK();
+ final PairIterator itr = host.iterator();
+ double kxq0 = configK;
+ double kxq1 = 0;
+ while (itr.nextValid()) {
+ final int actualValue = itr.getValue();
+ if (actualValue < 32) { kxq0 += invPow2(actualValue) - 1; }
+ else { kxq1 += invPow2(actualValue) - 1; }
+ }
+ return kxq0 + kxq1;
+ }
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 07/10: Updating UnionLogic
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit baa9da42eb2badfd1b1cbd437170d660e566d325
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Dec 5 14:58:54 2019 -0800
Updating UnionLogic
---
.../cpc/IconPolynomialCoefficients.java | 4 +-
.../hll/CompositeInterpolationXTable.java | 4 +-
.../org/apache/datasketches/hll/CouponList.java | 6 +-
.../apache/datasketches/hll/DirectCouponList.java | 6 +-
.../apache/datasketches/hll/DirectHll4Array.java | 6 +-
.../apache/datasketches/hll/DirectHll6Array.java | 7 +-
.../apache/datasketches/hll/DirectHll8Array.java | 6 +-
.../org/apache/datasketches/hll/Hll4Array.java | 6 +-
.../org/apache/datasketches/hll/Hll6Array.java | 6 +-
.../org/apache/datasketches/hll/Hll8Array.java | 18 ++-
.../org/apache/datasketches/hll/HllEstimators.java | 1 +
.../org/apache/datasketches/hll/HllSketchImpl.java | 2 +-
.../java/org/apache/datasketches/hll/Union.java | 134 ++++++++++-----------
13 files changed, 97 insertions(+), 109 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java b/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java
index 27cad7a..6c08528 100644
--- a/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java
+++ b/src/main/java/org/apache/datasketches/cpc/IconPolynomialCoefficients.java
@@ -31,7 +31,7 @@ final class IconPolynomialCoefficients {
static final int iconPolynomialNumCoefficients = 1 + iconPolynomialDegree;
static final int iconTableSize = iconPolynomialNumCoefficients * ((1 + maxLgK) - minLgK);
- // CHECKSTYLE:OFF LineLength
+ //CHECKSTYLE.OFF: LineLength
static final double[] iconPolynomialCoefficents = new double[] {
// log K = 4
0.9895027971889700513, 0.3319496644645180128, 0.1242818722715769986, -0.03324149686026930256, -0.2985637298081619817,
@@ -171,5 +171,5 @@ final class IconPolynomialCoefficients {
-18.29035093605569884, 15.28892246224570073, -9.724916375991760731, 4.6978877652334603, -1.707974125916829955,
0.4588937864564729963, -0.08824617586088029375, 0.01147732114826570046, -0.00090384524860747295, 3.253252703695579795e-05,
};
- // CHECKSTYLE:ON LineLength
+ //CHECKSTYLE.ON: LineLength
}
diff --git a/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java b/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java
index 47726ab..119f1c7 100644
--- a/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java
+++ b/src/main/java/org/apache/datasketches/hll/CompositeInterpolationXTable.java
@@ -25,7 +25,7 @@ package org.apache.datasketches.hll;
*/
final class CompositeInterpolationXTable {
- // CHECKSTYLE:OFF LineLength
+ //CHECKSTYLE.OFF: LineLength
/**
* 18 Values, index 0 is LgK = 4, index 17 is LgK = 21.
*/
@@ -779,5 +779,5 @@ final class CompositeInterpolationXTable {
20970344.006053
}
};
- // CHECKSTYLE:ON LineLength
+ //CHECKSTYLE.ON: LineLength
}
diff --git a/src/main/java/org/apache/datasketches/hll/CouponList.java b/src/main/java/org/apache/datasketches/hll/CouponList.java
index 6c67b73..7fc363e 100644
--- a/src/main/java/org/apache/datasketches/hll/CouponList.java
+++ b/src/main/java/org/apache/datasketches/hll/CouponList.java
@@ -206,15 +206,13 @@ class CouponList extends AbstractCoupons {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
+ void mergeTo(final HllSketchImpl that) {
final int arrLen = couponIntArr.length;
for (int i = 0; i < arrLen; i++) {
final int pair = couponIntArr[i];
if (pair == 0) { continue; }
- out = out.couponUpdate(pair);
+ that.couponUpdate(pair);
}
- return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
index 9d26d4d..4cc8acb 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
@@ -224,16 +224,14 @@ class DirectCouponList extends AbstractCoupons {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
+ void mergeTo(final HllSketchImpl that) {
final int lenInts = (compact) ? getCouponCount() : 1 << getLgCouponArrInts();
final int dataStart = getMemDataStart();
for (int i = 0; i < lenInts; i++) {
final int pair = mem.getInt(dataStart + (i << 2));
if (pair == 0) { continue; }
- out = out.couponUpdate(pair);
+ that.couponUpdate(pair);
}
- return out;
}
@Override //not used on the direct side
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
index e016b58..900b637 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
@@ -119,8 +119,7 @@ class DirectHll4Array extends DirectHllArray {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
+ void mergeTo(final HllSketchImpl that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0; slotNo < slots; slotNo++) {
int value = mem.getByte(HLL_BYTE_ARR_START + (slotNo >>> 1)) & 0xFF;
@@ -132,9 +131,8 @@ class DirectHll4Array extends DirectHllArray {
value = nib;
}
if (value == 0) { continue; }
- out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
+ that.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
}
- return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
index d69d2ed..2a13dbf 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
@@ -86,18 +86,15 @@ class DirectHll6Array extends DirectHllArray {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
+ void mergeTo(final HllSketchImpl that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0, bitOffset = 0; slotNo < slots; slotNo++, bitOffset += 6) {
final int tmp = mem.getShort(HLL_BYTE_ARR_START + (bitOffset / 8));
final int shift = (bitOffset % 8) & 0X7;
final int value = (tmp >>> shift) & VAL_MASK_6;
if (value == 0) { continue; }
- out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
- System.out.println(out.curMode.toString()); //TODO
+ that.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
}
- return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
index 938ad8c..77fe08d 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
@@ -88,15 +88,13 @@ class DirectHll8Array extends DirectHllArray {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
+ void mergeTo(final HllSketchImpl that) {
final int slots = 1 << lgConfigK;
for (int i = 0; i < slots; i++ ) {
final int value = mem.getByte(HLL_BYTE_ARR_START + i) & VAL_MASK_6;
if (value == 0) { continue; }
- out = out.couponUpdate((value << KEY_BITS_26) | (i & KEY_MASK_26));
+ that.couponUpdate((value << KEY_BITS_26) | (i & KEY_MASK_26));
}
- return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/Hll4Array.java b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
index 5c4af9d..d9f74a6 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll4Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
@@ -116,8 +116,7 @@ class Hll4Array extends HllArray {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
+ void mergeTo(final HllSketchImpl that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0; slotNo < slots; slotNo++) {
int value = hllByteArr[slotNo >>> 1] & 0xFF;
@@ -129,9 +128,8 @@ class Hll4Array extends HllArray {
value = nib;
}
if (value == 0) { continue; }
- out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
+ that.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
}
- return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/Hll6Array.java b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
index 495b54a..f8d17d4 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
@@ -95,17 +95,15 @@ class Hll6Array extends HllArray {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
+ void mergeTo(final HllSketchImpl that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0, bitOffset = 0; slotNo < slots; slotNo++, bitOffset += 6) {
final int tmp = mem.getShort(bitOffset / 8);
final int shift = (bitOffset % 8) & 0X7;
final int value = (tmp >>> shift) & VAL_MASK_6;
if (value == 0) { continue; }
- out = out.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
+ that.couponUpdate((value << KEY_BITS_26) | (slotNo & KEY_MASK_26));
}
- return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/Hll8Array.java b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
index f810f1c..535df45 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
@@ -92,15 +92,21 @@ class Hll8Array extends HllArray {
}
@Override
- HllSketchImpl mergeTo(final HllSketchImpl impl) {
- HllSketchImpl out = impl;
- final int slots = 1 << lgConfigK;
- for (int i = 0; i < slots; i++ ) {
+ void mergeTo(final HllSketchImpl that) {
+ final int thisK = 1 << lgConfigK;
+ if ((thisK == that.getLgConfigK()) && (that instanceof Hll8Array)) {
+ final byte[] thisArr = hllByteArr;
+ final byte[] thatArr = ((Hll8Array) that).hllByteArr;
+ for (int i = 0; i < thisK; i++) {
+ thatArr[i] = (thisArr[i] > thatArr[i]) ? thisArr[i] : thatArr[i];
+ }
+ return;
+ }
+ for (int i = 0; i < thisK; i++ ) {
final int value = hllByteArr[i] & VAL_MASK_6;
if (value == 0) { continue; }
- out = out.couponUpdate((value << KEY_BITS_26) | (i & KEY_MASK_26));
+ that.couponUpdate((value << KEY_BITS_26) | (i & KEY_MASK_26));
}
- return out;
}
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/HllEstimators.java b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
index f77b299..4aed96d 100644
--- a/src/main/java/org/apache/datasketches/hll/HllEstimators.java
+++ b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
@@ -97,6 +97,7 @@ class HllEstimators {
//In C: again-two-registers.c hhb_get_composite_estimate L1489
static final double hllCompositeEstimate(final AbstractHllArray absHllArr) {
final int lgConfigK = absHllArr.getLgConfigK();
+ //TODO Rebuild KxQ registers.
final double rawEst = getHllRawEstimate(lgConfigK, absHllArr.getKxQ0() + absHllArr.getKxQ1());
final double[] xArr = CompositeInterpolationXTable.xArrs[lgConfigK - MIN_LOG_K];
diff --git a/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java b/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
index 15497c5..09f47fa 100644
--- a/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
+++ b/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
@@ -98,7 +98,7 @@ abstract class HllSketchImpl {
abstract PairIterator iterator();
- abstract HllSketchImpl mergeTo(HllSketchImpl impl);
+ abstract void mergeTo(HllSketchImpl impl);
abstract void putEmptyFlag(boolean empty);
diff --git a/src/main/java/org/apache/datasketches/hll/Union.java b/src/main/java/org/apache/datasketches/hll/Union.java
index 1a58984..3611c23 100644
--- a/src/main/java/org/apache/datasketches/hll/Union.java
+++ b/src/main/java/org/apache/datasketches/hll/Union.java
@@ -298,18 +298,17 @@ public class Union extends BaseHllSketch {
* perform the union. This may involve swapping, down-sampling, transforming, and / or
* copying one of the arguments and may completely replace the internals of the union.
*
- * <p>Copies or downsamples the given HLLmode sketch to tgtLgK, HLL_8.</p>
- *
* <p>A swap in update direction is required:</p>
- * <ul><li>If Gadget is in LIST, SET or EMPTY mode, AND </li>
- * <li>(The incoming source sketch is in HLL mode and not empty,</li>
- * <li>OR, if both source and Gadget are in HLL mode and src LgK < Gadget LgK.)</li>
+ * <ul><li>If the Gadget is in LIST, SET or EMPTY mode, AND
+ * The source sketch is in HLL mode.
+ * The source sketch will need to be copied or downsampled to the heap in HLL_8 mode if it is
+ * larger than maxLgK, and then replace the Gadget. If the Gadget was Memory, the resulting
+ * heap object will need to be converted to Memory form.</li>
* </ul>
*
- * <p>A downsample or copy is required:</p>
- * <ul><li>If swap is required, AND</li>
- * <li>(If source lgK > destination LgK OR if source sketch is not type HLL_8),</li>
- * <li>OR, if source lgK > maxLgK.</li>
+ * <p>A downsample of gadget is required:</p>
+ * <ul><li>If both source and Gadget are in HLL mode AND source LgK <b>less than</b> Gadget LgK.
+ * Downsample Gadget, convert back to memory form if required, update gadget from source.</li>
* </ul>
*
* @param incoming the given incoming sketch, which may not be modified.
@@ -324,7 +323,7 @@ public class Union extends BaseHllSketch {
assert gadget.getTgtHllType() == HLL_8;
if ((incoming == null) || incoming.isEmpty()) { return gadget.hllSketchImpl; }
final HllSketchImpl srcImpl = incoming.hllSketchImpl;
- HllSketchImpl dstImpl = gadget.hllSketchImpl;
+ HllSketchImpl gdtImpl = gadget.hllSketchImpl;
final int inLgK = incoming.getLgConfigK();
final int gadgetLgK = gadget.getLgConfigK();
@@ -333,139 +332,136 @@ public class Union extends BaseHllSketch {
final int sw = (hi2bits << 2) | lo2bits;
switch (sw) {
case 0: { //src: LIST, gadget: LIST
- dstImpl = srcImpl.mergeTo(dstImpl);
+ srcImpl.mergeTo(gdtImpl);
//whichever is True wins:
- dstImpl.putOutOfOrderFlag(dstImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
+ gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
break;
}
case 1: { //src: SET, gadget: LIST
- dstImpl = srcImpl.mergeTo(dstImpl);
- dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
case 2: { //src: HLL, gadget: LIST; Swap, Downsample if srcLgK > maxLgK
- final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
- HllSketchImpl dstImplTmp = dstImpl.mergeTo(heapSrcHll8); //reverse merge
+ final HllSketchImpl srcHll8HeapCopy = srcImpl.copyAs(HLL_8); //to heap HLL8
+ final boolean gdtIsMem = gdtImpl.isMemory();
+ gdtImpl.mergeTo(srcHll8HeapCopy); //reverse merge
+ //srcHll8HeapCopy now has the right merged data.
+
+ HllSketchImpl gdtImplTmp = gdtImpl;
if (inLgK > lgMaxK) { //downsample
- dstImplTmp = copyOrDownsampleHll(dstImplTmp, lgMaxK);
+ gdtImplTmp = copyOrDownsampleHll(gdtImplTmp, lgMaxK);
}
- if (dstImpl.isMemory()) {
- final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = dstImpl.getWritableMemory(); //use the original wmem
+ if (gdtIsMem) {
+ final byte[] byteArr = gdtImplTmp.toUpdatableByteArray();
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the original wmem
wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
+ gdtImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
}
- dstImpl = dstImplTmp;
+ gdtImpl = gdtImplTmp;
//whichever is True wins:
- dstImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag() | dstImpl.isOutOfOrderFlag());
+ gdtImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag() | gdtImpl.isOutOfOrderFlag());
break;
}
case 4: { //src: LIST, gadget: SET
- dstImpl = srcImpl.mergeTo(dstImpl);
- dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
case 5: { //src: SET, gadget: SET
- dstImpl = srcImpl.mergeTo(dstImpl);
- dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
case 6: { //src: HLL, gadget: SET
final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
- HllSketchImpl dstImplTmp = dstImpl.mergeTo(heapSrcHll8); //reverse merge
+ final boolean memory = gdtImpl.isMemory();
+ gdtImpl.mergeTo(heapSrcHll8); //reverse merge
+ HllSketchImpl dstImplTmp = gdtImpl;
if (inLgK > lgMaxK) { //downsample
- dstImplTmp = copyOrDownsampleHll(dstImplTmp, lgMaxK);
+ dstImplTmp = copyOrDownsampleHll(gdtImpl, lgMaxK);
}
- if (dstImpl.isMemory()) {
+ if (memory) {
final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = dstImpl.getWritableMemory(); //use the original wmem
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the original wmem
wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
}
- dstImpl = dstImplTmp;
- dstImpl.putOutOfOrderFlag(true); //merging SET into non-empty HLL -> true
+ gdtImpl = dstImplTmp;
+ gdtImpl.putOutOfOrderFlag(true); //merging SET into non-empty HLL -> true
break;
}
case 8: { //src: LIST, gadget: HLL
- dstImpl = srcImpl.mergeTo(dstImpl);
+ srcImpl.mergeTo(gdtImpl);
//whichever is True wins:
- dstImpl.putOutOfOrderFlag(dstImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
+ gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
break;
}
case 9: { //src: SET, gadget: HLL
- dstImpl = srcImpl.mergeTo(dstImpl);
- dstImpl.putOutOfOrderFlag(true); //merging SET into existing HLL -> true
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(true); //merging SET into existing HLL -> true
break;
}
case 10: { //src: HLL, gadget: HLL
if (inLgK >= gadgetLgK) {
- dstImpl = srcImpl.mergeTo(dstImpl); //normal merge direction
- dstImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
+ srcImpl.mergeTo(gdtImpl); //normal merge direction
+ gdtImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
break; //done
}
+ final boolean memory = gdtImpl.isMemory();
//inLgK < gadgetLgK, must reverse merge to src copy, then downsample gadget to inLgK
final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
- HllSketchImpl dstImplTmp = dstImpl.mergeTo(heapSrcHll8); //swap merge direction
- dstImplTmp = copyOrDownsampleHll(dstImplTmp, inLgK); //heap, HLL8, inLgK
+ gdtImpl.mergeTo(heapSrcHll8); //swap merge direction
+ HllSketchImpl dstImplTmp = copyOrDownsampleHll(heapSrcHll8, inLgK); //heap, HLL8, inLgK
- if (dstImpl.isMemory()) {
+ if (memory) {
final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = dstImpl.getWritableMemory(); //need to use the original wmem
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //need to use the original wmem
wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
}
- dstImpl = dstImplTmp;
- dstImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
+ gdtImpl = dstImplTmp;
+ gdtImpl.putOutOfOrderFlag(true); //union of two HLL modes is always true
break;
}
case 12: { //src: LIST, gadget: empty
- dstImpl = srcImpl.mergeTo(dstImpl);
- dstImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is
break;
}
case 13: { //src: SET, gadget: empty
- dstImpl = srcImpl.mergeTo(dstImpl);
- dstImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
+ srcImpl.mergeTo(gdtImpl);
+ gdtImpl.putOutOfOrderFlag(true); //SET oooFlag is always true
break;
}
case 14: { //src: HLL, gadget: empty; Downsample if srcLgK > maxLgK
final HllSketchImpl heapSrcHll8 = srcImpl.copyAs(HLL_8); //to heap, whether HLL8 or not
+ final boolean memory = gdtImpl.isMemory();
HllSketchImpl dstImplTmp = heapSrcHll8; //no merge
if (inLgK > lgMaxK) { //downsample
dstImplTmp = copyOrDownsampleHll(dstImplTmp, lgMaxK);
}
- if (dstImpl.isMemory()) {
+ if (memory) {
final byte[] byteArr = dstImplTmp.toUpdatableByteArray();
- final WritableMemory wmem = dstImpl.getWritableMemory(); //use the original wmem
+ final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the original wmem
wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
dstImplTmp = HllSketch.writableWrap(wmem).hllSketchImpl;
}
- dstImpl = dstImplTmp;
- dstImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is.
+ gdtImpl = dstImplTmp;
+ gdtImpl.putOutOfOrderFlag(srcImpl.isOutOfOrderFlag()); //whatever source is.
break;
}
}
- return dstImpl;
+ return gdtImpl;
}
//Used by union operator. Always copies or downsamples to Heap HLL_8.
//Caller must ultimately manage oooFlag, as caller has more context.
/**
- * Copies or downsamples the given HLLmode sketch to tgtLgK, HLL_8.
- *
- * <p>A swap in update direction is required:</p>
- * <ul><li>If Gadget is in LIST, SET or EMPTY mode, AND </li>
- * <li>The incoming source sketch is in HLL mode and not empty.</li>
- * <li>Or, if both source and Gadget are in HLL mode and src LgK < Gadget LgK.</li>
- * </ul>
- *
- * <p>A downsample is required:</p>
- * <ul><li>If swap is required, AND</li>
- * <li>If source lgK > Gadget LgK OR if source sketch is not type HLL_8.</li>
- * </ul>
+ * Copies or downsamples the given HLLmode sketch to tgtLgK, HLL_8, on the heap.
*
* @param srcImpl the HllSketchImpl to possibly downsample
* @param tgtLgK the LgK to downsample to.
@@ -473,11 +469,11 @@ public class Union extends BaseHllSketch {
*/
private static final HllSketchImpl copyOrDownsampleHll(
final HllSketchImpl srcImpl, final int tgtLgK) {
- assert srcImpl.getCurMode() == HLL;
+ assert (srcImpl.getCurMode() == HLL) && (!srcImpl.isEmpty());
final AbstractHllArray src = (AbstractHllArray) srcImpl;
final int srcLgK = src.getLgConfigK();
if ((srcLgK <= tgtLgK) && (src.getTgtHllType() == TgtHllType.HLL_8)) {
- return src.copy();
+ return src.copy(); //on heap
}
final int minLgK = Math.min(srcLgK, tgtLgK);
final HllArray tgtHllArr = HllArray.newHeapHll(minLgK, TgtHllType.HLL_8);
@@ -488,7 +484,7 @@ public class Union extends BaseHllSketch {
//both of these are required for isomorphism
tgtHllArr.putHipAccum(src.getHipAccum());
tgtHllArr.putOutOfOrderFlag(src.isOutOfOrderFlag());
- return tgtHllArr;
+ return tgtHllArr; //on heap
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 10/10: Interim update
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch NewHllIterator
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 53e1d9f1c48f657bd3cd412048c7fdc3d504fe40
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Dec 17 10:05:34 2019 -0800
Interim update
---
.../apache/datasketches/hll/AbstractCoupons.java | 5 +
.../apache/datasketches/hll/AbstractHllArray.java | 5 +
.../org/apache/datasketches/hll/CouponList.java | 2 +-
.../apache/datasketches/hll/DirectCouponList.java | 2 +-
.../apache/datasketches/hll/DirectHll4Array.java | 2 +-
.../apache/datasketches/hll/DirectHll6Array.java | 2 +-
.../apache/datasketches/hll/DirectHll8Array.java | 2 +-
.../org/apache/datasketches/hll/Hll4Array.java | 2 +-
.../org/apache/datasketches/hll/Hll6Array.java | 2 +-
.../org/apache/datasketches/hll/Hll8Array.java | 2 +-
.../org/apache/datasketches/hll/HllSketch.java | 17 +
.../org/apache/datasketches/hll/HllSketchImpl.java | 4 +-
.../java/org/apache/datasketches/hll/Union.java | 268 ++++++------
.../datasketches/hll/DirectUnionCaseTest.java | 458 -------------------
.../org/apache/datasketches/hll/UnionCaseTest.java | 487 +++++++++------------
15 files changed, 377 insertions(+), 883 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java b/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java
index a713d28..bb01e13 100644
--- a/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java
+++ b/src/main/java/org/apache/datasketches/hll/AbstractCoupons.java
@@ -65,6 +65,11 @@ abstract class AbstractCoupons extends HllSketchImpl {
return max(est, couponCount);
}
+ @Override
+ double getHipEstimate() {
+ return getEstimate();
+ }
+
abstract int getLgCouponArrInts();
@Override
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
index aa20026..d9d0ee3 100644
--- a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
+++ b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
@@ -101,6 +101,11 @@ abstract class AbstractHllArray extends HllSketchImpl {
*/
abstract double getHipAccum();
+ @Override
+ double getHipEstimate() {
+ return getHipAccum();
+ }
+
abstract int getHllByteArrBytes();
/**
diff --git a/src/main/java/org/apache/datasketches/hll/CouponList.java b/src/main/java/org/apache/datasketches/hll/CouponList.java
index 7fc363e..5a3c6e6 100644
--- a/src/main/java/org/apache/datasketches/hll/CouponList.java
+++ b/src/main/java/org/apache/datasketches/hll/CouponList.java
@@ -206,7 +206,7 @@ class CouponList extends AbstractCoupons {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int arrLen = couponIntArr.length;
for (int i = 0; i < arrLen; i++) {
final int pair = couponIntArr[i];
diff --git a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
index 4cc8acb..52c8f93 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
@@ -224,7 +224,7 @@ class DirectCouponList extends AbstractCoupons {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int lenInts = (compact) ? getCouponCount() : 1 << getLgCouponArrInts();
final int dataStart = getMemDataStart();
for (int i = 0; i < lenInts; i++) {
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
index 900b637..ea2e321 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll4Array.java
@@ -119,7 +119,7 @@ class DirectHll4Array extends DirectHllArray {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0; slotNo < slots; slotNo++) {
int value = mem.getByte(HLL_BYTE_ARR_START + (slotNo >>> 1)) & 0xFF;
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
index 2a13dbf..ce5286d 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll6Array.java
@@ -86,7 +86,7 @@ class DirectHll6Array extends DirectHllArray {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0, bitOffset = 0; slotNo < slots; slotNo++, bitOffset += 6) {
final int tmp = mem.getShort(HLL_BYTE_ARR_START + (bitOffset / 8));
diff --git a/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java b/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
index 77fe08d..0d674db 100644
--- a/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/DirectHll8Array.java
@@ -88,7 +88,7 @@ class DirectHll8Array extends DirectHllArray {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int slots = 1 << lgConfigK;
for (int i = 0; i < slots; i++ ) {
final int value = mem.getByte(HLL_BYTE_ARR_START + i) & VAL_MASK_6;
diff --git a/src/main/java/org/apache/datasketches/hll/Hll4Array.java b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
index d9f74a6..470d6e1 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll4Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll4Array.java
@@ -116,7 +116,7 @@ class Hll4Array extends HllArray {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0; slotNo < slots; slotNo++) {
int value = hllByteArr[slotNo >>> 1] & 0xFF;
diff --git a/src/main/java/org/apache/datasketches/hll/Hll6Array.java b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
index f8d17d4..190d37e 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll6Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll6Array.java
@@ -95,7 +95,7 @@ class Hll6Array extends HllArray {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int slots = 1 << lgConfigK;
for (int slotNo = 0, bitOffset = 0; slotNo < slots; slotNo++, bitOffset += 6) {
final int tmp = mem.getShort(bitOffset / 8);
diff --git a/src/main/java/org/apache/datasketches/hll/Hll8Array.java b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
index ec87630..4ea367c 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
@@ -92,7 +92,7 @@ class Hll8Array extends HllArray {
}
@Override
- void mergeTo(final HllSketchImpl that) {
+ void mergeTo(final HllSketch that) {
final int thisK = 1 << lgConfigK;
// if ((thisK == that.getLgConfigK()) && (that instanceof Hll8Array)) {
// //does not update KxQ
diff --git a/src/main/java/org/apache/datasketches/hll/HllSketch.java b/src/main/java/org/apache/datasketches/hll/HllSketch.java
index 16c02b9..ba1e222 100644
--- a/src/main/java/org/apache/datasketches/hll/HllSketch.java
+++ b/src/main/java/org/apache/datasketches/hll/HllSketch.java
@@ -278,6 +278,10 @@ public class HllSketch extends BaseHllSketch {
return hllSketchImpl.getEstimate();
}
+ double getHipEstimate() {
+ return hllSketchImpl.getHipEstimate();
+ }
+
@Override
public int getLgConfigK() {
return hllSketchImpl.getLgConfigK();
@@ -329,6 +333,10 @@ public class HllSketch extends BaseHllSketch {
return hllSketchImpl.getUpdatableSerializationBytes();
}
+ WritableMemory getWritableMemory() {
+ return hllSketchImpl.getWritableMemory();
+ }
+
@Override
public double getUpperBound(final int numStdDev) {
return hllSketchImpl.getUpperBound(numStdDev);
@@ -364,6 +372,14 @@ public class HllSketch extends BaseHllSketch {
return hllSketchImpl.isSameResource(mem);
}
+ void mergeTo(final HllSketch that) {
+ hllSketchImpl.mergeTo(that);
+ }
+
+ void putOutOfOrderFlag(final boolean oooFlag) {
+ hllSketchImpl.putOutOfOrderFlag(oooFlag);
+ }
+
@Override
public void reset() {
hllSketchImpl = hllSketchImpl.reset();
@@ -388,6 +404,7 @@ public class HllSketch extends BaseHllSketch {
sb.append(" Log Config K : ").append(getLgConfigK()).append(LS);
sb.append(" Hll Target : ").append(getTgtHllType()).append(LS);
sb.append(" Current Mode : ").append(getCurMode()).append(LS);
+ sb.append(" Memory : ").append(isMemory()).append(LS);
sb.append(" LB : ").append(getLowerBound(1)).append(LS);
sb.append(" Estimate : ").append(getEstimate()).append(LS);
sb.append(" UB : ").append(getUpperBound(1)).append(LS);
diff --git a/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java b/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
index 09f47fa..6465403 100644
--- a/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
+++ b/src/main/java/org/apache/datasketches/hll/HllSketchImpl.java
@@ -64,6 +64,8 @@ abstract class HllSketchImpl {
abstract double getEstimate();
+ abstract double getHipEstimate();
+
int getLgConfigK() {
return lgConfigK;
}
@@ -98,7 +100,7 @@ abstract class HllSketchImpl {
abstract PairIterator iterator();
- abstract void mergeTo(HllSketchImpl impl);
+ abstract void mergeTo(HllSketch that);
abstract void putEmptyFlag(boolean empty);
diff --git a/src/main/java/org/apache/datasketches/hll/Union.java b/src/main/java/org/apache/datasketches/hll/Union.java
index d9fdd30..c18db38 100644
--- a/src/main/java/org/apache/datasketches/hll/Union.java
+++ b/src/main/java/org/apache/datasketches/hll/Union.java
@@ -302,7 +302,7 @@ public class Union extends BaseHllSketch {
* The source sketch is in HLL mode.
* The source sketch will need to be copied or downsampled to the heap in HLL_8 mode if it is
* larger than maxLgK, and then replace the Gadget. If the Gadget was Memory, the resulting
- * heap object will need to be converted to Memory form.</li>
+ * heap object will need to be converted to Memory form using the Gadget Memory.</li>
* </ul>
*
* <p>A downsample of gadget is required:</p>
@@ -310,31 +310,29 @@ public class Union extends BaseHllSketch {
* Downsample Gadget, convert back to memory form if required, update gadget from source.</li>
* </ul>
*
- * @param incoming the given incoming sketch, which may not be modified.
+ * @param source the given incoming sketch, which must not be modified.
* @param gadget the given gadget sketch, which must have a target of HLL_8 and may be
* modified.
* @param lgMaxK the maximum value of log2 K for this union.
* @return the union of the two sketches in the form of the internal HllSketchImpl, which for
* the union is always in HLL_8 form.
*/
- private static final HllSketchImpl unionImpl(final HllSketch incoming,
- final HllSketch gadget, final int lgMaxK) {
+ private static HllSketchImpl unionImpl(final HllSketch source, final HllSketch gadget,
+ final int lgMaxK) {
assert gadget.getTgtHllType() == HLL_8;
- if ((incoming == null) || incoming.isEmpty()) { return gadget.hllSketchImpl; }
- final HllSketchImpl srcImpl = incoming.hllSketchImpl;
- HllSketchImpl gdtImpl = gadget.hllSketchImpl;
- if (srcImpl.getCurMode() == CurMode.LIST ) {
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
- return gdtImpl;
+ if ((source == null) || source.isEmpty()) { return gadget.hllSketchImpl; }
+ if (source.getCurMode() == CurMode.LIST ) {
+ source.mergeTo(gadget);
+ gadget.putOutOfOrderFlag(gadget.isOutOfOrderFlag() | source.isOutOfOrderFlag());
+ return gadget.hllSketchImpl;
}
- if (srcImpl.getCurMode() == CurMode.SET ) {
- srcImpl.mergeTo(gdtImpl);
- gdtImpl.putOutOfOrderFlag(true);
- return gdtImpl;
+ if (source.getCurMode() == CurMode.SET ) {
+ source.mergeTo(gadget);
+ gadget.putOutOfOrderFlag(true);
+ return gadget.hllSketchImpl;
}
//Hereafter, the srcImpl is in HLL mode.
- final int srcLgK = incoming.getLgConfigK();
+ final int srcLgK = source.getLgConfigK();
final int gadgetLgK = gadget.getLgConfigK();
final int bit0 = gadget.isMemory() ? 1 : 0;
final int bits1_2 = (gadget.isEmpty() ? 3 : gadget.getCurMode().ordinal()) << 1;
@@ -342,168 +340,164 @@ public class Union extends BaseHllSketch {
final int bit4 = (srcLgK > lgMaxK) ? 16 : 0;
final int sw = bit4 | bit3 | bits1_2 | bit0;
switch (sw) {
- case 0: //src <= max, src >= gdt, gdtLIST, gdtHeap, swap, no downsample, ooof=OR
- case 8: //src <= max, src < gdt, gdtLIST, gdtHeap, swap, no downsample, ooof=OR
- { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- gdtImpl = srcHll8Heap; //replace gdt
- gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
- break;
+ case 0: //src <= max, src >= gdt, gdtLIST, gdtHeap, reverse merge, no downsample, ooof=OR
+ case 8: //src <= max, src < gdt, gdtLIST, gdtHeap, reverse merge, no downsample, ooof=OR
+ { final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final HllSketch gdtTmp = srcHll8Heap; //replace gdt
+ gdtTmp.putOutOfOrderFlag(gdtTmp.isOutOfOrderFlag() | source.isOutOfOrderFlag());
+ return gdtTmp.hllSketchImpl;
}
- case 1: //src <= max, src >= gdt, gdtLIST, gdtDirect, swap, no downsample, ooof=OR
- case 9: //src <= max, src < gdt, gdtLIST, gdtDirect, swap, no downsample, ooof=OR
- { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
- final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
- gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
- break;
+ case 1: //src <= max, src >= gdt, gdtLIST, gdtDirect, reverse merge, no downsample, ooof=OR
+ case 9: //src <= max, src < gdt, gdtLIST, gdtDirect, reverse merge, no downsample, ooof=OR
+ { final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray();//serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ final HllSketch gdtTmp = HllSketch.writableWrap(wmem); //wrap & replace gdt
+ gdtTmp.putOutOfOrderFlag(gdtTmp.isOutOfOrderFlag() | source.isOutOfOrderFlag());
+ return gdtTmp.hllSketchImpl;
}
- case 2: //src <= max, src >= gdt, gdtSET, gdtHeap, swap, no downsample, ooof=True
- case 10: //src <= max, src < gdt, gdtSET, gdtHeap, swap, no downsample, ooof=True
- { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- gdtImpl = srcHll8Heap; //replace gdt
- gdtImpl.putOutOfOrderFlag(true);
- break;
+ case 2: //src <= max, src >= gdt, gdtSET, gdtHeap, reverse merge, no downsample, ooof=True
+ case 10: //src <= max, src < gdt, gdtSET, gdtHeap, reverse merge, no downsample, ooof=True
+ { final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final HllSketch gdtTmp = srcHll8Heap; //replace gdt
+ gdtTmp.putOutOfOrderFlag(true);
+ return gdtTmp.hllSketchImpl;
}
- case 3: //src <= max, src >= gdt, gdtSET, gdtDirect, swap, no downsample, ooof=True
- case 11: //src <= max, src < gdt, gdtSET, gdtDirect, swap, no downsample, ooof=True
- { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
- final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
- gdtImpl.putOutOfOrderFlag(true);
- break;
+ case 3: //src <= max, src >= gdt, gdtSET, gdtDirect, reverse merge, no downsample, ooof=True
+ case 11: //src <= max, src < gdt, gdtSET, gdtDirect, reverse merge, no downsample, ooof=True
+ { final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray();//serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ final HllSketch gdtTmp = HllSketch.writableWrap(wmem); //wrap & replace gdt
+ gdtTmp.putOutOfOrderFlag(true);
+ return gdtTmp.hllSketchImpl;
}
- case 4: //src <= max, src >= gdt, gdtHLL, gdtHeap, no swap, no downsample, ooof=True
- case 5: //src <= max, src >= gdt, gdtHLL, gdtDirect, no swap, no downsample, ooof=True
- case 20: //src > max, src >= gdt, gdtHLL, gdtHeap, no swap, no downsample, ooof=True
- case 21: //src > max, src >= gdt, gdtHLL, gdtDirect, no swap, no downsample, ooof=True
+ case 4: //src <= max, src >= gdt, gdtHLL, gdtHeap, forward merge, no downsample, ooof=True
+ case 5: //src <= max, src >= gdt, gdtHLL, gdtDirect, forward merge, no downsample, ooof=True
+ case 20: //src > max, src >= gdt, gdtHLL, gdtHeap, forward merge, no downsample, ooof=True
+ case 21: //src > max, src >= gdt, gdtHLL, gdtDirect, forward merge, no downsample, ooof=True
{ //Possible Optimization if srcLgK = gdtLgK && src is HLL_8
- srcImpl.mergeTo(gdtImpl); //merge src -> gdt
- gdtImpl.putOutOfOrderFlag(true);
- break;
+ source.mergeTo(gadget); //merge src -> gdt
+ gadget.putOutOfOrderFlag(true);
+ return gadget.hllSketchImpl;
}
- case 6: //src <= max, src >= gdt, gdtEmpty, gdtHeap, no swap, no downsample, ooof=Src
- case 14: //src <= max, src < gdt, gdtEmpty, gdtHeap, no swap, no downsample, ooof=Src
- { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
- gdtImpl = srcHll8Heap;
+ case 6: //src <= max, src >= gdt, gdtEmpty, gdtHeap, replace, no downsample, ooof=Src
+ case 14: //src <= max, src < gdt, gdtEmpty, gdtHeap, replace, no downsample, ooof=Src
+ { final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
//ooof is already what source is.
- break;
+ return srcHll8Heap.hllSketchImpl;
}
- case 7: //src <= max, src >= gdt, gdtEmpty, gdtDirect, no swap, no downsample, ooof=Src
- case 15: //src <= max, src < gdt, gdtEmpty, gdtDirect, no swap, no downsample, ooof=Src
- { final HllSketchImpl srcHll8Heap = srcImpl.copyAs(HLL_8); //copy src to Heap
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
- final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ case 7: //src <= max, src >= gdt, gdtEmpty, gdtDirect, replace mem, no downsample, ooof=Src
+ case 15: //src <= max, src < gdt, gdtEmpty, gdtDirect, replace mem, no downsample, ooof=Src
+ { final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray();//serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ final HllSketch gdtTmp = HllSketch.writableWrap(wmem); //wrap & replace gdt
//ooof is already what source is.
- break;
+ return gdtTmp.hllSketchImpl;
}
- case 12: //src <= max, src < gdt, gdtHLL, gdtHeap, no swap, downsample Gdt, ooof=True
+ case 12: //src <= max, src < gdt, gdtHLL, gdtHeap, fwd Merge/replace, downsample Gdt, ooof=True
{
- final HllSketchImpl gdtHll8Heap = downsample(gdtImpl, srcLgK); //downsample gdt to srcLgK
- srcImpl.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
- gdtImpl = gdtHll8Heap; //replace gdt
- gdtImpl.putOutOfOrderFlag(true);
- break;
+ final HllSketch gdtHll8Heap = downsample(gadget, srcLgK); //downsample gdt to srcLgK
+ source.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
+ gdtHll8Heap.putOutOfOrderFlag(true);
+ return gdtHll8Heap.hllSketchImpl;
}
- case 13: //src <= max, src < gdt, gdtHLL, gdtDirect, no swap, downsample Gdt, ooof=True
+ case 13: //src <= max, src < gdt, gdtHLL, gdtDirect, fwd merge/repl mem, downsample Gdt, ooof=True
{
- final HllSketchImpl gdtHll8Heap = downsample(gdtImpl, srcLgK); //downsample gdt to srcLgK
- srcImpl.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
- final byte[] byteArr = gdtHll8Heap.toUpdatableByteArray(); //serialize gdtCopy
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
- gdtImpl.putOutOfOrderFlag(true);
- break;
+ final HllSketch gdtHll8Heap = downsample(gadget, srcLgK); //downsample gdt to srcLgK
+ source.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
+ final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = gdtHll8Heap.toUpdatableByteArray();//serialize gdtCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ final HllSketch gdtTmp = HllSketch.writableWrap(wmem); //wrap & replace gdt
+ gdtTmp.putOutOfOrderFlag(true);
+ return gdtTmp.hllSketchImpl;
}
- case 16: //src > max, src >= gdt, gdtList, gdtHeap, swap, downsample Src, ooof=OR
+ case 16: //src > max, src >= gdt, gdtList, gdtHeap, reverse merge, downsample Src, ooof=OR
{
- final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- gdtImpl = srcHll8Heap; //replace gdt
- gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
- break;
+ final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final HllSketch gdtTmp = srcHll8Heap; //replace gdt
+ gdtTmp.putOutOfOrderFlag(gdtTmp.isOutOfOrderFlag() | source.isOutOfOrderFlag());
+ return gdtTmp.hllSketchImpl;
}
- case 17: //src > max, src >= gdt, gdtList, gdtDirect, swap, downsample Src, ooof=OR
+ case 17: //src > max, src >= gdt, gdtList, gdtDirect, rev merge/repl mem, downsample Src, ooof=OR
{
- final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
- final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
- gdtImpl.putOutOfOrderFlag(gdtImpl.isOutOfOrderFlag() | srcImpl.isOutOfOrderFlag());
- break;
+ final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray();//serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ final HllSketch gdtTmp = HllSketch.writableWrap(wmem); //wrap & replace gdt
+ gdtTmp.putOutOfOrderFlag(gdtTmp.isOutOfOrderFlag() | source.isOutOfOrderFlag());
+ return gdtTmp.hllSketchImpl;
}
- case 18: //src > max, src >= gdt, gdtSet, gdtHeap, swap, downsample Src, ooof=True
+ case 18: //src > max, src >= gdt, gdtSet, gdtHeap, rev merge, downsample Src, ooof=True
{
- final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- gdtImpl = srcHll8Heap; //replace gdt
- gdtImpl.putOutOfOrderFlag(true);
- break;
+ final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final HllSketch gdtTmp = srcHll8Heap; //replace gdt
+ gdtTmp.putOutOfOrderFlag(true);
+ return gdtTmp.hllSketchImpl;
}
- case 19: //src > max, src >= gdt, gdtSet, gdtDirect, swap, downsample Src, ooof=True
+ case 19: //src > max, src >= gdt, gdtSet, gdtDirect, rev merge/rep mem, downsample Src, ooof=True
{
- final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
- gdtImpl.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
- final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
- gdtImpl.putOutOfOrderFlag(true);
- break;
+ final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
+ gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray();//serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ final HllSketch gdtTmp = HllSketch.writableWrap(wmem); //wrap & replace gdt
+ gdtTmp.putOutOfOrderFlag(true);
+ return gdtTmp.hllSketchImpl;
}
- case 22: //src > max, src >= gdt, gdtEmpty, gdtHeap, no swap, downsample Src, ooof=Src
+ case 22: //src > max, src >= gdt, gdtEmpty, gdtHeap, replace, downsample Src, ooof=Src
{
- final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
- gdtImpl = srcHll8Heap; //replace gdt
+ final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
+ return srcHll8Heap.hllSketchImpl; //replace gdt
//ooof is already what source is.
- break;
}
- case 23: //src > max, src >= gdt, gdtEmpty, gdtDirect, no swap, downsample Src, ooof=Src
+ case 23: //src > max, src >= gdt, gdtEmpty, gdtDirect, replace mem, downsample Src, ooof=Src
{
- final HllSketchImpl srcHll8Heap = downsample(srcImpl, lgMaxK); //downsample src to Max
- final WritableMemory wmem = gdtImpl.getWritableMemory(); //use the gdt wmem
- final byte[] byteArr = srcHll8Heap.toUpdatableByteArray(); //serialize srcCopy
- wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
- gdtImpl = HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
+ final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
+ final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
+ final byte[] byteArr = srcHll8Heap.toUpdatableByteArray();//serialize srcCopy
+ wmem.putByteArray(0, byteArr, 0, byteArr.length); //replace old data with new
+ return HllSketch.writableWrap(wmem).hllSketchImpl; //wrap & replace gdt
//ooof is already what source is.
- break;
}
+ default: return gadget.hllSketchImpl;
}
- return gdtImpl;
}
//Used by union operator. Always copies or downsamples to Heap HLL_8.
//Caller must ultimately manage oooFlag, as caller has more context.
/**
- * Copies or downsamples the given HLLmode sketch to tgtLgK, HLL_8, on the heap.
+ * Copies or downsamples the given candidate HLLmode sketch to tgtLgK, HLL_8, on the heap.
*
- * @param candidate the HllSketchImpl to downsample
+ * @param candidate the HllSketch to downsample, must be in HLL mode.
* @param tgtLgK the LgK to downsample to.
- * @return the downsampled HllSketchImpl.
+ * @return the downsampled HllSketch.
*/
- private static final HllSketchImpl downsample(final HllSketchImpl candidate, final int tgtLgK) {
- final AbstractHllArray candArr = (AbstractHllArray) candidate;
+ private static final HllSketch downsample(final HllSketch candidate, final int tgtLgK) {
+ final AbstractHllArray candArr = (AbstractHllArray) candidate.hllSketchImpl;
final HllArray tgtHllArr = HllArray.newHeapHll(tgtLgK, TgtHllType.HLL_8);
- final PairIterator srcItr = candArr.iterator();
- while (srcItr.nextValid()) {
- tgtHllArr.couponUpdate(srcItr.getPair());
+ final PairIterator candItr = candArr.iterator();
+ while (candItr.nextValid()) {
+ tgtHllArr.couponUpdate(candItr.getPair());
}
//both of these are required for isomorphism
tgtHllArr.putHipAccum(candArr.getHipAccum());
- tgtHllArr.putOutOfOrderFlag(candArr.isOutOfOrderFlag());
- return tgtHllArr;
+ tgtHllArr.putOutOfOrderFlag(candidate.isOutOfOrderFlag());
+ return new HllSketch(tgtHllArr);
}
}
diff --git a/src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java b/src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java
deleted file mode 100644
index e00cc09..0000000
--- a/src/test/java/org/apache/datasketches/hll/DirectUnionCaseTest.java
+++ /dev/null
@@ -1,458 +0,0 @@
-/*
- * 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.hll;
-
-import static org.apache.datasketches.hll.CurMode.HLL;
-import static org.apache.datasketches.hll.CurMode.LIST;
-import static org.apache.datasketches.hll.CurMode.SET;
-import static org.apache.datasketches.hll.TgtHllType.HLL_4;
-import static org.apache.datasketches.hll.TgtHllType.HLL_6;
-import static org.apache.datasketches.hll.TgtHllType.HLL_8;
-import static org.testng.Assert.assertEquals;
-import static org.testng.Assert.assertFalse;
-import static org.testng.Assert.assertTrue;
-
-import org.apache.datasketches.memory.WritableMemory;
-import org.testng.annotations.Test;
-
-/**
- * @author Lee Rhodes
- */
-@SuppressWarnings("javadoc")
-public class DirectUnionCaseTest {
- long v = 0;
-
- @Test
- public void checkCase0() { //src: LIST, gadget: LIST, cases 0, 0
- int n1 = 2;
- int n2 = 3;
- int n3 = 2;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- println(u.toString());
- HllSketch h2 = build(11, HLL_6, n2);
- HllSketch h3 = build(10, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- assertEquals(u.getLgConfigK(), 12);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase1() { //src: SET, gadget: LIST, cases 0, 1
- int n1 = 5;
- int n2 = 2;
- int n3 = 16;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST, 5
- HllSketch h2 = build(11, HLL_6, n2); //LIST, 2
- HllSketch h3 = build(10, HLL_8, n3); //SET
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- assertEquals(u.getLgConfigK(), 12);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
-
- }
-
- @Test
- public void checkCase2() { //src: HLL, gadget: LIST, swap, cases 0, 2
- int n1 = 5;
- int n2 = 2;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(10, HLL_4, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase2B() { //src: HLL, gadget: LIST, swap, cases 0, 2; different lgKs
- int n1 = 5;
- int n2 = 2;
- int n3 = 769;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(13, HLL_4, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 12);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase4() { //src: LIST, gadget: SET, cases 0, 4
- int n1 = 6;
- int n2 = 10;
- int n3 = 6;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_6, n2); //SET
- HllSketch h3 = build(10, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- assertEquals(u.getLgConfigK(), 12);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase5() { //src: SET, gadget: SET, cases 0, 5
- int n1 = 6;
- int n2 = 10;
- int n3 = 16;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_6, n2);
- HllSketch h3 = build(10, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- assertEquals(u.getLgConfigK(), 12);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase6() { //src: HLL, gadget: SET, swap, cases 1, 6
- int n1 = 2;
- int n2 = 192;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(10, HLL_4, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase6B() { //src: HLL, gadget: SET, swap, downsize, cases 1, 6
- int n1 = 6;
- int n2 = 20;
- int n3 = 769;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(13, HLL_4, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 12);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase8() { //src: LIST, gadget: HLL, cases 2 (swap), 8
- int n1 = 6;
- int n2 = 193;
- int n3 = 7;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL
- HllSketch h3 = build(10, HLL_8, n3); //LIST
- u.update(h2); //SET
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 11);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase9() { //src: SET, gadget: HLL, cases 2 (swap), 9
- int n1 = 6;
- int n2 = 193;
- int n3 = 16;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL
- HllSketch h3 = build(10, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 11);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase10() { //src: HLL, gadget: HLL, cases 2 (swap), 10, downsample
- int n1 = 6;
- int n2 = 193;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL
- HllSketch h3 = build(10, HLL_8, n3); //HLL
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase10B() { //src: HLL, gadget: HLL, cases 2 (swap), 10, copy to HLL_8
- int n1 = 6;
- int n2 = 193;
- int n3 = 193;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL_6
- HllSketch h3 = build(11, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 11);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase12() { //src: LIST, gadget: empty, case 12
- int n1 = 0;
- int n2 = 0;
- int n3 = 7;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty, ignored
- HllSketch h3 = build(10, HLL_8, n3); //Src LIST
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- assertEquals(u.getLgConfigK(), 12);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase13() { //src: SET, gadget: empty, case 13
- int n1 = 0;
- int n2 = 0;
- int n3 = 16;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty, ignored
- HllSketch h3 = build(10, HLL_8, n3); // Src Set
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- assertEquals(u.getLgConfigK(), 12);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase14() { //src: HLL, gadget: empty, case 14
- int n1 = 0;
- int n2 = 0;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty
- HllSketch h3 = build(10, HLL_8, n3); // Src HLL
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase14B() { //src: HLL, gadget: empty, case 14, downsize
- int n1 = 0;
- int n2 = 0;
- int n3 = 385;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty
- HllSketch h3 = build(12, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 12);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkMisc() {
- Union u = buildUnion(12, 0);
- int bytes = u.getCompactSerializationBytes();
- assertEquals(bytes, 8);
- bytes = Union.getMaxSerializationBytes(7);
- assertEquals(bytes, 40 + 128);
- double v = u.getEstimate();
- assertEquals(v, 0.0, 0.0);
- v = u.getLowerBound(1);
- assertEquals(v, 0.0, 0.0);
- v = u.getUpperBound(1);
- assertEquals(v, 0.0, 0.0);
- assertTrue(u.isEmpty());
- u.reset();
- assertTrue(u.isEmpty());
- println(u.toString(true, false, false, false));
- byte[] bArr = u.toCompactByteArray();
- assertEquals(bArr.length, 8);
- }
-
- private static double errorFactor(int lgK, boolean oooFlag, double numStdDev) {
- double f;
- if (oooFlag) {
- f = (1.2 * numStdDev) / Math.sqrt(1 << lgK);
- } else {
- f = (0.9 * numStdDev) / Math.sqrt(1 << lgK);
- }
- return f;
- }
-
- private Union buildUnion(int lgMaxK, int n) {
- final int bytes = HllSketch.getMaxUpdatableSerializationBytes(lgMaxK, TgtHllType.HLL_8);
- WritableMemory wmem = WritableMemory.allocate(bytes);
- Union u = new Union(lgMaxK, wmem);
- for (int i = 0; i < n; i++) { u.update(i + v); }
- v += n;
- return u;
- }
-
- private HllSketch build(int lgK, TgtHllType tgtHllType, int n) {
- final int bytes = HllSketch.getMaxUpdatableSerializationBytes(lgK, tgtHllType);
- WritableMemory wmem = WritableMemory.allocate(bytes);
- HllSketch sk = new HllSketch(lgK, tgtHllType, wmem);
- for (int i = 0; i < n; i++) { sk.update(i + v); }
- v += n;
- return sk;
- }
-
- @Test
- public void printlnTest() {
- println("PRINTING: "+this.getClass().getName());
- }
-
- /**
- * @param s value to print
- */
- static void println(String s) {
- //System.out.println(s); //disable here
- }
-
-
-}
diff --git a/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java b/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
index c5daf8d..633e9eb 100644
--- a/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
+++ b/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
@@ -19,9 +19,10 @@
package org.apache.datasketches.hll;
-import static org.apache.datasketches.hll.CurMode.HLL;
import static org.apache.datasketches.hll.CurMode.LIST;
import static org.apache.datasketches.hll.CurMode.SET;
+import static org.apache.datasketches.hll.HllUtil.HLL_HIP_RSE_FACTOR;
+import static org.apache.datasketches.hll.HllUtil.HLL_NON_HIP_RSE_FACTOR;
import static org.apache.datasketches.hll.TgtHllType.HLL_4;
import static org.apache.datasketches.hll.TgtHllType.HLL_6;
import static org.apache.datasketches.hll.TgtHllType.HLL_8;
@@ -29,6 +30,7 @@ import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
+import org.apache.datasketches.memory.WritableMemory;
import org.testng.annotations.Test;
/**
@@ -37,16 +39,150 @@ import org.testng.annotations.Test;
@SuppressWarnings("javadoc")
public class UnionCaseTest {
long v = 0;
+ final int maxLgK = 12;
+ HllSketch source;
+ Union union;
+ String hfmt = "%10s%10s%10s%10s%10s%10s%10s%10s%10s%10s%10s\n";
+ String hdr = String.format(hfmt, "caseNum","srcLgKStr","gdtLgKStr","srcType","gdtType",
+ "srcMem","gdtMem","srcMode","gdtMode","srcOoof","gdtOoof");
@Test
- public void checkCase0() { //src: LIST, gadget: LIST, cases 0, 0
+ public void checkAllCases() {
+ print(hdr);
+ for (int i = 0; i < 24; i++) {
+ checkCase(i, HLL_4, false);
+ }
+ println("");
+
+ print(hdr);
+ for (int i = 0; i < 24; i++) {
+ checkCase(i, HLL_6, false);
+ }
+ println("");
+
+ print(hdr);
+ for (int i = 0; i < 24; i++) {
+ checkCase(i, HLL_8, false);
+ }
+ println("");
+
+ print(hdr);
+ for (int i = 0; i < 24; i++) {
+ checkCase(i, HLL_4, true);
+ }
+ println("");
+
+ print(hdr);
+ for (int i = 0; i < 24; i++) {
+ checkCase(i, HLL_6, true);
+ }
+ println("");
+
+ print(hdr);
+ for (int i = 0; i < 24; i++) {
+ checkCase(i, HLL_8, true);
+ }
+ println("");
+ }
+
+ private void checkCase(int caseNum, TgtHllType srcType, boolean srcMem) {
+ source = getSource(caseNum, srcType, srcMem);
+ boolean gdtMem = (caseNum & 1) > 0;
+ Union union = getUnion(caseNum, gdtMem);
+ union.update(source);
+ int totalU = getSrcCount(caseNum, maxLgK) + getUnionCount(caseNum);
+ output(caseNum, source, union, totalU);
+ }
+
+ private void output(int caseNum, HllSketch source, Union union, int totalU) {
+ double estU = union.getEstimate();
+ double err = Math.abs((estU / totalU) - 1.0);
+ int gdtLgK = union.getLgConfigK();
+ boolean uooof = union.isOutOfOrderFlag();
+ double rseFactor = (uooof) ? HLL_NON_HIP_RSE_FACTOR : HLL_HIP_RSE_FACTOR;
+ double rse = (rseFactor * 3) / Math.sqrt(1 << gdtLgK); //99.7% conf
+ assertTrue(err < rse);
+
+ //output other parameters
+ String caseNumStr = Integer.toString(caseNum);
+ String srcLgKStr = Integer.toString(source.getLgConfigK());
+ String gdtLgKStr = Integer.toString(union.getLgConfigK());
+ String srcType = source.getTgtHllType().toString();
+ String gdtType = union.getTgtHllType().toString();
+ String srcMem = Boolean.toString(source.isMemory());
+ String gdtMem = Boolean.toString(union.isMemory());
+ String srcMode = source.getCurMode().toString();
+ String gdtMode = union.getCurMode().toString();
+ String srcOoof = Boolean.toString(source.isOutOfOrderFlag());
+ String gdtOoof = Boolean.toString(union.isOutOfOrderFlag());
+ printf(hfmt, caseNumStr, srcLgKStr, gdtLgKStr, srcType, gdtType, srcMem, gdtMem,
+ srcMode, gdtMode, srcOoof, gdtOoof);
+ }
+
+
+ private HllSketch getSource(int caseNum, TgtHllType tgtHllType, boolean memory) {
+ int srcLgK = getSrcLgK(caseNum, maxLgK);
+ int srcU = getSrcCount(caseNum, maxLgK);
+ if (memory) {
+ return buildMemorySketch(srcLgK, tgtHllType, srcU);
+ } else {
+ return buildHeapSketch(srcLgK, tgtHllType, srcU);
+ }
+ }
+
+ private Union getUnion(int caseNum, boolean memory) {
+ int unionU = getUnionCount(caseNum);
+ return (memory) ? buildMemoryUnion(maxLgK, unionU) : buildHeapUnion(maxLgK, unionU);
+ }
+
+ private static int getUnionCount(int caseNum) {
+ int gdtMode = (caseNum >> 1) & 3; //list, set, hll, empty
+ return (gdtMode == 0) ? 4 : (gdtMode == 1) ? 380 : (gdtMode == 2) ? 400 : 0;
+ }
+
+ private static int getSrcCount(int caseNum, int maxLgK) {
+ int srcLgK = getSrcLgK(caseNum, maxLgK);
+ return (((1 << srcLgK) * 3) / 4) + 100; //always HLL
+ }
+
+ private static int getSrcLgK(int caseNum, int maxLgK) {
+ int srcLgK = maxLgK;
+ int bits34 = (caseNum >> 3) & 3;
+ if (bits34 == 1) { srcLgK = maxLgK - 1;}
+ if (bits34 == 2) { srcLgK = maxLgK + 1;}
+ return srcLgK;
+ }
+
+ @Test
+ public void checkMisc() {
+ Union u = buildHeapUnion(12, 0);
+ int bytes = u.getCompactSerializationBytes();
+ assertEquals(bytes, 8);
+ bytes = Union.getMaxSerializationBytes(7);
+ assertEquals(bytes, 40 + 128);
+ double v = u.getEstimate();
+ assertEquals(v, 0.0, 0.0);
+ v = u.getLowerBound(1);
+ assertEquals(v, 0.0, 0.0);
+ v = u.getUpperBound(1);
+ assertEquals(v, 0.0, 0.0);
+ assertTrue(u.isEmpty());
+ u.reset();
+ assertTrue(u.isEmpty());
+ println(u.toString(true, false, false, false));
+ byte[] bArr = u.toCompactByteArray();
+ assertEquals(bArr.length, 8);
+ }
+
+ @Test
+ public void checkSrcListList() { //src: LIST, gadget: LIST
int n1 = 2;
int n2 = 3;
int n3 = 2;
int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_6, n2);
- HllSketch h3 = build(10, HLL_8, n3);
+ Union u = buildHeapUnion(12, n1); //gdt = list
+ HllSketch h2 = buildHeapSketch(11, HLL_6, n2); //src = list
+ HllSketch h3 = buildHeapSketch(10, HLL_8, n3); //src = list
u.update(h2);
println(u.toString());
assertEquals(u.getCurMode(), LIST);
@@ -55,20 +191,20 @@ public class UnionCaseTest {
assertEquals(u.getCurMode(), LIST);
assertEquals(u.getLgConfigK(), 12);
assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
+ double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 3.0);
println("ErrToll: " + err);
assertEquals(u.getEstimate(), sum, err);
}
@Test
- public void checkCase1() { //src: SET, gadget: LIST, cases 0, 1
+ public void checkSrcListSet() { //src: SET, gadget: LIST, cases 0, 1
int n1 = 5;
int n2 = 2;
int n3 = 16;
int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST, 5
- HllSketch h2 = build(11, HLL_6, n2); //LIST, 2
- HllSketch h3 = build(10, HLL_8, n3); //SET
+ Union u = buildHeapUnion(12, n1); //LIST, 5
+ HllSketch h2 = buildHeapSketch(11, HLL_6, n2); //LIST, 2
+ HllSketch h3 = buildHeapSketch(10, HLL_8, n3); //SET, 16
u.update(h2);
println(u.toString());
assertEquals(u.getCurMode(), LIST);
@@ -77,65 +213,20 @@ public class UnionCaseTest {
assertEquals(u.getCurMode(), SET);
assertEquals(u.getLgConfigK(), 12);
assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
+ double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 3.0);
println("ErrToll: " + err);
assertEquals(u.getEstimate(), sum, err);
-
}
@Test
- public void checkCase2() { //src: HLL, gadget: LIST, swap, cases 0, 2
- int n1 = 5;
- int n2 = 2;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(10, HLL_4, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase2B() { //src: HLL, gadget: LIST, swap, cases 0, 2; different lgKs
- int n1 = 5;
- int n2 = 2;
- int n3 = 769;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(13, HLL_4, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 12);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase4() { //src: LIST, gadget: SET, cases 0, 4
+ public void checkSrcSetList() { //src: LIST, gadget: SET, cases 0, 4
int n1 = 6;
int n2 = 10;
int n3 = 6;
int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_6, n2); //SET
- HllSketch h3 = build(10, HLL_8, n3);
+ Union u = buildHeapUnion(12, n1);
+ HllSketch h2 = buildHeapSketch(11, HLL_6, n2); //SET
+ HllSketch h3 = buildHeapSketch(10, HLL_8, n3); //LIST
u.update(h2);
println(u.toString());
assertEquals(u.getCurMode(), SET);
@@ -144,174 +235,42 @@ public class UnionCaseTest {
assertEquals(u.getCurMode(), SET);
assertEquals(u.getLgConfigK(), 12);
assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
+ double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 3.0);
println("ErrToll: " + err);
assertEquals(u.getEstimate(), sum, err);
}
@Test
- public void checkCase5() { //src: SET, gadget: SET, cases 0, 5
+ public void checkSrcSetSet() { //src: SET, gadget: SET, cases 0, 5
int n1 = 6;
int n2 = 10;
int n3 = 16;
int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_6, n2);
- HllSketch h3 = build(10, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), SET);
- assertEquals(u.getLgConfigK(), 12);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase6() { //src: HLL, gadget: SET, swap, cases 1, 6
- int n1 = 2;
- int n2 = 192;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(10, HLL_4, n3);
+ Union u = buildHeapUnion(12, n1);
+ HllSketch h2 = buildHeapSketch(11, HLL_6, n2); //src: SET
+ HllSketch h3 = buildHeapSketch(10, HLL_8, n3); //src: SET
u.update(h2);
println(u.toString());
assertEquals(u.getCurMode(), SET);
u.update(h3);
println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase6B() { //src: HLL, gadget: SET, swap, downsize, cases 1, 6
- int n1 = 6;
- int n2 = 20;
- int n3 = 769;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1);
- HllSketch h2 = build(11, HLL_8, n2);
- HllSketch h3 = build(13, HLL_4, n3);
- u.update(h2);
- println(u.toString());
assertEquals(u.getCurMode(), SET);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
assertEquals(u.getLgConfigK(), 12);
assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
+ double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 3.0);
println("ErrToll: " + err);
assertEquals(u.getEstimate(), sum, err);
}
@Test
- public void checkCase8() { //src: LIST, gadget: HLL, cases 2 (swap), 8
- int n1 = 6;
- int n2 = 193;
- int n3 = 7;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL
- HllSketch h3 = build(10, HLL_8, n3); //LIST
- u.update(h2); //SET
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 11);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase9() { //src: SET, gadget: HLL, cases 2 (swap), 9
- int n1 = 6;
- int n2 = 193;
- int n3 = 16;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST 6
- HllSketch h2 = build(11, HLL_6, n2); //HLL 193
- HllSketch h3 = build(10, HLL_8, n3); //16
- u.update(h2); //6 + 193 = 199 HLL
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 11);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase10() { //src: HLL, gadget: HLL, cases 2 (swap), 10, downsample
- int n1 = 6;
- int n2 = 193;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL
- HllSketch h3 = build(10, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase10B() { //src: HLL, gadget: HLL, cases 2 (swap), 10, copy to HLL_8
- int n1 = 6;
- int n2 = 193;
- int n3 = 193;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST
- HllSketch h2 = build(11, HLL_6, n2); //HLL_6
- HllSketch h3 = build(11, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 11);
- assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase12() { //src: LIST, gadget: empty, case 12
+ public void checkSrcEmptyList() { //src: LIST, gadget: empty, case 12
int n1 = 0;
int n2 = 0;
int n3 = 7;
int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty, ignored
- HllSketch h3 = build(10, HLL_8, n3); //Src LIST
+ Union u = buildHeapUnion(12, n1); //LIST empty
+ HllSketch h2 = buildHeapSketch(11, HLL_6, n2); //src: LIST empty, ignored
+ HllSketch h3 = buildHeapSketch(10, HLL_8, n3); //src: LIST
u.update(h2);
println(u.toString());
assertEquals(u.getCurMode(), LIST);
@@ -320,20 +279,20 @@ public class UnionCaseTest {
assertEquals(u.getCurMode(), LIST);
assertEquals(u.getLgConfigK(), 12);
assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
+ double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 3.0);
println("ErrToll: " + err);
assertEquals(u.getEstimate(), sum, err);
}
@Test
- public void checkCase13() { //src: SET, gadget: empty, case 13
+ public void checkSrcEmptySet() {
int n1 = 0;
int n2 = 0;
int n3 = 16;
int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty, ignored
- HllSketch h3 = build(10, HLL_8, n3); // Src Set
+ Union u = buildHeapUnion(12, n1); //LIST empty
+ HllSketch h2 = buildHeapSketch(11, HLL_6, n2); //LIST empty, ignored
+ HllSketch h3 = buildHeapSketch(10, HLL_8, n3); // Src Set
u.update(h2);
println(u.toString());
assertEquals(u.getCurMode(), LIST);
@@ -342,110 +301,80 @@ public class UnionCaseTest {
assertEquals(u.getCurMode(), SET);
assertEquals(u.getLgConfigK(), 12);
assertTrue(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase14() { //src: HLL, gadget: empty, case 14
- int n1 = 0;
- int n2 = 0;
- int n3 = 97;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty
- HllSketch h3 = build(10, HLL_8, n3); // Src HLL
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 10);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
- println("ErrToll: " + err);
- assertEquals(u.getEstimate(), sum, err);
- }
-
- @Test
- public void checkCase14B() { //src: HLL, gadget: empty, case 14, downsize
- int n1 = 0;
- int n2 = 0;
- int n3 = 385;
- int sum = n1 + n2 + n3;
- Union u = buildUnion(12, n1); //LIST empty
- HllSketch h2 = build(11, HLL_6, n2); //LIST empty
- HllSketch h3 = build(12, HLL_8, n3);
- u.update(h2);
- println(u.toString());
- assertEquals(u.getCurMode(), LIST);
- u.update(h3);
- println(u.toString());
- assertEquals(u.getCurMode(), HLL);
- assertEquals(u.getLgConfigK(), 12);
- assertFalse(u.isOutOfOrderFlag());
- double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 2.0);
+ double err = sum * errorFactor(u.getLgConfigK(), u.isOutOfOrderFlag(), 3.0);
println("ErrToll: " + err);
assertEquals(u.getEstimate(), sum, err);
}
- @Test
- public void checkMisc() {
- Union u = buildUnion(12, 0);
- int bytes = u.getCompactSerializationBytes();
- assertEquals(bytes, 8);
- bytes = Union.getMaxSerializationBytes(7);
- assertEquals(bytes, 40 + 128);
- double v = u.getEstimate();
- assertEquals(v, 0.0, 0.0);
- v = u.getLowerBound(1);
- assertEquals(v, 0.0, 0.0);
- v = u.getUpperBound(1);
- assertEquals(v, 0.0, 0.0);
- assertTrue(u.isEmpty());
- u.reset();
- assertTrue(u.isEmpty());
- println(u.toString(true, false, false, false));
- byte[] bArr = u.toCompactByteArray();
- assertEquals(bArr.length, 8);
- }
-
private static double errorFactor(int lgK, boolean oooFlag, double numStdDev) {
double f;
if (oooFlag) {
- f = (1.2 * numStdDev) / Math.sqrt(1 << lgK);
+ f = (1.04 * numStdDev) / Math.sqrt(1 << lgK);
} else {
f = (0.9 * numStdDev) / Math.sqrt(1 << lgK);
}
return f;
}
- private Union buildUnion(int lgMaxK, int n) {
+ //BUILDERS
+ private Union buildHeapUnion(int lgMaxK, int n) {
Union u = new Union(lgMaxK);
for (int i = 0; i < n; i++) { u.update(i + v); }
v += n;
return u;
}
- private HllSketch build(int lgK, TgtHllType tgtHllType, int n) {
+ private Union buildMemoryUnion(int lgMaxK, int n) {
+ final int bytes = HllSketch.getMaxUpdatableSerializationBytes(lgMaxK, TgtHllType.HLL_8);
+ WritableMemory wmem = WritableMemory.allocate(bytes);
+ Union u = new Union(lgMaxK, wmem);
+ for (int i = 0; i < n; i++) { u.update(i + v); }
+ v += n;
+ return u;
+ }
+
+ private HllSketch buildHeapSketch(int lgK, TgtHllType tgtHllType, int n) {
HllSketch sk = new HllSketch(lgK, tgtHllType);
for (int i = 0; i < n; i++) { sk.update(i + v); }
v += n;
return sk;
}
+ private HllSketch buildMemorySketch(int lgK, TgtHllType tgtHllType, int n) {
+ final int bytes = HllSketch.getMaxUpdatableSerializationBytes(lgK,tgtHllType);
+ WritableMemory wmem = WritableMemory.allocate(bytes);
+ HllSketch sk = new HllSketch(lgK, tgtHllType, wmem);
+ for (int i = 0; i < n; i++) { sk.update(i + v); }
+ v += n;
+ return sk;
+ }
+
+
@Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
}
/**
- * @param s value to print
+ * @param o value to print
+ */
+ static void println(Object o) {
+ print(o.toString() + "\n");
+ }
+
+ /**
+ * @param o value to print
+ */
+ static void print(Object o) {
+ //System.out.print(o.toString()); //disable here
+ }
+
+ /**
+ * @param fmt format
+ * @param args arguments
*/
- static void println(String s) {
- //System.out.println(s); //disable here
+ static void printf(String fmt, Object...args) {
+ //System.out.printf(fmt, args); //disable here
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org