You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by pl...@apache.org on 2024/07/11 15:04:04 UTC
(datasketches-go) branch cpc-sketch updated: CPC - finish basic update and estimates
This is an automated email from the ASF dual-hosted git repository.
placave pushed a commit to branch cpc-sketch
in repository https://gitbox.apache.org/repos/asf/datasketches-go.git
The following commit(s) were added to refs/heads/cpc-sketch by this push:
new a25bd63 CPC - finish basic update and estimates
a25bd63 is described below
commit a25bd6316fc9d1d428da1e6c141fc64ff7fdf454
Author: Pierre Lacave <pi...@datadoghq.com>
AuthorDate: Thu Jul 11 17:03:52 2024 +0200
CPC - finish basic update and estimates
---
cpc/cpc_sketch.go | 83 ++++++++++++++++++++++++++++++++++++++++++++++----
cpc/cpc_sketch_test.go | 3 ++
cpc/pair_table.go | 9 +++---
3 files changed, 84 insertions(+), 11 deletions(-)
diff --git a/cpc/cpc_sketch.go b/cpc/cpc_sketch.go
index 873f0ac..4d1c157 100644
--- a/cpc/cpc_sketch.go
+++ b/cpc/cpc_sketch.go
@@ -127,7 +127,7 @@ func (c *CpcSketch) UpdateString(datum string) error {
}
func (c *CpcSketch) hashUpdate(hash0, hash1 uint64) error {
- col := 64 - bits.LeadingZeros64(hash1)
+ col := bits.LeadingZeros64(hash1)
if col < c.fiCol {
return nil // important speed optimization
}
@@ -186,14 +186,11 @@ func (c *CpcSketch) updateSparse(rowCol int) error {
}
if isNovel {
c.numCoupons++
- // TODO (pierre)
- //c.updateHIP(rowCol)
+ c.updateHIP(rowCol)
c32post := c.numCoupons << 5
if c32post >= (3 * k) {
- // TODO (pierre)
- // c.promoteSparseToWindowed() // C >= 3K/32
+ c.promoteSparseToWindowed() // C >= 3K/32
}
-
}
return nil
}
@@ -229,6 +226,80 @@ func (c *CpcSketch) getFlavor() cpcFlavor {
return determineFlavor(c.lgK, c.numCoupons)
}
+func (c *CpcSketch) updateHIP(rowCol int) {
+ k := 1 << c.lgK
+ col := rowCol & 63
+ oneOverP := float64(k) / c.kxp
+ c.hipEstAccum += oneOverP
+ kxp, _ := internal.InvPow2(col + 1)
+ c.kxp -= kxp
+}
+
+func (c *CpcSketch) promoteSparseToWindowed() {
+ window := make([]byte, 1<<c.lgK)
+ newTable, _ := NewPairTable(2, 6+c.lgK)
+ oldTable := c.pairTable
+
+ oldSlots := oldTable.slotsArr
+ oldNumSlots := 1 << oldTable.lgSizeInts
+
+ for i := 0; i < oldNumSlots; i++ {
+ rowCol := oldSlots[i]
+ if rowCol != -1 {
+ col := rowCol & 63
+ if col < 8 {
+ row := rowCol >> 6
+ window[row] |= 1 << col
+ } else {
+ newTable.mustInsert(rowCol)
+ }
+ }
+ }
+
+ c.slidingWindow = window
+ c.pairTable = newTable
+}
+
+/*
+ //In terms of flavor, this promotes SPARSE to HYBRID.
+ private static void promoteSparseToWindowed(final CpcSketch sketch) {
+ final int lgK = sketch.lgK;
+ final int k = (1 << lgK);
+ final long c32 = sketch.numCoupons << 5;
+ assert ((c32 == (3 * k)) || ((lgK == 4) && (c32 > (3 * k))));
+
+ final byte[] window = new byte[k];
+
+ final PairTable newTable = new PairTable(2, 6 + lgK);
+ final PairTable oldTable = sketch.pairTable;
+
+ final int[] oldSlots = oldTable.getSlotsArr();
+ final int oldNumSlots = (1 << oldTable.getLgSizeInts());
+
+ assert (sketch.windowOffset == 0);
+
+ for (int i = 0; i < oldNumSlots; i++) {
+ final int rowCol = oldSlots[i];
+ if (rowCol != -1) {
+ final int col = rowCol & 63;
+ if (col < 8) {
+ final int row = rowCol >>> 6;
+ window[row] |= (1 << col);
+ }
+ else {
+ // cannot use Table.mustInsert(), because it doesn't provide for growth
+ final boolean isNovel = PairTable.maybeInsert(newTable, rowCol);
+ assert (isNovel == true);
+ }
+ }
+ }
+
+ assert (sketch.slidingWindow == null);
+ sketch.slidingWindow = window;
+ sketch.pairTable = newTable;
+ }
+*/
+
func (c *CpcSketch) reset() {
c.numCoupons = 0
c.mergeFlag = false
diff --git a/cpc/cpc_sketch_test.go b/cpc/cpc_sketch_test.go
index 265bb49..fef126e 100644
--- a/cpc/cpc_sketch_test.go
+++ b/cpc/cpc_sketch_test.go
@@ -35,6 +35,9 @@ func TestCPCCheckUpdatesEstimate(t *testing.T) {
bytes := []byte{4, 4}
err = sk.UpdateByteSlice(bytes)
assert.NoError(t, err)
+ bytes2 := []byte{4}
+ err = sk.UpdateByteSlice(bytes2)
+ assert.NoError(t, err)
err = sk.UpdateCharSlice([]byte{5})
assert.NoError(t, err)
err = sk.UpdateInt32Slice([]int32{6})
diff --git a/cpc/pair_table.go b/cpc/pair_table.go
index eecf11b..4886c76 100644
--- a/cpc/pair_table.go
+++ b/cpc/pair_table.go
@@ -56,18 +56,17 @@ func (p *pairTable) maybeInsert(item int) (bool, error) {
//rtAssert(shift > 0)
probe := item >> shift
//rtAssert((probe >= 0) && (probe <= mask))
- arr := p.slotsArr
- fetched := arr[probe]
+ fetched := p.slotsArr[probe]
for fetched != item && fetched != -1 {
probe = (probe + 1) & mask
- fetched = arr[probe]
+ fetched = p.slotsArr[probe]
}
//END SHARED CODE
- if fetched != item {
+ if fetched == item {
return false, nil
} else {
//assert (fetched == -1)
- arr[probe] = item
+ p.slotsArr[probe] = item
p.numPairs++
for (upsizeDenom * p.numPairs) > (upsizeNumer * (1 << p.lgSizeInts)) {
if err := p.rebuild(p.lgSizeInts + 1); err != nil {
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org