@spec capabilities() :: ExDataSketch.Sketch.capabilities()

Returns the set of operation names supported by ExDataSketch.MisraGries.

See ExDataSketch.Sketch for the shared capability vocabulary.

Examples

iex> ExDataSketch.MisraGries.capabilities() |> MapSet.member?(:estimate)
true

iex> ExDataSketch.MisraGries.capabilities() |> MapSet.member?(:no_such_operation)
false

@spec count(t()) :: non_neg_integer()

Returns the total number of items inserted into the sketch.

Examples

iex> ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.count()
0

@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}

Deserializes an EXSK binary into a MisraGries sketch.

Returns {:ok, sketch} on success or {:error, reason} on failure.

Examples

iex> ExDataSketch.MisraGries.deserialize(<<"invalid">>)
{:error, %ExDataSketch.Errors.DeserializationError{message: "deserialization failed: invalid magic bytes, expected EXSK"}}

@spec entry_count(t()) :: non_neg_integer()

Returns the number of distinct tracked entries.

Examples

iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "b", "c"])
iex> ExDataSketch.MisraGries.entry_count(sketch)
3

@spec estimate(t(), term()) :: non_neg_integer()

Returns the estimated frequency of an item.

The estimate is a lower bound on the true count. If the item is not tracked, returns 0.

Examples

iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "a", "b"])
iex> ExDataSketch.MisraGries.estimate(sketch, "a")
2

@spec frequent(t(), float()) :: [{term(), non_neg_integer()}]

Returns entries whose estimated frequency exceeds the given threshold.

The threshold is a fraction in (0.0, 1.0). Returns entries whose count is greater than threshold * count(sketch).

Examples

iex> sketch = ExDataSketch.MisraGries.new(k: 5)
iex> sketch = Enum.reduce(1..100, sketch, fn _, s -> ExDataSketch.MisraGries.update(s, "heavy") end)
iex> sketch = Enum.reduce(1..10, sketch, fn i, s -> ExDataSketch.MisraGries.update(s, "light_#{i}") end)
iex> frequent = ExDataSketch.MisraGries.frequent(sketch, 0.5)
iex> Enum.any?(frequent, fn {item, _count} -> item == "heavy" end)
true

@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: t()

Creates a new MisraGries sketch from an enumerable.

Examples

iex> sketch = ExDataSketch.MisraGries.from_enumerable(["a", "b", "a"], k: 5)
iex> ExDataSketch.MisraGries.count(sketch)
3

@spec merge(t(), t()) :: t()

Merges two MisraGries instances.

Both sketches must have the same k parameter.

Examples

iex> a = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "a"])
iex> b = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "b"])
iex> merged = ExDataSketch.MisraGries.merge(a, b)
iex> ExDataSketch.MisraGries.count(merged)
4

@spec merge_many(Enumerable.t()) :: t()

Merges a non-empty enumerable of MisraGries instances into one.

Examples

iex> sketches = Enum.map(1..3, fn _ ->
...>   ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update("x")
...> end)
iex> merged = ExDataSketch.MisraGries.merge_many(sketches)
iex> ExDataSketch.MisraGries.count(merged)
3

@spec merger(keyword()) :: (t(), t() -> t())

Returns a 2-arity merge function suitable for combining sketches.

Examples

iex> is_function(ExDataSketch.MisraGries.merger(), 2)
true

@spec new(keyword()) :: t()

Creates a new MisraGries sketch.

Options

• :k - maximum number of counters (default: 10, must be >= 1).
• :key_encoding - :binary (default), :int, or {:term, :external}.
• :backend - backend module (default: ExDataSketch.Backend.Pure).

Examples

iex> sketch = ExDataSketch.MisraGries.new(k: 10)
iex> sketch.opts[:k]
10
iex> ExDataSketch.MisraGries.count(sketch)
0

@spec reducer() :: (term(), t() -> t())

Returns a 2-arity reducer function suitable for Enum.reduce/3.

Examples

iex> is_function(ExDataSketch.MisraGries.reducer(), 2)
true

@spec serialize(
  t(),
  keyword()
) :: binary()

Serializes the sketch to the ExDataSketch-native EXSK binary format.

Options

• :format - serialization format: :v2 (default, EXSK v2 with CRC32C) or :v1 (legacy EXSK v1, compatible with v0.7.x readers). MisraGries does not have a hash-strategy option, so v1 has no restriction.

Examples

iex> sketch = ExDataSketch.MisraGries.new()
iex> binary = ExDataSketch.MisraGries.serialize(sketch)
iex> <<"EXSK", _rest::binary>> = binary
iex> byte_size(binary) > 0
true

iex> sketch = ExDataSketch.MisraGries.new()
iex> binary = ExDataSketch.MisraGries.serialize(sketch, format: :v1)
iex> <<"EXSK", 1, 14, _rest::binary>> = binary

@spec size_bytes(t()) :: non_neg_integer()

Returns the size of the sketch state in bytes.

Examples

iex> sketch = ExDataSketch.MisraGries.new()
iex> ExDataSketch.MisraGries.size_bytes(sketch) > 0
true

@spec top_k(t(), non_neg_integer()) :: [{term(), non_neg_integer()}]

Returns the top entries sorted by count descending.

Each entry is a {item, count} tuple where the item is decoded using the configured key encoding.

Examples

iex> sketch = ExDataSketch.MisraGries.new()
iex> sketch = ExDataSketch.MisraGries.update_many(sketch, ["a", "a", "a", "b", "b", "c"])
iex> [{top_item, top_count} | _] = ExDataSketch.MisraGries.top_k(sketch, 2)
iex> top_item
"a"
iex> top_count
3

@spec update(t(), term()) :: t()

Updates the sketch with a single item.

The item is encoded using the configured key encoding before insertion.

Examples

iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update("hello")
iex> ExDataSketch.MisraGries.count(sketch)
1

@spec update_many(t(), Enumerable.t()) :: t()

Updates the sketch with multiple items in a single pass.

Examples

iex> sketch = ExDataSketch.MisraGries.new() |> ExDataSketch.MisraGries.update_many(["a", "b", "a"])
iex> ExDataSketch.MisraGries.count(sketch)
3