Merge pull request #194 from apache/req_python
Req python
diff --git a/kll/include/kll_sketch.hpp b/kll/include/kll_sketch.hpp
index af36ceb..bbca76f 100644
--- a/kll/include/kll_sketch.hpp
+++ b/kll/include/kll_sketch.hpp
@@ -203,6 +203,12 @@
bool is_empty() const;
/**
+ * Returns configured parameter k
+ * @return parameter k
+ */
+ uint16_t get_k() const;
+
+ /**
* Returns the length of the input stream.
* @return stream length
*/
diff --git a/kll/include/kll_sketch_impl.hpp b/kll/include/kll_sketch_impl.hpp
index 90d3be7..0e0ef87 100644
--- a/kll/include/kll_sketch_impl.hpp
+++ b/kll/include/kll_sketch_impl.hpp
@@ -234,6 +234,11 @@
}
template<typename T, typename C, typename S, typename A>
+uint16_t kll_sketch<T, C, S, A>::get_k() const {
+ return k_;
+}
+
+template<typename T, typename C, typename S, typename A>
uint64_t kll_sketch<T, C, S, A>::get_n() const {
return n_;
}
diff --git a/kll/test/kll_sketch_test.cpp b/kll/test/kll_sketch_test.cpp
index 13f7673..26ee7dd 100644
--- a/kll/test/kll_sketch_test.cpp
+++ b/kll/test/kll_sketch_test.cpp
@@ -471,6 +471,9 @@
REQUIRE(sketch2.get_min_value() == n);
REQUIRE(sketch2.get_max_value() == 2.0f * n - 1);
+ REQUIRE(sketch1.get_k() == 256);
+ REQUIRE(sketch2.get_k() == 128);
+
REQUIRE(sketch1.get_normalized_rank_error(false) < sketch2.get_normalized_rank_error(false));
REQUIRE(sketch1.get_normalized_rank_error(true) < sketch2.get_normalized_rank_error(true));
diff --git a/python/CMakeLists.txt b/python/CMakeLists.txt
index e1d8eb1..0b76799 100644
--- a/python/CMakeLists.txt
+++ b/python/CMakeLists.txt
@@ -35,6 +35,7 @@
fi
theta
sampling
+ req
pybind11::module
)
@@ -57,5 +58,6 @@
src/fi_wrapper.cpp
src/theta_wrapper.cpp
src/vo_wrapper.cpp
+ src/req_wrapper.cpp
src/vector_of_kll.cpp
)
diff --git a/python/README.md b/python/README.md
index 84e5e61..5153405 100644
--- a/python/README.md
+++ b/python/README.md
@@ -1,4 +1,4 @@
-# Python Wrapper for Apache Datasketches
+# Python Wrapper for Apache DataSketches
## Installation
@@ -43,9 +43,12 @@
## Available Sketch Classes
-- KLL
+- KLL (Absolute Error Quantiles)
- `kll_ints_sketch`
- `kll_floats_sketch`
+- REQ (Relative Error Quantiles)
+ - `req_ints_sketch`
+ - `req_floats_sketch`
- Frequent Items
- `frequent_strings_sketch`
- Error types are `frequent_items_error_type.{NO_FALSE_NEGATIVES | NO_FALSE_POSITIVES}`
diff --git a/python/src/datasketches.cpp b/python/src/datasketches.cpp
index 288c145..4ef491b 100644
--- a/python/src/datasketches.cpp
+++ b/python/src/datasketches.cpp
@@ -27,6 +27,7 @@
void init_cpc(py::module& m);
void init_theta(py::module& m);
void init_vo(py::module& m);
+void init_req(py::module& m);
void init_vector_of_kll(py::module& m);
PYBIND11_MODULE(datasketches, m) {
@@ -36,5 +37,6 @@
init_cpc(m);
init_theta(m);
init_vo(m);
+ init_req(m);
init_vector_of_kll(m);
}
diff --git a/python/src/kll_wrapper.cpp b/python/src/kll_wrapper.cpp
index 8ffdc12..d356358 100644
--- a/python/src/kll_wrapper.cpp
+++ b/python/src/kll_wrapper.cpp
@@ -130,6 +130,8 @@
"Produces a string summary of the sketch")
.def("is_empty", &kll_sketch<T>::is_empty,
"Returns True if the sketch is empty, otherwise False")
+ .def("get_k", &kll_sketch<T>::get_k,
+ "Returns the configured parameter k")
.def("get_n", &kll_sketch<T>::get_n,
"Returns the length of the input stream")
.def("get_num_retained", &kll_sketch<T>::get_num_retained,
@@ -198,7 +200,7 @@
"If pmf is True, returns the 'double-sided' normalized rank error for the get_PMF() function.\n"
"Otherwise, it is the 'single-sided' normalized rank error for all the other queries.\n"
"Constants were derived as the best fit to 99 percentile empirically measured max error in thousands of trials")
- .def("serialize", &dspy::kll_sketch_serialize<T>, "Serailizes the sketch into a bytes object")
+ .def("serialize", &dspy::kll_sketch_serialize<T>, "Serializes the sketch into a bytes object")
.def_static("deserialize", &dspy::kll_sketch_deserialize<T>, "Deserializes the sketch from a bytes object")
;
}
diff --git a/python/src/req_wrapper.cpp b/python/src/req_wrapper.cpp
new file mode 100644
index 0000000..9ef0b87
--- /dev/null
+++ b/python/src/req_wrapper.cpp
@@ -0,0 +1,246 @@
+/*
+ * 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 "req_sketch.hpp"
+
+#include <pybind11/pybind11.h>
+#include <pybind11/stl.h>
+#include <pybind11/numpy.h>
+#include <sstream>
+#include <vector>
+
+namespace py = pybind11;
+
+namespace datasketches {
+
+namespace python {
+
+template<typename T>
+req_sketch<T> req_sketch_deserialize(py::bytes sk_bytes) {
+ std::string sk_str = sk_bytes; // implicit cast
+ return req_sketch<T>::deserialize(sk_str.c_str(), sk_str.length());
+}
+
+template<typename T>
+py::object req_sketch_serialize(const req_sketch<T>& sk) {
+ auto ser_result = sk.serialize();
+ return py::bytes((char*)ser_result.data(), ser_result.size());
+}
+
+// maybe possible to disambiguate the static vs method rank error calls, but
+// this is easier for now
+template<typename T>
+double req_sketch_generic_normalized_rank_error(uint16_t k, bool pmf) {
+ return req_sketch<T>::get_normalized_rank_error(k, pmf);
+}
+
+template<typename T>
+double req_sketch_get_rank(const req_sketch<T>& sk,
+ const T& item,
+ bool inclusive) {
+ if (inclusive)
+ return sk.template get_rank<true>(item);
+ else
+ return sk.template get_rank<false>(item);
+}
+
+template<typename T>
+T req_sketch_get_quantile(const req_sketch<T>& sk,
+ double rank,
+ bool inclusive) {
+ if (inclusive)
+ return T(sk.template get_quantile<true>(rank));
+ else
+ return T(sk.template get_quantile<false>(rank));
+}
+
+template<typename T>
+py::list req_sketch_get_quantiles(const req_sketch<T>& sk,
+ std::vector<double>& fractions,
+ bool inclusive) {
+ size_t n_quantiles = fractions.size();
+ auto result = inclusive
+ ? sk.template get_quantiles<true>(&fractions[0], n_quantiles)
+ : sk.template get_quantiles<false>(&fractions[0], n_quantiles);
+
+ // returning as std::vector<> would copy values to a list anyway
+ py::list list(n_quantiles);
+ for (size_t i = 0; i < n_quantiles; ++i) {
+ list[i] = result[i];
+ }
+
+ return list;
+}
+
+template<typename T>
+py::list req_sketch_get_pmf(const req_sketch<T>& sk,
+ std::vector<T>& split_points,
+ bool inclusive) {
+ size_t n_points = split_points.size();
+ auto result = inclusive
+ ? sk.template get_PMF<true>(&split_points[0], n_points)
+ : sk.template get_PMF<false>(&split_points[0], n_points);
+
+ py::list list(n_points + 1);
+ for (size_t i = 0; i <= n_points; ++i) {
+ list[i] = result[i];
+ }
+
+ return list;
+}
+
+template<typename T>
+py::list req_sketch_get_cdf(const req_sketch<T>& sk,
+ std::vector<T>& split_points,
+ bool inclusive) {
+ size_t n_points = split_points.size();
+ auto result = inclusive
+ ? sk.template get_CDF<true>(&split_points[0], n_points)
+ : sk.template get_CDF<false>(&split_points[0], n_points);
+
+ py::list list(n_points + 1);
+ for (size_t i = 0; i <= n_points; ++i) {
+ list[i] = result[i];
+ }
+
+ return list;
+}
+
+template<typename T>
+void req_sketch_update(req_sketch<T>& sk, py::array_t<T, py::array::c_style | py::array::forcecast> items) {
+ if (items.ndim() != 1) {
+ throw std::invalid_argument("input data must have only one dimension. Found: "
+ + std::to_string(items.ndim()));
+ }
+
+ auto data = items.template unchecked<1>();
+ for (uint32_t i = 0; i < data.size(); ++i) {
+ sk.update(data(i));
+ }
+}
+
+}
+}
+
+namespace dspy = datasketches::python;
+
+template<typename T>
+void bind_req_sketch(py::module &m, const char* name) {
+ using namespace datasketches;
+
+ py::class_<req_sketch<T>>(m, name)
+ .def(py::init<uint16_t, bool>(), py::arg("k")=12, py::arg("is_hra")=true)
+ .def(py::init<const req_sketch<T>&>())
+ .def("update", (void (req_sketch<T>::*)(const T&)) &req_sketch<T>::update, py::arg("item"),
+ "Updates the sketch with the given value")
+ .def("update", &dspy::req_sketch_update<T>, py::arg("array"),
+ "Updates the sketch with the values in the given array")
+ .def("merge", (void (req_sketch<T>::*)(const req_sketch<T>&)) &req_sketch<T>::merge, py::arg("sketch"),
+ "Merges the provided sketch into the this one")
+ .def("__str__", &req_sketch<T>::to_string, py::arg("print_levels")=false, py::arg("print_items")=false,
+ "Produces a string summary of the sketch")
+ .def("to_string", &req_sketch<T>::to_string, py::arg("print_levels")=false, py::arg("print_items")=false,
+ "Produces a string summary of the sketch")
+ .def("is_hra", &req_sketch<T>::is_HRA,
+ "Returns True if the sketch is in High Rank Accuracy mode, otherwise False")
+ .def("is_empty", &req_sketch<T>::is_empty,
+ "Returns True if the sketch is empty, otherwise False")
+ .def("get_k", &req_sketch<T>::get_k,
+ "Returns the configured parameter k")
+ .def("get_n", &req_sketch<T>::get_n,
+ "Returns the length of the input stream")
+ .def("get_num_retained", &req_sketch<T>::get_num_retained,
+ "Returns the number of retained items (samples) in the sketch")
+ .def("is_estimation_mode", &req_sketch<T>::is_estimation_mode,
+ "Returns True if the sketch is in estimation mode, otherwise False")
+ .def("get_min_value", &req_sketch<T>::get_min_value,
+ "Returns the minimum value from the stream. If empty, req_floats_sketch returns nan; req_ints_sketch throws a RuntimeError")
+ .def("get_max_value", &req_sketch<T>::get_max_value,
+ "Returns the maximum value from the stream. If empty, req_floats_sketch returns nan; req_ints_sketch throws a RuntimeError")
+ .def("get_quantile", &dspy::req_sketch_get_quantile<T>, py::arg("rank"), py::arg("inclusive")=false,
+ "Returns an approximation to the value of the data item "
+ "that would be preceded by the given fraction of a hypothetical sorted "
+ "version of the input stream so far.\n"
+ "Note that this method has a fairly large overhead (microseconds instead of nanoseconds) "
+ "so it should not be called multiple times to get different quantiles from the same "
+ "sketch. Instead use get_quantiles(), which pays the overhead only once.\n"
+ "For req_floats_sketch: if the sketch is empty this returns nan. "
+ "For req_ints_sketch: if the sketch is empty this throws a RuntimeError.")
+ .def("get_quantiles", &dspy::req_sketch_get_quantiles<T>, py::arg("ranks"), py::arg("inclusive")=false,
+ "This is a more efficient multiple-query version of get_quantile().\n"
+ "This returns an array that could have been generated by using get_quantile() for each "
+ "fractional rank separately, but would be very inefficient. "
+ "This method incurs the internal set-up overhead once and obtains multiple quantile values in "
+ "a single query. It is strongly recommend that this method be used instead of multiple calls "
+ "to get_quantile().\n"
+ "If the sketch is empty this returns an empty vector.")
+ .def("get_rank", &dspy::req_sketch_get_rank<T>, py::arg("item"), py::arg("inclusive")=false,
+ "Returns an approximation to the normalized (fractional) rank of the given value from 0 to 1, inclusive.\n"
+ "The resulting approximation has a probabilistic guarantee that can be obtained from the "
+ "get_normalized_rank_error(False) function.\n"
+ "If the sketch is empty this returns nan.")
+ .def("get_pmf", &dspy::req_sketch_get_pmf<T>, py::arg("split_points"), py::arg("inclusive")=false,
+ "Returns an approximation to the Probability Mass Function (PMF) of the input stream "
+ "given a set of split points (values).\n"
+ "The resulting approximations have a probabilistic guarantee that can be obtained from the "
+ "get_normalized_rank_error(True) function.\n"
+ "If the sketch is empty this returns an empty vector.\n"
+ "split_points is an array of m unique, monotonically increasing float values "
+ "that divide the real number line into m+1 consecutive disjoint intervals.\n"
+ "The definition of an 'interval' is inclusive of the left split point (or minimum value) and "
+ "exclusive of the right split point, with the exception that the last interval will include "
+ "the maximum value.\n"
+ "It is not necessary to include either the min or max values in these split points.")
+ .def("get_cdf", &dspy::req_sketch_get_cdf<T>, py::arg("split_points"), py::arg("inclusive")=false,
+ "Returns an approximation to the Cumulative Distribution Function (CDF), which is the "
+ "cumulative analog of the PMF, of the input stream given a set of split points (values).\n"
+ "The resulting approximations have a probabilistic guarantee that can be obtained from the "
+ "get_normalized_rank_error(True) function.\n"
+ "If the sketch is empty this returns an empty vector.\n"
+ "split_points is an array of m unique, monotonically increasing float values "
+ "that divide the real number line into m+1 consecutive disjoint intervals.\n"
+ "The definition of an 'interval' is inclusive of the left split point (or minimum value) and "
+ "exclusive of the right split point, with the exception that the last interval will include "
+ "the maximum value.\n"
+ "It is not necessary to include either the min or max values in these split points.")
+ .def("get_rank_lower_bound", &req_sketch<T>::get_rank_lower_bound, py::arg("rank"), py::arg("num_std_dev"),
+ "Returns an approximate lower bound on the given normalized rank.\n"
+ "Normalized rank must be a value between 0.0 and 1.0 (inclusive); "
+ "the number of standard deviations must be 1, 2, or 3.")
+ .def("get_rank_upper_bound", &req_sketch<T>::get_rank_upper_bound, py::arg("rank"), py::arg("num_std_dev"),
+ "Returns an approximate upper bound on the given normalized rank.\n"
+ "Normalized rank must be a value between 0.0 and 1.0 (inclusive); "
+ "the number of standard deviations must be 1, 2, or 3.")
+ .def_static("get_RSE", &req_sketch<T>::get_RSE,
+ py::arg("k"), py::arg("rank"), py::arg("is_hra"), py::arg("n"),
+ "Returns an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]). "
+ "Derived from Lemma 12 in http://arxiv.org/abs/2004.01668v2, but the constant factors have been "
+ "modified based on empirical measurements, for a given value of parameter k.\n"
+ "Normalized rank must be a value between 0.0 and 1.0 (inclusive). If is_hra is True, uses high "
+ "rank accuracy mode, else low rank accuracy. N is an estimate of the total number of points "
+ "provided to the sketch.")
+ .def("serialize", &dspy::req_sketch_serialize<T>, "Serializes the sketch into a bytes object")
+ .def_static("deserialize", &dspy::req_sketch_deserialize<T>, "Deserializes the sketch from a bytes object")
+ ;
+}
+
+void init_req(py::module &m) {
+ bind_req_sketch<int>(m, "req_ints_sketch");
+ bind_req_sketch<float>(m, "req_floats_sketch");
+}
diff --git a/python/tests/kll_test.py b/python/tests/kll_test.py
index abe92ec..696260f 100644
--- a/python/tests/kll_test.py
+++ b/python/tests/kll_test.py
@@ -16,9 +16,7 @@
# under the License.
import unittest
-from datasketches import (kll_ints_sketch, kll_floats_sketch,
- vector_of_kll_ints_sketches,
- vector_of_kll_floats_sketches)
+from datasketches import kll_ints_sketch, kll_floats_sketch
import numpy as np
class KllTest(unittest.TestCase):
@@ -59,6 +57,7 @@
self.assertFalse(kll.is_empty())
self.assertTrue(kll.is_estimation_mode())
self.assertEqual(kll.get_n(), n)
+ self.assertEqual(kll.get_k(), k)
self.assertLess(kll.get_num_retained(), n)
# merging itself will double the number of items the sketch has seen
@@ -86,6 +85,7 @@
self.assertEqual(kll.get_n(), n)
self.assertFalse(kll.is_empty())
self.assertFalse(kll.is_estimation_mode()) # n < k
+ self.assertEqual(kll.get_k(), k)
pmf = kll.get_pmf([round(n/2)])
self.assertIsNotNone(pmf)
diff --git a/python/tests/req_test.py b/python/tests/req_test.py
new file mode 100644
index 0000000..1e39bb7
--- /dev/null
+++ b/python/tests/req_test.py
@@ -0,0 +1,126 @@
+# 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.
+
+import unittest
+from datasketches import req_ints_sketch, req_floats_sketch
+import numpy as np
+
+class reqTest(unittest.TestCase):
+ def test_req_example(self):
+ k = 12
+ n = 2 ** 20
+
+ # create a sketch and inject ~1 million N(0,1) points as an array and as a single item
+ req = req_floats_sketch(k, True) # high rank accuracy
+ req.update(np.random.normal(size=n-1))
+ req.update(0.0)
+
+ # 0 should be near the median
+ self.assertAlmostEqual(0.5, req.get_rank(0.0), delta=0.03)
+
+ # the median should be near 0
+ self.assertAlmostEqual(0.0, req.get_quantile(0.5), delta=0.03)
+
+ # we also track the min/max independently from the rest of the data
+ # which lets us know the full observed data range
+ self.assertLessEqual(req.get_min_value(), req.get_quantile(0.01))
+ self.assertLessEqual(0.0, req.get_rank(req.get_min_value()))
+ self.assertGreaterEqual(req.get_max_value(), req.get_quantile(0.99))
+ self.assertGreaterEqual(1.0, req.get_rank(req.get_max_value()))
+
+ # we can also extract a list of values at a time,
+ # here the values should give us something close to [-2, -1, 0, 1, 2].
+ # then get the CDF, which will return something close to
+ # the original values used in get_quantiles()
+ # finally, can check the normalized rank error bound
+ pts = req.get_quantiles([0.0228, 0.1587, 0.5, 0.8413, 0.9772])
+ cdf = req.get_cdf(pts) # include 1.0 at end to account for all probability mass
+ self.assertEqual(len(cdf), len(pts)+1)
+
+ # For relative error quantiles, the error depends on the actual rank
+ # so we need to use that to detemrine the bounds
+ est = req.get_rank(0.999, True)
+ lb = req.get_rank_lower_bound(est, 1)
+ ub = req.get_rank_upper_bound(est, 1)
+ self.assertLessEqual(lb, est)
+ self.assertLessEqual(est, ub)
+
+ # and a few basic queries about the sketch
+ self.assertFalse(req.is_empty())
+ self.assertTrue(req.is_estimation_mode())
+ self.assertEqual(req.get_n(), n)
+ self.assertLess(req.get_num_retained(), n)
+ self.assertEqual(req.get_k(), k)
+
+ # merging itself will double the number of items the sketch has seen
+ req.merge(req)
+ self.assertEqual(req.get_n(), 2*n)
+
+ # we can then serialize and reconstruct the sketch
+ req_bytes = req.serialize()
+ new_req = req.deserialize(req_bytes)
+ self.assertEqual(req.get_num_retained(), new_req.get_num_retained())
+ self.assertEqual(req.get_min_value(), new_req.get_min_value())
+ self.assertEqual(req.get_max_value(), new_req.get_max_value())
+ self.assertEqual(req.get_quantile(0.7), new_req.get_quantile(0.7))
+ self.assertEqual(req.get_rank(0.0), new_req.get_rank(0.0))
+
+ def test_req_ints_sketch(self):
+ k = 100
+ n = 10
+ req = req_ints_sketch(k)
+ for i in range(0, n):
+ req.update(i)
+
+ self.assertEqual(req.get_min_value(), 0)
+ self.assertEqual(req.get_max_value(), n-1)
+ self.assertEqual(req.get_n(), n)
+ self.assertFalse(req.is_empty())
+ self.assertFalse(req.is_estimation_mode()) # n < k
+ self.assertEqual(req.get_k(), k)
+
+ pmf = req.get_pmf([round(n/2)])
+ self.assertIsNotNone(pmf)
+ self.assertEqual(len(pmf), 2)
+
+ cdf = req.get_cdf([round(n/2)])
+ self.assertIsNotNone(cdf)
+ self.assertEqual(len(cdf), 2)
+
+ self.assertEqual(req.get_quantile(0.5), round(n/2))
+ quants = req.get_quantiles([0.25, 0.5, 0.75])
+ self.assertIsNotNone(quants)
+ self.assertEqual(len(quants), 3)
+
+ self.assertEqual(req.get_rank(round(n/2)), 0.5)
+
+ # merge self
+ req.merge(req)
+ self.assertEqual(req.get_n(), 2 * n)
+
+ sk_bytes = req.serialize()
+ self.assertTrue(isinstance(req_ints_sketch.deserialize(sk_bytes), req_ints_sketch))
+
+ def test_req_floats_sketch(self):
+ # already tested ints and it's templatized, so just make sure it instantiates properly
+ k = 75
+ req = req_floats_sketch(k, False) # low rank accuracy
+ self.assertTrue(req.is_empty())
+ self.assertFalse(req.is_hra())
+
+if __name__ == '__main__':
+ unittest.main()
diff --git a/setup.py b/setup.py
index 83cd994..5fb3cd8 100644
--- a/setup.py
+++ b/setup.py
@@ -80,9 +80,9 @@
setup(
name='datasketches',
version='2.2.0.dev0',
- author='Apache Datasketches Developers',
+ author='Apache DataSketches Developers',
author_email='dev@datasketches.apache.org',
- description='A wrapper for the C++ Apache Datasketches library',
+ description='A wrapper for the C++ Apache DataSketches library',
license='Apache License 2.0',
url='http://datasketches.apache.org',
long_description=open('python/README.md').read(),
