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:55 UTC
[incubator-datasketches-java] 10/10: Interim update
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