implemented get_quantiles()
diff --git a/req/include/req_quantile_calculator.hpp b/req/include/req_quantile_calculator.hpp
index 52665af..2a6e245 100755
--- a/req/include/req_quantile_calculator.hpp
+++ b/req/include/req_quantile_calculator.hpp
@@ -38,7 +38,7 @@
template<bool inclusive>
void convert_to_cummulative();
- const T& get_quantile(double rank) const;
+ const T* get_quantile(double rank) const;
private:
using Entry = std::pair<const T*, uint64_t>;
diff --git a/req/include/req_quantile_calculator_impl.hpp b/req/include/req_quantile_calculator_impl.hpp
index 829868d..63f0e92 100755
--- a/req/include/req_quantile_calculator_impl.hpp
+++ b/req/include/req_quantile_calculator_impl.hpp
@@ -48,11 +48,11 @@
}
template<typename T, typename C, typename A>
-const T& req_quantile_calculator<T, C, A>::get_quantile(double rank) const {
+const T* req_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);
- return *(it->first);
+ if (it == entries_.end()) return entries_[entries_.size() - 1].first;
+ return it->first;
}
} /* namespace datasketches */
diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp
index 666e2ba..41da409 100755
--- a/req/include/req_sketch.hpp
+++ b/req/include/req_sketch.hpp
@@ -37,6 +37,7 @@
public:
using Compactor = req_compactor<T, IsHighRank, Comparator, Allocator>;
using AllocCompactor = typename std::allocator_traits<Allocator>::template rebind_alloc<Compactor>;
+ using AllocPtrT = typename std::allocator_traits<Allocator>::template rebind_alloc<const T*>;
explicit req_sketch(uint16_t k, const Allocator& allocator = Allocator());
~req_sketch();
@@ -105,10 +106,24 @@
template<bool inclusive = false>
double get_rank(const T& item) const;
+ /**
+ * Returns an approximate quantile of the given normalized rank.
+ * The normalized rank must be in the range [0.0, 1.0] (both inclusive).
+ * @param rank the given normalized rank
+ * @return approximate quantile given the normalized rank
+ */
template<bool inclusive = false>
const T& get_quantile(double rank) const;
/**
+ * Returns an array of quantiles that correspond to the given array of normalized ranks.
+ * @param ranks given array of normalized ranks.
+ * @return array of quantiles that correspond to the given array of normalized ranks
+ */
+ template<bool inclusive = false>
+ std::vector<const T*, AllocPtrT> get_quantiles(const double* ranks, uint32_t size) const;
+
+ /**
* Computes size needed to serialize the current state of the sketch.
* This version is for fixed-size arithmetic types (integral and floating point).
* @return size in bytes needed to serialize this sketch
@@ -186,6 +201,13 @@
void update_num_retained();
void compress();
+ using QuantileCalculator = req_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>;
+ template<bool inclusive>
+ QuantileCalculatorPtr get_quantile_calculator() const;
+
// for deserialization
class item_deleter;
req_sketch(uint32_t k, uint64_t n, std::unique_ptr<T, item_deleter> min_value, std::unique_ptr<T, item_deleter> max_value, std::vector<Compactor, AllocCompactor>&& compactors);
diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp
index a7e3020..a43c21b 100755
--- a/req/include/req_sketch_impl.hpp
+++ b/req/include/req_sketch_impl.hpp
@@ -199,15 +199,66 @@
if ((rank < 0.0) || (rank > 1.0)) {
throw std::invalid_argument("Rank cannot be less than zero or greater than 1.0");
}
+ return *(get_quantile_calculator<inclusive>()->get_quantile(rank));
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+template<bool inclusive>
+auto req_sketch<T, H, C, S, A>::get_quantiles(const double* ranks, uint32_t size) const
+-> std::vector<const T*, AllocPtrT> {
+ std::vector<const T*, AllocPtrT> quantiles;
+ if (is_empty()) return quantiles;
+ QuantileCalculatorPtr quantile_calculator(nullptr, calculator_deleter(allocator_));
+ quantiles.reserve(size);
+ for (uint32_t i = 0; i < size; ++i) {
+ const double rank = ranks[i];
+ if ((rank < 0.0) || (rank > 1.0)) {
+ throw std::invalid_argument("rank cannot be less than zero or greater than 1.0");
+ }
+ if (rank == 0.0) quantiles.push_back(min_value_);
+ else if (rank == 1.0) quantiles.push_back(max_value_);
+ else {
+ if (!quantile_calculator) {
+ // has side effect of sorting level zero if needed
+ quantile_calculator = const_cast<req_sketch*>(this)->get_quantile_calculator<inclusive>();
+ }
+ quantiles.push_back(quantile_calculator->get_quantile(rank));
+ }
+ }
+ return quantiles;
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+class req_sketch<T, H, C, S, A>::calculator_deleter {
+ public:
+ calculator_deleter(const AllocCalc& allocator): allocator_(allocator) {}
+ void operator() (QuantileCalculator* ptr) {
+ if (ptr != nullptr) {
+ ptr->~QuantileCalculator();
+ allocator_.deallocate(ptr, 1);
+ }
+ }
+ private:
+ AllocCalc allocator_;
+};
+
+template<typename T, bool H, typename C, typename S, typename A>
+template<bool inclusive>
+auto req_sketch<T, H, C, S, A>::get_quantile_calculator() const -> QuantileCalculatorPtr {
if (!compactors_[0].is_sorted()) {
const_cast<Compactor&>(compactors_[0]).sort(); // allow this side effect
}
- req_quantile_calculator<T, C, A> quantile_calculator(n_, allocator_);
+ AllocCalc ac(allocator_);
+ QuantileCalculatorPtr quantile_calculator(
+ new (ac.allocate(1)) req_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->add(compactor.begin(), compactor.end(), compactor.get_lg_weight());
}
- quantile_calculator.template convert_to_cummulative<inclusive>();
- return quantile_calculator.get_quantile(rank);
+ quantile_calculator->template convert_to_cummulative<inclusive>();
+ return quantile_calculator;
}
// implementation for fixed-size arithmetic types (integral and floating point)
diff --git a/req/test/req_sketch_test.cpp b/req/test/req_sketch_test.cpp
index e7d1fca..3c551cd 100755
--- a/req/test/req_sketch_test.cpp
+++ b/req/test/req_sketch_test.cpp
@@ -46,6 +46,8 @@
REQUIRE(std::isnan(sketch.get_quantile(0)));
REQUIRE(std::isnan(sketch.get_quantile(0.5)));
REQUIRE(std::isnan(sketch.get_quantile(1)));
+ const double ranks[3] {0, 0.5, 1};
+ REQUIRE(sketch.get_quantiles(ranks, 3).size() == 0);
}
TEST_CASE("req sketch: single value", "[req_sketch]") {
@@ -62,6 +64,13 @@
REQUIRE(sketch.get_quantile(0) == 1);
REQUIRE(sketch.get_quantile(0.5) == 1);
REQUIRE(sketch.get_quantile(1) == 1);
+
+ const double ranks[3] {0, 0.5, 1};
+ auto quantiles = sketch.get_quantiles(ranks, 3);
+ REQUIRE(quantiles.size() == 3);
+ REQUIRE(*quantiles[0] == 1);
+ REQUIRE(*quantiles[1] == 1);
+ REQUIRE(*quantiles[2] == 1);
}
TEST_CASE("req sketch: repeated values", "[req_sketch]") {
@@ -117,6 +126,13 @@
REQUIRE(sketch.get_quantile<true>(0.5) == 5);
REQUIRE(sketch.get_quantile<true>(0.9) == 9);
REQUIRE(sketch.get_quantile<true>(1) == 10);
+
+ const double ranks[3] {0, 0.5, 1};
+ auto quantiles = sketch.get_quantiles(ranks, 3);
+ REQUIRE(quantiles.size() == 3);
+ REQUIRE(*quantiles[0] == 1);
+ REQUIRE(*quantiles[1] == 6);
+ REQUIRE(*quantiles[2] == 10);
}
TEST_CASE("req sketch: estimation mode", "[req_sketch]") {