You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by jm...@apache.org on 2020/02/15 09:04:21 UTC
[incubator-datasketches-cpp] branch sampling updated (4b96ede ->
4f91eba)
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a change to branch sampling
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git.
from 4b96ede [WIP, almost done] improve serialization coverage, update tests to allow for equivalence when random selection invovled in get_result()
new 7e3e8ab finish deserialization tests from java, describe code used to generate java binaries
new 4f91eba add varopt to python, with changes to support human-readable to_string() even if type has no operator<< defined
The 2 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.
Summary of changes:
python/CMakeLists.txt | 2 +
python/src/datasketches.cpp | 2 +
python/src/vo_wrapper.cpp | 120 +++++++++++++++++++++
sampling/include/var_opt_sketch.hpp | 5 +
sampling/include/var_opt_sketch_impl.hpp | 16 ++-
sampling/include/var_opt_union_impl.hpp | 1 -
sampling/test/binaries_from_java.txt | 67 ++++++++++++
sampling/test/var_opt_sketch_test.cpp | 4 +-
sampling/test/var_opt_union_test.cpp | 65 +++--------
...ampling.bin => varopt_sketch_long_sampling.bin} | Bin
...ng_exact.bin => varopt_sketch_string_exact.bin} | Bin
sampling/test/varopt_union_double_sampling.bin | Bin 0 -> 572 bytes
12 files changed, 228 insertions(+), 54 deletions(-)
create mode 100644 python/src/vo_wrapper.cpp
create mode 100644 sampling/test/binaries_from_java.txt
rename sampling/test/{varopt_long_sampling.bin => varopt_sketch_long_sampling.bin} (100%)
rename sampling/test/{varopt_string_exact.bin => varopt_sketch_string_exact.bin} (100%)
create mode 100644 sampling/test/varopt_union_double_sampling.bin
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 02/02: add varopt to python,
with changes to support human-readable to_string() even if type has
no operator<< defined
Posted by jm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch sampling
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit 4f91eba2e7b56d19a3120d5508705e09c7f764c5
Author: Jon Malkin <jm...@users.noreply.github.com>
AuthorDate: Sat Feb 15 01:04:08 2020 -0800
add varopt to python, with changes to support human-readable to_string() even if type has no operator<< defined
---
python/CMakeLists.txt | 2 +
python/src/datasketches.cpp | 2 +
python/src/vo_wrapper.cpp | 120 +++++++++++++++++++++++++++++++
sampling/include/var_opt_sketch.hpp | 5 ++
sampling/include/var_opt_sketch_impl.hpp | 16 ++++-
sampling/include/var_opt_union_impl.hpp | 1 -
6 files changed, 143 insertions(+), 3 deletions(-)
diff --git a/python/CMakeLists.txt b/python/CMakeLists.txt
index 1136382..d1a3f9f 100644
--- a/python/CMakeLists.txt
+++ b/python/CMakeLists.txt
@@ -34,6 +34,7 @@ target_link_libraries(python
cpc
fi
theta
+ sampling
pybind11::module
)
@@ -55,4 +56,5 @@ target_sources(python
src/cpc_wrapper.cpp
src/fi_wrapper.cpp
src/theta_wrapper.cpp
+ src/vo_wrapper.cpp
)
diff --git a/python/src/datasketches.cpp b/python/src/datasketches.cpp
index 158f97c..f8c138a 100644
--- a/python/src/datasketches.cpp
+++ b/python/src/datasketches.cpp
@@ -26,6 +26,7 @@ void init_kll(py::module& m);
void init_fi(py::module& m);
void init_cpc(py::module& m);
void init_theta(py::module& m);
+void init_vo(py::module& m);
PYBIND11_MODULE(datasketches, m) {
init_hll(m);
@@ -33,4 +34,5 @@ PYBIND11_MODULE(datasketches, m) {
init_fi(m);
init_cpc(m);
init_theta(m);
+ init_vo(m);
}
diff --git a/python/src/vo_wrapper.cpp b/python/src/vo_wrapper.cpp
new file mode 100644
index 0000000..a2346e5
--- /dev/null
+++ b/python/src/vo_wrapper.cpp
@@ -0,0 +1,120 @@
+/*
+ * 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 "var_opt_sketch.hpp"
+#include "var_opt_union.hpp"
+
+#include <pybind11/pybind11.h>
+#include <sstream>
+
+namespace py = pybind11;
+
+namespace datasketches {
+namespace python {
+
+template<typename T>
+py::list vo_sketch_get_samples(const var_opt_sketch<T>& sk) {
+ py::list list;
+ for (auto& item : sk) {
+ py::tuple t = py::make_tuple(item.first, item.second);
+ list.append(t);
+ }
+ return list;
+}
+
+template<typename T>
+std::string vo_sketch_to_string(const var_opt_sketch<T>& sk, bool print_items) {
+ if (print_items) {
+ std::ostringstream ss;
+ sk.to_stream(ss);
+ ss << "### VarOpt Sketch Items" << std::endl;
+ int i = 0;
+ for (auto& item : sk) {
+ // item.second is always a double
+ // item.first is an arbitrary py::object, so get the value by
+ // using internal str() method then casting to C++ std::string
+ py::str item_pystr(item.first);
+ std::string item_str = py::cast<std::string>(item_pystr);
+ // item.second is guaranteed to be a double
+ ss << i++ << ": " << item_str << "\twt = " << item.second << std::endl;
+ }
+ return ss.str();
+ } else {
+ return sk.to_string();
+ }
+}
+
+template<typename T>
+std::string vo_union_to_string(const var_opt_union<T>& u) {
+ // no direct access to gadget so we can't easily print the item list
+ // for arbitrary python objects
+ return u.to_string();
+}
+
+}
+}
+
+namespace dspy = datasketches::python;
+
+template<typename T>
+void bind_vo_sketch(py::module &m, const char* name) {
+ using namespace datasketches;
+
+ py::class_<var_opt_sketch<T>>(m, name)
+ .def(py::init<uint32_t>(), py::arg("k"))
+ .def("__str__", &dspy::vo_sketch_to_string<T>, py::arg("print_items"))
+ .def("to_string", &dspy::vo_sketch_to_string<T>, py::arg("print_items"))
+ .def("update", (void (var_opt_sketch<T>::*)(const T&, double)) &var_opt_sketch<T>::update, py::arg("item"), py::arg("weight")=1.0)
+ .def_property_readonly("k", &var_opt_sketch<T>::get_k)
+ .def_property_readonly("n", &var_opt_sketch<T>::get_n)
+ .def_property_readonly("num_samples", &var_opt_sketch<T>::get_num_samples)
+ .def("get_samples", &dspy::vo_sketch_get_samples<T>)
+ .def("is_empty", &var_opt_sketch<T>::is_empty)
+ // As of writing, not yet clear how to serialize arbitrary python objects,
+ // especially in any sort of language-portable way
+ //.def("get_serialized_size_bytes", &var_opt_sketch<T>::get_serialized_size_bytes)
+ //.def("serialize", &dspy::vo_sketch_serialize<T>)
+ //.def_static("deserialize", &dspy::vo_sketch_deserialize<T>)
+ ;
+}
+
+template<typename T>
+void bind_vo_union(py::module &m, const char* name) {
+ using namespace datasketches;
+
+ py::class_<var_opt_union<T>>(m, name)
+ .def(py::init<uint32_t>(), py::arg("max_k"))
+ .def("__str__", &dspy::vo_union_to_string<T>)
+ .def("to_string", &dspy::vo_union_to_string<T>)
+ .def("update", (void (var_opt_union<T>::*)(const var_opt_sketch<T>& sk)) &var_opt_union<T>::update, py::arg("sketch"))
+ .def("get_result", &var_opt_union<T>::get_result)
+ .def("reset", &var_opt_union<T>::reset)
+ // As of writing, not yet clear how to serialize arbitrary python objects,
+ // especially in any sort of language-portable way
+ //.def("get_serialized_size_bytes", &var_opt_sketch<T>::get_serialized_size_bytes)
+ //.def("serialize", &dspy::vo_union_serialize<T>)
+ //.def_static("deserialize", &dspy::vo_union_deserialize<T>)
+ ;
+}
+
+
+void init_vo(py::module &m) {
+ bind_vo_sketch<py::object>(m, "varopt_object_sketch");
+ bind_vo_union<py::object>(m, "varopt_object_uunion");
+}
diff --git a/sampling/include/var_opt_sketch.hpp b/sampling/include/var_opt_sketch.hpp
index 7230537..0f044bd 100644
--- a/sampling/include/var_opt_sketch.hpp
+++ b/sampling/include/var_opt_sketch.hpp
@@ -90,6 +90,11 @@ class var_opt_sketch {
std::ostream& to_stream(std::ostream& os) const;
std::string to_string() const;
+ // These will only work for T with a defined operator<<()
+ // Kept separate to allow to_string() to compile for all types T
+ std::ostream& items_to_stream(std::ostream& os) const;
+ std::string items_to_string() const;
+
subset_summary estimate_subset_sum(std::function<bool(T)> predicate) const;
class const_iterator;
diff --git a/sampling/include/var_opt_sketch_impl.hpp b/sampling/include/var_opt_sketch_impl.hpp
index 4fea686..9673950 100644
--- a/sampling/include/var_opt_sketch_impl.hpp
+++ b/sampling/include/var_opt_sketch_impl.hpp
@@ -687,6 +687,13 @@ std::ostream& var_opt_sketch<T,S,A>::to_stream(std::ostream& os) const {
os << " weight_r : " << total_wt_r_ << std::endl;
os << " Current size : " << curr_items_alloc_ << std::endl;
os << " Resize factor: " << (1 << rf_) << std::endl;
+ os << "### END SKETCH SUMMARY" << std::endl;
+
+ return os;
+}
+
+template<typename T, typename S, typename A>
+std::ostream& var_opt_sketch<T,S,A>::items_to_stream(std::ostream& os) const {
os << "### Sketch Items" << std::endl;
uint32_t print_length = (n_ < k_ ? n_ : k_ + 1);
@@ -697,8 +704,6 @@ std::ostream& var_opt_sketch<T,S,A>::to_stream(std::ostream& os) const {
os << i << ": " << data_[i] << "\twt = " << weights_[i] << std::endl;
}
}
-
- os << "### END SKETCH SUMMARY" << std::endl;
return os;
}
@@ -710,6 +715,13 @@ std::string var_opt_sketch<T,S,A>::to_string() const {
return ss.str();
}
+template <typename T, typename S, typename A>
+std::string var_opt_sketch<T,S,A>::items_to_string() const {
+ std::ostringstream ss;
+ items_to_stream(ss);
+ return ss.str();
+}
+
template<typename T, typename S, typename A>
void var_opt_sketch<T,S,A>::update(const T& item, double weight, bool mark) {
if (weight <= 0.0) {
diff --git a/sampling/include/var_opt_union_impl.hpp b/sampling/include/var_opt_union_impl.hpp
index dd87ca8..adb21d4 100644
--- a/sampling/include/var_opt_union_impl.hpp
+++ b/sampling/include/var_opt_union_impl.hpp
@@ -313,7 +313,6 @@ std::string var_opt_union<T,S,A>::to_string() const {
return ss.str();
}
-
template<typename T, typename S, typename A>
void var_opt_union<T,S,A>::update(var_opt_sketch<T,S,A>& sk) {
merge_into(sk);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 01/02: finish deserialization tests
from java, describe code used to generate java binaries
Posted by jm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch sampling
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit 7e3e8ab36d8978e2dfd95cf6468550509168172b
Author: Jon Malkin <jm...@users.noreply.github.com>
AuthorDate: Fri Feb 14 11:39:27 2020 -0800
finish deserialization tests from java, describe code used to generate java binaries
---
sampling/test/binaries_from_java.txt | 67 +++++++++++++++++++++
sampling/test/var_opt_sketch_test.cpp | 4 +-
sampling/test/var_opt_union_test.cpp | 65 +++++---------------
...ampling.bin => varopt_sketch_long_sampling.bin} | Bin
...ng_exact.bin => varopt_sketch_string_exact.bin} | Bin
sampling/test/varopt_union_double_sampling.bin | Bin 0 -> 572 bytes
6 files changed, 85 insertions(+), 51 deletions(-)
diff --git a/sampling/test/binaries_from_java.txt b/sampling/test/binaries_from_java.txt
new file mode 100644
index 0000000..eb3ea30
--- /dev/null
+++ b/sampling/test/binaries_from_java.txt
@@ -0,0 +1,67 @@
+/*
+ * 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.
+ */
+
+Code snippets used to generate to generate the binary images from Java.
+Heavy items have negative weights to allow a simple predicate to filter
+heavy vs light sketch entires.
+
+
+varopt_sketch_long_sampling.bin:
+final VarOptItemsSketch<String> sk = VarOptItemsSketch.newInstance(1024);
+for (int i = 1; i <= 200; ++i) {
+ sk.update(Integer.toString(i), 1000.0 / i);
+}
+byte[] bytes = sk.toByteArray(new ArrayOfStringsSerDe());
+
+
+varopt_sketch_string_exact.bin:
+final VarOptItemsSketch<Long> sk = VarOptItemsSketch.newInstance(1024);
+for (long i = 0; i < 2000; ++i) {
+ sk.update(i, 1.0);
+}
+sk.update(-1L, 100000.0);
+sk.update(-2L, 110000.0);
+sk.update(-3L, 120000.0);
+byte[] bytes = sk.toByteArray(new ArrayOfLongsSerDe());
+
+
+varopt_union_double_sampling.bin:
+// parallels small samplign sketch test
+final int kSmall = 16;
+final int n1 = 32;
+final int n2 = 64;
+final int kMax = 128;
+
+// small k sketch, but sampling
+VarOptItemsSketch<Double> sketch = VarOptItemsSketch.newInstance(kSmall);
+for (int i = 0; i < n1; ++i) {
+ sketch.update(1.0 * i, 1.0);
+}
+sketch.update(-1.0, n1 * n1); // add a heavy item
+
+final VarOptItemsUnion<Double> union = VarOptItemsUnion.newInstance(kMax);
+union.update(sketch);
+
+// another one, but different n to get a different per-item weight
+sketch = VarOptItemsSketch.newInstance(kSmall);
+for (int i = 0; i < n2; ++i) {
+ sketch.update(1.0 * i, 1.0);
+}
+union.update(sketch);
+byte[] bytes = union.toByteArray(new ArrayOfDoublesSerDe());
diff --git a/sampling/test/var_opt_sketch_test.cpp b/sampling/test/var_opt_sketch_test.cpp
index a2819f3..2472a3a 100644
--- a/sampling/test/var_opt_sketch_test.cpp
+++ b/sampling/test/var_opt_sketch_test.cpp
@@ -513,7 +513,7 @@ class var_opt_sketch_test: public CppUnit::TestFixture {
void deserialize_exact_from_java() {
std::ifstream is;
is.exceptions(std::ios::failbit | std::ios::badbit);
- is.open(testBinaryInputPath + "varopt_string_exact.bin", std::ios::binary);
+ is.open(testBinaryInputPath + "varopt_sketch_string_exact.bin", std::ios::binary);
var_opt_sketch<std::string> sketch = var_opt_sketch<std::string>::deserialize(is);
CPPUNIT_ASSERT(!sketch.is_empty());
CPPUNIT_ASSERT_EQUAL((uint32_t) 1024, sketch.get_k());
@@ -529,7 +529,7 @@ class var_opt_sketch_test: public CppUnit::TestFixture {
void deserialize_sampling_from_java() {
std::ifstream is;
is.exceptions(std::ios::failbit | std::ios::badbit);
- is.open(testBinaryInputPath + "varopt_long_sampling.bin", std::ios::binary);
+ is.open(testBinaryInputPath + "varopt_sketch_long_sampling.bin", std::ios::binary);
var_opt_sketch<int64_t> sketch = var_opt_sketch<int64_t>::deserialize(is);
CPPUNIT_ASSERT(!sketch.is_empty());
CPPUNIT_ASSERT_EQUAL((uint32_t) 1024, sketch.get_k());
diff --git a/sampling/test/var_opt_union_test.cpp b/sampling/test/var_opt_union_test.cpp
index 45f92ab..fd3460b 100644
--- a/sampling/test/var_opt_union_test.cpp
+++ b/sampling/test/var_opt_union_test.cpp
@@ -54,8 +54,7 @@ class var_opt_union_test: public CppUnit::TestFixture {
CPPUNIT_TEST(serialize_empty);
CPPUNIT_TEST(serialize_exact);
CPPUNIT_TEST(serialize_sampling);
- // CPPUNIT_TEST(deserialize_exact_from_java);
- // CPPUNIT_TEST(deserialize_sampling_from_java);
+ CPPUNIT_TEST(deserialize_from_java);
CPPUNIT_TEST_SUITE_END();
var_opt_sketch<int> create_unweighted_sketch(uint32_t k, uint64_t n) {
@@ -316,7 +315,7 @@ class var_opt_union_test: public CppUnit::TestFixture {
CPPUNIT_ASSERT_DOUBLES_EQUAL(expected_wt + (n1 * n1), ss.total_sketch_weight, EPS);
CPPUNIT_ASSERT_LESS(k_max, result.get_k());
- // check tha tmark information is preserved as expected
+ // check that mark information is preserved as expected
compare_serialization_deserialization(u, false);
}
@@ -344,54 +343,22 @@ class var_opt_union_test: public CppUnit::TestFixture {
compare_serialization_deserialization(u);
}
-/**********************************************************/
-
-
- void test_union() {
- var_opt_union<int> u(10);
-
- var_opt_sketch<int> sk = create_unweighted_sketch(9, 100);
- u.update(sk);
- std::cout << u.to_string() << std::endl;
-
- auto vec = u.serialize();
- std::cout << vec.size() << "\t" << vec.capacity() << "\t" << vec.empty() << std::endl;
- }
-
- void deserialize_exact_from_java() {
+ void deserialize_from_java() {
std::ifstream is;
is.exceptions(std::ios::failbit | std::ios::badbit);
- is.open(testBinaryInputPath + "varopt_string_exact.bin", std::ios::binary);
- var_opt_sketch<std::string> sketch = var_opt_sketch<std::string>::deserialize(is);
- CPPUNIT_ASSERT(!sketch.is_empty());
- CPPUNIT_ASSERT_EQUAL((uint32_t) 1024, sketch.get_k());
- CPPUNIT_ASSERT_EQUAL((uint64_t) 200, sketch.get_n());
- CPPUNIT_ASSERT_EQUAL((uint32_t) 200, sketch.get_num_samples());
- subset_summary ss = sketch.estimate_subset_sum([](std::string x){ return true; });
-
- double tgt_wt = 0.0;
- for (int i = 1; i <= 200; ++i) { tgt_wt += 1000.0 / i; }
- CPPUNIT_ASSERT_DOUBLES_EQUAL(tgt_wt, ss.total_sketch_weight, EPS);
- }
-
- void deserialize_sampling_from_java() {
- std::ifstream is;
- is.exceptions(std::ios::failbit | std::ios::badbit);
- is.open(testBinaryInputPath + "varopt_long_sampling.bin", std::ios::binary);
- var_opt_sketch<int64_t> sketch = var_opt_sketch<int64_t>::deserialize(is);
- CPPUNIT_ASSERT(!sketch.is_empty());
- CPPUNIT_ASSERT_EQUAL((uint32_t) 1024, sketch.get_k());
- CPPUNIT_ASSERT_EQUAL((uint64_t) 2003, sketch.get_n());
- CPPUNIT_ASSERT_EQUAL(sketch.get_k(), sketch.get_num_samples());
- subset_summary ss = sketch.estimate_subset_sum([](int64_t x){ return true; });
- CPPUNIT_ASSERT_DOUBLES_EQUAL(332000.0, ss.estimate, EPS);
- CPPUNIT_ASSERT_DOUBLES_EQUAL(332000.0, ss.total_sketch_weight, EPS);
-
- ss = sketch.estimate_subset_sum([](int64_t x){ return x < 0; });
- CPPUNIT_ASSERT_DOUBLES_EQUAL(330000.0, ss.estimate, 0.0);
-
- ss = sketch.estimate_subset_sum([](int64_t x){ return x >= 0; });
- CPPUNIT_ASSERT_DOUBLES_EQUAL(2000.0, ss.estimate, EPS);
+ is.open(testBinaryInputPath + "varopt_union_double_sampling.bin", std::ios::binary);
+ var_opt_union<double> u = var_opt_union<double>::deserialize(is);
+
+ // must reduce k in the process, like in small_sampling_sketch()
+ var_opt_sketch<double> result = u.get_result();
+ CPPUNIT_ASSERT(!result.is_empty());
+ CPPUNIT_ASSERT_EQUAL((uint64_t) 97, result.get_n());
+
+ double expected_wt = 96.0;// light items -- ignoring the heavy one
+ subset_summary ss = result.estimate_subset_sum([](float x){return x >= 0;});
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(expected_wt, ss.estimate, EPS);
+ CPPUNIT_ASSERT_DOUBLES_EQUAL(expected_wt + 1024.0, ss.total_sketch_weight, EPS);
+ CPPUNIT_ASSERT_LESS((uint32_t) 128, result.get_k());
}
};
diff --git a/sampling/test/varopt_long_sampling.bin b/sampling/test/varopt_sketch_long_sampling.bin
similarity index 100%
rename from sampling/test/varopt_long_sampling.bin
rename to sampling/test/varopt_sketch_long_sampling.bin
diff --git a/sampling/test/varopt_string_exact.bin b/sampling/test/varopt_sketch_string_exact.bin
similarity index 100%
rename from sampling/test/varopt_string_exact.bin
rename to sampling/test/varopt_sketch_string_exact.bin
diff --git a/sampling/test/varopt_union_double_sampling.bin b/sampling/test/varopt_union_double_sampling.bin
new file mode 100644
index 0000000..b3a229e
Binary files /dev/null and b/sampling/test/varopt_union_double_sampling.bin differ
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org