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/01/25 23:42:22 UTC
[datasketches-cpp] 01/01: quantile sketch sorted view
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch quantile_sketch_sorted_view
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit b71947452556b48215c109159386392b6d8bc114
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Tue Jan 25 15:41:46 2022 -0800
quantile sketch sorted view
---
common/CMakeLists.txt | 2 +
common/include/quantile_sketch_sorted_view.hpp | 97 +++++++++++
.../include/quantile_sketch_sorted_view_impl.hpp | 80 +++++++++
kll/CMakeLists.txt | 2 -
kll/include/kll_quantile_calculator.hpp | 75 ---------
kll/include/kll_quantile_calculator_impl.hpp | 184 ---------------------
kll/include/kll_sketch.hpp | 22 ++-
kll/include/kll_sketch_impl.hpp | 61 +++----
kll/include/kolmogorov_smirnov_impl.hpp | 20 +--
kll/test/kll_sketch_test.cpp | 46 ++++++
10 files changed, 279 insertions(+), 310 deletions(-)
diff --git a/common/CMakeLists.txt b/common/CMakeLists.txt
index 73d8b36..df7f1c0 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/quantile_sketch_sorted_view.hpp
+ include/quantile_sketch_sorted_view_impl.hpp
DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/common/include/quantile_sketch_sorted_view.hpp b/common/include/quantile_sketch_sorted_view.hpp
new file mode 100755
index 0000000..13b5d2d
--- /dev/null
+++ b/common/include/quantile_sketch_sorted_view.hpp
@@ -0,0 +1,97 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#ifndef QUANTILE_SKETCH_SORTED_VIEW_HPP_
+#define QUANTILE_SKETCH_SORTED_VIEW_HPP_
+
+#include <functional>
+
+namespace datasketches {
+
+template<
+ typename T,
+ typename Comparator, // strict weak ordering function (see C++ named requirements: Compare)
+ typename Allocator
+>
+class quantile_sketch_sorted_view {
+public:
+ using Entry = std::pair<const T*, uint64_t>;
+ using AllocEntry = typename std::allocator_traits<Allocator>::template rebind_alloc<Entry>;
+ using Container = std::vector<Entry, AllocEntry>;
+
+ quantile_sketch_sorted_view(const Allocator& allocator);
+
+ template<typename Iterator>
+ void add(Iterator begin, Iterator end, uint64_t weight);
+
+ template<bool inclusive>
+ void convert_to_cummulative();
+
+ class const_iterator;
+ const_iterator begin() const;
+ const_iterator end() const;
+
+ size_t size() const;
+
+ // makes sense only with cumulative weight
+ const T& get_quantile(double rank) const;
+
+ template<typename C>
+ struct compare_pairs_by_first_ptr {
+ bool operator()(const Entry& a, const Entry& b) {
+ return C()(*a.first, *b.first);
+ }
+ };
+
+ struct compare_pairs_by_second {
+ bool operator()(const Entry& a, const Entry& b) {
+ return a.second < b.second;
+ }
+ };
+
+ uint64_t total_weight_;
+ Container entries_;
+};
+
+template<typename T, typename C, typename A>
+class quantile_sketch_sorted_view<T, C, A>::const_iterator: public quantile_sketch_sorted_view<T, C, A>::Container::const_iterator {
+public:
+ using Base = typename quantile_sketch_sorted_view<T, C, A>::Container::const_iterator;
+ using value_type = std::pair<const T&, const uint64_t>;
+
+ const_iterator(const Base& it): Base(it) {}
+
+ const value_type operator*() const { return value_type(*(Base::operator*().first), Base::operator*().second); }
+
+ class return_value_holder {
+ public:
+ return_value_holder(value_type value): value_(value) {}
+ const value_type* operator->() const { return &value_; }
+ private:
+ value_type value_;
+ };
+
+ return_value_holder operator->() const { return **this; }
+};
+
+} /* namespace datasketches */
+
+#include "quantile_sketch_sorted_view_impl.hpp"
+
+#endif
diff --git a/common/include/quantile_sketch_sorted_view_impl.hpp b/common/include/quantile_sketch_sorted_view_impl.hpp
new file mode 100755
index 0000000..f585b66
--- /dev/null
+++ b/common/include/quantile_sketch_sorted_view_impl.hpp
@@ -0,0 +1,80 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#ifndef QUANTILE_SKETCH_SORTED_VIEW_IMPL_HPP_
+#define QUANTILE_SKETCH_SORTED_VIEW_IMPL_HPP_
+
+#include <algorithm>
+
+namespace datasketches {
+
+template<typename T, typename C, typename A>
+quantile_sketch_sorted_view<T, C, A>::quantile_sketch_sorted_view(const A& allocator):
+total_weight_(0),
+entries_(allocator)
+{}
+
+template<typename T, typename C, typename A>
+template<typename Iterator>
+void quantile_sketch_sorted_view<T, C, A>::add(Iterator first, Iterator last, uint64_t weight) {
+ if (entries_.capacity() < entries_.size() + std::distance(first, last)) entries_.reserve(entries_.size() + std::distance(first, last));
+ const size_t size_before = entries_.size();
+ for (auto it = first; it != last; ++it) entries_.push_back(Entry(&*it, weight));
+ if (size_before > 0) std::inplace_merge(entries_.begin(), entries_.begin() + size_before, entries_.end(), compare_pairs_by_first_ptr<C>());
+}
+
+template<typename T, typename C, typename A>
+template<bool inclusive>
+void quantile_sketch_sorted_view<T, C, A>::convert_to_cummulative() {
+ uint64_t subtotal = 0;
+ for (auto& entry: entries_) {
+ const uint64_t new_subtotal = subtotal + entry.second;
+ entry.second = inclusive ? new_subtotal : subtotal;
+ subtotal = new_subtotal;
+ }
+ total_weight_ = subtotal;
+}
+
+template<typename T, typename C, typename A>
+const T& quantile_sketch_sorted_view<T, C, A>::get_quantile(double rank) const {
+ if (total_weight_ == 0) throw std::invalid_argument("supported for cumulative weight only");
+ uint64_t weight = static_cast<uint64_t>(rank * total_weight_);
+ 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);
+}
+
+template<typename T, typename C, typename A>
+auto quantile_sketch_sorted_view<T, C, A>::begin() const -> const_iterator {
+ return const_iterator(entries_.begin());
+}
+
+template<typename T, typename C, typename A>
+auto quantile_sketch_sorted_view<T, C, A>::end() const -> const_iterator {
+ return entries_.end();
+}
+
+template<typename T, typename C, typename A>
+size_t quantile_sketch_sorted_view<T, C, A>::size() const {
+ return entries_.size();
+}
+
+} /* namespace datasketches */
+
+#endif
diff --git a/kll/CMakeLists.txt b/kll/CMakeLists.txt
index 73245c3..230f020 100644
--- a/kll/CMakeLists.txt
+++ b/kll/CMakeLists.txt
@@ -41,8 +41,6 @@ install(FILES
include/kll_sketch_impl.hpp
include/kll_helper.hpp
include/kll_helper_impl.hpp
- include/kll_quantile_calculator.hpp
- include/kll_quantile_calculator_impl.hpp
include/kolmogorov_smirnov.hpp
include/kolmogorov_smirnov_impl.hpp
DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/kll/include/kll_quantile_calculator.hpp b/kll/include/kll_quantile_calculator.hpp
deleted file mode 100644
index a329ff2..0000000
--- a/kll/include/kll_quantile_calculator.hpp
+++ /dev/null
@@ -1,75 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-#ifndef KLL_QUANTILE_CALCULATOR_HPP_
-#define KLL_QUANTILE_CALCULATOR_HPP_
-
-#include <memory>
-
-namespace datasketches {
-
-// forward declaration
-template<typename T, typename C, typename S, typename A> class kll_sketch;
-
-template <typename T, typename C, typename A>
-class kll_quantile_calculator {
- public:
- using Entry = std::pair<T, uint64_t>;
- using AllocEntry = typename std::allocator_traits<A>::template rebind_alloc<Entry>;
- using Container = std::vector<Entry, AllocEntry>;
- using const_iterator = typename Container::const_iterator;
-
- template<typename S>
- kll_quantile_calculator(const kll_sketch<T, C, S, A>& sketch);
-
- T get_quantile(double fraction) const;
- const_iterator begin() const;
- const_iterator end() const;
-
- private:
- using AllocU32 = typename std::allocator_traits<A>::template rebind_alloc<uint32_t>;
- using vector_u32 = std::vector<uint32_t, AllocU32>;
- uint64_t n_;
- vector_u32 levels_;
- Container entries_;
-
- void populate_from_sketch(const T* items, const uint32_t* levels, uint8_t num_levels);
- T approximately_answer_positional_query(uint64_t pos) const;
- void convert_to_preceding_cummulative();
- uint32_t chunk_containing_pos(uint64_t pos) const;
- uint32_t search_for_chunk_containing_pos(uint64_t pos, uint64_t l, uint64_t r) const;
- static void merge_sorted_blocks(Container& entries, const uint32_t* levels, uint8_t num_levels, uint32_t num_items);
- static void merge_sorted_blocks_direct(Container& orig, Container& temp, const uint32_t* levels, uint8_t starting_level, uint8_t num_levels);
- static void merge_sorted_blocks_reversed(Container& orig, Container& temp, const uint32_t* levels, uint8_t starting_level, uint8_t num_levels);
- static uint64_t pos_of_phi(double phi, uint64_t n);
-
- template<typename Comparator>
- struct compare_pair_by_first {
- template<typename Entry1, typename Entry2>
- bool operator()(Entry1&& a, Entry2&& b) const {
- return Comparator()(std::forward<Entry1>(a).first, std::forward<Entry2>(b).first);
- }
- };
-};
-
-} /* namespace datasketches */
-
-#include "kll_quantile_calculator_impl.hpp"
-
-#endif // KLL_QUANTILE_CALCULATOR_HPP_
diff --git a/kll/include/kll_quantile_calculator_impl.hpp b/kll/include/kll_quantile_calculator_impl.hpp
deleted file mode 100644
index 4d3d118..0000000
--- a/kll/include/kll_quantile_calculator_impl.hpp
+++ /dev/null
@@ -1,184 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-#ifndef KLL_QUANTILE_CALCULATOR_IMPL_HPP_
-#define KLL_QUANTILE_CALCULATOR_IMPL_HPP_
-
-#include <memory>
-#include <cmath>
-#include <algorithm>
-
-#include "kll_helper.hpp"
-
-namespace datasketches {
-
-template<typename T, typename C, typename A>
-template<typename S>
-kll_quantile_calculator<T, C, A>::kll_quantile_calculator(const kll_sketch<T, C, S, A>& sketch):
-n_(sketch.n_), levels_(sketch.num_levels_ + 1, 0, sketch.allocator_), entries_(sketch.allocator_)
-{
- const uint32_t num_items = sketch.levels_[sketch.num_levels_] - sketch.levels_[0];
- if (num_items > 0) {
- entries_.reserve(num_items);
- populate_from_sketch(sketch.items_, sketch.levels_.data(), sketch.num_levels_);
- if (!sketch.is_level_zero_sorted_) std::sort(entries_.begin(), entries_.begin() + levels_[1], compare_pair_by_first<C>());
- merge_sorted_blocks(entries_, levels_.data(), static_cast<uint8_t>(levels_.size()) - 1, num_items);
- if (!is_sorted(entries_.begin(), entries_.end(), compare_pair_by_first<C>())) throw std::logic_error("entries must be sorted");
- convert_to_preceding_cummulative();
- }
-}
-
-template<typename T, typename C, typename A>
-T kll_quantile_calculator<T, C, A>::get_quantile(double fraction) const {
- return approximately_answer_positional_query(pos_of_phi(fraction, n_));
-}
-
-template<typename T, typename C, typename A>
-auto kll_quantile_calculator<T, C, A>::begin() const -> const_iterator {
- return entries_.begin();
-}
-
-template<typename T, typename C, typename A>
-auto kll_quantile_calculator<T, C, A>::end() const -> const_iterator {
- return entries_.end();
-}
-
-template<typename T, typename C, typename A>
-void kll_quantile_calculator<T, C, A>::populate_from_sketch(const T* items, const uint32_t* levels, uint8_t num_levels) {
- size_t src_level = 0;
- size_t dst_level = 0;
- uint64_t weight = 1;
- uint32_t offset = levels[0];
- while (src_level < num_levels) {
- const uint32_t from_index(levels[src_level] - offset);
- const uint32_t to_index(levels[src_level + 1] - offset); // exclusive
- if (from_index < to_index) { // skip empty levels
- for (uint32_t i = from_index; i < to_index; ++i) {
- entries_.push_back(Entry(items[i + offset], weight));
- }
- levels_[dst_level] = from_index;
- levels_[dst_level + 1] = to_index;
- dst_level++;
- }
- src_level++;
- weight *= 2;
- }
- if (levels_.size() > static_cast<size_t>(dst_level + 1)) levels_.resize(dst_level + 1);
-}
-
-template<typename T, typename C, typename A>
-T kll_quantile_calculator<T, C, A>::approximately_answer_positional_query(uint64_t pos) const {
- if (pos >= n_) throw std::logic_error("position out of range");
- const uint32_t num_items = levels_[levels_.size() - 1];
- if (pos > entries_[num_items - 1].second) return entries_[num_items - 1].first;
- const uint32_t index = chunk_containing_pos(pos);
- return entries_[index].first;
-}
-
-template<typename T, typename C, typename A>
-void kll_quantile_calculator<T, C, A>::convert_to_preceding_cummulative() {
- uint64_t subtotal = 0;
- for (auto& entry: entries_) {
- const uint64_t new_subtotal = subtotal + entry.second;
- entry.second = subtotal;
- subtotal = new_subtotal;
- }
-}
-
-template<typename T, typename C, typename A>
-uint64_t kll_quantile_calculator<T, C, A>::pos_of_phi(double phi, uint64_t n) {
- const uint64_t pos = static_cast<uint64_t>(std::floor(phi * n));
- return (pos == n) ? n - 1 : pos;
-}
-
-template<typename T, typename C, typename A>
-uint32_t kll_quantile_calculator<T, C, A>::chunk_containing_pos(uint64_t pos) const {
- if (entries_.size() < 1) throw std::logic_error("array too short");
- if (pos < entries_[0].second) throw std::logic_error("position too small");
- if (pos > entries_[entries_.size() - 1].second) throw std::logic_error("position too large");
- return search_for_chunk_containing_pos(pos, 0, entries_.size());
-}
-
-template<typename T, typename C, typename A>
-uint32_t kll_quantile_calculator<T, C, A>::search_for_chunk_containing_pos(uint64_t pos, uint64_t l, uint64_t r) const {
- if (l + 1 == r) {
- return static_cast<uint32_t>(l);
- }
- const uint64_t m = l + (r - l) / 2;
- if (entries_[m].second <= pos) {
- return search_for_chunk_containing_pos(pos, m, r);
- }
- return search_for_chunk_containing_pos(pos, l, m);
-}
-
-template<typename T, typename C, typename A>
-void kll_quantile_calculator<T, C, A>::merge_sorted_blocks(Container& entries, const uint32_t* levels, uint8_t num_levels, uint32_t num_items) {
- if (num_levels == 1) return;
- Container temporary(entries.get_allocator());
- temporary.reserve(num_items);
- merge_sorted_blocks_direct(entries, temporary, levels, 0, num_levels);
-}
-
-template<typename T, typename C, typename A>
-void kll_quantile_calculator<T, C, A>::merge_sorted_blocks_direct(Container& orig, Container& temp, const uint32_t* levels,
- uint8_t starting_level, uint8_t num_levels) {
- if (num_levels == 1) return;
- const uint8_t num_levels_1 = num_levels / 2;
- const uint8_t num_levels_2 = num_levels - num_levels_1;
- const uint8_t starting_level_1 = starting_level;
- const uint8_t starting_level_2 = starting_level + num_levels_1;
- const auto initial_size = temp.size();
- merge_sorted_blocks_reversed(orig, temp, levels, starting_level_1, num_levels_1);
- merge_sorted_blocks_reversed(orig, temp, levels, starting_level_2, num_levels_2);
- const uint32_t num_items_1 = levels[starting_level_1 + num_levels_1] - levels[starting_level_1];
- const auto chunk_begin = temp.begin() + initial_size;
- std::merge(
- std::make_move_iterator(chunk_begin), std::make_move_iterator(chunk_begin + num_items_1),
- std::make_move_iterator(chunk_begin + num_items_1), std::make_move_iterator(temp.end()),
- orig.begin() + levels[starting_level], compare_pair_by_first<C>()
- );
- temp.erase(chunk_begin, temp.end());
-}
-
-template<typename T, typename C, typename A>
-void kll_quantile_calculator<T, C, A>::merge_sorted_blocks_reversed(Container& orig, Container& temp, const uint32_t* levels,
- uint8_t starting_level, uint8_t num_levels) {
- if (num_levels == 1) {
- std::move(orig.begin() + levels[starting_level], orig.begin() + levels[starting_level + 1], std::back_inserter(temp));
- return;
- }
- const uint8_t num_levels_1 = num_levels / 2;
- const uint8_t num_levels_2 = num_levels - num_levels_1;
- const uint8_t starting_level_1 = starting_level;
- const uint8_t starting_level_2 = starting_level + num_levels_1;
- merge_sorted_blocks_direct(orig, temp, levels, starting_level_1, num_levels_1);
- merge_sorted_blocks_direct(orig, temp, levels, starting_level_2, num_levels_2);
- std::merge(
- std::make_move_iterator(orig.begin() + levels[starting_level_1]),
- std::make_move_iterator(orig.begin() + levels[starting_level_1 + num_levels_1]),
- std::make_move_iterator(orig.begin() + levels[starting_level_2]),
- std::make_move_iterator(orig.begin() + levels[starting_level_2 + num_levels_2]),
- std::back_inserter(temp),
- compare_pair_by_first<C>()
- );
-}
-
-} /* namespace datasketches */
-
-#endif // KLL_QUANTILE_CALCULATOR_IMPL_HPP_
diff --git a/kll/include/kll_sketch.hpp b/kll/include/kll_sketch.hpp
index 3a3e7bd..c0e0712 100644
--- a/kll/include/kll_sketch.hpp
+++ b/kll/include/kll_sketch.hpp
@@ -24,7 +24,7 @@
#include <memory>
#include <vector>
-#include "kll_quantile_calculator.hpp"
+#include "quantile_sketch_sorted_view.hpp"
#include "common_defs.hpp"
#include "serde.hpp"
@@ -271,10 +271,12 @@ class kll_sketch {
* These are also called normalized ranks or fractional ranks.
* If fraction = 0.0, the true minimum value of the stream is returned.
* If fraction = 1.0, the true maximum value of the stream is returned.
+ * If the parameter inclusive=true, the given rank is considered inclusive (includes the weight of an item)
*
* @return the approximation to the value at the given fraction
*/
- T get_quantile(double fraction) const;
+ template<bool inclusive = false>
+ const T& get_quantile(double fraction) const;
/**
* This is a more efficient multiple-query version of get_quantile().
@@ -290,10 +292,12 @@ class kll_sketch {
* @param fractions given array of fractional positions in the hypothetical sorted stream.
* These are also called normalized ranks or fractional ranks.
* These fractions must be in the interval [0.0, 1.0], inclusive.
+ * If the parameter inclusive=true, the given fractions are considered inclusive (include weights of items)
*
* @return array of approximations to the given fractions in the same order as given fractions
* in the input array.
*/
+ template<bool inclusive = false>
std::vector<T, A> get_quantiles(const double* fractions, uint32_t size) const;
/**
@@ -309,6 +313,7 @@ class kll_sketch {
*
* @return array of approximations to the given number of evenly-spaced fractional ranks.
*/
+ template<bool inclusive = false>
std::vector<T, A> get_quantiles(uint32_t num) const;
/**
@@ -485,6 +490,9 @@ class kll_sketch {
const_iterator begin() const;
const_iterator end() const;
+ template<bool inclusive = false>
+ quantile_sketch_sorted_view<T, C, A> get_sorted_view(bool cumulative) const;
+
#ifdef KLL_VALIDATION
uint8_t get_num_levels() { return num_levels_; }
uint32_t* get_levels() { return levels_; }
@@ -528,8 +536,6 @@ class kll_sketch {
T* max_value_;
bool is_level_zero_sorted_;
- friend class kll_quantile_calculator<T, C, A>;
-
// for deserialization
class item_deleter;
class items_deleter;
@@ -548,7 +554,6 @@ class kll_sketch {
uint8_t find_level_to_compact() const;
void add_empty_top_level_to_completely_full_sketch();
void sort_level_zero();
- std::unique_ptr<kll_quantile_calculator<T, C, A>, std::function<void(kll_quantile_calculator<T, C, A>*)>> get_quantile_calculator();
template<bool inclusive>
vector_d<A> get_PMF_or_CDF(const T* split_points, uint32_t size, bool is_CDF) const;
@@ -573,8 +578,9 @@ class kll_sketch {
// implementations for floating point types
template<typename TT = T, typename std::enable_if<std::is_floating_point<TT>::value, int>::type = 0>
- static TT get_invalid_value() {
- return std::numeric_limits<TT>::quiet_NaN();
+ static const TT& get_invalid_value() {
+ static TT value = std::numeric_limits<TT>::quiet_NaN();
+ return value;
}
template<typename TT = T, typename std::enable_if<std::is_floating_point<TT>::value, int>::type = 0>
@@ -584,7 +590,7 @@ class kll_sketch {
// implementations for all other types
template<typename TT = T, typename std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
- static TT get_invalid_value() {
+ static const TT& get_invalid_value() {
throw std::runtime_error("getting quantiles from empty sketch is not supported for this type of values");
}
diff --git a/kll/include/kll_sketch_impl.hpp b/kll/include/kll_sketch_impl.hpp
index 2276b05..5aa0b15 100644
--- a/kll/include/kll_sketch_impl.hpp
+++ b/kll/include/kll_sketch_impl.hpp
@@ -266,43 +266,44 @@ T kll_sketch<T, C, S, A>::get_max_value() const {
}
template<typename T, typename C, typename S, typename A>
-T kll_sketch<T, C, S, A>::get_quantile(double fraction) const {
+template<bool inclusive>
+const T& kll_sketch<T, C, S, A>::get_quantile(double rank) const {
if (is_empty()) return get_invalid_value();
- if (fraction == 0.0) return *min_value_;
- if (fraction == 1.0) return *max_value_;
- if ((fraction < 0.0) || (fraction > 1.0)) {
+ if (rank == 0.0) return *min_value_;
+ if (rank == 1.0) return *max_value_;
+ if ((rank < 0.0) || (rank > 1.0)) {
throw std::invalid_argument("Fraction cannot be less than zero or greater than 1.0");
}
- // has side effect of sorting level zero if needed
- auto quantile_calculator(const_cast<kll_sketch*>(this)->get_quantile_calculator());
- return quantile_calculator->get_quantile(fraction);
+ // may have a side effect of sorting level zero if needed
+ return get_sorted_view<inclusive>(true).get_quantile(rank);
}
template<typename T, typename C, typename S, typename A>
-std::vector<T, A> kll_sketch<T, C, S, A>::get_quantiles(const double* fractions, uint32_t size) const {
+template<bool inclusive>
+std::vector<T, A> kll_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;
- std::unique_ptr<kll_quantile_calculator<T, C, A>, std::function<void(kll_quantile_calculator<T, C, A>*)>> quantile_calculator;
quantiles.reserve(size);
+
+ // may have a side effect of sorting level zero if needed
+ auto view = get_sorted_view<inclusive>(true);
+
for (uint32_t i = 0; i < size; i++) {
- const double fraction = fractions[i];
- if ((fraction < 0.0) || (fraction > 1.0)) {
+ const double rank = ranks[i];
+ if ((rank < 0.0) || (rank > 1.0)) {
throw std::invalid_argument("Fraction cannot be less than zero or greater than 1.0");
}
- if (fraction == 0.0) quantiles.push_back(*min_value_);
- else if (fraction == 1.0) quantiles.push_back(*max_value_);
+ else 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<kll_sketch*>(this)->get_quantile_calculator();
- }
- quantiles.push_back(quantile_calculator->get_quantile(fraction));
+ quantiles.push_back(view.get_quantile(rank));
}
}
return quantiles;
}
template<typename T, typename C, typename S, typename A>
+template<bool inclusive>
std::vector<T, A> kll_sketch<T, C, S, A>::get_quantiles(uint32_t num) const {
if (is_empty()) return std::vector<T, A>(allocator_);
if (num == 0) {
@@ -316,7 +317,7 @@ std::vector<T, A> kll_sketch<T, C, S, A>::get_quantiles(uint32_t num) const {
if (num > 1) {
fractions[num - 1] = 1.0;
}
- return get_quantiles(fractions.data(), num);
+ return get_quantiles<inclusive>(fractions.data(), num);
}
template<typename T, typename C, typename S, typename A>
@@ -789,15 +790,19 @@ void kll_sketch<T, C, S, A>::sort_level_zero() {
}
template<typename T, typename C, typename S, typename A>
-std::unique_ptr<kll_quantile_calculator<T, C, A>, std::function<void(kll_quantile_calculator<T, C, A>*)>> kll_sketch<T, C, S, A>::get_quantile_calculator() {
- sort_level_zero();
- using AllocCalc = typename std::allocator_traits<A>::template rebind_alloc<kll_quantile_calculator<T, C, A>>;
- AllocCalc alloc(allocator_);
- std::unique_ptr<kll_quantile_calculator<T, C, A>, std::function<void(kll_quantile_calculator<T, C, A>*)>> quantile_calculator(
- new (alloc.allocate(1)) kll_quantile_calculator<T, C, A>(*this),
- [&alloc](kll_quantile_calculator<T, C, A>* ptr){ ptr->~kll_quantile_calculator<T, C, A>(); alloc.deallocate(ptr, 1); }
- );
- return quantile_calculator;
+template<bool inclusive>
+quantile_sketch_sorted_view<T, C, A> kll_sketch<T, C, S, A>::get_sorted_view(bool cumulative) const {
+ const_cast<kll_sketch*>(this)->sort_level_zero(); // allow this side effect
+ quantile_sketch_sorted_view<T, C, A> view(allocator_);
+ uint8_t level = 0;
+ while (level < num_levels_) {
+ const auto from = items_ + levels_[level];
+ const auto to = items_ + levels_[level + 1]; // exclusive
+ view.add(from, to, 1 << level);
+ ++level;
+ }
+ if (cumulative) view.template convert_to_cummulative<inclusive>();
+ return view;
}
template<typename T, typename C, typename S, typename A>
diff --git a/kll/include/kolmogorov_smirnov_impl.hpp b/kll/include/kolmogorov_smirnov_impl.hpp
index 17eaf0d..2cb0ace 100644
--- a/kll/include/kolmogorov_smirnov_impl.hpp
+++ b/kll/include/kolmogorov_smirnov_impl.hpp
@@ -22,23 +22,17 @@
namespace datasketches {
-// type resolver
-template<typename T, typename C, typename S, typename A>
-kll_quantile_calculator<T, C, A> make_quantile_calculator(const kll_sketch<T, C, S, A>& sketch) {
- return kll_quantile_calculator<T, C, A>(sketch);
-}
-
template<typename Sketch>
double kolmogorov_smirnov::delta(const Sketch& sketch1, const Sketch& sketch2) {
using Comparator = typename Sketch::comparator;
- auto calc1 = make_quantile_calculator(sketch1);
- auto calc2 = make_quantile_calculator(sketch2);
- auto it1 = calc1.begin();
- auto it2 = calc2.begin();
+ auto view1 = sketch1.get_sorted_view(true);
+ auto view2 = sketch2.get_sorted_view(true);
+ auto it1 = view1.begin();
+ auto it2 = view2.begin();
const auto n1 = sketch1.get_n();
const auto n2 = sketch2.get_n();
double delta = 0;
- while (it1 != calc1.end() && it2 != calc2.end()) {
+ while (it1 != view1.end() && it2 != view2.end()) {
const double norm_cum_wt1 = static_cast<double>((*it1).second) / n1;
const double norm_cum_wt2 = static_cast<double>((*it2).second) / n2;
delta = std::max(delta, std::abs(norm_cum_wt1 - norm_cum_wt2));
@@ -51,8 +45,8 @@ double kolmogorov_smirnov::delta(const Sketch& sketch1, const Sketch& sketch2) {
++it2;
}
}
- const double norm_cum_wt1 = it1 == calc1.end() ? 1 : static_cast<double>((*it1).second) / n1;
- const double norm_cum_wt2 = it2 == calc2.end() ? 1 : static_cast<double>((*it2).second) / n2;
+ const double norm_cum_wt1 = it1 == view1.end() ? 1 : static_cast<double>((*it1).second) / n1;
+ const double norm_cum_wt2 = it2 == view2.end() ? 1 : static_cast<double>((*it2).second) / n2;
delta = std::max(delta, std::abs(norm_cum_wt1 - norm_cum_wt2));
return delta;
}
diff --git a/kll/test/kll_sketch_test.cpp b/kll/test/kll_sketch_test.cpp
index b2e2b96..9cb5619 100644
--- a/kll/test/kll_sketch_test.cpp
+++ b/kll/test/kll_sketch_test.cpp
@@ -788,6 +788,52 @@ TEST_CASE("kll sketch", "[kll_sketch]") {
auto kll2 = kll_sketch<int8_t>::deserialize(blob.data(), blob.size());
}
+ SECTION("sorted view") {
+ kll_sketch<int> kll;
+ kll.update(2);
+ kll.update(3);
+ kll.update(1);
+
+ { // non-cumulative, using operator->
+ auto view = kll.get_sorted_view(false);
+ REQUIRE(view.size() == 3);
+ auto it = view.begin();
+ REQUIRE(it->first == 1);
+ REQUIRE(it->second == 1);
+ ++it;
+ REQUIRE(it->first == 2);
+ REQUIRE(it->second == 1);
+ ++it;
+ REQUIRE(it->first == 3);
+ REQUIRE(it->second == 1);
+ }
+ { // cumulative, non-inclusive, using operator->
+ auto view = kll.get_sorted_view(true);
+ REQUIRE(view.size() == 3);
+ auto it = view.begin();
+ REQUIRE(it->first == 1);
+ REQUIRE(it->second == 0);
+ ++it;
+ REQUIRE(it->first == 2);
+ REQUIRE(it->second == 1);
+ ++it;
+ REQUIRE(it->first == 3);
+ REQUIRE(it->second == 2);
+ }
+ { // cumulative, inclusive, using operator*
+ auto view = kll.get_sorted_view<true>(true);
+ REQUIRE(view.size() == 3);
+ auto it = view.begin();
+ REQUIRE((*it).first == 1);
+ REQUIRE((*it).second == 1);
+ ++it;
+ REQUIRE((*it).first == 2);
+ REQUIRE((*it).second == 2);
+ ++it;
+ REQUIRE((*it).first == 3);
+ REQUIRE((*it).second == 3);
+ }
+ }
// cleanup
if (test_allocator_total_bytes != 0) {
REQUIRE(test_allocator_total_bytes == 0);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org