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 2020/04/16 00:04:08 UTC
[incubator-datasketches-cpp] branch api_and_docs updated (87878a1
-> 91dcc88)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch api_and_docs
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git.
from 87878a1 doc
new f7b9f44 doc
new 91dcc88 indentation fix
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_sketch.hpp | 354 ++++++++++++++++++++++++++++-------------
cpc/include/cpc_union.hpp | 89 +++++++----
theta/include/theta_sketch.hpp | 22 ++-
3 files changed, 311 insertions(+), 154 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: doc
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch api_and_docs
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit f7b9f440149706315ac147ce278e899bf57b9e3d
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Wed Apr 15 17:03:32 2020 -0700
doc
---
cpc/include/cpc_union.hpp | 89 +++++++++++++++++++++++++-----------------
theta/include/theta_sketch.hpp | 22 +++++++----
2 files changed, 68 insertions(+), 43 deletions(-)
diff --git a/cpc/include/cpc_union.hpp b/cpc/include/cpc_union.hpp
index bc06975..63e1856 100644
--- a/cpc/include/cpc_union.hpp
+++ b/cpc/include/cpc_union.hpp
@@ -38,41 +38,60 @@ typedef cpc_union_alloc<std::allocator<void>> cpc_union;
template<typename A>
class cpc_union_alloc {
- public:
-
- explicit cpc_union_alloc(uint8_t lg_k = CPC_DEFAULT_LG_K, uint64_t seed = DEFAULT_SEED);
- cpc_union_alloc(const cpc_union_alloc<A>& other);
- cpc_union_alloc(cpc_union_alloc<A>&& other) noexcept;
- ~cpc_union_alloc();
-
- cpc_union_alloc<A>& operator=(const cpc_union_alloc<A>& other);
- cpc_union_alloc<A>& operator=(cpc_union_alloc<A>&& other) noexcept;
-
- void update(const cpc_sketch_alloc<A>& sketch);
- void update(cpc_sketch_alloc<A>&& sketch);
- cpc_sketch_alloc<A> get_result() const;
-
- private:
- 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;
-
- uint8_t lg_k;
- uint64_t seed;
- cpc_sketch_alloc<A>* accumulator;
- vector_u64<A> bit_matrix;
-
- template<typename S> void internal_update(S&& sketch); // to support both rvalue and lvalue
-
- cpc_sketch_alloc<A> get_result_from_accumulator() const;
- cpc_sketch_alloc<A> get_result_from_bit_matrix() const;
-
- 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 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);
+public:
+ /**
+ * Creates an instance of the union given the lg_k parameter and hash seed.
+ * @param lg_k base 2 logarithm of the number of bins in the sketch
+ * @param seed for hash function
+ */
+ explicit cpc_union_alloc(uint8_t lg_k = CPC_DEFAULT_LG_K, uint64_t seed = DEFAULT_SEED);
+
+ cpc_union_alloc(const cpc_union_alloc<A>& other);
+ cpc_union_alloc(cpc_union_alloc<A>&& other) noexcept;
+ ~cpc_union_alloc();
+
+ cpc_union_alloc<A>& operator=(const cpc_union_alloc<A>& other);
+ cpc_union_alloc<A>& operator=(cpc_union_alloc<A>&& other) noexcept;
+
+ /**
+ * This method is to update the union with a given sketch (lvalue)
+ * @param sketch to update the union with
+ */
+ void update(const cpc_sketch_alloc<A>& sketch);
+
+ /**
+ * This method is to update the union with a given sketch (rvalue)
+ * @param sketch to update the union with
+ */
+ void update(cpc_sketch_alloc<A>&& sketch);
+
+ /**
+ * This method produces a copy of the current state of the union as a sketch.
+ * @return the result of the union
+ */
+ cpc_sketch_alloc<A> get_result() const;
+
+private:
+ 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;
+
+ uint8_t lg_k;
+ uint64_t seed;
+ cpc_sketch_alloc<A>* accumulator;
+ vector_u64<A> bit_matrix;
+
+ template<typename S> void internal_update(S&& sketch); // to support both rvalue and lvalue
+
+ cpc_sketch_alloc<A> get_result_from_accumulator() const;
+ cpc_sketch_alloc<A> get_result_from_bit_matrix() const;
+
+ 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 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);
};
} /* namespace datasketches */
diff --git a/theta/include/theta_sketch.hpp b/theta/include/theta_sketch.hpp
index a623006..04ec9c0 100644
--- a/theta/include/theta_sketch.hpp
+++ b/theta/include/theta_sketch.hpp
@@ -54,7 +54,7 @@ public:
virtual ~theta_sketch_alloc();
/**
- * @return true if this sketch is empty
+ * @return true if this sketch represents an empty set (not the same as no retained entries!)
*/
bool is_empty() const;
@@ -64,16 +64,20 @@ public:
double get_estimate() const;
/**
- * Returns the approximate lower error bound given a number of Standard Deviations.
+ * Returns the approximate lower error bound given a number of standard deviations.
+ * This parameter is similar to the number of standard deviations of the normal distribution
+ * and corresponds to approximately 67%, 95% and 99% confidence intervals.
* @param num_std_devs number of Standard Deviations (1, 2 or 3)
* @return the lower bound
*/
double get_lower_bound(uint8_t num_std_devs) const;
/**
- * Returns the approximate upper error bound given a number of Standard Deviations.
+ * Returns the approximate upper error bound given a number of standard deviations.
+ * This parameter is similar to the number of standard deviations of the normal distribution
+ * and corresponds to approximately 67%, 95% and 99% confidence intervals.
* @param num_std_devs number of Standard Deviations (1, 2 or 3)
- * @return the lower bound
+ * @return the upper bound
*/
double get_upper_bound(uint8_t num_std_devs) const;
@@ -88,7 +92,7 @@ public:
double get_theta() const;
/**
- * @return theta as a positive integer bewteen 0 and LLONG_MAX
+ * @return theta as a positive integer between 0 and LLONG_MAX
*/
uint64_t get_theta64() const;
@@ -105,7 +109,7 @@ public:
virtual bool is_ordered() const = 0;
/**
- * Writes a human readable summary of this sketch to a given stream
+ * Writes a human-readable summary of this sketch to a given stream
* @param os output stream
* @param print_items if true include the list of items retained by the sketch
*/
@@ -294,9 +298,11 @@ public:
/**
* Update this sketch with given data of any type.
+ * This is a "universal" update that covers all cases above,
+ * but may produce different hashes.
* Be very careful to hash input values consistently using the same approach
- * either over time or on different platforms
- * or while passing sketches from Java environment or to Java environment.
+ * both over time and on different platforms
+ * and while passing sketches between C++ environment and Java environment.
* Otherwise two sketches that should represent overlapping sets will be disjoint
* For instance, for signed 32-bit values call update(int32_t) method above,
* which does widening conversion to int64_t, if compatibility with Java is expected
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 02/02: indentation fix
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch api_and_docs
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit 91dcc887c23359aa3c172bbd4ca3ba768b3f828d
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Wed Apr 15 17:03:56 2020 -0700
indentation fix
---
cpc/include/cpc_sketch.hpp | 354 +++++++++++++++++++++++++++++++--------------
1 file changed, 243 insertions(+), 111 deletions(-)
diff --git a/cpc/include/cpc_sketch.hpp b/cpc/include/cpc_sketch.hpp
index f6df2c2..852aa4a 100644
--- a/cpc/include/cpc_sketch.hpp
+++ b/cpc/include/cpc_sketch.hpp
@@ -60,117 +60,249 @@ template<typename A> void cpc_init();
template<typename A>
class cpc_sketch_alloc {
- public:
-
- explicit cpc_sketch_alloc(uint8_t lg_k = CPC_DEFAULT_LG_K, uint64_t seed = DEFAULT_SEED);
- uint8_t get_lg_k() const;
- bool is_empty() const;
- double get_estimate() const;
- double get_lower_bound(unsigned kappa) const;
- double get_upper_bound(unsigned kappa) const;
-
- void update(const std::string& value);
- void update(uint64_t value);
- void update(int64_t value);
-
- // for compatibility with Java implementation
- void update(uint32_t value);
- void update(int32_t value);
- void update(uint16_t value);
- void update(int16_t value);
- void update(uint8_t value);
- void update(int8_t value);
- void update(double value);
- void update(float value);
-
- // This is a "universal" update that covers all cases above, but may produce different hashes
- // Be very careful to hash input values consistently using the same approach over time,
- // on different platforms and while passing sketches from or to Java environment
- // Otherwise two sketches that should represent overlapping sets will be disjoint
- // For instance, for signed 32-bit values call update(int32_t) method above,
- // which does widening conversion to int64_t, if compatibility with Java is expected
- void update(const void* value, int size);
-
- // prints a sketch summary to a given stream
- void to_stream(std::ostream& os) const;
-
- void serialize(std::ostream& os) const;
- typedef vector_u8<A> vector_bytes; // alias for users
- vector_bytes serialize(unsigned header_size_bytes = 0) const;
-
- static cpc_sketch_alloc<A> deserialize(std::istream& is, uint64_t seed = DEFAULT_SEED);
- static cpc_sketch_alloc<A> deserialize(const void* bytes, size_t size, uint64_t seed = DEFAULT_SEED);
-
- // for internal use
- uint32_t get_num_coupons() const;
-
- // for debugging
- // this should catch some forms of corruption during serialization-deserialization
- bool validate() const;
-
- private:
- static const uint8_t SERIAL_VERSION = 1;
- static const uint8_t FAMILY = 16;
-
- enum flags { IS_BIG_ENDIAN, IS_COMPRESSED, HAS_HIP, HAS_TABLE, HAS_WINDOW };
-
- // Note: except for brief transitional moments, these sketches always obey
- // the following strict mapping between the flavor of a sketch and the
- // number of coupons that it has collected
- enum flavor {
- EMPTY, // 0 == C < 1
- SPARSE, // 1 <= C < 3K/32
- HYBRID, // 3K/32 <= C < K/2
- PINNED, // K/2 <= C < 27K/8 [NB: 27/8 = 3 + 3/8]
- SLIDING // 27K/8 <= C
- };
-
- uint8_t lg_k;
- uint64_t seed;
- bool was_merged; // is the sketch the result of merging?
- uint32_t num_coupons; // the number of coupons collected so far
-
- u32_table<A> surprising_value_table;
- vector_u8<A> sliding_window;
- uint8_t window_offset; // derivable from num_coupons, but made explicit for speed
- uint8_t first_interesting_column; // This is part of a speed optimization
-
- double kxp;
- double hip_est_accum;
-
- // for deserialization and cpc_union::get_result()
- cpc_sketch_alloc(uint8_t lg_k, uint32_t num_coupons, uint8_t first_interesting_column, u32_table<A>&& table,
- vector_u8<A>&& window, bool has_hip, double kxp, double hip_est_accum, uint64_t seed);
-
- inline void row_col_update(uint32_t row_col);
- inline void update_sparse(uint32_t row_col);
- inline void update_windowed(uint32_t row_col);
- inline void update_hip(uint32_t row_col);
- void promote_sparse_to_windowed();
- void move_window();
- void refresh_kxp(const uint64_t* bit_matrix);
-
- friend double get_hip_confidence_lb<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
- friend double get_hip_confidence_ub<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
- friend double get_icon_confidence_lb<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
- friend double get_icon_confidence_ub<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
- double get_hip_estimate() const;
- double get_icon_estimate() const;
-
- inline flavor determine_flavor() const;
- static inline flavor determine_flavor(uint8_t lg_k, uint64_t c);
-
- static inline uint8_t determine_correct_offset(uint8_t lg_k, uint64_t c);
-
- // this produces a full-size k-by-64 bit matrix
- 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;
- inline size_t copy_hip_to_mem(void* dst) const;
-
- friend cpc_compressor<A>;
- friend cpc_union_alloc<A>;
+public:
+ /**
+ * Creates an instance of the sketch given the lg_k parameter and hash seed.
+ * @param lg_k base 2 logarithm of the number of bins in the sketch
+ * @param seed for hash function
+ */
+ explicit cpc_sketch_alloc(uint8_t lg_k = CPC_DEFAULT_LG_K, uint64_t seed = DEFAULT_SEED);
+
+ /**
+ * @return configured lg_k of this sketch
+ */
+ uint8_t get_lg_k() const;
+
+ /**
+ * @return true if this sketch represents an empty set
+ */
+ bool is_empty() const;
+
+ /**
+ * @return estimate of the distinct count of the input stream
+ */
+ double get_estimate() const;
+
+ /**
+ * Returns the approximate lower error bound given a parameter kappa (1, 2 or 3).
+ * This parameter is similar to the number of standard deviations of the normal distribution
+ * and corresponds to approximately 67%, 95% and 99% confidence intervals.
+ * @param kappa parameter to specify confidence interval (1, 2 or 3)
+ * @return the lower bound
+ */
+ double get_lower_bound(unsigned kappa) const;
+
+ /**
+ * Returns the approximate upper error bound given a parameter kappa (1, 2 or 3).
+ * This parameter is similar to the number of standard deviations of the normal distribution
+ * and corresponds to approximately 67%, 95% and 99% confidence intervals.
+ * @param kappa parameter to specify confidence interval (1, 2 or 3)
+ * @return the upper bound
+ */
+ double get_upper_bound(unsigned kappa) const;
+
+ /**
+ * Update this sketch with a given string.
+ * @param value string to update the sketch with
+ */
+ void update(const std::string& value);
+
+ /**
+ * Update this sketch with a given unsigned 64-bit integer.
+ * @param value uint64_t to update the sketch with
+ */
+ void update(uint64_t value);
+
+ /**
+ * Update this sketch with a given signed 64-bit integer.
+ * @param value int64_t to update the sketch with
+ */
+ void update(int64_t value);
+
+ /**
+ * Update this sketch with a given unsigned 32-bit integer.
+ * For compatibility with Java implementation.
+ * @param value uint32_t to update the sketch with
+ */
+ void update(uint32_t value);
+
+ /**
+ * Update this sketch with a given signed 32-bit integer.
+ * For compatibility with Java implementation.
+ * @param value int32_t to update the sketch with
+ */
+ void update(int32_t value);
+
+ /**
+ * Update this sketch with a given unsigned 16-bit integer.
+ * For compatibility with Java implementation.
+ * @param value uint16_t to update the sketch with
+ */
+ void update(uint16_t value);
+
+ /**
+ * Update this sketch with a given signed 16-bit integer.
+ * For compatibility with Java implementation.
+ * @param value int16_t to update the sketch with
+ */
+ void update(int16_t value);
+
+ /**
+ * Update this sketch with a given unsigned 8-bit integer.
+ * For compatibility with Java implementation.
+ * @param value uint8_t to update the sketch with
+ */
+ void update(uint8_t value);
+
+ /**
+ * Update this sketch with a given signed 8-bit integer.
+ * For compatibility with Java implementation.
+ * @param value int8_t to update the sketch with
+ */
+ void update(int8_t value);
+
+ /**
+ * Update this sketch with a given double-precision floating point value.
+ * For compatibility with Java implementation.
+ * @param value double to update the sketch with
+ */
+ void update(double value);
+
+ /**
+ * Update this sketch with a given floating point value.
+ * For compatibility with Java implementation.
+ * @param value float to update the sketch with
+ */
+ void update(float value);
+
+ /**
+ * Update this sketch with given data of any type.
+ * This is a "universal" update that covers all cases above,
+ * but may produce different hashes.
+ * Be very careful to hash input values consistently using the same approach
+ * both over time and on different platforms
+ * and while passing sketches between C++ environment and Java environment.
+ * Otherwise two sketches that should represent overlapping sets will be disjoint
+ * For instance, for signed 32-bit values call update(int32_t) method above,
+ * which does widening conversion to int64_t, if compatibility with Java is expected
+ * @param data pointer to the data
+ * @param length of the data in bytes
+ */
+ void update(const void* value, int size);
+
+ /**
+ * Writes a human-readable summary of this sketch to a given stream
+ * @param os output stream
+ * @param print_items if true include the list of items retained by the sketch
+ */
+ void to_stream(std::ostream& os) const;
+
+ /**
+ * This method serializes the sketch into a given stream in a binary form
+ * @param os output stream
+ */
+ void serialize(std::ostream& os) const;
+
+ // This is a convenience alias for users
+ // The type returned by the following serialize method
+ typedef vector_u8<A> vector_bytes;
+
+ /**
+ * This method serializes the sketch as a vector of bytes.
+ * An optional header can be reserved in front of the sketch.
+ * It is an uninitialized space of a given size.
+ * This header is used in Datasketches PostgreSQL extension.
+ * @param header_size_bytes space to reserve in front of the sketch
+ */
+ vector_bytes serialize(unsigned header_size_bytes = 0) const;
+
+ /**
+ * This method deserializes a sketch from a given stream.
+ * @param is input stream
+ * @param seed the seed for the hash function that was used to create the sketch
+ * @return an instance of a sketch
+ */
+ static cpc_sketch_alloc<A> deserialize(std::istream& is, uint64_t seed = DEFAULT_SEED);
+
+ /**
+ * This method deserializes a sketch from a given array of bytes.
+ * @param bytes pointer to the array of bytes
+ * @param size the size of the array
+ * @param seed the seed for the hash function that was used to create the sketch
+ * @return an instance of the sketch
+ */
+ static cpc_sketch_alloc<A> deserialize(const void* bytes, size_t size, uint64_t seed = DEFAULT_SEED);
+
+ // for internal use
+ uint32_t get_num_coupons() const;
+
+ // for debugging
+ // this should catch some forms of corruption during serialization-deserialization
+ bool validate() const;
+
+private:
+ static const uint8_t SERIAL_VERSION = 1;
+ static const uint8_t FAMILY = 16;
+
+ enum flags { IS_BIG_ENDIAN, IS_COMPRESSED, HAS_HIP, HAS_TABLE, HAS_WINDOW };
+
+ // Note: except for brief transitional moments, these sketches always obey
+ // the following strict mapping between the flavor of a sketch and the
+ // number of coupons that it has collected
+ enum flavor {
+ EMPTY, // 0 == C < 1
+ SPARSE, // 1 <= C < 3K/32
+ HYBRID, // 3K/32 <= C < K/2
+ PINNED, // K/2 <= C < 27K/8 [NB: 27/8 = 3 + 3/8]
+ SLIDING // 27K/8 <= C
+ };
+
+ uint8_t lg_k;
+ uint64_t seed;
+ bool was_merged; // is the sketch the result of merging?
+ uint32_t num_coupons; // the number of coupons collected so far
+
+ u32_table<A> surprising_value_table;
+ vector_u8<A> sliding_window;
+ uint8_t window_offset; // derivable from num_coupons, but made explicit for speed
+ uint8_t first_interesting_column; // This is part of a speed optimization
+
+ double kxp;
+ double hip_est_accum;
+
+ // for deserialization and cpc_union::get_result()
+ cpc_sketch_alloc(uint8_t lg_k, uint32_t num_coupons, uint8_t first_interesting_column, u32_table<A>&& table,
+ vector_u8<A>&& window, bool has_hip, double kxp, double hip_est_accum, uint64_t seed);
+
+ inline void row_col_update(uint32_t row_col);
+ inline void update_sparse(uint32_t row_col);
+ inline void update_windowed(uint32_t row_col);
+ inline void update_hip(uint32_t row_col);
+ void promote_sparse_to_windowed();
+ void move_window();
+ void refresh_kxp(const uint64_t* bit_matrix);
+
+ friend double get_hip_confidence_lb<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
+ friend double get_hip_confidence_ub<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
+ friend double get_icon_confidence_lb<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
+ friend double get_icon_confidence_ub<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
+ double get_hip_estimate() const;
+ double get_icon_estimate() const;
+
+ inline flavor determine_flavor() const;
+ static inline flavor determine_flavor(uint8_t lg_k, uint64_t c);
+
+ static inline uint8_t determine_correct_offset(uint8_t lg_k, uint64_t c);
+
+ // this produces a full-size k-by-64 bit matrix
+ 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;
+ inline size_t copy_hip_to_mem(void* dst) const;
+
+ friend cpc_compressor<A>;
+ friend cpc_union_alloc<A>;
};
} /* namespace datasketches */
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org