Sparse

template<typename RegType, template<typename> class MergeOp, template<typename, typename> class MapType, typename KeyType, std::size_t Size, std::size_t CompactionThreshold> class Sparse

General Sparse Sketch container.

Implements the container handling infrastructure of any sketch whose atomic elements can be stored as sorted sparse index-value pairs into a notional register list of fixed size and supporting a merge operation consisting of the union of their index-value pair lists with the application of an element-wise operator on pairs with matching indices.

Template Parameters:

RegType – The type held by each register.
MergeOp – An template merge operator to combine two sketches.
MapType – The underlying map class to use for buffered updates to the underlying compacting_map.
KeyType – The key type to use for this underlying compacting map.
Size – The maximum number of registers. Must equal the embedding dimension of the transform to be used.

Public Types

using register_type = RegType : Alias for the fully-templated register compacting map type.

Public Functions

inline Sparse(): Construct a new Sparse container object.

inline Sparse(const self_type &rhs)

Copy constructor.

Parameters:: rhs – The base Sparse container to copy.

template<class Archive> inline void serialize(Archive &archive)

Serialize Sparse object to/from cereal archive.

Template Parameters:: Archive – cereal archive type.
Parameters:: archive – The cereal archive to which to serialize the sketch.

inline constexpr bool is_compact() const

Checks whether the compacting sketch is compact.

Returns:: true The update buffer is empty.
Returns:: false The update buffer is not empty.

inline void compactify(): Flush the update buffer.

inline void clear(): Remove all information from sketch.

inline bool empty() const: Check if registers contain any information.

inline constexpr void erase(const std::uint64_t index)

Erase a map index.

Parameters:: index – The map index to erase.

inline constexpr void merge(const self_type &rhs)

Merge other Sparse registers into this.

merge_type determines how register lists are combined. For linear sketches, merge amounts to the element-wise addition of register arrays.

Parameters:: rhs – the other Sparse. Care must be taken to ensure that one does not merge sketches of different types.
Throws:: std::logic_error – if invoked on uncompacted sketches.

inline self_type &operator+=(const self_type &rhs)

Operator overload for convenience for embeddings without additional consistency checks.

Parameters:: rhs – the other Sparse. Care must be taken to ensure that one does not merge subspace embeddings of different types.
Returns:: self_type& this Sparse, having been merged with rhs.

inline constexpr auto begin(): Mutable begin iterator.

inline constexpr auto begin() const: Const begin iterator.

inline constexpr auto cbegin() const: Const begin iterator.

inline constexpr auto end(): Mutable end iterator.

inline constexpr auto end() const: Const end iterator.

inline constexpr auto cend(): Const end iterator.

inline constexpr const register_type &operator[](const std::uint64_t index) const

Const access Sparse at index.

Parameters:: index – The index of the underlying vector to index. Must be less than size.
Returns:: constexpr const register_type& A const refernce to _registers[index].

inline register_type &operator[](const std::uint64_t index)

Access Sparse at index.

Parameters:: index – The index of the underlying vector to index. Must be less than size.
Returns:: register_type& A refernce to _registers[index].

inline register_type &at(const std::uint64_t index)

Access Sparse at index.

Parameters:: index – The index of the underlying vector to index. Must be less than size.
Returns:: register_type& A refernce to _registers.at(index).

inline register_type &at(const std::uint64_t index, const register_type def)

Access Sparse at index.

Parameters:

index – The index of the underlying vector to index. Must be less than size.
def – The default value to return if the index does not exist.

Returns:

register_type& A refernce to _registers.at(index).

inline constexpr bool is_sparse() const: Sparse is always Sparse.

inline constexpr std::size_t size() const: The current size of the compacting_map.

inline dense_registers_type registers() const

Get a copy of the raw (sparse) register vector.

Throws:: std::logic_error – if the object is not compact.
Returns:: std::vector<register_type> The register vector, with zeros for unset indices.

inline dense_registers_type scaled_registers(const double scaling_factor) const

Get a copy of the raw (sparse) register vector with a scaling factor.

Parameters:: scaling_factor – the scalar scaling factor.
Throws:: std::logic_error – if the object is not compact.
Returns:: std::vector<register_type> The register vector, with zeros for unset indices.

inline constexpr bool same_registers(const self_type &rhs) const

Checks whether another Sparse container has the same register state.

Parameters:: rhs – The other container.
Returns:: true The registers agree.
Returns:: false At least one register disagrees.

inline self_type &operator=(self_type rhs)

Copy-and-swap assignment operator.

Note

https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

Parameters:: rhs – The other container.
Returns:: self_type& this, having been swapped with rhs.

Public Static Functions

static inline constexpr std::string name()

Returns a description of the type of container.

Returns:: std::string “Sparse”

static inline constexpr std::string full_name()

Returns a description of the fully-qualified type of container.

Returns:: std::string “Sparse” plus the full name of the fully-templated compacting_map type.

static inline constexpr std::size_t reg_size(): The number of bytes used by each register.

static inline constexpr std::size_t max_size(): The maximum possible size of the compacting_map.

static inline constexpr std::size_t embedding_size(): The size of the embedding. Equal to max_size()

static inline constexpr std::size_t compaction_threshold(): The size at which the compaction buffer will flush.

Friends

inline friend void swap(self_type &lhs, self_type &rhs)

Swap two Sparse containers.

Swap boilerplate.

Note

For some reason, calling std::swap on the registers here causes a segfault in Distributed::data_t::swap, but not Sketch::swap. Peculiar.

Parameters:

lhs – The left-hand container.
rhs – The right-hand container.

inline friend constexpr friend self_type operator+ (self_type lhs, const self_type &rhs)

Merge two Sparse containers.

Parameters:

lhs – The left-hand container.
rhs – The right-hand container.

Returns:

self_type The merge of the two containers.

inline friend constexpr bool operator==(const self_type &lhs, const self_type &rhs)

Checks equality between two Sparse containers.

Parameters:

lhs – The left-hand container.
rhs – The right-hand container.

Returns:

true The registers agree.

Returns:

false At least one register disagrees.

inline friend constexpr bool operator!=(const self_type &lhs, const self_type &rhs)

Checks inequality between two Sparse containers.

Parameters:

lhs – The left-hand container.
rhs – The right-hand container.

Returns:

true At least one register disagrees.

Returns:

false The registers agree.

inline friend std::ostream &operator<<(std::ostream &os, const self_type &sk)

Serialize a Sparse container to human-readable output stream.

Output format is a list of (key, value) pairs, skipping empty registers.

Note

Intended for debugging only.

Parameters:

os – The output stream.
sk – The Sparse object.

Throws:

std::logic_error – if invoked on uncompacted sketch.

Returns:

std::ostream& The new stream state.

template<typename RetType> inline friend RetType accumulate(const self_type &sk, const RetType init)

Accumulate sum of register values.

Template Parameters:

RetType – The value type to return.

Parameters:

sk – The Sparse to accumulate.
init – Initial value of return.

Returns:

RetType The sum over all register values + init.

template<typename Func> inline friend void for_each(const self_type &sk, const Func &func)

Apply a given function to all register values.

Template Parameters:

Func – The (probably lambda) function type.

Parameters:

sk – The Sparse object.
func – The particular function to apply.