stojkomilos opened a new pull request, #515: URL: https://github.com/apache/datasketches-cpp/pull/515
## What changed Add `get_result()` to `update_theta_sketch_alloc`. It returns a `compact_theta_sketch` trimmed to at most the nominal size `k` (`2^lg_k`) in a single pass, without rebuilding the hash table. Background: an update sketch's hash table retains up to `~15/16 * 2k` entries between rebuilds, and `compact()` intentionally keeps all of them (extra entries below theta improve the estimate). To bound a result to `k` today, a caller does `trim()` then `compact()`. `trim()` calls `rebuild()`, which allocates a fresh `2k` array, zero-fills it, and rehashes the survivors via open-addressing probing, and that hash table is then discarded by the following `compact()`. `get_result()` skips the rebuild: it copies the retained entries into the output vector that `compact()` already allocates, and when there are more than `k` it applies `nth_element`, sets theta to the (k+1)-th smallest, and erases the tail. No extra allocation, no rehash. The result is unordered. ## Why This mirrors `theta_union::get_result()` (`theta_union_base::get_result`), which guarantees a result of at most the nominal size `k = 2^lg_k` and implements it with exactly this `nth_element` / `erase` cutback on the output vector. The standalone update sketch had no equivalent: a caller either kept the over-provisioned `compact()` output, or paid for the `trim()` rehash. `get_result()` gives the update sketch the same at-most-`k` guarantee and the same efficient one-pass implementation. Note: `theta_intersection::get_result()` does not apply this trim. An intersection result is naturally bounded by its smallest operand, so it returns its table as-is. The parallel here is specifically with union. ## How tested New Catch2 cases in `theta/test/theta_sketch_test.cpp`: - `get_result trims to k in one pass`: builds an 8000-item sketch (retains more than `k`); asserts `get_result()` returns exactly `k` entries, is unordered, and yields the identical theta and retained-hash set as `trim()` + `compact(false)`. - `get_result on empty and below-k sketches`: empty stays empty; a 100-item exact-mode sketch returns untrimmed with all entries. Local run: ``` cmake --build build --target theta_test -j ./build/theta/test/theta_test "[theta_sketch]" # All tests passed (85764 assertions in 34 test cases) ``` -- 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]
