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 2019/11/05 00:08:03 UTC
[incubator-datasketches-cpp] branch cpc_template updated (e29531d
-> 271aa54)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch cpc_template
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git.
from e29531d union test
new 94b563a use vector for bit matrix
new 271aa54 test reducing k
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
cpc/include/cpc_common.hpp | 10 ++++--
cpc/include/cpc_sketch.hpp | 3 +-
cpc/include/cpc_sketch_impl.hpp | 15 ++++----
cpc/include/cpc_union.hpp | 7 ++--
cpc/include/cpc_union_impl.hpp | 76 +++++++++++++++++------------------------
cpc/test/cpc_union_test.cpp | 51 +++++++++++++++++++++++++--
6 files changed, 98 insertions(+), 64 deletions(-)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 01/02: use vector for bit matrix
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch cpc_template
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit 94b563a8e7e036370da6f0164817747b2b2d2e88
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Mon Nov 4 15:56:53 2019 -0800
use vector for bit matrix
---
cpc/include/cpc_common.hpp | 10 ++++--
cpc/include/cpc_sketch.hpp | 3 +-
cpc/include/cpc_sketch_impl.hpp | 15 ++++----
cpc/include/cpc_union.hpp | 7 ++--
cpc/include/cpc_union_impl.hpp | 76 +++++++++++++++++------------------------
5 files changed, 50 insertions(+), 61 deletions(-)
diff --git a/cpc/include/cpc_common.hpp b/cpc/include/cpc_common.hpp
index 921c36f..4819c66 100644
--- a/cpc/include/cpc_common.hpp
+++ b/cpc/include/cpc_common.hpp
@@ -35,6 +35,12 @@ static const uint64_t DEFAULT_SEED = 9001;
typedef std::unique_ptr<void, std::function<void(void*)>> void_ptr_with_deleter;
typedef std::unique_ptr<uint32_t, std::function<void(uint32_t*)>> u32_ptr_with_deleter;
+template<typename A> using AllocU8 = typename std::allocator_traits<A>::template rebind_alloc<uint8_t>;
+template<typename A> using AllocU64 = typename std::allocator_traits<A>::template rebind_alloc<uint64_t>;
+
+template<typename A> using vector_u8 = std::vector<uint8_t, AllocU8<A>>;
+template<typename A> using vector_u64 = std::vector<uint64_t, AllocU64<A>>;
+
struct compressed_state {
u32_ptr_with_deleter table_data_ptr;
uint32_t table_data_words;
@@ -45,8 +51,8 @@ struct compressed_state {
template<typename A>
struct uncompressed_state {
- typedef typename std::allocator_traits<A>::template rebind_alloc<uint8_t> AllocU8;
- typedef typename std::vector<uint8_t, AllocU8> window_type;
+ //typedef typename std::allocator_traits<A>::template rebind_alloc<uint8_t> AllocU8;
+ typedef typename std::vector<uint8_t, AllocU8<A>> window_type;
u32_table<A> table;
window_type window;
};
diff --git a/cpc/include/cpc_sketch.hpp b/cpc/include/cpc_sketch.hpp
index 8502df1..7fe3f46 100644
--- a/cpc/include/cpc_sketch.hpp
+++ b/cpc/include/cpc_sketch.hpp
@@ -156,8 +156,7 @@ class cpc_sketch_alloc {
static inline uint8_t determine_correct_offset(uint8_t lg_k, uint64_t c);
// this produces a full-size k-by-64 bit matrix
- // since this is for internal use, deallocation of the matrix is on the caller
- uint64_t* build_bit_matrix() const;
+ vector_u64<A> build_bit_matrix() const;
static uint8_t get_preamble_ints(uint32_t num_coupons, bool has_hip, bool has_table, bool has_window);
inline void write_hip(std::ostream& os) const;
diff --git a/cpc/include/cpc_sketch_impl.hpp b/cpc/include/cpc_sketch_impl.hpp
index 8ac11dc..b83c3d4 100644
--- a/cpc/include/cpc_sketch_impl.hpp
+++ b/cpc/include/cpc_sketch_impl.hpp
@@ -303,10 +303,10 @@ void cpc_sketch_alloc<A>::move_window() {
const uint64_t k = 1 << lg_k;
// Construct the full-sized bit matrix that corresponds to the sketch
- uint64_t* bit_matrix = build_bit_matrix();
+ vector_u64<A> bit_matrix = build_bit_matrix();
// refresh the KXP register on every 8th window shift.
- if ((new_offset & 0x7) == 0) refresh_kxp(bit_matrix);
+ if ((new_offset & 0x7) == 0) refresh_kxp(bit_matrix.data());
surprising_value_table.clear(); // the new number of surprises will be about the same
@@ -331,7 +331,6 @@ void cpc_sketch_alloc<A>::move_window() {
}
}
- AllocU64().deallocate(bit_matrix, k);
window_offset = new_offset;
first_interesting_column = count_trailing_zeros_in_u64(all_surprises_ored);
@@ -674,9 +673,8 @@ uint32_t cpc_sketch_alloc<A>::get_num_coupons() const {
template<typename A>
bool cpc_sketch_alloc<A>::validate() const {
- uint64_t* bit_matrix = build_bit_matrix();
- const uint64_t num_bits_set = count_bits_set_in_matrix(bit_matrix, 1 << lg_k);
- AllocU64().deallocate(bit_matrix, 1 << lg_k);
+ vector_u64<A> bit_matrix = build_bit_matrix();
+ const uint64_t num_bits_set = count_bits_set_in_matrix(bit_matrix.data(), 1 << lg_k);
return num_bits_set == num_coupons;
}
@@ -744,15 +742,14 @@ uint8_t cpc_sketch_alloc<A>::determine_correct_offset(uint8_t lg_k, uint64_t c)
}
template<typename A>
-uint64_t* cpc_sketch_alloc<A>::build_bit_matrix() const {
+vector_u64<A> cpc_sketch_alloc<A>::build_bit_matrix() const {
const size_t k = 1 << lg_k;
if (window_offset > 56) throw std::logic_error("offset > 56");
- uint64_t* matrix = AllocU64().allocate(k);
// Fill the matrix with default rows in which the "early zone" is filled with ones.
// This is essential for the routine's O(k) time cost (as opposed to O(C)).
const uint64_t default_row = (1 << window_offset) - 1;
- std::fill(matrix, &matrix[k], default_row);
+ vector_u64<A> matrix(k, default_row);
if (num_coupons == 0) return matrix;
diff --git a/cpc/include/cpc_union.hpp b/cpc/include/cpc_union.hpp
index b299cc1..4841fdb 100644
--- a/cpc/include/cpc_union.hpp
+++ b/cpc/include/cpc_union.hpp
@@ -56,12 +56,11 @@ class cpc_union_alloc {
typedef typename std::allocator_traits<A>::template rebind_alloc<uint8_t> AllocU8;
typedef typename std::allocator_traits<A>::template rebind_alloc<uint64_t> AllocU64;
typedef typename std::allocator_traits<A>::template rebind_alloc<cpc_sketch_alloc<A>> AllocCpc;
- typedef typename std::vector<uint8_t, AllocU8> window_type;
uint8_t lg_k;
uint64_t seed;
cpc_sketch_alloc<A>* accumulator;
- uint64_t* bit_matrix;
+ vector_u64<A> bit_matrix;
cpc_sketch_alloc<A> get_result_from_accumulator() const;
cpc_sketch_alloc<A> get_result_from_bit_matrix() const;
@@ -69,8 +68,8 @@ class cpc_union_alloc {
void switch_to_bit_matrix();
void walk_table_updating_sketch(const u32_table<A>& table);
void or_table_into_matrix(const u32_table<A>& table);
- void or_window_into_matrix(const window_type& sliding_window, uint8_t offset, uint8_t src_lg_k);
- void or_matrix_into_matrix(const uint64_t* src_matrix, uint8_t src_lg_k);
+ void or_window_into_matrix(const vector_u8<A>& sliding_window, uint8_t offset, uint8_t src_lg_k);
+ void or_matrix_into_matrix(const vector_u64<A>& src_matrix, uint8_t src_lg_k);
void reduce_k(uint8_t new_lg_k);
};
diff --git a/cpc/include/cpc_union_impl.hpp b/cpc/include/cpc_union_impl.hpp
index ca87bf4..28f610c 100644
--- a/cpc/include/cpc_union_impl.hpp
+++ b/cpc/include/cpc_union_impl.hpp
@@ -27,7 +27,7 @@ cpc_union_alloc<A>::cpc_union_alloc(uint8_t lg_k, uint64_t seed):
lg_k(lg_k),
seed(seed),
accumulator(new (AllocCpc().allocate(1)) cpc_sketch_alloc<A>(lg_k, seed)),
-bit_matrix(nullptr)
+bit_matrix()
{
if (lg_k < CPC_MIN_LG_K or lg_k > CPC_MAX_LG_K) {
throw std::invalid_argument("lg_k must be >= " + std::to_string(CPC_MIN_LG_K) + " and <= " + std::to_string(CPC_MAX_LG_K) + ": " + std::to_string(lg_k));
@@ -44,11 +44,6 @@ bit_matrix(other.bit_matrix)
if (accumulator != nullptr) {
accumulator = new (AllocCpc().allocate(1)) cpc_sketch_alloc<A>(*other.accumulator);
}
- if (bit_matrix != nullptr) {
- const size_t k = 1 << lg_k;
- bit_matrix = AllocU64().allocate(k);
- std::copy(other.bit_matrix, &other.bit_matrix[k], bit_matrix);
- }
}
template<typename A>
@@ -56,10 +51,9 @@ cpc_union_alloc<A>::cpc_union_alloc(cpc_union_alloc<A>&& other) noexcept:
lg_k(other.lg_k),
seed(other.seed),
accumulator(other.accumulator),
-bit_matrix(other.bit_matrix)
+bit_matrix(std::move(other.bit_matrix))
{
other.accumulator = nullptr;
- other.bit_matrix = nullptr;
}
template<typename A>
@@ -68,9 +62,6 @@ cpc_union_alloc<A>::~cpc_union_alloc() {
accumulator->~cpc_sketch_alloc<A>();
AllocCpc().deallocate(accumulator, 1);
}
- if (bit_matrix != nullptr) {
- AllocU64().deallocate(bit_matrix, 1 << lg_k);
- }
}
template<typename A>
@@ -79,7 +70,7 @@ cpc_union_alloc<A>& cpc_union_alloc<A>::operator=(const cpc_union_alloc<A>& othe
std::swap(lg_k, copy.lg_k);
seed = copy.seed;
std::swap(accumulator, copy.accumulator);
- std::swap(bit_matrix, copy.bit_matrix);
+ bit_matrix = std::move(copy.bit_matrix);
return *this;
}
@@ -88,7 +79,7 @@ cpc_union_alloc<A>& cpc_union_alloc<A>::operator=(cpc_union_alloc<A>&& other) no
std::swap(lg_k, other.lg_k);
seed = other.seed;
std::swap(accumulator, other.accumulator);
- std::swap(bit_matrix, other.bit_matrix);
+ bit_matrix = std::move(other.bit_matrix);
return *this;
}
@@ -106,10 +97,10 @@ void cpc_union_alloc<A>::update(const cpc_sketch_alloc<A>& sketch) {
if (sketch.get_lg_k() < lg_k) reduce_k(sketch.get_lg_k());
if (sketch.get_lg_k() < lg_k) throw std::logic_error("sketch lg_k < union lg_k");
- if (accumulator == nullptr and bit_matrix == nullptr) throw std::logic_error("both accumulator and bit matrix are null");
+ if (accumulator == nullptr and bit_matrix.size() == 0) throw std::logic_error("both accumulator and bit matrix are absent");
if (cpc_sketch_alloc<A>::flavor::SPARSE == src_flavor and accumulator != nullptr) { // Case A
- if (bit_matrix != nullptr) throw std::logic_error("union bit_matrix != null");
+ if (bit_matrix.size() > 0) throw std::logic_error("union bit_matrix is not expected");
const auto initial_dest_flavor = accumulator->determine_flavor();
if (cpc_sketch_alloc<A>::flavor::EMPTY != initial_dest_flavor and
cpc_sketch_alloc<A>::flavor::SPARSE != initial_dest_flavor) throw std::logic_error("wrong flavor");
@@ -124,15 +115,12 @@ void cpc_union_alloc<A>::update(const cpc_sketch_alloc<A>& sketch) {
const auto final_dst_flavor = accumulator->determine_flavor();
// if the accumulator has graduated beyond sparse, switch to a bit matrix representation
if (final_dst_flavor != cpc_sketch_alloc<A>::flavor::EMPTY and final_dst_flavor != cpc_sketch_alloc<A>::flavor::SPARSE) {
- bit_matrix = accumulator->build_bit_matrix();
- accumulator->~cpc_sketch_alloc<A>();
- AllocCpc().deallocate(accumulator, 1);
- accumulator = nullptr;
+ switch_to_bit_matrix();
}
return;
}
- if (cpc_sketch_alloc<A>::flavor::SPARSE == src_flavor and bit_matrix != nullptr) { // Case B
+ if (cpc_sketch_alloc<A>::flavor::SPARSE == src_flavor and bit_matrix.size() > 0) { // Case B
if (accumulator != nullptr) throw std::logic_error("union accumulator != null");
or_table_into_matrix(sketch.surprising_value_table);
return;
@@ -143,14 +131,14 @@ void cpc_union_alloc<A>::update(const cpc_sketch_alloc<A>& sketch) {
// source is past SPARSE mode, so make sure that dest is a bit matrix
if (accumulator != nullptr) {
- if (bit_matrix != nullptr) throw std::logic_error("union bit matrix != null");
+ if (bit_matrix.size() > 0) throw std::logic_error("union bit matrix is not expected");
const auto dst_flavor = accumulator->determine_flavor();
if (cpc_sketch_alloc<A>::flavor::EMPTY != dst_flavor and cpc_sketch_alloc<A>::flavor::SPARSE != dst_flavor) {
throw std::logic_error("wrong flavor");
}
switch_to_bit_matrix();
}
- if (bit_matrix == nullptr) throw std::logic_error("union bit_matrix == null");
+ if (bit_matrix.size() == 0) throw std::logic_error("union bit_matrix is expected");
if (cpc_sketch_alloc<A>::flavor::HYBRID == src_flavor or cpc_sketch_alloc<A>::flavor::PINNED == src_flavor) { // Case C
or_window_into_matrix(sketch.sliding_window, sketch.window_offset, sketch.get_lg_k());
@@ -161,18 +149,17 @@ void cpc_union_alloc<A>::update(const cpc_sketch_alloc<A>& sketch) {
// SLIDING mode involves inverted logic, so we can't just walk the source sketch.
// Instead, we convert it to a bitMatrix that can be OR'ed into the destination.
if (cpc_sketch_alloc<A>::flavor::SLIDING != src_flavor) throw std::logic_error("wrong flavor"); // Case D
- uint64_t* src_matrix = sketch.build_bit_matrix();
+ vector_u64<A> src_matrix = sketch.build_bit_matrix();
or_matrix_into_matrix(src_matrix, sketch.get_lg_k());
- AllocU64().deallocate(src_matrix, 1 << sketch.get_lg_k());
}
template<typename A>
cpc_sketch_alloc<A> cpc_union_alloc<A>::get_result() const {
if (accumulator != nullptr) {
- if (bit_matrix != nullptr) throw std::logic_error("bit_matrix is not expected");
+ if (bit_matrix.size() > 0) throw std::logic_error("bit_matrix is not expected");
return get_result_from_accumulator();
}
- if (bit_matrix == nullptr) throw std::logic_error("bit_matrix is expected");
+ if (bit_matrix.size() == 0) throw std::logic_error("bit_matrix is expected");
return get_result_from_bit_matrix();
}
@@ -191,7 +178,7 @@ cpc_sketch_alloc<A> cpc_union_alloc<A>::get_result_from_accumulator() const {
template<typename A>
cpc_sketch_alloc<A> cpc_union_alloc<A>::get_result_from_bit_matrix() const {
const uint64_t k = 1 << lg_k;
- const uint64_t num_coupons = count_bits_set_in_matrix(bit_matrix, k);
+ const uint64_t num_coupons = count_bits_set_in_matrix(bit_matrix.data(), k);
const auto flavor = cpc_sketch_alloc<A>::determine_flavor(lg_k, num_coupons);
if (flavor != cpc_sketch_alloc<A>::flavor::HYBRID and flavor != cpc_sketch_alloc<A>::flavor::PINNED
@@ -199,7 +186,7 @@ cpc_sketch_alloc<A> cpc_union_alloc<A>::get_result_from_bit_matrix() const {
const uint8_t offset = cpc_sketch_alloc<A>::determine_correct_offset(lg_k, num_coupons);
- window_type sliding_window(k);
+ vector_u8<A> sliding_window(k);
// don't need to zero the window's memory
// dynamically growing caused snowplow effect
@@ -284,7 +271,7 @@ void cpc_union_alloc<A>::or_table_into_matrix(const u32_table<A>& table) {
}
template<typename A>
-void cpc_union_alloc<A>::or_window_into_matrix(const window_type& sliding_window, uint8_t offset, uint8_t src_lg_k) {
+void cpc_union_alloc<A>::or_window_into_matrix(const vector_u8<A>& sliding_window, uint8_t offset, uint8_t src_lg_k) {
if (lg_k > src_lg_k) throw std::logic_error("dst LgK > src LgK");
const uint64_t dst_mask = (1 << lg_k) - 1; // downsamples when dst lgK < src LgK
const size_t src_k = 1 << src_lg_k;
@@ -294,7 +281,7 @@ void cpc_union_alloc<A>::or_window_into_matrix(const window_type& sliding_window
}
template<typename A>
-void cpc_union_alloc<A>::or_matrix_into_matrix(const uint64_t* src_matrix, uint8_t src_lg_k) {
+void cpc_union_alloc<A>::or_matrix_into_matrix(const vector_u64<A>& src_matrix, uint8_t src_lg_k) {
if (lg_k > src_lg_k) throw std::logic_error("dst LgK > src LgK");
const uint64_t dst_mask = (1 << lg_k) - 1; // downsamples when dst lgK < src LgK
const size_t src_k = 1 << src_lg_k;
@@ -306,34 +293,35 @@ void cpc_union_alloc<A>::or_matrix_into_matrix(const uint64_t* src_matrix, uint8
template<typename A>
void cpc_union_alloc<A>::reduce_k(uint8_t new_lg_k) {
if (new_lg_k >= lg_k) throw std::logic_error("new LgK >= union lgK");
- if (accumulator == nullptr and bit_matrix == nullptr) throw std::logic_error("both accumulator and bit_matrix are null");
+ if (accumulator == nullptr and bit_matrix.size() == 0) throw std::logic_error("both accumulator and bit_matrix are absent");
- if (bit_matrix != nullptr) { // downsample the unioner's bit matrix
+ if (bit_matrix.size() > 0) { // downsample the unioner's bit matrix
if (accumulator != nullptr) throw std::logic_error("accumulator is not null");
- uint64_t* old_matrix = bit_matrix;
+ vector_u64<A> old_matrix = std::move(bit_matrix);
const uint8_t old_lg_k = lg_k;
const size_t new_k = 1 << new_lg_k;
- bit_matrix = AllocU64().allocate(new_k);
+ bit_matrix = vector_u64<A>(new_k, 0);
lg_k = new_lg_k;
- std::fill(bit_matrix, &bit_matrix[new_k], 0);
or_matrix_into_matrix(old_matrix, old_lg_k);
- AllocU64().deallocate(bit_matrix, 1 << old_lg_k);
return;
}
if (accumulator != nullptr) { // downsample the unioner's sketch
- if (bit_matrix != nullptr) throw std::logic_error("bit_matrix is not null");
- cpc_sketch_alloc<A> old_accumulator(*accumulator);
- *accumulator = cpc_sketch_alloc<A>(new_lg_k, seed);
- walk_table_updating_sketch(old_accumulator.surprising_value_table);
+ if (bit_matrix.size() > 0) throw std::logic_error("bit_matrix is not expected");
+ if (!accumulator->is_empty()) {
+ cpc_sketch_alloc<A> old_accumulator(*accumulator);
+ *accumulator = cpc_sketch_alloc<A>(new_lg_k, seed);
+ walk_table_updating_sketch(old_accumulator.surprising_value_table);
+ }
+ lg_k = new_lg_k;
const auto final_new_flavor = accumulator->determine_flavor();
- if (final_new_flavor == cpc_sketch_alloc<A>::flavor::EMPTY) throw std::logic_error("final_new_flavor == EMPTY");
- if (final_new_flavor != cpc_sketch_alloc<A>::flavor::SPARSE) {
- // the new sketch has graduated beyond sparse, so convert to bit_matrix
+ // if the new sketch has graduated beyond sparse, convert to bit_matrix
+ if (final_new_flavor != cpc_sketch_alloc<A>::flavor::EMPTY and
+ final_new_flavor != cpc_sketch_alloc<A>::flavor::SPARSE) {
switch_to_bit_matrix();
- return;
}
+ return;
}
throw std::logic_error("invalid state");
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 02/02: test reducing k
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch cpc_template
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit 271aa54d2237c145280c20e48c2a934f7e047288
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Mon Nov 4 16:07:51 2019 -0800
test reducing k
---
cpc/test/cpc_union_test.cpp | 51 ++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 48 insertions(+), 3 deletions(-)
diff --git a/cpc/test/cpc_union_test.cpp b/cpc/test/cpc_union_test.cpp
index 63ac2c3..256ee10 100644
--- a/cpc/test/cpc_union_test.cpp
+++ b/cpc/test/cpc_union_test.cpp
@@ -34,6 +34,9 @@ class cpc_union_test: public CppUnit::TestFixture {
CPPUNIT_TEST(copy);
CPPUNIT_TEST(custom_seed);
CPPUNIT_TEST(large);
+ CPPUNIT_TEST(reduce_k_empty);
+ CPPUNIT_TEST(reduce_k_sparse);
+ CPPUNIT_TEST(reduce_k_window);
CPPUNIT_TEST_SUITE_END();
void lg_k_limits() {
@@ -65,7 +68,7 @@ class cpc_union_test: public CppUnit::TestFixture {
u1 = u2; // operator=
auto s2 = u1.get_result();
CPPUNIT_ASSERT(!s2.is_empty());
- CPPUNIT_ASSERT_DOUBLES_EQUAL(2, s2.get_estimate(), RELATIVE_ERROR_FOR_LG_K_11);
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(2, s2.get_estimate(), 2 * RELATIVE_ERROR_FOR_LG_K_11);
}
void custom_seed() {
@@ -79,7 +82,7 @@ class cpc_union_test: public CppUnit::TestFixture {
u1.update(s);
auto r = u1.get_result();
CPPUNIT_ASSERT(!r.is_empty());
- CPPUNIT_ASSERT_DOUBLES_EQUAL(3, r.get_estimate(), RELATIVE_ERROR_FOR_LG_K_11);
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(3, r.get_estimate(), 3 * RELATIVE_ERROR_FOR_LG_K_11);
// incompatible seed
cpc_union u2(11, 234);
@@ -101,7 +104,49 @@ class cpc_union_test: public CppUnit::TestFixture {
}
cpc_sketch r = u.get_result();
CPPUNIT_ASSERT_EQUAL(s.get_num_coupons(), r.get_num_coupons());
- CPPUNIT_ASSERT_DOUBLES_EQUAL(s.get_estimate(), r.get_estimate(), s.get_estimate() * 0.01);
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(s.get_estimate(), r.get_estimate(), s.get_estimate() * RELATIVE_ERROR_FOR_LG_K_11);
+ }
+
+ void reduce_k_empty() {
+ cpc_sketch s(11);
+ for (int i = 0; i < 10000; i++) s.update(i);
+ cpc_union u(12);
+ u.update(s);
+ cpc_sketch r = u.get_result();
+ CPPUNIT_ASSERT_EQUAL(11, (int) r.get_lg_k());
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(10000, r.get_estimate(), 10000 * RELATIVE_ERROR_FOR_LG_K_11);
+ }
+
+ void reduce_k_sparse() {
+ cpc_union u(12);
+
+ cpc_sketch s12(12);
+ for (int i = 0; i < 100; i++) s12.update(i);
+ u.update(s12);
+
+ cpc_sketch s11(11);
+ for (int i = 0; i < 1000; i++) s11.update(i);
+ u.update(s11);
+
+ cpc_sketch r = u.get_result();
+ CPPUNIT_ASSERT_EQUAL(11, (int) r.get_lg_k());
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(1000, r.get_estimate(), 1000 * RELATIVE_ERROR_FOR_LG_K_11);
+ }
+
+ void reduce_k_window() {
+ cpc_union u(12);
+
+ cpc_sketch s12(12);
+ for (int i = 0; i < 500; i++) s12.update(i);
+ u.update(s12);
+
+ cpc_sketch s11(11);
+ for (int i = 0; i < 1000; i++) s11.update(i);
+ u.update(s11);
+
+ cpc_sketch r = u.get_result();
+ CPPUNIT_ASSERT_EQUAL(11, (int) r.get_lg_k());
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(1000, r.get_estimate(), 1000 * RELATIVE_ERROR_FOR_LG_K_11);
}
};
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org