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 2023/12/19 20:41:55 UTC
(datasketches-cpp) branch tdigest created (now 3b9ef63)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch tdigest
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
at 3b9ef63 incomplete implementation of t-digest
This branch includes the following new commits:
new 3b9ef63 incomplete implementation of t-digest
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: incomplete implementation of t-digest
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch tdigest
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit 3b9ef635590598af2ae12f4f0c9ec6aa3fd03a94
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Tue Dec 19 12:41:45 2023 -0800
incomplete implementation of t-digest
---
CMakeLists.txt | 1 +
tdigest/CMakeLists.txt | 41 ++++++
tdigest/include/tdigest.hpp | 202 ++++++++++++++++++++++++++++++
tdigest/include/tdigest_impl.hpp | 264 +++++++++++++++++++++++++++++++++++++++
tdigest/test/CMakeLists.txt | 41 ++++++
tdigest/test/tdigest_test.cpp | 111 ++++++++++++++++
6 files changed, 660 insertions(+)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 5336ea2..e3505c1 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -118,6 +118,7 @@ add_subdirectory(req)
add_subdirectory(quantiles)
add_subdirectory(count)
add_subdirectory(density)
+add_subdirectory(tdigest)
if (WITH_PYTHON)
add_subdirectory(python)
diff --git a/tdigest/CMakeLists.txt b/tdigest/CMakeLists.txt
new file mode 100755
index 0000000..d7deee3
--- /dev/null
+++ b/tdigest/CMakeLists.txt
@@ -0,0 +1,41 @@
+# 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.
+
+add_library(tdigest INTERFACE)
+
+add_library(${PROJECT_NAME}::QUANTILES ALIAS tdigest)
+
+if (BUILD_TESTS)
+ add_subdirectory(test)
+endif()
+
+target_include_directories(tdigest
+ INTERFACE
+ $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/include>
+ $<INSTALL_INTERFACE:$<INSTALL_PREFIX>/include>
+)
+
+target_link_libraries(tdigest INTERFACE common)
+
+install(TARGETS tdigest
+ EXPORT ${PROJECT_NAME}
+)
+
+install(FILES
+ include/tdigest.hpp
+ include/tdigest_impl.hpp
+ DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/tdigest/include/tdigest.hpp b/tdigest/include/tdigest.hpp
new file mode 100644
index 0000000..8ebd13c
--- /dev/null
+++ b/tdigest/include/tdigest.hpp
@@ -0,0 +1,202 @@
+/*
+ * 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 _TDIGEST_HPP_
+#define _TDIGEST_HPP_
+
+#include <type_traits>
+#include <limits>
+
+#include "common_defs.hpp"
+
+namespace datasketches {
+
+// this is equivalent of K_2 (default) in the Java implementation mentioned below
+struct scale_function {
+ double k(double q, double normalizer) const {
+ return limit([normalizer] (double q) { return std::log(q / (1 - q)) * normalizer; }, q, 1e-15, 1 - 1e-15);
+ }
+ double q(double k, double normalizer) const {
+ const double w = std::exp(k / normalizer);
+ return w / (1 + w);
+ }
+ double max(double q, double normalizer) const {
+ return q * (1 - q) / normalizer;
+ }
+ double normalizer(double compression, double n) const {
+ return compression / z(compression, n);
+ }
+ double z(double compression, double n) const {
+ return 4 * std::log(n / compression) + 24;
+ }
+
+ template<typename Func>
+ double limit(Func f, double x, double low, double high) const {
+ if (x < low) return f(low);
+ if (x > high) return f(high);
+ return f(x);
+ }
+};
+
+// forward declaration
+template <typename T, typename Allocator = std::allocator<T>> class tdigest;
+
+/// TDigest float sketch
+using tdigest_float = tdigest<float>;
+/// TDigest double sketch
+using tdigest_double = tdigest<double>;
+
+/**
+ * t-Digest for estimating quantiles and ranks.
+ * This implementation is based on the following paper:
+ * Ted Dunning, Otmar Ertl. Extremely Accurate Quantiles Using t-Digests
+ * and the following implementation in Java:
+ * https://github.com/tdunning/t-digest
+ * This implementation is similar to MergingDigest in the above Java implementation
+ */
+template <typename T, typename Allocator>
+class tdigest {
+ static_assert(std::is_floating_point<T>::value, "Floating-point type expected");
+ static_assert(std::numeric_limits<T>::is_iec559, "IEEE 754 compatibility required");
+public:
+ using value_type = T;
+ using allocator_type = Allocator;
+
+ static const bool USE_ALTERNATING_SORT = true;
+ static const bool USE_TWO_LEVEL_COMPRESSION = true;
+ static const bool USE_WEIGHT_LIMIT = true;
+
+ class centroid {
+ public:
+ centroid(T value, uint64_t weight): mean_(value), weight_(weight) {}
+ void add(const centroid& other) {
+ weight_ += other.weight_;
+ mean_ += (other.mean_ - mean_) * other.weight_ / weight_;
+ }
+ T get_mean() const { return mean_; }
+ uint64_t get_weight() const { return weight_; }
+ private:
+ T mean_;
+ uint64_t weight_;
+ };
+ using vector_centroid = std::vector<centroid, typename std::allocator_traits<Allocator>::template rebind_alloc<centroid>>;
+
+ struct centroid_cmp {
+ centroid_cmp(bool reverse): reverse_(reverse) {}
+ bool operator()(const centroid& a, const centroid& b) const {
+ if (a.get_mean() < b.get_mean()) return !reverse_;
+ return reverse_;
+ }
+ bool reverse_;
+ };
+
+ /**
+ * Constructor
+ * @param k affects the size of the sketch and its estimation error
+ * @param allocator used to allocate memory
+ */
+ explicit tdigest(uint16_t k = 100, const Allocator& allocator = Allocator());
+
+ /**
+ * Update this t-Digest with the given value
+ * @param value to update the t-Digest with
+ */
+ void update(T value);
+
+ /**
+ * Merge the given t-Digest into this one
+ * @param other t-Digest to merge
+ */
+ void merge(tdigest& other);
+
+ /**
+ * Process buffered values and merge centroids if needed
+ */
+ void compress();
+
+ /**
+ * @return true if t-Digest has not seen any data
+ */
+ bool is_empty() const;
+
+ /**
+ * @return minimum value seen by t-Digest
+ */
+ T get_min_value() const;
+
+ /**
+ * @return maximum value seen by t-Digest
+ */
+ T get_max_value() const;
+
+ /**
+ * @return total weight
+ */
+ uint64_t get_total_weight() const;
+
+ /**
+ * Compute approximate normalized rank of the given value.
+ * @param value to be ranked
+ * @return normalized rank (from 0 to 1 inclusive)
+ */
+ double get_rank(T value) const;
+
+ /**
+ * Compute approximate quantile value corresponding to the given normalized rank
+ * @param rank normalized rank (from 0 to 1 inclusive)
+ * @return quantile value corresponding to the given rank
+ */
+ T get_quantile(double rank) const;
+
+ /**
+ * @return parameter k (compression) that was used to configure this t-Digest
+ */
+ uint16_t get_k() const;
+
+ /**
+ * Human-readable summary of this t-Digest as a string
+ * @param print_centroids if true append the list of centroids with weights
+ * @return summary of this t-Digest
+ */
+ string<Allocator> to_string(bool print_centroids = false) const;
+
+private:
+ Allocator allocator_;
+ uint16_t k_;
+ uint16_t internal_k_;
+ uint32_t merge_count_;
+ T min_;
+ T max_;
+ size_t centroids_capacity_;
+ vector_centroid centroids_;
+ uint64_t total_weight_;
+ size_t buffer_capacity_;
+ vector_centroid buffer_;
+ uint64_t buffered_weight_;
+
+ void merge_new_values();
+ void merge_new_values(bool force, uint16_t k);
+ void merge_new_values(vector_centroid& centroids, uint64_t weight, uint16_t k, bool reverse);
+};
+
+} /* namespace datasketches */
+
+#include "tdigest_impl.hpp"
+
+#endif // _TDIGEST_HPP_
diff --git a/tdigest/include/tdigest_impl.hpp b/tdigest/include/tdigest_impl.hpp
new file mode 100644
index 0000000..5f57e85
--- /dev/null
+++ b/tdigest/include/tdigest_impl.hpp
@@ -0,0 +1,264 @@
+/*
+ * 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 _TDIGEST_IMPL_HPP_
+#define _TDIGEST_IMPL_HPP_
+
+#include <cmath>
+#include <sstream>
+
+namespace datasketches {
+
+template<typename T, typename A>
+tdigest<T, A>::tdigest(uint16_t k, const A& allocator):
+allocator_(allocator),
+k_(k),
+internal_k_(k),
+merge_count_(0),
+min_(std::numeric_limits<T>::infinity()),
+max_(-std::numeric_limits<T>::infinity()),
+centroids_capacity_(0),
+centroids_(allocator),
+total_weight_(0),
+buffer_capacity_(0),
+buffer_(allocator),
+buffered_weight_(0)
+{
+ if (k < 10) throw std::invalid_argument("k must be at least 10");
+ size_t fudge = 0;
+ if (USE_WEIGHT_LIMIT) {
+ fudge = 10;
+ if (k < 30) fudge +=20;
+ }
+ centroids_capacity_ = 2 * k_ + fudge;
+ buffer_capacity_ = 5 * centroids_capacity_;
+ double scale = std::max(1.0, static_cast<double>(buffer_capacity_) / centroids_capacity_ - 1.0);
+ if (!USE_TWO_LEVEL_COMPRESSION) scale = 1;
+ internal_k_ = std::ceil(std::sqrt(scale) * k_);
+ if (centroids_capacity_ < internal_k_ + fudge) {
+ centroids_capacity_ = internal_k_ + fudge;
+ }
+ if (buffer_capacity_ < 2 * centroids_capacity_) buffer_capacity_ = 2 * centroids_capacity_;
+}
+
+template<typename T, typename A>
+void tdigest<T, A>::update(T value) {
+ // check for NaN
+ if (buffer_.size() >= buffer_capacity_ - centroids_.size() - 1) merge_new_values(); // - 1 for compatibility with Java
+ buffer_.push_back(centroid(value, 1));
+ ++buffered_weight_;
+ min_ = std::min(min_, value);
+ max_ = std::max(max_, value);
+}
+
+template<typename T, typename A>
+void tdigest<T, A>::merge(tdigest& other) {
+}
+
+template<typename T, typename A>
+void tdigest<T, A>::compress() {
+ merge_new_values(true, k_);
+}
+
+template<typename T, typename A>
+bool tdigest<T, A>::is_empty() const {
+ return centroids_.empty() && buffer_.empty();
+}
+
+template<typename T, typename A>
+T tdigest<T, A>::get_min_value() const {
+ if (is_empty()) throw std::runtime_error("operation is undefined for an empty sketch");
+ return min_;
+}
+
+template<typename T, typename A>
+T tdigest<T, A>::get_max_value() const {
+ if (is_empty()) throw std::runtime_error("operation is undefined for an empty sketch");
+ return max_;
+}
+
+template<typename T, typename A>
+uint64_t tdigest<T, A>::get_total_weight() const {
+ return total_weight_ + buffered_weight_;
+}
+
+template<typename T, typename A>
+double tdigest<T, A>::get_rank(T value) const {
+ if (is_empty()) throw std::runtime_error("operation is undefined for an empty sketch");
+ // check for NaN
+ if (value < min_) return 0;
+ if (value > max_) return 1;
+ // one centroid and value == min_ == max_
+ if ((centroids_.size() + buffer_.size()) == 1) return 0.5;
+
+ const_cast<tdigest*>(this)->merge_new_values(); // side effect
+
+ // left tail
+ const T first_mean = centroids_.front().get_mean();
+ if (value < first_mean) {
+ if (first_mean - min_ > 0) {
+ if (value == min_) return 0.5 / total_weight_;
+ return (1.0 + (value - min_) / (first_mean - min_) * (centroids_.front().get_weight() / 2.0 - 1.0)); // ?
+ }
+ return 0; // should never happen
+ }
+
+ // right tail
+ const T last_mean = centroids_.back().get_mean();
+ if (value > last_mean) {
+ if (max_ - last_mean > 0) {
+ if (value == max_) return 1.0 - 0.5 / total_weight_;
+ return 1 - ((1 + (max_ - value) / (max_ - last_mean) * (centroids_.back().get_weight() / 2.0 - 1.0)) / total_weight_); // ?
+ }
+ return 1; // should never happen
+ }
+
+ auto lower = std::lower_bound(centroids_.begin(), centroids_.end(), centroid(value, 1), centroid_cmp(false));
+ if (lower == centroids_.end()) throw std::logic_error("lower == end in get_rank()");
+ auto upper = std::upper_bound(lower, centroids_.end(), centroid(value, 1), centroid_cmp(false));
+ if (upper == centroids_.begin()) throw std::logic_error("upper == begin in get_rank()");
+ if (value < lower->get_mean()) --lower;
+ if (upper == centroids_.end() || (upper != centroids_.begin() && !((upper - 1)->get_mean() < value))) --upper;
+ double weight_below = 0;
+ auto it = centroids_.begin();
+ while (it != lower) {
+ weight_below += it->get_weight();
+ ++it;
+ }
+ weight_below += lower->get_weight() / 2.0;
+ double weight_delta = 0;
+ while (it != upper) {
+ weight_delta += it->get_weight();
+ ++it;
+ }
+ weight_delta -= lower->get_weight() / 2.0;
+ weight_delta += upper->get_weight() / 2.0;
+ if (upper->get_mean() - lower->get_mean() > 0) {
+ return (weight_below + weight_delta * (value - lower->get_mean()) / (upper->get_mean() - lower->get_mean())) / total_weight_;
+ }
+ return (weight_below + weight_delta / 2.0) / total_weight_;
+}
+
+template<typename T, typename A>
+T tdigest<T, A>::get_quantile(double rank) const {
+ if (is_empty()) throw std::runtime_error("operation is undefined for an empty sketch");
+ return 0;
+}
+
+template<typename T, typename A>
+uint16_t tdigest<T, A>::get_k() const {
+ return k_;
+}
+
+template<typename T, typename A>
+string<A> tdigest<T, A>::to_string(bool print_centroids) const {
+ // Using a temporary stream for implementation here does not comply with AllocatorAwareContainer requirements.
+ // The stream does not support passing an allocator instance, and alternatives are complicated.
+ std::ostringstream os;
+ os << "### t-Digest summary:" << std::endl;
+ os << " Nominal k : " << k_ << std::endl;
+ os << " Internal k : " << internal_k_ << std::endl;
+ os << " Centroids : " << centroids_.size() << std::endl;
+ os << " Buffered : " << buffer_.size() << std::endl;
+ os << " Centroids capacity : " << centroids_capacity_ << std::endl;
+ os << " Buffer capacity : " << buffer_capacity_ << std::endl;
+ os << " Total Weight : " << total_weight_ << std::endl;
+ os << " Buffered Weight : " << buffered_weight_ << std::endl;
+ os << " Merge count : " << merge_count_ << std::endl;
+ if (!is_empty()) {
+ os << " Min : " << min_ << std::endl;
+ os << " Max : " << max_ << std::endl;
+ }
+ os << "### End t-Digest summary" << std::endl;
+ if (print_centroids) {
+ os << "Centroids:" << std::endl;
+ int i = 0;
+ for (auto centroid: centroids_) {
+ os << i << ": " << centroid.get_mean() << ", " << centroid.get_weight() << std::endl;
+ ++i;
+ }
+ }
+ return string<A>(os.str().c_str(), allocator_);
+}
+
+template<typename T, typename A>
+void tdigest<T, A>::merge_new_values() {
+ merge_new_values(false, internal_k_);
+}
+
+template<typename T, typename A>
+void tdigest<T, A>::merge_new_values(bool force, uint16_t k) {
+ if (total_weight_ == 0 && buffered_weight_ == 0) return;
+ if (force || buffered_weight_ > 0) {
+ merge_new_values(buffer_, buffered_weight_, k, USE_ALTERNATING_SORT & (merge_count_ & 1));
+ ++merge_count_;
+ buffer_.clear();
+ buffered_weight_ = 0;
+ }
+}
+
+template<typename T, typename A>
+void tdigest<T, A>::merge_new_values(vector_centroid& incoming_centroids, uint64_t weight, uint16_t k, bool reverse) {
+ for (const auto& centroid: centroids_) incoming_centroids.push_back(centroid);
+ centroids_.clear();
+ std::stable_sort(incoming_centroids.begin(), incoming_centroids.end(), centroid_cmp(reverse));
+ total_weight_ += weight;
+ auto it = incoming_centroids.begin();
+ centroids_.push_back(*it);
+ ++it;
+ double weight_so_far = 0;
+ const double normalizer = scale_function().normalizer(k, total_weight_);
+ double k1 = scale_function().k(0, normalizer);
+ double w_limit = total_weight_ * scale_function().q(k1 + 1, normalizer);
+ while (it != incoming_centroids.end()) {
+ const double proposed_weight = centroids_.back().get_weight() + it->get_weight();
+ const double projected_weight = weight_so_far + proposed_weight;
+ bool add_this;
+ if (USE_WEIGHT_LIMIT) {
+ const double q0 = weight_so_far / total_weight_;
+ const double q2 = (weight_so_far + proposed_weight) / total_weight_;
+ add_this = proposed_weight <= total_weight_ * std::min(scale_function().max(q0, normalizer), scale_function().max(q2, normalizer));
+ } else {
+ add_this = projected_weight <= w_limit;
+ }
+ if (std::distance(incoming_centroids.begin(), it) == 1 || std::distance(incoming_centroids.end(), it) == 1) {
+ add_this = false;
+ }
+ if (add_this) {
+ centroids_.back().add(*it);
+ } else {
+ weight_so_far += centroids_.back().get_weight();
+ if (!USE_WEIGHT_LIMIT) {
+ k1 = scale_function().k(weight_so_far / total_weight_, normalizer);
+ w_limit = total_weight_ * scale_function().q(k1 + 1, normalizer);
+ }
+ centroids_.push_back(*it);
+ }
+ ++it;
+ }
+ if (reverse) std::reverse(centroids_.begin(), centroids_.end());
+ if (total_weight_ > 0) {
+ min_ = std::min(min_, centroids_.front().get_mean());
+ max_ = std::max(max_, centroids_.back().get_mean());
+ }
+}
+
+} /* namespace datasketches */
+
+#endif // _TDIGEST_IMPL_HPP_
diff --git a/tdigest/test/CMakeLists.txt b/tdigest/test/CMakeLists.txt
new file mode 100644
index 0000000..2382c70
--- /dev/null
+++ b/tdigest/test/CMakeLists.txt
@@ -0,0 +1,41 @@
+# 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.
+
+add_executable(tdigest_test)
+
+target_link_libraries(tdigest_test tdigest common common_test_lib)
+
+set_target_properties(tdigest_test PROPERTIES
+ CXX_STANDARD_REQUIRED YES
+)
+
+file(TO_CMAKE_PATH "${CMAKE_CURRENT_SOURCE_DIR}" tdigest_TEST_BINARY_PATH)
+string(APPEND tdigest_TEST_BINARY_PATH "/")
+target_compile_definitions(tdigest_test
+ PRIVATE
+ TEST_BINARY_INPUT_PATH="${tdigest_TEST_BINARY_PATH}"
+)
+
+add_test(
+ NAME tdigest_test
+ COMMAND tdigest_test
+)
+
+target_sources(tdigest_test
+ PRIVATE
+ tdigest_test.cpp
+)
diff --git a/tdigest/test/tdigest_test.cpp b/tdigest/test/tdigest_test.cpp
new file mode 100644
index 0000000..e90faa7
--- /dev/null
+++ b/tdigest/test/tdigest_test.cpp
@@ -0,0 +1,111 @@
+/*
+ * 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.
+ */
+
+#include <catch2/catch.hpp>
+#include <iostream>
+
+#include "tdigest.hpp"
+
+namespace datasketches {
+
+TEST_CASE("empty", "[tdigest]") {
+ tdigest_double td(10);
+// std::cout << td.to_string();
+ REQUIRE(td.is_empty());
+ REQUIRE(td.get_k() == 10);
+ REQUIRE(td.get_total_weight() == 0);
+ REQUIRE_THROWS_AS(td.get_min_value(), std::runtime_error);
+ REQUIRE_THROWS_AS(td.get_max_value(), std::runtime_error);
+ REQUIRE_THROWS_AS(td.get_rank(0), std::runtime_error);
+ REQUIRE_THROWS_AS(td.get_quantile(0.5), std::runtime_error);
+}
+
+TEST_CASE("one value", "[tdigest]") {
+ tdigest_double td(100);
+ td.update(1);
+ REQUIRE(td.get_k() == 100);
+ REQUIRE(td.get_total_weight() == 1);
+ REQUIRE(td.get_min_value() == 1);
+ REQUIRE(td.get_max_value() == 1);
+ REQUIRE(td.get_rank(0.99) == 0);
+ REQUIRE(td.get_rank(1) == 0.5);
+ REQUIRE(td.get_rank(1.01) == 1);
+}
+
+TEST_CASE("many values", "[tdigest]") {
+ const size_t n = 10000;
+ tdigest_double td(100);
+ for (size_t i = 0; i < n; ++i) td.update(i);
+// td.compress();
+// std::cout << td.to_string(true);
+ REQUIRE_FALSE(td.is_empty());
+ REQUIRE(td.get_total_weight() == n);
+ REQUIRE(td.get_min_value() == 0);
+ REQUIRE(td.get_max_value() == n - 1);
+ REQUIRE(td.get_rank(0) == Approx(0).margin(0.0001));
+ REQUIRE(td.get_rank(n / 4) == Approx(0.25).margin(0.0001));
+ REQUIRE(td.get_rank(n / 2) == Approx(0.5).margin(0.0001));
+ REQUIRE(td.get_rank(n * 3 / 4) == Approx(0.75).margin(0.0001));
+ REQUIRE(td.get_rank(n) == 1);
+}
+
+TEST_CASE("rank - two values", "[tdigest]") {
+ tdigest_double td(100);
+ td.update(1);
+ td.update(2);
+// td.compress();
+// std::cout << td.to_string(true);
+ REQUIRE(td.get_rank(0.99) == 0);
+ REQUIRE(td.get_rank(1) == 0.25);
+ REQUIRE(td.get_rank(1.25) == 0.375);
+ REQUIRE(td.get_rank(1.5) == 0.5);
+ REQUIRE(td.get_rank(1.75) == 0.625);
+ REQUIRE(td.get_rank(2) == 0.75);
+ REQUIRE(td.get_rank(2.01) == 1);
+}
+
+TEST_CASE("rank - repeated value", "[tdigest]") {
+ tdigest_double td(100);
+ td.update(1);
+ td.update(1);
+ td.update(1);
+ td.update(1);
+// td.compress();
+// std::cout << td.to_string(true);
+ REQUIRE(td.get_rank(0.99) == 0);
+ REQUIRE(td.get_rank(1) == 0.5);
+ REQUIRE(td.get_rank(1.01) == 1);
+}
+
+TEST_CASE("rank - repeated block", "[tdigest]") {
+ tdigest_double td(100);
+ td.update(1);
+ td.update(2);
+ td.update(2);
+ td.update(3);
+// td.compress();
+// std::cout << td.to_string(true);
+ REQUIRE(td.get_rank(0.99) == 0);
+ REQUIRE(td.get_rank(1) == 0.125);
+ REQUIRE(td.get_rank(2) == 0.5);
+ REQUIRE(td.get_rank(3) == 0.875);
+ REQUIRE(td.get_rank(3.01) == 1);
+}
+
+} /* namespace datasketches */
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org