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 23:13:50 UTC
[incubator-datasketches-java] branch NewHllIterator updated:
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
The following commit(s) were added to refs/heads/NewHllIterator by this push:
new 94afdb8 Interim update
94afdb8 is described below
commit 94afdb841e86fbd98dd7ff2384039248d3a2ba65
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Dec 17 15:13:38 2019 -0800
Interim update
---
.../apache/datasketches/hll/AbstractHllArray.java | 2 +-
.../org/apache/datasketches/hll/Hll8Array.java | 9 --
.../org/apache/datasketches/hll/HllEstimators.java | 4 +-
.../java/org/apache/datasketches/hll/Union.java | 109 ++++++++++++++-------
.../org/apache/datasketches/hll/UnionCaseTest.java | 2 +-
5 files changed, 80 insertions(+), 46 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java b/src/main/java/org/apache/datasketches/hll/AbstractHllArray.java
index d9d0ee3..575fe7f 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, false);
+ return HllEstimators.hllCompositeEstimate(this, isOutOfOrderFlag());
}
abstract int getCurMin();
diff --git a/src/main/java/org/apache/datasketches/hll/Hll8Array.java b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
index 4ea367c..2c9f014 100644
--- a/src/main/java/org/apache/datasketches/hll/Hll8Array.java
+++ b/src/main/java/org/apache/datasketches/hll/Hll8Array.java
@@ -94,15 +94,6 @@ class Hll8Array extends HllArray {
@Override
void mergeTo(final HllSketch that) {
final int thisK = 1 << lgConfigK;
- // 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/HllEstimators.java b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
index 5dda41c..46c4cee 100644
--- a/src/main/java/org/apache/datasketches/hll/HllEstimators.java
+++ b/src/main/java/org/apache/datasketches/hll/HllEstimators.java
@@ -191,8 +191,8 @@ class HllEstimators {
double kxq1 = 0;
while (itr.nextValid()) {
final int actualValue = itr.getValue();
- if (actualValue < 32) { kxq0 += invPow2(actualValue) - 1; }
- else { kxq1 += invPow2(actualValue) - 1; }
+ if (actualValue < 32) { kxq0 += invPow2(actualValue) - 1.0; }
+ else { kxq1 += invPow2(actualValue) - 1.0; }
}
return kxq0 + kxq1;
}
diff --git a/src/main/java/org/apache/datasketches/hll/Union.java b/src/main/java/org/apache/datasketches/hll/Union.java
index c18db38..7127f33 100644
--- a/src/main/java/org/apache/datasketches/hll/Union.java
+++ b/src/main/java/org/apache/datasketches/hll/Union.java
@@ -342,16 +342,18 @@ public class Union extends BaseHllSketch {
switch (sw) {
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 srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,heap,list) -> src(Hll8,heap,hll), autofold
final HllSketch gdtTmp = srcHll8Heap; //replace gdt
gdtTmp.putOutOfOrderFlag(gdtTmp.isOutOfOrderFlag() | source.isOutOfOrderFlag());
return gdtTmp.hllSketchImpl;
}
- 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
+ case 1: //src <= max, src >= gdt, gdtLIST, gdtMemory, reverse merge, no downsample, ooof=OR
+ case 9: //src <= max, src < gdt, gdtLIST, gdtMemory, reverse merge, no downsample, ooof=OR
+ {
+ final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,mem,list) -> src(Hll8,heap,hll), autofold
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
@@ -361,16 +363,18 @@ public class Union extends BaseHllSketch {
}
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 srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,heap,set) -> src(Hll8,heap,hll), autofold
final HllSketch gdtTmp = srcHll8Heap; //replace gdt
gdtTmp.putOutOfOrderFlag(true);
return gdtTmp.hllSketchImpl;
}
- 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
+ case 3: //src <= max, src >= gdt, gdtSET, gdtMemory, reverse merge, no downsample, ooof=True
+ case 11: //src <= max, src < gdt, gdtSET, gdtMemory, reverse merge, no downsample, ooof=True
+ {
+ final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,mem,set) -> src(Hll8,heap,hll), autofold
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
@@ -379,23 +383,39 @@ public class Union extends BaseHllSketch {
return gdtTmp.hllSketchImpl;
}
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
+ {
+ if ((srcLgK == gadgetLgK) && (source.getTgtHllType() == HLL_8) && (!source.isMemory())) {
+ specialMerge(source, gadget);
+ } else {
+ source.mergeTo(gadget); //merge src(Hll?,heap/mem,hll) -> gdt(Hll8,heap,hll), autofold
+ }
+ gadget.putOutOfOrderFlag(true);
+ return gadget.hllSketchImpl;
+ }
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
- source.mergeTo(gadget); //merge src -> gdt
+ {
+ source.mergeTo(gadget); //merge src(Hll?,heap/mem,hll) -> gdt(Hll8,heap,hll), autofold
+ gadget.putOutOfOrderFlag(true);
+ return gadget.hllSketchImpl;
+ }
+ case 5: //src <= max, src >= gdt, gdtHLL, gdtMemory, forward merge, no downsample, ooof=True
+ case 21: //src > max, src >= gdt, gdtHLL, gdtMemory, forward merge, no downsample, ooof=True
+ {
+ source.mergeTo(gadget); //merge src(Hll?,heap/mem,hll) -> gdt(Hll8,mem,hll), autofold
gadget.putOutOfOrderFlag(true);
return gadget.hllSketchImpl;
}
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
+ {
+ final HllSketch srcHll8Heap = source.copyAs(HLL_8); //copy src to Heap
//ooof is already what source is.
return srcHll8Heap.hllSketchImpl;
}
- 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
+ case 7: //src <= max, src >= gdt, gdtEmpty, gdtMemory, replace mem, no downsample, ooof=Src
+ case 15: //src <= max, src < gdt, gdtEmpty, gdtMemory, 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
@@ -403,17 +423,21 @@ public class Union extends BaseHllSketch {
//ooof is already what source is.
return gdtTmp.hllSketchImpl;
}
- case 12: //src <= max, src < gdt, gdtHLL, gdtHeap, fwd Merge/replace, downsample Gdt, ooof=True
+ case 12: //src <= max, src < gdt, gdtHLL, gdtHeap, fwd merge/repl, downsample Gdt, ooof=True
{
final HllSketch gdtHll8Heap = downsample(gadget, srcLgK); //downsample gdt to srcLgK
- source.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
+ if ((source.getTgtHllType() == HLL_8) && (!source.isMemory())) {
+ specialMerge(source, gdtHll8Heap);
+ } else {
+ source.mergeTo(gdtHll8Heap);//merge src(Hll?,heap/mem,hll) -> gdt(Hll8,heap,hll), autofold
+ }
gdtHll8Heap.putOutOfOrderFlag(true);
return gdtHll8Heap.hllSketchImpl;
}
- case 13: //src <= max, src < gdt, gdtHLL, gdtDirect, fwd merge/repl mem, downsample Gdt, ooof=True
+ case 13: //src <= max, src < gdt, gdtHLL, gdtMemory, fwd merge/repl mem, downsample Gdt, ooof=True
{
final HllSketch gdtHll8Heap = downsample(gadget, srcLgK); //downsample gdt to srcLgK
- source.mergeTo(gdtHll8Heap); //merge src -> gdtCopy
+ source.mergeTo(gdtHll8Heap); //merge src(Hll?,heap/mem,hll) -> gdt(Hll8,heap,hll)
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
@@ -424,15 +448,15 @@ public class Union extends BaseHllSketch {
case 16: //src > max, src >= gdt, gdtList, gdtHeap, reverse merge, downsample Src, ooof=OR
{
final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
- gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
- final HllSketch gdtTmp = srcHll8Heap; //replace gdt
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,heap,list) -> src(Hll8,heap,hll)
+ final HllSketch gdtTmp = srcHll8Heap; //replace gdt
gdtTmp.putOutOfOrderFlag(gdtTmp.isOutOfOrderFlag() | source.isOutOfOrderFlag());
return gdtTmp.hllSketchImpl;
}
- case 17: //src > max, src >= gdt, gdtList, gdtDirect, rev merge/repl mem, downsample Src, ooof=OR
+ case 17: //src > max, src >= gdt, gdtList, gdtMemory, rev merge/repl mem, downsample Src, ooof=OR
{
final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
- gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,mem,list) -> src(Hll8,heap,hll)
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
@@ -443,15 +467,15 @@ public class Union extends BaseHllSketch {
case 18: //src > max, src >= gdt, gdtSet, gdtHeap, rev merge, downsample Src, ooof=True
{
final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
- gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,heap,set) -> src(Hll8,heap,hll)
final HllSketch gdtTmp = srcHll8Heap; //replace gdt
gdtTmp.putOutOfOrderFlag(true);
return gdtTmp.hllSketchImpl;
}
- case 19: //src > max, src >= gdt, gdtSet, gdtDirect, rev merge/rep mem, downsample Src, ooof=True
+ case 19: //src > max, src >= gdt, gdtSet, gdtMemory, rev merge/rep mem, downsample Src, ooof=True
{
final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
- gadget.mergeTo(srcHll8Heap); //merge gdt -> srcCopy
+ gadget.mergeTo(srcHll8Heap); //merge gdt(Hll8,mem,set) -> src(Hll8,heap,hll)
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
@@ -462,10 +486,10 @@ public class Union extends BaseHllSketch {
case 22: //src > max, src >= gdt, gdtEmpty, gdtHeap, replace, downsample Src, ooof=Src
{
final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
- return srcHll8Heap.hllSketchImpl; //replace gdt
+ return srcHll8Heap.hllSketchImpl; //replace gdt
//ooof is already what source is.
}
- case 23: //src > max, src >= gdt, gdtEmpty, gdtDirect, replace mem, downsample Src, ooof=Src
+ case 23: //src > max, src >= gdt, gdtEmpty, gdtMemory, replace mem, downsample Src, ooof=Src
{
final HllSketch srcHll8Heap = downsample(source, lgMaxK); //downsample src to Max
final WritableMemory wmem = gadget.getWritableMemory(); //use the gdt wmem
@@ -478,6 +502,25 @@ public class Union extends BaseHllSketch {
}
}
+ /**
+ * Source and target must both be type HLL_8, mode HLL, and with equal LgK.
+ * @param source merge source
+ * @param target merge target
+ */
+ private static void specialMerge(final HllSketch source, final HllSketch target) {
+ final int k = 1 << target.getLgConfigK();
+ final byte[] srcArr = ((Hll8Array) source.hllSketchImpl).hllByteArr;
+ final Hll8Array tgtHll8Arr = (Hll8Array) target.hllSketchImpl;
+ final byte[] tgtArr = tgtHll8Arr.hllByteArr;
+ int numZeros = 0;
+ for (int i = 0; i < k; i++) {
+ final byte out = (srcArr[i] > tgtArr[i]) ? srcArr[i] : tgtArr[i];
+ tgtArr[i] = out;
+ if (out == 0) { numZeros++; }
+ }
+ tgtHll8Arr.putNumAtCurMin(numZeros);
+ }
+
//Used by union operator. Always copies or downsamples to Heap HLL_8.
//Caller must ultimately manage oooFlag, as caller has more context.
/**
diff --git a/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java b/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
index 633e9eb..3272295 100644
--- a/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
+++ b/src/test/java/org/apache/datasketches/hll/UnionCaseTest.java
@@ -101,7 +101,6 @@ public class UnionCaseTest {
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);
@@ -117,6 +116,7 @@ public class UnionCaseTest {
String gdtOoof = Boolean.toString(union.isOutOfOrderFlag());
printf(hfmt, caseNumStr, srcLgKStr, gdtLgKStr, srcType, gdtType, srcMem, gdtMem,
srcMode, gdtMode, srcOoof, gdtOoof);
+ assertTrue(err < rse);
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org