You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "jmalkin (via GitHub)" <gi...@apache.org> on 2023/04/06 07:31:22 UTC

[GitHub] [datasketches-cpp] jmalkin opened a new pull request, #354: Count min python

jmalkin opened a new pull request, #354:
URL: https://github.com/apache/datasketches-cpp/pull/354

   Adds python support for count_min, using double -- thinking maybe it should be int64_t weights by default instead? Or maybe unsigned if deletions aren't a thing?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


[GitHub] [datasketches-cpp] c-dickens commented on a diff in pull request #354: Count min python

Posted by "c-dickens (via GitHub)" <gi...@apache.org>.
c-dickens commented on code in PR #354:
URL: https://github.com/apache/datasketches-cpp/pull/354#discussion_r1159518470


##########
python/tests/count_min_test.py:
##########
@@ -0,0 +1,86 @@
+# 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 count_min_sketch
+
+class CountMinTest(unittest.TestCase):
+  def test_count_min_example(self):
+    # we'll define target confidence and relative error and use the built-in
+    # methods to determine how many hashes and buckets to use
+    confidence = 0.95
+    num_hashes = count_min_sketch.suggest_num_hashes(confidence)
+    relative_error = 0.01
+    num_buckets = count_min_sketch.suggest_num_buckets(relative_error)
+
+    # now we can create a few empty sketches
+    cm = count_min_sketch(num_hashes, num_buckets)
+    cm2 = count_min_sketch(num_hashes, num_buckets)
+    self.assertTrue(cm.is_empty())
+
+    # we'll use a moderate number of distinct items with
+    # increasing weights, with each item's weight being
+    # equal to its value
+    n = 1000
+    total_wt = 0
+    for i in range(1, n+1):
+      cm.update(i, i)
+      total_wt += i
+    self.assertFalse(cm.is_empty())
+    self.assertEqual(cm.get_total_weight(), total_wt)
+
+    # querying the items, each of them should
+    # have a non-zero count.  the estimate should
+    # be at least i with appropriately behaved bounds.
+    for i in range(1, n+1):
+      val = cm.get_estimate(i)
+      self.assertGreaterEqual(val, i)
+      self.assertGreaterEqual(val, cm.get_lower_bound(i))
+      self.assertGreater(cm.get_upper_bound(i), val)
+
+    # values not in the sketch should have lower estimates, but
+    # are not guaranteed to be zero and will succeed
+    self.assertIsNotNone(cm.get_estimate("not in set"))
+
+    # we can create another sketch with partial overlap
+    # and merge them
+    for i in range(int(n / 2), int(3 * n / 2)):
+      cm2.update(i, i)
+    cm.merge(cm2)
+
+    # and the estimated weight for the meerged values should now be
+    # at least 2x the value
+    self.assertGreaterEqual(cm.get_estimate(n), 2 * n)

Review Comment:
   Is it worth specifying that this only applies to the items in the overlap interval [n/2, n] ?
   Items n+1, ... 3n / 2 - 1 have all been included only once with their weight.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


[GitHub] [datasketches-cpp] coveralls commented on pull request #354: Count min python

