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:21 UTC
[datasketches-cpp] branch quantile_sketch_sorted_view created (now b719474)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch quantile_sketch_sorted_view
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git.
at b719474 quantile sketch sorted view
This branch includes the following new commits:
new b719474 quantile sketch sorted view
The 1 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.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[datasketches-cpp] 01/01: quantile sketch sorted view
Posted by al...@apache.org.
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