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 2022/10/05 20:00:20 UTC
[datasketches-cpp] branch universal_sorted_view updated: common get_CDF and get_PMF
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch universal_sorted_view
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
The following commit(s) were added to refs/heads/universal_sorted_view by this push:
new c5a58d2 common get_CDF and get_PMF
c5a58d2 is described below
commit c5a58d292b5d5bd4a3a3afbf6e9b863e60762de0
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Wed Oct 5 13:00:14 2022 -0700
common get_CDF and get_PMF
---
common/include/quantile_sketch_sorted_view.hpp | 29 ++++++++++++++++++--
.../include/quantile_sketch_sorted_view_impl.hpp | 21 ++++++++++++++
kll/include/kll_helper.hpp | 32 ----------------------
kll/include/kll_sketch_impl.hpp | 19 +++----------
quantiles/include/quantiles_sketch.hpp | 21 --------------
quantiles/include/quantiles_sketch_impl.hpp | 19 +++----------
req/include/req_sketch.hpp | 21 --------------
req/include/req_sketch_impl.hpp | 17 +++---------
8 files changed, 60 insertions(+), 119 deletions(-)
diff --git a/common/include/quantile_sketch_sorted_view.hpp b/common/include/quantile_sketch_sorted_view.hpp
index f5e805e..996a841 100755
--- a/common/include/quantile_sketch_sorted_view.hpp
+++ b/common/include/quantile_sketch_sorted_view.hpp
@@ -53,7 +53,14 @@ public:
using quantile_return_type = typename std::conditional<std::is_arithmetic<T>::value, T, const T&>::type;
quantile_return_type get_quantile(double rank, bool inclusive = true) const;
+ using vector_double = std::vector<double, typename std::allocator_traits<Allocator>::template rebind_alloc<double>>;
+ vector_double get_CDF(const T* split_points, uint32_t size, bool inclusive = true) const;
+ vector_double get_PMF(const T* split_points, uint32_t size, bool inclusive = true) const;
+
private:
+ uint64_t total_weight_;
+ Container entries_;
+
static inline const T& deref_helper(const T* t) { return *t; }
static inline T deref_helper(T t) { return t; }
@@ -81,8 +88,26 @@ private:
template<typename TT = T, typename std::enable_if<!std::is_arithmetic<TT>::value, int>::type = 0>
static inline Entry make_dummy_entry(uint64_t weight) { return Entry(nullptr, weight); }
- uint64_t total_weight_;
- Container entries_;
+ template<typename TT = T, typename std::enable_if<std::is_floating_point<TT>::value, int>::type = 0>
+ static inline void check_split_points(const T* items, uint32_t size) {
+ for (uint32_t i = 0; i < size ; i++) {
+ if (std::isnan(items[i])) {
+ throw std::invalid_argument("Values must not be NaN");
+ }
+ if ((i < (size - 1)) && !(Comparator()(items[i], items[i + 1]))) {
+ throw std::invalid_argument("Values must be unique and monotonically increasing");
+ }
+ }
+ }
+
+ template<typename TT = T, typename std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
+ static inline void check_split_points(const T* items, uint32_t size) {
+ for (uint32_t i = 0; i < size ; i++) {
+ if ((i < (size - 1)) && !(Comparator()(items[i], items[i + 1]))) {
+ throw std::invalid_argument("Items must be unique and monotonically increasing");
+ }
+ }
+ }
};
template<typename T, typename C, typename A>
diff --git a/common/include/quantile_sketch_sorted_view_impl.hpp b/common/include/quantile_sketch_sorted_view_impl.hpp
index ddb51f3..1c32fc5 100755
--- a/common/include/quantile_sketch_sorted_view_impl.hpp
+++ b/common/include/quantile_sketch_sorted_view_impl.hpp
@@ -80,6 +80,27 @@ auto quantile_sketch_sorted_view<T, C, A>::get_quantile(double rank, bool inclus
return deref_helper(it->first);
}
+template<typename T, typename C, typename A>
+auto quantile_sketch_sorted_view<T, C, A>::get_CDF(const T* split_points, uint32_t size, bool inclusive) const -> vector_double {
+ vector_double buckets(entries_.get_allocator());
+ if (entries_.size() == 0) return buckets;
+ check_split_points(split_points, size);
+ buckets.reserve(size + 1);
+ for (uint32_t i = 0; i < size; ++i) buckets.push_back(get_rank(split_points[i], inclusive));
+ buckets.push_back(1);
+ return buckets;
+}
+
+template<typename T, typename C, typename A>
+auto quantile_sketch_sorted_view<T, C, A>::get_PMF(const T* split_points, uint32_t size, bool inclusive) const -> vector_double {
+ auto buckets = get_CDF(split_points, size, inclusive);
+ if (buckets.size() == 0) return buckets;
+ for (uint32_t i = size; i > 0; --i) {
+ buckets[i] -= buckets[i - 1];
+ }
+ return buckets;
+}
+
template<typename T, typename C, typename A>
auto quantile_sketch_sorted_view<T, C, A>::begin() const -> const_iterator {
return const_iterator(entries_.begin(), entries_.begin());
diff --git a/kll/include/kll_helper.hpp b/kll/include/kll_helper.hpp
index 91c1720..750dd7e 100644
--- a/kll/include/kll_helper.hpp
+++ b/kll/include/kll_helper.hpp
@@ -48,38 +48,6 @@ class kll_helper {
static inline uint16_t int_cap_aux_aux(uint16_t k, uint8_t depth);
static inline uint64_t sum_the_sample_weights(uint8_t num_levels, const uint32_t* levels);
- /*
- * This version is for floating point types
- * Checks the sequential validity of the given array of values.
- * They must be unique, monotonically increasing and not NaN.
- */
- template <typename T, typename C>
- static typename std::enable_if<std::is_floating_point<T>::value, void>::type
- validate_values(const T* values, uint32_t size) {
- for (uint32_t i = 0; i < size ; i++) {
- if (std::isnan(values[i])) {
- throw std::invalid_argument("Values must not be NaN");
- }
- if ((i < (size - 1)) && !(C()(values[i], values[i + 1]))) {
- throw std::invalid_argument("Values must be unique and monotonically increasing");
- }
- }
- }
- /*
- * This version is for non-floating point types
- * Checks the sequential validity of the given array of values.
- * They must be unique and monotonically increasing.
- */
- template <typename T, typename C>
- static typename std::enable_if<!std::is_floating_point<T>::value, void>::type
- validate_values(const T* values, uint32_t size) {
- for (uint32_t i = 0; i < size ; i++) {
- if ((i < (size - 1)) && !(C()(values[i], values[i + 1]))) {
- throw std::invalid_argument("Values must be unique and monotonically increasing");
- }
- }
- }
-
template <typename T>
static void randomly_halve_down(T* buf, uint32_t start, uint32_t length);
diff --git a/kll/include/kll_sketch_impl.hpp b/kll/include/kll_sketch_impl.hpp
index 2488fd7..c83c6bd 100644
--- a/kll/include/kll_sketch_impl.hpp
+++ b/kll/include/kll_sketch_impl.hpp
@@ -335,25 +335,14 @@ double kll_sketch<T, C, A>::get_rank(const T& item, bool inclusive) const {
template<typename T, typename C, typename A>
vector_d<A> kll_sketch<T, C, A>::get_PMF(const T* split_points, uint32_t size, bool inclusive) const {
- auto buckets = get_CDF(split_points, size, inclusive);
- if (buckets.size() > 0) {
- for (uint32_t i = size; i > 0; --i) {
- buckets[i] -= buckets[i - 1];
- }
- }
- return buckets;
+ setup_sorted_view();
+ return sorted_view_->get_PMF(split_points, size, inclusive);
}
template<typename T, typename C, typename A>
vector_d<A> kll_sketch<T, C, A>::get_CDF(const T* split_points, uint32_t size, bool inclusive) const {
- if (is_empty()) return vector_d<A>(allocator_);
- kll_helper::validate_values<T, C>(split_points, size);
- vector_d<A> buckets(size + 1, 0, allocator_);
- for (uint32_t i = 0; i < size; ++i) {
- buckets[i] = get_rank(split_points[i], inclusive);
- }
- buckets[size] = 1;
- return buckets;
+ setup_sorted_view();
+ return sorted_view_->get_CDF(split_points, size, inclusive);
}
template<typename T, typename C, typename A>
diff --git a/quantiles/include/quantiles_sketch.hpp b/quantiles/include/quantiles_sketch.hpp
index 94211ad..5a9b95f 100644
--- a/quantiles/include/quantiles_sketch.hpp
+++ b/quantiles/include/quantiles_sketch.hpp
@@ -568,18 +568,6 @@ private:
return !std::isnan(item);
}
- template<typename TT = T, typename std::enable_if<std::is_floating_point<TT>::value, int>::type = 0>
- static inline void check_split_points(const T* values, uint32_t size) {
- for (uint32_t i = 0; i < size ; i++) {
- if (std::isnan(values[i])) {
- throw std::invalid_argument("Values must not be NaN");
- }
- if ((i < (size - 1)) && !(Comparator()(values[i], values[i + 1]))) {
- throw std::invalid_argument("Values must be unique and monotonically increasing");
- }
- }
- }
-
// implementations for all other types
template<typename TT = T, typename std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
static const TT& get_invalid_value() {
@@ -590,15 +578,6 @@ private:
static inline bool check_update_item(TT) {
return true;
}
-
- template<typename TT = T, typename std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
- static inline void check_split_points(const T* items, uint32_t size) {
- for (uint32_t i = 0; i < size ; i++) {
- if ((i < (size - 1)) && !(Comparator()(items[i], items[i + 1]))) {
- throw std::invalid_argument("Items must be unique and monotonically increasing");
- }
- }
- }
};
diff --git a/quantiles/include/quantiles_sketch_impl.hpp b/quantiles/include/quantiles_sketch_impl.hpp
index 15cc022..f5d80b3 100644
--- a/quantiles/include/quantiles_sketch_impl.hpp
+++ b/quantiles/include/quantiles_sketch_impl.hpp
@@ -804,25 +804,14 @@ double quantiles_sketch<T, C, A>::get_rank(const T& item, bool inclusive) const
template<typename T, typename C, typename A>
auto quantiles_sketch<T, C, A>::get_PMF(const T* split_points, uint32_t size, bool inclusive) const -> vector_double {
- auto buckets = get_CDF(split_points, size, inclusive);
- if (is_empty()) return buckets;
- for (uint32_t i = size; i > 0; --i) {
- buckets[i] -= buckets[i - 1];
- }
- return buckets;
+ setup_sorted_view();
+ return sorted_view_->get_PMF(split_points, size, inclusive);
}
template<typename T, typename C, typename A>
auto quantiles_sketch<T, C, A>::get_CDF(const T* split_points, uint32_t size, bool inclusive) const -> vector_double {
- vector_double buckets(allocator_);
- if (is_empty()) return buckets;
- check_split_points(split_points, size);
- buckets.reserve(size + 1);
- for (uint32_t i = 0; i < size; ++i) {
- buckets.push_back(get_rank(split_points[i], inclusive));
- }
- buckets.push_back(1);
- return buckets;
+ setup_sorted_view();
+ return sorted_view_->get_CDF(split_points, size, inclusive);
}
template<typename T, typename C, typename A>
diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp
index a900772..0b9a255 100755
--- a/req/include/req_sketch.hpp
+++ b/req/include/req_sketch.hpp
@@ -372,18 +372,6 @@ private:
return !std::isnan(value);
}
- template<typename TT = T, typename std::enable_if<std::is_floating_point<TT>::value, int>::type = 0>
- static inline void check_split_points(const T* items, uint32_t size) {
- for (uint32_t i = 0; i < size ; i++) {
- if (std::isnan(items[i])) {
- throw std::invalid_argument("Values must not be NaN");
- }
- if ((i < (size - 1)) && !(Comparator()(items[i], items[i + 1]))) {
- throw std::invalid_argument("Values must be unique and monotonically increasing");
- }
- }
- }
-
// implementations for all other types
template<typename TT = T, typename std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
static const TT& get_invalid_value() {
@@ -395,15 +383,6 @@ private:
return true;
}
- template<typename TT = T, typename std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
- static inline void check_split_points(const T* items, uint32_t size) {
- for (uint32_t i = 0; i < size ; i++) {
- if ((i < (size - 1)) && !(Comparator()(items[i], items[i + 1]))) {
- throw std::invalid_argument("Items must be unique and monotonically increasing");
- }
- }
- }
-
// for type converting constructor
template<typename TT, typename CC, typename AA> friend class req_sketch;
};
diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp
index cd1309b..d404fd7 100755
--- a/req/include/req_sketch_impl.hpp
+++ b/req/include/req_sketch_impl.hpp
@@ -248,23 +248,14 @@ double req_sketch<T, C, A>::get_rank(const T& item, bool inclusive) const {
template<typename T, typename C, typename A>
auto req_sketch<T, C, A>::get_PMF(const T* split_points, uint32_t size, bool inclusive) const -> vector_double {
- auto buckets = get_CDF(split_points, size, inclusive);
- if (is_empty()) return buckets;
- for (uint32_t i = size; i > 0; --i) {
- buckets[i] -= buckets[i - 1];
- }
- return buckets;
+ setup_sorted_view();
+ return sorted_view_->get_PMF(split_points, size, inclusive);
}
template<typename T, typename C, typename A>
auto req_sketch<T, C, A>::get_CDF(const T* split_points, uint32_t size, bool inclusive) const -> vector_double {
- vector_double buckets(allocator_);
- if (is_empty()) return buckets;
- check_split_points(split_points, size);
- buckets.reserve(size + 1);
- for (uint32_t i = 0; i < size; ++i) buckets.push_back(get_rank(split_points[i], inclusive));
- buckets.push_back(1);
- return buckets;
+ setup_sorted_view();
+ return sorted_view_->get_CDF(split_points, size, inclusive);
}
template<typename T, typename C, typename A>
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org