leerho opened a new pull request, #524:
URL: https://github.com/apache/datasketches-cpp/pull/524
## What changed
Adds an optional second flag to the existing `compact()` on
`update_theta_sketch_alloc`:
```cpp
compact_theta_sketch_alloc<Allocator> compact(bool ordered = true, bool trim
= false) const;
```
`trim = true` reduces the returned sketch to at most the nominal size `k`.
The default is unchanged, and because the parameter is defaulted and
`compact()` is not virtual here, every existing call site compiles untouched.
Thanks to @stojkomilos for raising the underlying need in #515. This takes a
different approach — a flag on the existing method rather than a new
`get_result()` — for two reasons: it avoids adding public API surface, and
trimming turns out to be lossy enough that it should be an explicit opt-in
rather than the natural way to obtain a result.
## Why trimming is opt-in
Relative error scales with `1 / sqrt(retained)`, so discarding entries
always widens the confidence bounds, whatever mode the source is in. Measured
at the default `lg_k`, comparing `compact()` against `compact(true, true)`:
| n | retained | 2-sigma width | trimmed width | widened |
|-------:|---------:|--------------:|--------------:|--------:|
| 20000 | 5644 | 895.13 | 1120.26 | 1.25x |
| 40000 | 6037 | 1900.72 | 2419.57 | 1.27x |
| 60000 | 4800 | 3331.83 | 3585.58 | 1.08x |
| 100000 | 4285 | 5873.90 | 6024.14 | 1.03x |
The cost depends on where in the rebuild cycle the sketch is caught, which a
caller cannot predict. Worst case is bounded: a sketch grown to just under the
`15/16 * 2k` rebuild threshold loses nearly half its entries, widening the
bounds by about `sqrt(15/8)`, roughly 37%.
Separately, a sketch in **exact mode** can retain more than `k` entries —
nothing has been evicted, so theta is still 1.0. Trimming there discards real
data and returns an estimating sketch:
```
n=5000 k=4096 retained=5000 source exact=YES
compact() -> estimate 5000 exact=YES
compact(true, true) -> estimate 4983.64 exact=no
```
Both effects are documented on the `trim` parameter and pinned by tests.
## Implementation
The trim path copies the retained entries first — the method is `const`, and
quick select would permute the live table — then partitions with
`std::nth_element` at 0-based index `k`, so `entries[k]` becomes the new theta
and the `k` entries below it are kept. Sorting happens only when an ordered
result is requested. This is the same pivot convention already used by
`rebuild()` in `theta_update_sketch_base_impl.hpp`, so trimming and rebuilding
cannot drift apart.
## How tested
New cases in `theta/test/theta_sketch_test.cpp`:
- **all four ordered/trim combinations**, including that the source sketch
is unmodified afterwards, that trimmed output matches `trim()` + `compact()` on
theta and retained set, and that every retained hash is strictly below the new
theta
- **exact to estimation conversion** at n=5000
- **bounds widening** for a source already in estimation mode
- **empty and below-k** sketches, where trimming is a no-op
```
./build/theta/test/theta_test
All tests passed (20250056 assertions in 89 test cases)
ctest --test-dir build
100% tests passed, 0 tests failed out of 17
```
## Note on the Java side
`datasketches-java` should get the same capability, but it cannot use the
same mechanism: `ThetaSketch.compact(boolean dstOrdered, MemorySegment dstSeg)`
is `abstract` and already occupies the two-argument slot, so Java needs an
overload rather than an added parameter, and `compact(true, null)` would be
ambiguous. Also worth care there: `QuickSelect.selectExcludingZeros` is 1-based
while `std::nth_element` is 0-based, so the Java port should assert `retained
== k` the way these tests do. That work is deliberately left to a separate PR.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
https://claude.ai/code/session_017EDHa7UhfW4eSj5L82panJ
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
