You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "Fengzdadi (via GitHub)" <gi...@apache.org> on 2026/01/18 19:06:13 UTC
[PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Fengzdadi opened a new pull request, #104:
URL: https://github.com/apache/datasketches-go/pull/104
## Summary
This PR completes the [ReservoirItemsUnion](cci:2://file:///d:/Code/Projects/apache/datasketches-go/sampling/reservoir_items_union.go:37:0-40:1) implementation to align with Java's functionality.
## Changes
### Core Logic Fixes
- Fixed `twoWayMergeInternal` to correctly handle 4 merge cases
- Added `DownsampledCopy`, `Copy`, `GetImplicitSampleWeight` methods
- Added internal helpers: `getValueAtPosition`, `insertValueAtPosition`, `forceIncrementItemsSeen`
- Serialization: `ToSlice()`and `NewReservoirItemsUnionFromSlice()`
- UpdateFromRaw: Create sketch from raw components (n, k, items)
- `String()`: Human-readable summary
### Tests
- 17 test cases covering merge logic, serialization, and error handling
## Serialization Format
Compatible with Java V2:
- Byte 0: preLongs (1)
- Byte 1: serVer (2)
- Byte 2: familyID (12)
- Byte 3: flags
- Bytes 4-7: maxK (uint32 LE)
- Bytes 8+: gadget data
PS: Only V2 serialization is supported (V1 is legacy format from pre-2017).
Ref #103
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Posted by "proost (via GitHub)" <gi...@apache.org>.
proost merged PR #104:
URL: https://github.com/apache/datasketches-go/pull/104
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Posted by "Fengzdadi (via GitHub)" <gi...@apache.org>.
Fengzdadi commented on code in PR #104:
URL: https://github.com/apache/datasketches-go/pull/104#discussion_r2703422366
##########
sampling/reservoir_items_sketch.go:
##########
@@ -115,6 +115,62 @@ func (s *ReservoirItemsSketch[T]) Reset() {
s.data = s.data[:0]
}
+// GetImplicitSampleWeight returns N/K when in sampling mode, or 1.0 in exact mode.
+func (s *ReservoirItemsSketch[T]) GetImplicitSampleWeight() float64 {
Review Comment:
Solved
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Posted by "Fengzdadi (via GitHub)" <gi...@apache.org>.
Fengzdadi commented on code in PR #104:
URL: https://github.com/apache/datasketches-go/pull/104#discussion_r2703433246
##########
sampling/reservoir_items_sketch.go:
##########
@@ -115,6 +115,62 @@ func (s *ReservoirItemsSketch[T]) Reset() {
s.data = s.data[:0]
}
+// GetImplicitSampleWeight returns N/K when in sampling mode, or 1.0 in exact mode.
+func (s *ReservoirItemsSketch[T]) GetImplicitSampleWeight() float64 {
+ if s.n < int64(s.k) {
+ return 1.0
+ }
+ return float64(s.n) / float64(s.k)
+}
+
+// Copy returns a deep copy of the sketch.
+func (s *ReservoirItemsSketch[T]) Copy() *ReservoirItemsSketch[T] {
+ dataCopy := make([]T, len(s.data))
+ copy(dataCopy, s.data)
+ return &ReservoirItemsSketch[T]{
+ k: s.k,
+ n: s.n,
+ data: dataCopy,
+ }
+}
+
+// DownsampledCopy returns a copy with a reduced reservoir size.
+// If newK >= current K, returns a regular copy.
+func (s *ReservoirItemsSketch[T]) DownsampledCopy(newK int) *ReservoirItemsSketch[T] {
+ if newK >= s.k {
+ return s.Copy()
+ }
+
+ result, _ := NewReservoirItemsSketch[T](newK)
+
+ samples := s.Samples()
+ for _, item := range samples {
+ result.Update(item)
+ }
+
+ // Adjust N to preserve correct implicit weights
+ if result.n < s.n {
+ result.forceIncrementItemsSeen(s.n - result.n)
+ }
+
+ return result
+}
+
+// getValueAtPosition returns the item at the given position.
+func (s *ReservoirItemsSketch[T]) getValueAtPosition(pos int) T {
+ return s.data[pos]
+}
+
+// insertValueAtPosition replaces the item at the given position.
+func (s *ReservoirItemsSketch[T]) insertValueAtPosition(item T, pos int) {
+ s.data[pos] = item
+}
+
+// forceIncrementItemsSeen adds delta to the items seen count.
+func (s *ReservoirItemsSketch[T]) forceIncrementItemsSeen(delta int64) {
Review Comment:
I kept `forceIncrementItemsSeen` as-is because it only bumps n for implicit weights and never writes into the reservoir, so it can’t overfill capacity. Capacity validation now happens where it matters: `DownsampledCopy` returns an error on bad newK, `UpdateFromRaw` rejects k<1 or len(items)>k/n, and `UpdateSketch` propagates those errors/gadget creation failures.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Posted by "proost (via GitHub)" <gi...@apache.org>.
proost commented on code in PR #104:
URL: https://github.com/apache/datasketches-go/pull/104#discussion_r2703183206
##########
sampling/reservoir_items_sketch.go:
##########
@@ -115,6 +115,62 @@ func (s *ReservoirItemsSketch[T]) Reset() {
s.data = s.data[:0]
}
+// GetImplicitSampleWeight returns N/K when in sampling mode, or 1.0 in exact mode.
+func (s *ReservoirItemsSketch[T]) GetImplicitSampleWeight() float64 {
Review Comment:
can you remove `Get` prefix?
##########
sampling/reservoir_items_union.go:
##########
@@ -36,73 +46,137 @@ func NewReservoirItemsUnion[T any](maxK int) (*ReservoirItemsUnion[T], error) {
return nil, errors.New("maxK must be at least 1")
}
- gadget, err := NewReservoirItemsSketch[T](maxK)
- if err != nil {
- return nil, err
- }
-
return &ReservoirItemsUnion[T]{
maxK: maxK,
- gadget: gadget,
+ gadget: nil, // Start with nil gadget, will be initialized on first update
}, nil
}
// Update adds a single item to the union.
func (u *ReservoirItemsUnion[T]) Update(item T) {
+ if u.gadget == nil {
+ u.gadget, _ = NewReservoirItemsSketch[T](u.maxK)
+ }
u.gadget.Update(item)
}
// UpdateSketch merges another sketch into the union.
+// This implements Java's update(ReservoirItemsSketch) with twoWayMergeInternal logic.
func (u *ReservoirItemsUnion[T]) UpdateSketch(sketch *ReservoirItemsSketch[T]) {
if sketch == nil || sketch.IsEmpty() {
return
}
- samples := sketch.Samples()
- srcN := sketch.N()
+ // Downsample if input K > maxK
+ ris := sketch
+ if sketch.K() > u.maxK {
+ ris = sketch.DownsampledCopy(u.maxK)
+ }
- if u.gadget.IsEmpty() {
- // If gadget is empty, copy the source directly
- for _, v := range samples {
- u.gadget.data = append(u.gadget.data, v)
- }
- u.gadget.n = srcN
+ // Initialize gadget if empty
+ if u.gadget == nil || u.gadget.IsEmpty() {
+ u.createNewGadget(ris)
return
}
- // Merge using weighted sampling
- gadgetN := u.gadget.N()
- totalN := gadgetN + srcN
- gadgetK := u.gadget.NumSamples()
- targetK := u.maxK
-
- for _, item := range samples {
- if u.gadget.NumSamples() < targetK {
- u.gadget.data = append(u.gadget.data, item)
- } else {
- j := rand.Int63n(totalN)
- if j < int64(targetK) {
- u.gadget.data[j%int64(gadgetK)] = item
- }
+ u.twoWayMergeInternal(ris)
+}
+
+// UpdateFromRaw creates a sketch from raw components and merges it.
+// Useful in distributed environments. Items slice is used directly, not copied.
+func (u *ReservoirItemsUnion[T]) UpdateFromRaw(n int64, k int, items []T) {
+ if len(items) == 0 {
+ return
+ }
+
+ sketch := &ReservoirItemsSketch[T]{
+ k: k,
+ n: n,
+ data: items,
+ }
+
+ u.UpdateSketch(sketch)
+}
+
+// createNewGadget initializes the gadget based on the source sketch.
+// If source is in exact mode with K < maxK: upgrade to maxK.
+// Otherwise: preserve source's K.
+func (u *ReservoirItemsUnion[T]) createNewGadget(source *ReservoirItemsSketch[T]) {
+ if source.K() < u.maxK && source.N() <= int64(source.K()) {
+
+ u.gadget, _ = NewReservoirItemsSketch[T](u.maxK)
+ for i := 0; i < source.NumSamples(); i++ {
Review Comment:
can you use "twoWayMergeInternalStandard" instead?
##########
sampling/reservoir_items_sketch.go:
##########
@@ -115,6 +115,62 @@ func (s *ReservoirItemsSketch[T]) Reset() {
s.data = s.data[:0]
}
+// GetImplicitSampleWeight returns N/K when in sampling mode, or 1.0 in exact mode.
+func (s *ReservoirItemsSketch[T]) GetImplicitSampleWeight() float64 {
+ if s.n < int64(s.k) {
+ return 1.0
+ }
+ return float64(s.n) / float64(s.k)
+}
+
+// Copy returns a deep copy of the sketch.
+func (s *ReservoirItemsSketch[T]) Copy() *ReservoirItemsSketch[T] {
+ dataCopy := make([]T, len(s.data))
+ copy(dataCopy, s.data)
+ return &ReservoirItemsSketch[T]{
+ k: s.k,
+ n: s.n,
+ data: dataCopy,
+ }
+}
+
+// DownsampledCopy returns a copy with a reduced reservoir size.
+// If newK >= current K, returns a regular copy.
+func (s *ReservoirItemsSketch[T]) DownsampledCopy(newK int) *ReservoirItemsSketch[T] {
+ if newK >= s.k {
+ return s.Copy()
+ }
+
+ result, _ := NewReservoirItemsSketch[T](newK)
+
+ samples := s.Samples()
+ for _, item := range samples {
+ result.Update(item)
+ }
+
+ // Adjust N to preserve correct implicit weights
+ if result.n < s.n {
+ result.forceIncrementItemsSeen(s.n - result.n)
+ }
+
+ return result
+}
+
+// getValueAtPosition returns the item at the given position.
+func (s *ReservoirItemsSketch[T]) getValueAtPosition(pos int) T {
+ return s.data[pos]
+}
+
+// insertValueAtPosition replaces the item at the given position.
+func (s *ReservoirItemsSketch[T]) insertValueAtPosition(item T, pos int) {
+ s.data[pos] = item
+}
+
+// forceIncrementItemsSeen adds delta to the items seen count.
+func (s *ReservoirItemsSketch[T]) forceIncrementItemsSeen(delta int64) {
Review Comment:
We need to check that capacity is enough. If not we should return error.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Posted by "proost (via GitHub)" <gi...@apache.org>.
proost commented on code in PR #104:
URL: https://github.com/apache/datasketches-go/pull/104#discussion_r2706770157
##########
sampling/reservoir_items_sketch.go:
##########
@@ -115,6 +115,62 @@ func (s *ReservoirItemsSketch[T]) Reset() {
s.data = s.data[:0]
}
+// GetImplicitSampleWeight returns N/K when in sampling mode, or 1.0 in exact mode.
+func (s *ReservoirItemsSketch[T]) GetImplicitSampleWeight() float64 {
+ if s.n < int64(s.k) {
+ return 1.0
+ }
+ return float64(s.n) / float64(s.k)
+}
+
+// Copy returns a deep copy of the sketch.
+func (s *ReservoirItemsSketch[T]) Copy() *ReservoirItemsSketch[T] {
+ dataCopy := make([]T, len(s.data))
+ copy(dataCopy, s.data)
+ return &ReservoirItemsSketch[T]{
+ k: s.k,
+ n: s.n,
+ data: dataCopy,
+ }
+}
+
+// DownsampledCopy returns a copy with a reduced reservoir size.
+// If newK >= current K, returns a regular copy.
+func (s *ReservoirItemsSketch[T]) DownsampledCopy(newK int) *ReservoirItemsSketch[T] {
+ if newK >= s.k {
+ return s.Copy()
+ }
+
+ result, _ := NewReservoirItemsSketch[T](newK)
+
+ samples := s.Samples()
+ for _, item := range samples {
+ result.Update(item)
+ }
+
+ // Adjust N to preserve correct implicit weights
+ if result.n < s.n {
+ result.forceIncrementItemsSeen(s.n - result.n)
+ }
+
+ return result
+}
+
+// getValueAtPosition returns the item at the given position.
+func (s *ReservoirItemsSketch[T]) getValueAtPosition(pos int) T {
+ return s.data[pos]
+}
+
+// insertValueAtPosition replaces the item at the given position.
+func (s *ReservoirItemsSketch[T]) insertValueAtPosition(item T, pos int) {
+ s.data[pos] = item
+}
+
+// forceIncrementItemsSeen adds delta to the items seen count.
+func (s *ReservoirItemsSketch[T]) forceIncrementItemsSeen(delta int64) {
Review Comment:
Oh, you are right.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Posted by "Fengzdadi (via GitHub)" <gi...@apache.org>.
Fengzdadi commented on PR #104:
URL: https://github.com/apache/datasketches-go/pull/104#issuecomment-3775903562
Added cross-language coverage for reservoir unions (long/double/string): tests now load 27 Java-generated files (empty, exact 1/10/32/100/128, sampling maxK 32/64/128) and we also generate matching Go fixtures; `go test ./...` passes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat: Complete ReservoirItemsUnion implementation [datasketches-go]
Posted by "Fengzdadi (via GitHub)" <gi...@apache.org>.
Fengzdadi commented on code in PR #104:
URL: https://github.com/apache/datasketches-go/pull/104#discussion_r2703450095
##########
sampling/reservoir_items_union.go:
##########
@@ -36,73 +46,137 @@ func NewReservoirItemsUnion[T any](maxK int) (*ReservoirItemsUnion[T], error) {
return nil, errors.New("maxK must be at least 1")
}
- gadget, err := NewReservoirItemsSketch[T](maxK)
- if err != nil {
- return nil, err
- }
-
return &ReservoirItemsUnion[T]{
maxK: maxK,
- gadget: gadget,
+ gadget: nil, // Start with nil gadget, will be initialized on first update
}, nil
}
// Update adds a single item to the union.
func (u *ReservoirItemsUnion[T]) Update(item T) {
+ if u.gadget == nil {
+ u.gadget, _ = NewReservoirItemsSketch[T](u.maxK)
+ }
u.gadget.Update(item)
}
// UpdateSketch merges another sketch into the union.
+// This implements Java's update(ReservoirItemsSketch) with twoWayMergeInternal logic.
func (u *ReservoirItemsUnion[T]) UpdateSketch(sketch *ReservoirItemsSketch[T]) {
if sketch == nil || sketch.IsEmpty() {
return
}
- samples := sketch.Samples()
- srcN := sketch.N()
+ // Downsample if input K > maxK
+ ris := sketch
+ if sketch.K() > u.maxK {
+ ris = sketch.DownsampledCopy(u.maxK)
+ }
- if u.gadget.IsEmpty() {
- // If gadget is empty, copy the source directly
- for _, v := range samples {
- u.gadget.data = append(u.gadget.data, v)
- }
- u.gadget.n = srcN
+ // Initialize gadget if empty
+ if u.gadget == nil || u.gadget.IsEmpty() {
+ u.createNewGadget(ris)
return
}
- // Merge using weighted sampling
- gadgetN := u.gadget.N()
- totalN := gadgetN + srcN
- gadgetK := u.gadget.NumSamples()
- targetK := u.maxK
-
- for _, item := range samples {
- if u.gadget.NumSamples() < targetK {
- u.gadget.data = append(u.gadget.data, item)
- } else {
- j := rand.Int63n(totalN)
- if j < int64(targetK) {
- u.gadget.data[j%int64(gadgetK)] = item
- }
+ u.twoWayMergeInternal(ris)
+}
+
+// UpdateFromRaw creates a sketch from raw components and merges it.
+// Useful in distributed environments. Items slice is used directly, not copied.
+func (u *ReservoirItemsUnion[T]) UpdateFromRaw(n int64, k int, items []T) {
+ if len(items) == 0 {
+ return
+ }
+
+ sketch := &ReservoirItemsSketch[T]{
+ k: k,
+ n: n,
+ data: items,
+ }
+
+ u.UpdateSketch(sketch)
+}
+
+// createNewGadget initializes the gadget based on the source sketch.
+// If source is in exact mode with K < maxK: upgrade to maxK.
+// Otherwise: preserve source's K.
+func (u *ReservoirItemsUnion[T]) createNewGadget(source *ReservoirItemsSketch[T]) {
+ if source.K() < u.maxK && source.N() <= int64(source.K()) {
+
+ u.gadget, _ = NewReservoirItemsSketch[T](u.maxK)
+ for i := 0; i < source.NumSamples(); i++ {
Review Comment:
fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org