Posted by "coveralls (via GitHub)" <gi...@apache.org>.
coveralls commented on PR #354:
URL: https://github.com/apache/datasketches-cpp/pull/354#issuecomment-1498637716

   ## Pull Request Test Coverage Report for [Build 4626637749](https://coveralls.io/builds/58625314)
   
   * **34** of **36**   **(94.44%)**  changed or added relevant lines in **1** file are covered.
   * No unchanged relevant lines lost coverage.
   * Overall coverage decreased (**-0.03%**) to **97.016%**
   
   ---
   
   |  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
   | :-----|--------------|--------|---: |
   | [count/include/count_min_impl.hpp](https://coveralls.io/builds/58625314/source?filename=count%2Finclude%2Fcount_min_impl.hpp#L503) | 34 | 36 | 94.44%
   <!-- | **Total:** | **34** | **36** | **94.44%** | -->
   
   
   |  Totals | [![Coverage Status](https://coveralls.io/builds/58625314/badge)](https://coveralls.io/builds/58625314) |
   | :-- | --: |
   | Change from base [Build 4602996340](https://coveralls.io/builds/58532914): |  -0.03% |
   | Covered Lines: | 5072 |
   | Relevant Lines: | 5228 |
   
   ---
   ##### 💛  - [Coveralls](https://coveralls.io)
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


[GitHub] [datasketches-cpp] jmalkin commented on pull request #354: Count min python

Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on PR #354:
URL: https://github.com/apache/datasketches-cpp/pull/354#issuecomment-1499330691

   Definitely not going to merge before that's resolved


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


[GitHub] [datasketches-cpp] jmalkin merged pull request #354: Count min python

Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin merged PR #354:
URL: https://github.com/apache/datasketches-cpp/pull/354


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


[GitHub] [datasketches-cpp] c-dickens commented on a diff in pull request #354: Count min python

Posted by "c-dickens (via GitHub)" <gi...@apache.org>.
c-dickens commented on code in PR #354:
URL: https://github.com/apache/datasketches-cpp/pull/354#discussion_r1159507184


##########
python/src/count_wrapper.cpp:
##########
@@ -0,0 +1,101 @@
+/*
+ * 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 <pybind11/pybind11.h>
+
+#include "count_min.hpp"
+#include "common_defs.hpp"
+
+namespace py = pybind11;
+
+template<typename W>
+void bind_count_min_sketch(py::module &m, const char* name) {
+  using namespace datasketches;
+
+  py::class_<count_min_sketch<W>>(m, name)
+    .def(py::init<uint8_t, uint32_t, uint64_t>(), py::arg("num_hashes"), py::arg("num_buckets"), py::arg("seed")=DEFAULT_SEED)
+    .def(py::init<const count_min_sketch<W>&>())
+    .def_static("suggest_num_buckets", &count_min_sketch<W>::suggest_num_buckets, py::arg("relative_error"),
+                "Suggests the number of buckets needed to achieve an accuracy within the provided "
+                "relative_error. For example, when relative_error = 0.05, the returned frequency estimates "
+                "satisfy the 'relative_error' guarantee that never overestimates the weights by may "

Review Comment:
   by maty -> but may



##########
python/src/count_wrapper.cpp:
##########
@@ -0,0 +1,101 @@
+/*
+ * 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 <pybind11/pybind11.h>
+
+#include "count_min.hpp"
+#include "common_defs.hpp"
+
+namespace py = pybind11;
+
+template<typename W>
+void bind_count_min_sketch(py::module &m, const char* name) {
+  using namespace datasketches;
+
+  py::class_<count_min_sketch<W>>(m, name)
+    .def(py::init<uint8_t, uint32_t, uint64_t>(), py::arg("num_hashes"), py::arg("num_buckets"), py::arg("seed")=DEFAULT_SEED)
+    .def(py::init<const count_min_sketch<W>&>())
+    .def_static("suggest_num_buckets", &count_min_sketch<W>::suggest_num_buckets, py::arg("relative_error"),
+                "Suggests the number of buckets needed to achieve an accuracy within the provided "
+                "relative_error. For example, when relative_error = 0.05, the returned frequency estimates "
+                "satisfy the 'relative_error' guarantee that never overestimates the weights by may "

Review Comment:
   by may -> but may



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


[GitHub] [datasketches-cpp] c-dickens commented on a diff in pull request #354: Count min python

Posted by "c-dickens (via GitHub)" <gi...@apache.org>.
c-dickens commented on code in PR #354:
URL: https://github.com/apache/datasketches-cpp/pull/354#discussion_r1159507555


##########
python/src/count_wrapper.cpp:
##########
@@ -0,0 +1,101 @@
+/*
+ * 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 <pybind11/pybind11.h>
+
+#include "count_min.hpp"
+#include "common_defs.hpp"
+
+namespace py = pybind11;
+
+template<typename W>
+void bind_count_min_sketch(py::module &m, const char* name) {
+  using namespace datasketches;
+
+  py::class_<count_min_sketch<W>>(m, name)
+    .def(py::init<uint8_t, uint32_t, uint64_t>(), py::arg("num_hashes"), py::arg("num_buckets"), py::arg("seed")=DEFAULT_SEED)
+    .def(py::init<const count_min_sketch<W>&>())
+    .def_static("suggest_num_buckets", &count_min_sketch<W>::suggest_num_buckets, py::arg("relative_error"),
+                "Suggests the number of buckets needed to achieve an accuracy within the provided "
+                "relative_error. For example, when relative_error = 0.05, the returned frequency estimates "
+                "satisfy the 'relative_error' guarantee that never overestimates the weights by may "
+                "underestimate hte weights by 5% of the total weight in the sketch. "

Review Comment:
   hte -> the



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org