You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "proost (via GitHub)" <gi...@apache.org> on 2026/01/25 15:57:47 UTC

[I] [feature] Array of Strings tuple sketch [datasketches-cpp]

proost opened a new issue, #475:
URL: https://github.com/apache/datasketches-cpp/issues/475

   # Summary
   
   Adding Array of Strings Tuple Sketch.
   
   # Design
   
   - I reuse and extend the existing tuple sketch interfaces as much as possible.
   - I use `array<std::string>` as container for string collection, following the same approach as the ArrayOfDoubles tuple sketch.
   - Serialization and deserialization follow the existing tuple sketch patterns using `default_array_of_strings_serde` .
       - One difference from the Java implementation is UTF-8 validation. In the C++ ArrayOfStringsTupleSketch, I added validation to ensure each std::string contains valid UTF-8 encoded text. This difference comes from the fact that Java String is always valid Unicode, while C++ std::string may contain arbitrary bytes.
       - For validation, I use utfcpp (https://github.com/nemtrif/utfcpp). simdutf (https://github.com/simdutf/simdutf) is widely used and C++11 compatible, but it may trigger warnings because it does not strictly follow ISO C++ in all configurations. Since some users build with strict compiler flags and UTF-8 validation is not on the hot path (it runs only during serialization/deserialization), I chose utfcpp even though it may be slightly slower.
   
   ```cpp
   namespace datasketches {
   
   // default update policy for an array of strings
   template<typename Allocator = std::allocator<std::string>>
   class default_array_of_strings_update_policy {
   public:
     using array_of_strings = array<std::string, Allocator>;
   
     explicit default_array_of_strings_update_policy(const Allocator& allocator = Allocator());
   
     array_of_strings create() const;
   
     void update(array_of_strings& array, const array_of_strings& input) const;
   
     void update(array_of_strings& array, const array_of_strings* input) const;
   
   private:
     Allocator allocator_;
   };
   
   // serializer/deserializer for an array of strings
   // Requirements: all strings must be valid UTF-8 and array size must be <= 127.
   template<typename Allocator = std::allocator<std::string>>
   struct default_array_of_strings_serde {
     using array_of_strings = array<std::string, Allocator>;
     using summary_allocator = typename std::allocator_traits<Allocator>::template rebind_alloc<array_of_strings>;
   
     explicit default_array_of_strings_serde(const Allocator& allocator = Allocator());
   
     void serialize(std::ostream& os, const array_of_strings* items, unsigned num) const;
     void deserialize(std::istream& is, array_of_strings* items, unsigned num) const;
     size_t serialize(void* ptr, size_t capacity, const array_of_strings* items, unsigned num) const;
     size_t deserialize(const void* ptr, size_t capacity, array_of_strings* items, unsigned num) const;
     size_t size_of_item(const array_of_strings& item) const;
   
   private:
     Allocator allocator_;
     summary_allocator summary_allocator_;
     static void check_num_nodes(uint8_t num_nodes);
     static uint32_t compute_total_bytes(const array_of_strings& item);
     static void check_utf8(const std::string& value);
   };
   
   /**
    * Extended class of compact_tuple_sketch for array of strings
    * Requirements: all strings must be valid UTF-8 and array size must be <= 127.
    */
   template<typename Allocator = std::allocator<std::string>>
   class compact_array_of_strings_tuple_sketch:
     public compact_tuple_sketch<
       array<std::string, Allocator>,
       typename std::allocator_traits<Allocator>::template rebind_alloc<array<std::string, Allocator>>
     > {
   public:
     using array_of_strings = array<std::string, Allocator>;
     using summary_allocator = typename std::allocator_traits<Allocator>::template rebind_alloc<array_of_strings>;
     using Base = compact_tuple_sketch<array_of_strings, summary_allocator>;
     using vector_bytes = typename Base::vector_bytes;
     using Base::serialize;
   
     /**
      * Copy constructor.
      * Constructs a compact sketch from another sketch (update or compact)
      * @param other sketch to be constructed from
      * @param ordered if true make the resulting sketch ordered
      */
     template<typename Sketch>
     compact_array_of_strings_tuple_sketch(const Sketch& sketch, bool ordered = true);
   
     /**
      * This method deserializes a sketch from a given stream.
      * @param is input stream
      * @param seed the seed for the hash function that was used to create the sketch
      * @param sd instance of a SerDe
      * @param allocator instance of an Allocator
      * @return an instance of the sketch
      */
     template<typename SerDe = default_array_of_strings_serde<Allocator>>
     static compact_array_of_strings_tuple_sketch deserialize(std::istream& is, uint64_t seed = DEFAULT_SEED,
         const SerDe& sd = SerDe(), const Allocator& allocator = Allocator());
   
     /**
      * This method deserializes a sketch from a given array of bytes.
      * @param bytes pointer to the array of bytes
      * @param size the size of the array
      * @param seed the seed for the hash function that was used to create the sketch
      * @param sd instance of a SerDe
      * @param allocator instance of an Allocator
      * @return an instance of the sketch
      */
     template<typename SerDe = default_array_of_strings_serde<Allocator>>
     static compact_array_of_strings_tuple_sketch deserialize(const void* bytes, size_t size, uint64_t seed = DEFAULT_SEED,
         const SerDe& sd = SerDe(), const Allocator& allocator = Allocator());
   
   private:
     explicit compact_array_of_strings_tuple_sketch(Base&& base);
   };
   
   /**
    * Extended class of update_tuple_sketch for array of strings
    */
   template<template<typename> class Policy = default_array_of_strings_update_policy,
            typename Allocator = std::allocator<std::string>>
   class update_array_of_strings_tuple_sketch:
     public update_tuple_sketch<
       array<std::string, Allocator>,
       array<std::string, Allocator>,
       Policy<Allocator>,
       typename std::allocator_traits<Allocator>::template rebind_alloc<array<std::string, Allocator>>
     > {
   public:
     using array_of_strings = array<std::string, Allocator>;
     using summary_allocator = typename std::allocator_traits<Allocator>::template rebind_alloc<array_of_strings>;
     using policy_type = Policy<Allocator>;
     using Base = update_tuple_sketch<
       array_of_strings,
       array_of_strings,
       policy_type,
       summary_allocator
     >;
     using resize_factor = typename Base::resize_factor;
     class builder;
     using Base::update;
   
     /**
      * Updates the sketch with string array for both key and value.
      * @param key the given string array key
      * @param value the given string array value
      */
     void update(const array_of_strings& key, const array_of_strings& value);
   
     /**
      * Converts this sketch to a compact sketch (ordered or unordered).
      * @param ordered optional flag to specify if an ordered sketch should be produced
      * @return compact array of strings sketch
      */
     compact_array_of_strings_tuple_sketch<Allocator> compact(bool ordered = true) const;
   
   private:
     update_array_of_strings_tuple_sketch(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta,
         uint64_t seed, const policy_type& policy, const summary_allocator& allocator);
   
     // Matches Java Util.PRIME for ArrayOfStrings key hashing.
     static constexpr uint64_t STRING_ARR_HASH_SEED = 0x7A3CCA71ULL;
   
     static uint64_t hash_key(const array_of_strings& key);
   };
   
   template<template<typename> class Policy, typename Allocator>
   class update_array_of_strings_tuple_sketch<Policy, Allocator>::builder:
     public tuple_base_builder<builder, policy_type, summary_allocator> {
   public:
     builder(const policy_type& policy = policy_type(), const summary_allocator& allocator = summary_allocator());
   
     update_array_of_strings_tuple_sketch build() const;
   };
   
   } /* namespace datasketches */
   ```
   
   # Plan
   
   I will send a PR. But for the compatibility test, after [This PR ](https://github.com/apache/datasketches-java/pull/719) is merged i will send a PR


-- 
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.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


Re: [I] [feature] Array of Strings tuple sketch [datasketches-cpp]

Posted by "proost (via GitHub)" <gi...@apache.org>.
proost commented on issue #475:
URL: https://github.com/apache/datasketches-cpp/issues/475#issuecomment-3800394899

   @jmalkin 
   Thank you for review. you are right. At first, because of `update` method which use key as array of strings I design `update_array_of_strings_tuple_sketch`. But I found that we can just make non member function. So I changed it.


-- 
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


Re: [I] [feature] Array of Strings tuple sketch [datasketches-cpp]

Posted by "proost (via GitHub)" <gi...@apache.org>.
proost closed issue #475: [feature] Array of Strings tuple sketch
URL: https://github.com/apache/datasketches-cpp/issues/475


-- 
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


Re: [I] [feature] Array of Strings tuple sketch [datasketches-cpp]

Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on issue #475:
URL: https://github.com/apache/datasketches-cpp/issues/475#issuecomment-3796930061

   Comparing with array_of_doubles, which really just defines the template as being of type array<double> so you can specify policy and such for a base array_tuple_sketch, why does this need to define things like `class update_array_of_strings_tuple_sketch`?
   
   I feel like there can be a lot more re-use of existing code.


-- 
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


Re: [I] [feature] Array of Strings tuple sketch [datasketches-cpp]

Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #475:
URL: https://github.com/apache/datasketches-cpp/issues/475#issuecomment-3800738941

   Does the "Design" need to be changed? Is there more work to be done? If not, can we close this issue?


-- 
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