You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by al...@apache.org on 2024/01/03 01:05:47 UTC
(datasketches-go) 26/40: rename to LongsSketch and add more tests
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-go.git
commit 21bb5b544413d7fde4cc4c09f2f816d3274db148
Author: Pierre Lacave <pi...@datadoghq.com>
AuthorDate: Thu Dec 21 09:08:57 2023 +0100
rename to LongsSketch and add more tests
---
frequencies/dist_test.go | 13 ++++
frequencies/{long_sketch.go => longs_sketch.go} | 68 +++++++++-------
.../{long_sketch_test.go => longs_sketch_test.go} | 90 +++++++++++++++++++++-
frequencies/reverse_purge_long_hash_map.go | 12 +--
frequencies/row.go | 14 +++-
5 files changed, 161 insertions(+), 36 deletions(-)
diff --git a/frequencies/dist_test.go b/frequencies/dist_test.go
new file mode 100644
index 0000000..2b67ae0
--- /dev/null
+++ b/frequencies/dist_test.go
@@ -0,0 +1,13 @@
+package frequencies
+
+import (
+ "math"
+ "math/rand"
+)
+
+func randomGeometricDist(prob float64) int64 {
+ if prob <= 0.0 || prob >= 1.0 {
+ panic("prob must be in (0, 1)")
+ }
+ return int64(1 + math.Log(rand.Float64())/math.Log(1.0-prob))
+}
diff --git a/frequencies/long_sketch.go b/frequencies/longs_sketch.go
similarity index 85%
rename from frequencies/long_sketch.go
rename to frequencies/longs_sketch.go
index 544a252..ecb51a2 100644
--- a/frequencies/long_sketch.go
+++ b/frequencies/longs_sketch.go
@@ -26,7 +26,7 @@ import (
"strings"
)
-type LongSketch struct {
+type LongsSketch struct {
// Log2 Maximum length of the arrays internal to the hash map supported by the data
// structure.
lgMaxMapSize int
@@ -59,13 +59,13 @@ const (
* map managed by this sketch.
*/
-// NewLongSketch returns a new LongSketch with the given lgMaxMapSize and lgCurMapSize.
+// NewLongSketch returns a new LongsSketch with the given lgMaxMapSize and lgCurMapSize.
// lgMaxMapSize is the log2 of the physical size of the internal hash map managed by this
// sketch. The maximum capacity of this internal hash map is 0.75 times 2^lgMaxMapSize.
// Both the ultimate accuracy and size of this sketch are a function of lgMaxMapSize.
// lgCurMapSize is the log2 of the starting (current) physical size of the internal hash
// map managed by this sketch.
-func NewLongSketch(lgMaxMapSize int, lgCurMapSize int) (*LongSketch, error) {
+func NewLongSketch(lgMaxMapSize int, lgCurMapSize int) (*LongsSketch, error) {
//set initial size of hash map
lgMaxMapSize = max(lgMaxMapSize, _LG_MIN_MAP_SIZE)
lgCurMapSize = max(lgCurMapSize, _LG_MIN_MAP_SIZE)
@@ -74,10 +74,10 @@ func NewLongSketch(lgMaxMapSize int, lgCurMapSize int) (*LongSketch, error) {
return nil, err
}
curMapCap := hashMap.getCapacity()
- maxMapCap := int(float64(uint64(1<<lgMaxMapSize)) * loadFactor)
+ maxMapCap := int(float64(uint64(1<<lgMaxMapSize)) * reversePurgeLongHashMapLoadFactor)
offset := int64(0)
sampleSize := min(_SAMPLE_SIZE, maxMapCap)
- return &LongSketch{
+ return &LongsSketch{
lgMaxMapSize: int(lgMaxMapSize),
curMapCap: curMapCap,
offset: offset,
@@ -86,13 +86,13 @@ func NewLongSketch(lgMaxMapSize int, lgCurMapSize int) (*LongSketch, error) {
}, nil
}
-// NewLongSketchWithMaxMapSize constructs a new LongSketch with the given maxMapSize and the
+// NewLongSketchWithMaxMapSize constructs a new LongsSketch with the given maxMapSize and the
// default initialMapSize (8).
// maxMapSize determines the physical size of the internal hash map managed by this
// sketch and must be a power of 2. The maximum capacity of this internal hash map is
// 0.75 times * maxMapSize. Both the ultimate accuracy and size of this sketch are a
// function of maxMapSize.
-func NewLongSketchWithMaxMapSize(maxMapSize int) (*LongSketch, error) {
+func NewLongSketchWithMaxMapSize(maxMapSize int) (*LongsSketch, error) {
log2OfInt, err := common.ExactLog2(maxMapSize)
if err != nil {
return nil, fmt.Errorf("maxMapSize, %e", err)
@@ -100,7 +100,7 @@ func NewLongSketchWithMaxMapSize(maxMapSize int) (*LongSketch, error) {
return NewLongSketch(log2OfInt, _LG_MIN_MAP_SIZE)
}
-func NewLongSketchFromSlice(slc []byte) (*LongSketch, error) {
+func NewLongSketchFromSlice(slc []byte) (*LongsSketch, error) {
pre0, err := checkPreambleSize(slc)
if err != nil {
return nil, err
@@ -173,7 +173,7 @@ func NewLongSketchFromSlice(slc []byte) (*LongSketch, error) {
return fls, nil
}
-func NewLongSketchFromString(str string) (*LongSketch, error) {
+func NewLongSketchFromString(str string) (*LongsSketch, error) {
if len(str) < 1 {
return nil, fmt.Errorf("String is empty")
}
@@ -250,7 +250,7 @@ func NewLongSketchFromString(str string) (*LongSketch, error) {
return sk, nil
}
-func (s *LongSketch) getEstimate(item int64) (int64, error) {
+func (s *LongsSketch) getEstimate(item int64) (int64, error) {
itemCount, err := s.hashMap.get(item)
if err != nil {
return 0, err
@@ -258,12 +258,12 @@ func (s *LongSketch) getEstimate(item int64) (int64, error) {
return itemCount + s.offset, nil
}
-func (s *LongSketch) getLowerBound(item int64) (int64, error) {
+func (s *LongsSketch) getLowerBound(item int64) (int64, error) {
// LB = itemCount
return s.hashMap.get(item)
}
-func (s *LongSketch) getUpperBound(item int64) (int64, error) {
+func (s *LongsSketch) getUpperBound(item int64) (int64, error) {
itemCount, err := s.hashMap.get(item)
if err != nil {
return 0, err
@@ -271,44 +271,44 @@ func (s *LongSketch) getUpperBound(item int64) (int64, error) {
return itemCount + s.offset, nil
}
-func (s *LongSketch) getNumActiveItems() int {
+func (s *LongsSketch) getNumActiveItems() int {
return s.hashMap.numActive
}
// getMaximumMapCapacity returns the maximum number of counters the sketch is configured to
// support.
-func (s *LongSketch) getMaximumMapCapacity() int {
- return int(float64(uint64(1<<s.lgMaxMapSize)) * loadFactor)
+func (s *LongsSketch) getMaximumMapCapacity() int {
+ return int(float64(uint64(1<<s.lgMaxMapSize)) * reversePurgeLongHashMapLoadFactor)
}
-func (s *LongSketch) getStorageBytes() int {
+func (s *LongsSketch) getStorageBytes() int {
if s.isEmpty() {
return 8
}
return (4 * 8) + (16 * s.getNumActiveItems())
}
-func (s *LongSketch) getCurrentMapCapacity() int {
+func (s *LongsSketch) getCurrentMapCapacity() int {
return s.curMapCap
}
-func (s *LongSketch) getMaximumError() int64 {
+func (s *LongsSketch) getMaximumError() int64 {
return s.offset
}
-func (s *LongSketch) getStreamLength() int64 {
+func (s *LongsSketch) getStreamLength() int64 {
return s.streamWeight
}
-func (s *LongSketch) isEmpty() bool {
+func (s *LongsSketch) isEmpty() bool {
return s.getNumActiveItems() == 0
}
-func (s *LongSketch) Update(item int64) error {
+func (s *LongsSketch) Update(item int64) error {
return s.UpdateMany(item, 1)
}
-func (s *LongSketch) UpdateMany(item int64, count int64) error {
+func (s *LongsSketch) UpdateMany(item int64, count int64) error {
if count == 0 {
return nil
}
@@ -338,7 +338,7 @@ func (s *LongSketch) UpdateMany(item int64, count int64) error {
return nil
}
-func (s *LongSketch) merge(other *LongSketch) (*LongSketch, error) {
+func (s *LongsSketch) merge(other *LongsSketch) (*LongsSketch, error) {
if other == nil || other.isEmpty() {
return s, nil
}
@@ -355,7 +355,7 @@ func (s *LongSketch) merge(other *LongSketch) (*LongSketch, error) {
return s, nil
}
-func (s *LongSketch) serializeToString() (string, error) {
+func (s *LongsSketch) serializeToString() (string, error) {
var sb strings.Builder
//start the string with parameters of the sketch
serVer := _SER_VER //0
@@ -373,7 +373,7 @@ func (s *LongSketch) serializeToString() (string, error) {
return sb.String(), nil
}
-func (s *LongSketch) toSlice() ([]byte, error) {
+func (s *LongsSketch) toSlice() ([]byte, error) {
emtpy := s.isEmpty()
activeItems := s.getNumActiveItems()
preLongs := 1
@@ -416,7 +416,7 @@ func (s *LongSketch) toSlice() ([]byte, error) {
return outArr, nil
}
-func (s *LongSketch) Reset() {
+func (s *LongsSketch) Reset() {
hasMap, _ := NewReversePurgeLongHashMap(1 << _LG_MIN_MAP_SIZE)
s.curMapCap = hasMap.getCapacity()
s.offset = 0
@@ -424,6 +424,20 @@ func (s *LongSketch) Reset() {
s.hashMap = hasMap
}
-func (s *LongSketch) getFrequentItems(errorType ErrorType) ([]*Row, error) {
+/*
+ public Row[] getFrequentItems(final long threshold, final ErrorType errorType) {
+ return sortItems(threshold > getMaximumError() ? threshold : getMaximumError(), errorType);
+ }
+*/
+
+func (s *LongsSketch) getFrequentItemsWithThreshold(threshold int64, errorType ErrorType) ([]*Row, error) {
+ finalThreshold := s.getMaximumError()
+ if threshold > finalThreshold {
+ finalThreshold = threshold
+ }
+ return sortItems(s, finalThreshold, errorType)
+}
+
+func (s *LongsSketch) getFrequentItems(errorType ErrorType) ([]*Row, error) {
return sortItems(s, s.getMaximumError(), errorType)
}
diff --git a/frequencies/long_sketch_test.go b/frequencies/longs_sketch_test.go
similarity index 81%
rename from frequencies/long_sketch_test.go
rename to frequencies/longs_sketch_test.go
index 5ee6557..f0ec490 100644
--- a/frequencies/long_sketch_test.go
+++ b/frequencies/longs_sketch_test.go
@@ -19,6 +19,7 @@ package frequencies
import (
"encoding/binary"
+ "github.com/apache/datasketches-go/common"
"github.com/stretchr/testify/assert"
"testing"
)
@@ -228,7 +229,7 @@ func TestFreqLongStringSerDe(t *testing.T) {
checkEquality(t, sk1, sk2)
}
-func checkEquality(t *testing.T, sk1, sk2 *LongSketch) {
+func checkEquality(t *testing.T, sk1, sk2 *LongsSketch) {
assert.Equal(t, sk1.getNumActiveItems(), sk2.getNumActiveItems())
assert.Equal(t, sk1.getCurrentMapCapacity(), sk2.getCurrentMapCapacity())
assert.Equal(t, sk1.getMaximumError(), sk2.getMaximumError())
@@ -293,7 +294,7 @@ func tryBadMem(t *testing.T, mem []byte, byteOffset, byteValue int) {
}
func TestFreqLongStringSerDeError(t *testing.T) {
- //sk1, err := NewLongSketchWithMaxMapSize(8)
+ // sk1, err := NewLongSketchWithMaxMapSize(8)
// str1 := sk1.serializeToString()
// correct = "1,10,2,4,0,0,0,4,";
@@ -306,3 +307,88 @@ func tryBadString(t *testing.T, badString string) {
_, err := NewLongSketchFromString(badString)
assert.Error(t, err)
}
+
+func TestFreqLongs(t *testing.T) {
+ numSketches := 1
+ n := 2222
+ errorTolerance := 1.0 / 100
+
+ sketches := make([]*LongsSketch, numSketches)
+ for h := 0; h < numSketches; h++ {
+ sketches[h], _ = newFrequencySketch(errorTolerance)
+ }
+
+ prob := .001
+ for i := 0; i < n; i++ {
+ item := randomGeometricDist(prob) + 1
+ for h := 0; h < numSketches; h++ {
+ sketches[h].Update(item)
+ }
+ }
+
+ for h := 0; h < numSketches; h++ {
+ threshold := sketches[h].getMaximumError()
+ rows, err := sketches[h].getFrequentItems(NO_FALSE_NEGATIVES)
+ assert.NoError(t, err)
+ for i := 0; i < len(rows); i++ {
+ assert.True(t, rows[i].getUpperBound() > threshold)
+ }
+
+ rows, err = sketches[h].getFrequentItems(NO_FALSE_POSITIVES)
+ assert.NoError(t, err)
+ assert.Equal(t, len(rows), 0)
+ for i := 0; i < len(rows); i++ {
+ assert.True(t, rows[i].getLowerBound() > threshold)
+ }
+
+ rows, err = sketches[h].getFrequentItems(NO_FALSE_NEGATIVES)
+ }
+}
+
+func newFrequencySketch(eps float64) (*LongsSketch, error) {
+ maxMapSize := common.CeilPowerOf2(int(1.0 / (eps * reversePurgeLongHashMapLoadFactor)))
+ return NewLongSketchWithMaxMapSize(maxMapSize)
+}
+
+func TestUpdateOneTime(t *testing.T) {
+ size := 100
+ errorTolerance := 1.0 / float64(size)
+ //delta := .01
+ numSketches := 1
+ for h := 0; h < numSketches; h++ {
+ sketch, _ := newFrequencySketch(errorTolerance)
+ ub, err := sketch.getUpperBound(13)
+ assert.NoError(t, err)
+ assert.Equal(t, ub, int64(0))
+ lb, err := sketch.getLowerBound(13)
+ assert.NoError(t, err)
+ assert.Equal(t, lb, int64(0))
+ assert.Equal(t, sketch.getMaximumError(), int64(0))
+ est, err := sketch.getEstimate(13)
+ assert.NoError(t, err)
+ assert.Equal(t, est, int64(0))
+ sketch.Update(13)
+ // assert.Equal(t, sketch.getEstimate(13), 1)
+ }
+}
+
+func TestGetInstanceSlice(t *testing.T) {
+ sl := make([]byte, 4)
+ _, err := NewLongSketchFromSlice(sl)
+ assert.Error(t, err)
+}
+
+func TestGetInstanceString(t *testing.T) {
+ _, err := NewLongSketchFromString("")
+ assert.Error(t, err)
+}
+
+func TestUpdateNegative(t *testing.T) {
+ minSize := 1 << _LG_MIN_MAP_SIZE
+ fls, err := NewLongSketchWithMaxMapSize(minSize)
+ assert.NoError(t, err)
+ err = fls.UpdateMany(1, 0)
+ assert.NoError(t, err)
+ err = fls.UpdateMany(1, -1)
+ assert.Error(t, err)
+}
diff --git a/frequencies/reverse_purge_long_hash_map.go b/frequencies/reverse_purge_long_hash_map.go
index 36d26f8..03c2b16 100644
--- a/frequencies/reverse_purge_long_hash_map.go
+++ b/frequencies/reverse_purge_long_hash_map.go
@@ -47,8 +47,8 @@ type iteratorHashMap struct {
}
const (
- loadFactor = float64(0.75)
- driftLimit = 1024 //used only in stress testing
+ reversePurgeLongHashMapLoadFactor = float64(0.75)
+ reversePurgeLongHashMapDriftLimit = 1024 //used only in stress testing
)
// NewReversePurgeLongHashMap constructs a new reversePurgeLongHashMap.
@@ -61,7 +61,7 @@ func NewReversePurgeLongHashMap(mapSize int) (*reversePurgeLongHashMap, error) {
if err != nil {
return nil, fmt.Errorf("mapSize: %e", err)
}
- loadThreshold := int(float64(mapSize) * loadFactor)
+ loadThreshold := int(float64(mapSize) * reversePurgeLongHashMapLoadFactor)
keys := make([]int64, mapSize)
values := make([]int64, mapSize)
states := make([]int16, mapSize)
@@ -105,7 +105,7 @@ func (r *reversePurgeLongHashMap) adjustOrPutValue(key int64, adjustAmount int64
for r.states[probe] != 0 && r.keys[probe] != key {
probe = (probe + 1) & int64(arrayMask)
drift++
- if drift >= driftLimit {
+ if drift >= reversePurgeLongHashMapDriftLimit {
panic("drift >= driftLimit")
}
}
@@ -135,7 +135,7 @@ func (r *reversePurgeLongHashMap) resize(newSize int) error {
r.keys = make([]int64, newSize)
r.values = make([]int64, newSize)
r.states = make([]int16, newSize)
- r.loadThreshold = int(float64(newSize) * loadFactor)
+ r.loadThreshold = int(float64(newSize) * reversePurgeLongHashMapLoadFactor)
r.lgLength = bits.TrailingZeros(uint(newSize))
r.numActive = 0
err := error(nil)
@@ -234,7 +234,7 @@ func (r *reversePurgeLongHashMap) hashDelete(deleteProbe int) {
probe = (probe + 1) & arrayMask
drift++
//only used for theoretical analysis
- if drift >= driftLimit {
+ if drift >= reversePurgeLongHashMapDriftLimit {
panic("drift >= driftLimit")
}
}
diff --git a/frequencies/row.go b/frequencies/row.go
index f428975..21a2c81 100644
--- a/frequencies/row.go
+++ b/frequencies/row.go
@@ -46,7 +46,19 @@ func (r *Row) String() string {
return fmt.Sprintf(" %20d%20d%20d %d", r.item, r.est, r.ub, r.lb)
}
-func sortItems(sk *LongSketch, threshold int64, errorType ErrorType) ([]*Row, error) {
+func (r *Row) getEstimate() int64 {
+ return r.est
+}
+
+func (r *Row) getUpperBound() int64 {
+ return r.ub
+}
+
+func (r *Row) getLowerBound() int64 {
+ return r.lb
+}
+
+func sortItems(sk *LongsSketch, threshold int64, errorType ErrorType) ([]*Row, error) {
rowList := make([]*Row, 0)
iter := sk.hashMap.iterator()
if errorType == NO_FALSE_NEGATIVES {
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org