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 2024/10/14 08:01:14 UTC
(datasketches-python) branch bloom created (now 77ca90c)
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a change to branch bloom
in repository https://gitbox.apache.org/repos/asf/datasketches-python.git
at 77ca90c WIP: bloom filter. fix issue where t-digest default_k didn't export (dunno why) and temporarily build off master cpp branch
This branch includes the following new commits:
new 77ca90c WIP: bloom filter. fix issue where t-digest default_k didn't export (dunno why) and temporarily build off master cpp branch
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-python) 01/01: WIP: bloom filter. fix issue where t-digest default_k didn't export (dunno why) and temporarily build off master cpp branch
Posted by jm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch bloom
in repository https://gitbox.apache.org/repos/asf/datasketches-python.git
commit 77ca90c474f1a385e9eaa34777a2789887bc9cdc
Author: Jon <jm...@apache.org>
AuthorDate: Mon Oct 14 01:00:58 2024 -0700
WIP: bloom filter. fix issue where t-digest default_k didn't export (dunno why) and temporarily build off master cpp branch
---
CMakeLists.txt | 8 ++-
src/bloom_wrapper.cpp | 161 ++++++++++++++++++++++++++++++++++++++++++++++++
src/datasketches.cpp | 2 +
src/tdigest_wrapper.cpp | 2 +-
4 files changed, 171 insertions(+), 2 deletions(-)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 4e9ba96..8983986 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -17,6 +17,11 @@
cmake_minimum_required(VERSION 3.16.0)
+# version of the code library
+set(DATASKETCHES_CPP_VERSION master)
+
+set(CMAKE_BUILD_TYPE "Debug")
+
string(TIMESTAMP DT %Y%m%d UTC)
string(TIMESTAMP HHMM %H%M UTC)
configure_file(version.cfg.in version.cfg @ONLY)
@@ -109,6 +114,7 @@ target_sources(python
src/ks_wrapper.cpp
src/count_wrapper.cpp
src/tdigest_wrapper.cpp
+ src/bloom_wrapper.cpp
src/vector_of_kll.cpp
src/py_serde.cpp
)
@@ -117,7 +123,7 @@ cmake_policy(SET CMP0097 NEW)
include(ExternalProject)
ExternalProject_Add(datasketches
GIT_REPOSITORY https://github.com/apache/datasketches-cpp.git
- GIT_TAG 5.1.0
+ GIT_TAG ${DATASKETCHES_CPP_VERSION}
GIT_SHALLOW true
GIT_SUBMODULES ""
INSTALL_DIR /tmp/datasketches
diff --git a/src/bloom_wrapper.cpp b/src/bloom_wrapper.cpp
new file mode 100644
index 0000000..c40c472
--- /dev/null
+++ b/src/bloom_wrapper.cpp
@@ -0,0 +1,161 @@
+/*
+ * 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 <algorithm> // TODO: remove when bloom_filter_impl.hpp includes this
+
+#include <nanobind/nanobind.h>
+#include <nanobind/stl/optional.h>
+#include <nanobind/stl/string.h>
+
+#include "bloom_filter.hpp"
+#include "common_defs.hpp"
+
+namespace nb = nanobind;
+
+void init_bloom(nb::module_ &m) {
+ using namespace datasketches;
+
+ nb::class_<bloom_filter>(m, "bloom_filter")
+ .def_static("suggest_num_hashes",
+ nb::overload_cast<uint64_t, uint64_t>(&bloom_filter::builder::suggest_num_hashes),
+ nb::arg("max_distinct_items"),
+ nb::arg("num_filter_bits")
+ )
+ .def_static("suggest_num_hashes",
+ nb::overload_cast<double>(&bloom_filter::builder::suggest_num_hashes),
+ nb::arg("target_false_positive_prob")
+ )
+ .def_static("suggest_num_filter_bits",
+ nb::overload_cast<uint64_t, double>(&bloom_filter::builder::suggest_num_filter_bits),
+ nb::arg("max_distinct_items"),
+ nb::arg("target_false_positive_prob")
+ )
+ .def_static("create_by_accuracy",
+ [](uint64_t max_distinct_items, double target_fpp, std::optional<uint64_t> seed) {
+ return bloom_filter::builder::create_by_accuracy(max_distinct_items,
+ target_fpp,
+ seed.value_or(bloom_filter::builder::generate_random_seed()));
+ },
+ nb::arg("max_distinct_items"),
+ nb::arg("target_false_positive_prob"),
+ nb::arg("seed") = nb::none()
+ )
+ .def_static("create_by_size",
+ [](uint64_t num_bits, uint16_t num_hashes, std::optional<uint64_t> seed) {
+ return bloom_filter::builder::create_by_size(num_bits,
+ num_hashes,
+ seed.value_or(bloom_filter::builder::generate_random_seed()));
+ },
+ nb::arg("num_bits"),
+ nb::arg("num_hashes"),
+ nb::arg("seed") = nb::none()
+ )
+
+
+ .def_static("deserialize",
+ [](const nb::bytes& bytes) { return bloom_filter::deserialize(bytes.c_str(), bytes.size()); },
+ nb::arg("bytes"),
+ "Reads a bytes object and returns the corresponding bloom_filter"
+ )
+ .def_static(
+ "wrap",
+ [](const nb::bytes& bytes) { return bloom_filter::wrap(bytes.c_str(), bytes.size()); },
+ nb::arg("bytes"),
+ "Wraps the provided bytearray as a read-only Bloom filter"
+ )
+ .def_static(
+ "writable_wrap",
+ [](const nb::bytearray& bytearray) {
+ return bloom_filter::writable_wrap(const_cast<char*>(bytearray.c_str()), bytearray.size());
+ },
+ nb::arg("bytearray"),
+ "Wraps the provided bytearray as a writable Bloom filter"
+ )
+ .def("serialize",
+ [](const bloom_filter& bf) {
+ auto bytes = bf.serialize();
+ return nb::bytes(reinterpret_cast<const char*>(bytes.data()), bytes.size());
+ },
+ "Serializes the filter into a bytes object"
+ )
+
+ .def("__copy__", [](const bloom_filter& bf){ return bloom_filter(bf); })
+ .def("__str__", [](const bloom_filter& bf) { return bf.to_string(false); },
+ "Produces a string summary of the filter")
+ .def("to_string", &bloom_filter::to_string,
+ nb::arg("print_filter") = false,
+ "Produces a string summary of the filter")
+
+ .def("update", nb::overload_cast<uint64_t>(&bloom_filter::update), nb::arg("item"),
+ "Updates the sketch with the given 64-bit integer value")
+ .def("update", nb::overload_cast<double>(&bloom_filter::update), nb::arg("item"),
+ "Updates the sketch with the given 64-bit floating point value")
+ .def("update", nb::overload_cast<const std::string&>(&bloom_filter::update), nb::arg("item"),
+ "Updates the sketch with the given string")
+
+ .def("query_and_update", nb::overload_cast<uint64_t>(&bloom_filter::query_and_update), nb::arg("item"),
+ "Updates the sketch with the given 64-bit integer value\n"
+ "and returns the value from querying prior to the update")
+ .def("query_and_update", nb::overload_cast<double>(&bloom_filter::query_and_update), nb::arg("item"),
+ "Updates the sketch with the given 64-bit floating point value\n"
+ "and returns the value from querying prior to the update")
+ .def("query_and_update", nb::overload_cast<const std::string&>(&bloom_filter::query_and_update), nb::arg("item"),
+ "Updates the sketch with the given string and returns\n"
+ "the value from querying prior to the update")
+
+ .def("query", nb::overload_cast<uint64_t>(&bloom_filter::query, nb::const_), nb::arg("item"),
+ "Queries the sketch with the given 64-bit integer value and\n"
+ "returns whether the value might have been seen previously")
+ .def("query", nb::overload_cast<double>(&bloom_filter::query, nb::const_), nb::arg("item"),
+ "Updates the sketch with the given 64-bit floating point value and\n"
+ "returns whether the value might have been seen previously")
+ .def("query", nb::overload_cast<const std::string&>(&bloom_filter::query, nb::const_), nb::arg("item"),
+ "Updates the sketch with the given string and returns whether the\n"
+ "string might have been seen previously")
+
+ .def("union", &bloom_filter::union_with, nb::arg("other"),
+ "Unions two Bloom filters by applying a logical OR. The result will\n"
+ "recognize any values seen by either filter, as well as false positives")
+ .def("intersect", &bloom_filter::intersect, nb::arg("other"),
+ "Intersects two Bloom filters by applying a logical AND. The result will\n"
+ "recognize only values seen by both filter, as well as false positives")
+ .def("invert", &bloom_filter::invert,
+ "Inverts all the bits of the filter. Approximately inverts the notion of set-membership.")
+
+ .def("is_empty", &bloom_filter::is_empty,
+ "Returns True if the filter is empty, otherwise False")
+ .def("get_bits_used", &bloom_filter::get_bits_used,
+ "Returns the number of bits in the Bloom filter that are set to 1")
+ .def("get_capacity", &bloom_filter::get_capacity,
+ "Returns the total number of bits in the Bloom filter")
+ .def("get_num_hashes", &bloom_filter::get_num_hashes,
+ "Returns the configured number of hash functions for this Bloom filter")
+ .def("get_seed", &bloom_filter::get_seed,
+ "Returns the hash seed for this Bloom filter")
+ .def("reset", &bloom_filter::reset,
+ "Returns the Bloom filter to its original empty state")
+
+ .def("get_serialized_size_bytes", [](const bloom_filter& bf) { return bf.get_serialized_size_bytes(); },
+ "Returns the number of bytes needed to serialize the Bloom filter")
+ .def_static("get_serialized_size_bytes_given_bits", [](uint64_t num_bits) { return bloom_filter::get_serialized_size_bytes(num_bits); },
+ nb::arg("num_bits"),
+ "Returns the number of bytes needed to serialize a Bloom filter with a capacity of num_bits")
+ ;
+
+}
diff --git a/src/datasketches.cpp b/src/datasketches.cpp
index 118683b..121f9a5 100644
--- a/src/datasketches.cpp
+++ b/src/datasketches.cpp
@@ -40,6 +40,7 @@ void init_quantiles(nb::module_& m);
void init_count_min(nb::module_& m);
void init_density(nb::module_& m);
void init_tdigest(nb::module_& m);
+void init_bloom(nb::module_& m);
void init_vector_of_kll(nb::module_& m);
// supporting objects
@@ -72,6 +73,7 @@ NB_MODULE(_datasketches, m) {
init_count_min(m);
init_density(m);
init_tdigest(m);
+ init_bloom(m);
init_vector_of_kll(m);
init_kolmogorov_smirnov(m);
diff --git a/src/tdigest_wrapper.cpp b/src/tdigest_wrapper.cpp
index 059ee1d..1f240df 100644
--- a/src/tdigest_wrapper.cpp
+++ b/src/tdigest_wrapper.cpp
@@ -36,7 +36,7 @@ void bind_tdigest(nb::module_ &m, const char* name) {
using namespace datasketches;
auto tdigest_class = nb::class_<tdigest<T>>(m, name)
- .def(nb::init<uint16_t>(), nb::arg("k")=tdigest<T>::DEFAULT_K,
+ .def(nb::init<uint16_t>(), nb::arg("k")=static_cast<int32_t>(tdigest<T>::DEFAULT_K),
"Creates a tdigest instance with the given value of k.\n\n"
":param k: Controls the size/accuracy trade-off of the sketch. Default is 200.\n"
":type k: int, optional"
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org