You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by jm...@apache.org on 2022/01/20 09:05:46 UTC
[datasketches-cpp] branch quantiles updated: use common quantiles calculator between req and classic quantiles
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch quantiles
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
The following commit(s) were added to refs/heads/quantiles by this push:
new 59f40ad use common quantiles calculator between req and classic quantiles
59f40ad is described below
commit 59f40ad2cd7166b7ad8f2e0c87ff2b197e472ab6
Author: Jon Malkin <jm...@users.noreply.github.com>
AuthorDate: Thu Jan 20 01:05:33 2022 -0800
use common quantiles calculator between req and classic quantiles
---
common/CMakeLists.txt | 2 ++
.../include/quantile_calculator.hpp | 10 +++++-----
.../include/quantile_calculator_impl.hpp | 12 ++++++------
quantiles/CMakeLists.txt | 6 ------
quantiles/include/quantiles_sketch.hpp | 4 ++--
quantiles/include/quantiles_sketch_impl.hpp | 20 ++++++++++----------
req/CMakeLists.txt | 2 --
req/include/req_sketch.hpp | 4 ++--
req/include/req_sketch_impl.hpp | 18 +++++++++---------
9 files changed, 36 insertions(+), 42 deletions(-)
diff --git a/common/CMakeLists.txt b/common/CMakeLists.txt
index 73d8b36..48f3fa4 100644
--- a/common/CMakeLists.txt
+++ b/common/CMakeLists.txt
@@ -43,4 +43,6 @@ install(FILES
include/conditional_forward.hpp
include/ceiling_power_of_2.hpp
include/bounds_binomial_proportions.hpp
+ include/quantiles_calculator.hpp
+ include/quantiles_calculator_impl.hpp
DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/req/include/req_quantile_calculator.hpp b/common/include/quantile_calculator.hpp
similarity index 88%
rename from req/include/req_quantile_calculator.hpp
rename to common/include/quantile_calculator.hpp
index 2a6e245..0d93dc1 100755
--- a/req/include/req_quantile_calculator.hpp
+++ b/common/include/quantile_calculator.hpp
@@ -17,8 +17,8 @@
* under the License.
*/
-#ifndef REQ_QUANTILE_CALCULATOR_HPP_
-#define REQ_QUANTILE_CALCULATOR_HPP_
+#ifndef QUANTILE_CALCULATOR_HPP_
+#define QUANTILE_CALCULATOR_HPP_
#include <functional>
@@ -29,9 +29,9 @@ template<
typename Comparator,
typename Allocator
>
-class req_quantile_calculator {
+class quantile_calculator {
public:
- req_quantile_calculator(uint64_t n, const Allocator& allocator);
+ quantile_calculator(uint64_t n, const Allocator& allocator);
void add(const T* begin, const T* end, uint8_t lg_weight);
@@ -64,6 +64,6 @@ private:
} /* namespace datasketches */
-#include "req_quantile_calculator_impl.hpp"
+#include "quantile_calculator_impl.hpp"
#endif
diff --git a/req/include/req_quantile_calculator_impl.hpp b/common/include/quantile_calculator_impl.hpp
similarity index 82%
rename from req/include/req_quantile_calculator_impl.hpp
rename to common/include/quantile_calculator_impl.hpp
index 63f0e92..a422aec 100755
--- a/req/include/req_quantile_calculator_impl.hpp
+++ b/common/include/quantile_calculator_impl.hpp
@@ -17,19 +17,19 @@
* under the License.
*/
-#ifndef REQ_QUANTILE_CALCULATOR_IMPL_HPP_
-#define REQ_QUANTILE_CALCULATOR_IMPL_HPP_
+#ifndef QUANTILE_CALCULATOR_IMPL_HPP_
+#define QUANTILE_CALCULATOR_IMPL_HPP_
namespace datasketches {
template<typename T, typename C, typename A>
-req_quantile_calculator<T, C, A>::req_quantile_calculator(uint64_t n, const A& allocator):
+quantile_calculator<T, C, A>::quantile_calculator(uint64_t n, const A& allocator):
n_(n),
entries_(allocator)
{}
template<typename T, typename C, typename A>
-void req_quantile_calculator<T, C, A>::add(const T* begin, const T* end, uint8_t lg_weight) {
+void quantile_calculator<T, C, A>::add(const T* begin, const T* end, uint8_t lg_weight) {
if (entries_.capacity() < entries_.size() + std::distance(begin, end)) entries_.reserve(entries_.size() + std::distance(begin, end));
const size_t size_before = entries_.size();
for (auto it = begin; it != end; ++it) entries_.push_back(Entry(it, 1 << lg_weight));
@@ -38,7 +38,7 @@ void req_quantile_calculator<T, C, A>::add(const T* begin, const T* end, uint8_t
template<typename T, typename C, typename A>
template<bool inclusive>
-void req_quantile_calculator<T, C, A>::convert_to_cummulative() {
+void quantile_calculator<T, C, A>::convert_to_cummulative() {
uint64_t subtotal = 0;
for (auto& entry: entries_) {
const uint64_t new_subtotal = subtotal + entry.second;
@@ -48,7 +48,7 @@ void req_quantile_calculator<T, C, A>::convert_to_cummulative() {
}
template<typename T, typename C, typename A>
-const T* req_quantile_calculator<T, C, A>::get_quantile(double rank) const {
+const T* quantile_calculator<T, C, A>::get_quantile(double rank) const {
uint64_t weight = static_cast<uint64_t>(rank * n_);
auto it = std::lower_bound(entries_.begin(), entries_.end(), Entry(nullptr, weight), compare_pairs_by_second());
if (it == entries_.end()) return entries_[entries_.size() - 1].first;
diff --git a/quantiles/CMakeLists.txt b/quantiles/CMakeLists.txt
index ca9b583..9b07677 100755
--- a/quantiles/CMakeLists.txt
+++ b/quantiles/CMakeLists.txt
@@ -39,10 +39,4 @@ install(TARGETS quantiles
install(FILES
include/quantiles_sketch.hpp
include/quantiles_sketch_impl.hpp
- #include/quantiles_level.hpp
- #include/quantiles_level_impl.hpp
- include/quantiles_helper.hpp
- include/quantiles_helper_impl.hpp
- include/quantiles_quantile_calculator.hpp
- include/quantiles_quantile_calculator_impl.hpp
DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/quantiles/include/quantiles_sketch.hpp b/quantiles/include/quantiles_sketch.hpp
index 3587a94..8d3c8a2 100644
--- a/quantiles/include/quantiles_sketch.hpp
+++ b/quantiles/include/quantiles_sketch.hpp
@@ -24,7 +24,7 @@
#include <memory>
#include <vector>
-#include "../../req/include/req_quantile_calculator.hpp"
+#include "quantile_calculator.hpp"
#include "common_defs.hpp"
#include "serde.hpp"
@@ -463,7 +463,7 @@ private:
T* min_value_;
T* max_value_;
- using QuantileCalculator = req_quantile_calculator<T, Comparator, Allocator>;
+ using QuantileCalculator = quantile_calculator<T, Comparator, Allocator>;
using AllocCalc = typename std::allocator_traits<Allocator>::template rebind_alloc<QuantileCalculator>;
class calculator_deleter;
using QuantileCalculatorPtr = typename std::unique_ptr<QuantileCalculator, calculator_deleter>;
diff --git a/quantiles/include/quantiles_sketch_impl.hpp b/quantiles/include/quantiles_sketch_impl.hpp
index 5d06348..bf09014 100644
--- a/quantiles/include/quantiles_sketch_impl.hpp
+++ b/quantiles/include/quantiles_sketch_impl.hpp
@@ -281,20 +281,20 @@ auto quantiles_sketch<T, C, S, A>::get_quantile_calculator() const -> QuantileCa
std::sort(const_cast<Level&>(base_buffer_).begin(), const_cast<Level&>(base_buffer_).end(), C());
AllocCalc ac(allocator_);
- QuantileCalculatorPtr quantile_calculator(
- new (ac.allocate(1)) req_quantile_calculator<T, C, A>(n_, ac),
+ QuantileCalculatorPtr quantile_calculator_ptr(
+ new (ac.allocate(1)) quantile_calculator<T, C, A>(n_, ac),
calculator_deleter(ac)
);
uint64_t lg_weight = 0;
- quantile_calculator->add(base_buffer_.data(), base_buffer_.data() + base_buffer_.size(), lg_weight);
+ quantile_calculator_ptr->add(base_buffer_.data(), base_buffer_.data() + base_buffer_.size(), lg_weight);
for (auto& level : levels_) {
++lg_weight;
if (level.empty()) { continue; }
- quantile_calculator->add(level.data(), level.data() + k_, lg_weight);
+ quantile_calculator_ptr->add(level.data(), level.data() + k_, lg_weight);
}
- quantile_calculator->template convert_to_cummulative<inclusive>();
- return quantile_calculator;
+ quantile_calculator_ptr->template convert_to_cummulative<inclusive>();
+ return quantile_calculator_ptr;
}
template<typename T, typename C, typename S, typename A>
@@ -314,7 +314,7 @@ template<bool inclusive>
std::vector<T, A> quantiles_sketch<T, C, S, A>::get_quantiles(const double* ranks, uint32_t size) const {
std::vector<T, A> quantiles(allocator_);
if (is_empty()) return quantiles;
- QuantileCalculatorPtr quantile_calculator(nullptr, calculator_deleter(allocator_));
+ QuantileCalculatorPtr quantile_calculator_ptr(nullptr, calculator_deleter(allocator_));
quantiles.reserve(size);
for (uint32_t i = 0; i < size; ++i) {
const double rank = ranks[i];
@@ -324,11 +324,11 @@ std::vector<T, A> quantiles_sketch<T, C, S, A>::get_quantiles(const double* rank
if (rank == 0.0) quantiles.push_back(*min_value_);
else if (rank == 1.0) quantiles.push_back(*max_value_);
else {
- if (!quantile_calculator) {
+ if (!quantile_calculator_ptr) {
// has side effect of sorting level zero if needed
- quantile_calculator = const_cast<quantiles_sketch*>(this)->get_quantile_calculator<inclusive>();
+ quantile_calculator_ptr = const_cast<quantiles_sketch*>(this)->get_quantile_calculator<inclusive>();
}
- quantiles.push_back(*(quantile_calculator->get_quantile(rank)));
+ quantiles.push_back(*(quantile_calculator_ptr->get_quantile(rank)));
}
}
return quantiles;
diff --git a/req/CMakeLists.txt b/req/CMakeLists.txt
index d630afe..9ffc468 100755
--- a/req/CMakeLists.txt
+++ b/req/CMakeLists.txt
@@ -42,6 +42,4 @@ install(FILES
include/req_sketch_impl.hpp
include/req_compactor.hpp
include/req_compactor_impl.hpp
- include/req_quantile_calculator.hpp
- include/req_quantile_calculator_impl.hpp
DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp
index 779caba..0496c5b 100755
--- a/req/include/req_sketch.hpp
+++ b/req/include/req_sketch.hpp
@@ -22,7 +22,7 @@
#include "req_common.hpp"
#include "req_compactor.hpp"
-#include "req_quantile_calculator.hpp"
+#include "quantile_calculator.hpp"
namespace datasketches {
@@ -310,7 +310,7 @@ private:
static double get_rank_ub(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n, bool hra);
static bool is_exact_rank(uint16_t k, uint8_t num_levels, double rank, uint64_t n, bool hra);
- using QuantileCalculator = req_quantile_calculator<T, Comparator, Allocator>;
+ using QuantileCalculator = quantile_calculator<T, Comparator, Allocator>;
using AllocCalc = typename std::allocator_traits<Allocator>::template rebind_alloc<QuantileCalculator>;
class calculator_deleter;
using QuantileCalculatorPtr = typename std::unique_ptr<QuantileCalculator, calculator_deleter>;
diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp
index 7648546..4dc9d17 100755
--- a/req/include/req_sketch_impl.hpp
+++ b/req/include/req_sketch_impl.hpp
@@ -245,7 +245,7 @@ template<bool inclusive>
std::vector<T, A> req_sketch<T, C, S, A>::get_quantiles(const double* ranks, uint32_t size) const {
std::vector<T, A> quantiles(allocator_);
if (is_empty()) return quantiles;
- QuantileCalculatorPtr quantile_calculator(nullptr, calculator_deleter(allocator_));
+ QuantileCalculatorPtr quantile_calculator_ptr(nullptr, calculator_deleter(allocator_));
quantiles.reserve(size);
for (uint32_t i = 0; i < size; ++i) {
const double rank = ranks[i];
@@ -255,11 +255,11 @@ std::vector<T, A> req_sketch<T, C, S, A>::get_quantiles(const double* ranks, uin
if (rank == 0.0) quantiles.push_back(*min_value_);
else if (rank == 1.0) quantiles.push_back(*max_value_);
else {
- if (!quantile_calculator) {
+ if (!quantile_calculator_ptr) {
// has side effect of sorting level zero if needed
- quantile_calculator = const_cast<req_sketch*>(this)->get_quantile_calculator<inclusive>();
+ quantile_calculator_ptr = const_cast<req_sketch*>(this)->get_quantile_calculator<inclusive>();
}
- quantiles.push_back(*(quantile_calculator->get_quantile(rank)));
+ quantiles.push_back(*(quantile_calculator_ptr->get_quantile(rank)));
}
}
return quantiles;
@@ -286,16 +286,16 @@ auto req_sketch<T, C, S, A>::get_quantile_calculator() const -> QuantileCalculat
const_cast<Compactor&>(compactors_[0]).sort(); // allow this side effect
}
AllocCalc ac(allocator_);
- QuantileCalculatorPtr quantile_calculator(
- new (ac.allocate(1)) req_quantile_calculator<T, C, A>(n_, ac),
+ QuantileCalculatorPtr quantile_calculator_ptr(
+ new (ac.allocate(1)) quantile_calculator<T, C, A>(n_, ac),
calculator_deleter(ac)
);
for (auto& compactor: compactors_) {
- quantile_calculator->add(compactor.begin(), compactor.end(), compactor.get_lg_weight());
+ quantile_calculator_ptr->add(compactor.begin(), compactor.end(), compactor.get_lg_weight());
}
- quantile_calculator->template convert_to_cummulative<inclusive>();
- return quantile_calculator;
+ quantile_calculator_ptr->template convert_to_cummulative<inclusive>();
+ return quantile_calculator_ptr;
}
template<typename T, typename C, typename S, typename A>
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org